摘要
对于标准型的凸二次规划问题本文给出了一个新算法．算法的每一步迭代，利用内椭球的思想来近似求解一个线性规划子问题而得到迭代方向，再适当选取步长而使之成为多项式算法，其迭代步数为Ｏ（ｎＬ２），每一步迭代所需计算量为Ｏ（ｎ３），其中ｎ为变量个数，Ｌ为问题的输入长度．
in this paper, a new variant of the interior ellipsoid method for convex quadraticprogramming is developed. Compared to the algorithm proposed by Ye and Tse[5]. the sub-problem of new algorithm is a linear programming which is easy to solve, although bothhave the same complexity.
出处
《应用数学学报》
CSCD
北大核心
1996年第1期46-50,共5页
Acta Mathematicae Applicatae Sinica
基金
国家自然科学基金
关键词
凸二次规划
内椭球算法
多项式算法
二次规划
Convex quadratic programming, interior ellipsoid method,Karmarkar algorithm, complexity
