框式凸二次规划宽邻域原始-对偶势下降内点算法

A wide-neighborhood primal-dual interior-point algorithm based on reduced potential function for convex quadratic programming with box constrains

基于线性规划原始-对偶势下降内点算法的思想,对框式凸二次规划提出一种新的内点算法宽邻域原始-对偶势下降内点算法.算法选取牛顿方向作为迭代方向,利用势函数选择迭代步长,分析算法的多项式迭代复杂性,并证明新算法具有较好的迭代复杂性O(nL).

Based on the idea of primal-dual interior-point algorithm with potential reduction for linear programming, a new interior-point algorithm called wide-neighborhood primal-dual potential-reduction interior-point algorithm was devised. In this algorithm, the Newton-direction was used as its iteration direction and its iteration step was determined by using potential function to analyze the complexity of polynomial iteration in the algorithm, proving that this new algorithm possessed a better iteration complexity O（nL）.