大规模简单界约束的凸二次规划新算法  

New Algorithm of Large Scale Convex Quadratic Programs with Simple Bound Constraints

作　　者：朱克强[1] 贺力群 

机构地区：[1]北方交通大学经济与工商管理学院 [2]北京理工大学计算机系

出　　处：《北方交通大学学报》1998年第3期98-103,共6页Journal of Northern Jiaotong University

摘　　要：利用Ｆｌｅｔｃｈｅｒ作用集方法的思想，将Ｍｕｒｔｙ等提出的正交校正共轭梯度法推广来求解具有上、下界约束的简单凸二次规划，证明了新算法具有有限步终止性，并且改进了Ｐｏｌｙａｋ的迭代法．数值结果表明，新算法比Ｐｏｌｙａｋ的迭代法求解速度快，且由于算法在求解过程中，不用求逆矩阵，零元素不用存储，也不参加运算，算法对求解大规模问题有效．数值结果还表明，新算法比Ｃｏｔｔｌｅ和Ｃｏｈｅｅｎ的ＳＯＲ法稳定．This paper applies active set method and CGM-OC to the problem of minimizing the simple convex quadratic program subject to upper and lower bounds on the variables. The Polyak interation has been improved. The numerical results express that the rate of new algorithm is faster than that of the Polyak interation. This method exploits sparsity structure in the matrix of the quadratic form. It avoids the computation of inverse matrix and the storage of zero. Convergence results are established. We present the results of numerical experiments showing the effectiveness of the algorithm on large scale problems. The numerical results also express that the stability of new algorithm is better than that of the SOR method of Cottle and Coheen.

关 键 词：作用集 正交校正 共轭梯度法 凸二次规划 

分 类 号：O221.2[理学—运筹学与控制论]