文档介绍：维普资讯
第卷第期甘肃联舍大学学报自然科学版..
.
年月
文章编号:——
一般二次规划的一种分解算法
孙培培
山东经济学院统计与数学学院,山东济南
摘要:
正则分裂,即并且满足—.
在矩阵是正定的条件下,算法具有线性收敛性质,
时,算法产生的点列收敛到问题的稳定点.
关键词:二次规划;分解算法;正则分裂;收敛
中图分类号:. 文献标识码:
一,
引言
则
本文考虑如下形式的二次规划问题: 厂一, 一—:/.
厂一/ 为了求解问题,可以先求解以下问题:
.. —,≥, ,
其中,∈为对称矩阵,∈,∈,∈.. —,≥.
.记该问题的可行域为,并且假设有界. 构造如下算法:
:假设,是的一正则分裂.
求解线性代数方程组的迭代方法,对矩阵进行步:设‘∈是给定的初始点,为允许
正则分裂, ,要求满足—是正定误差,令忌一.
:令一,求解问题,并令蚪一
,算法具,.
有线性收敛性质,产生的迭代点列收敛到原问题步:若一‘,则终止计算,
的最优解;当矩阵不正定时,算法产生的点列即为问题的一近似解,否则令:一,转步
收敛到问题的稳定点. 】.
算法的构造算法涉及的几个问题
定义假设∈为对称矩阵,,称. 初始可行解的构造
为是的一正则分裂,如果。—;。若没有一个明显的可行解,则可以构造一
—是对称正定矩阵,其中,∈. 个人工变量,其系数列为。一一一。
对于任意的∈,有. · 一,构成如下问题
厂一—一, /
厂一至一—/一.. 井井一,,井≥.
厂十一; —/ 这里, 为一个充分大的正数,一,,⋯,
一一~ /, ,该问题的最优解与原问题的
⋯一一
一构成了的一个可行解.
,一厂十妻一~
为了讨论方便,以后假定的一个初始可行
收稿日期:——.
作者简介:孙培培一,女,山东济南人,山东经济学院教师,主要从事运筹学研究.
维普资讯
甘肃联合大学学报自然科学版第卷
解。是已知的. 抖一—抖一/.
. 矩阵的正则分解在式中令一州,,有
由算法的构造可见,每次迭代中主要的计算抖一抖一
≤.
对角矩阵时,算法可以极大的简化,即—由以上两式易得:
一≤
,∑,表
一抖一—抖一/.
示的第行第』—:—由—的正定性可得
‘≤.
取为的对角元素. 所以,
收敛性分析敛的.
证毕.
引理设∈,是问题的最优解,即引理设是对称正定的,若有,
对任意的∈,以下不等式成立: ∈和∈使得≥成立,则
一’—’~ ≥. ≤,
、
且
证明由的定义可见对任意的∈,有一业,
,一,≥