使用自正则度量的凸二次规划的原始对偶内点法的多项式复杂性

最近Peng等人使用新的搜索方向和自正则度量为求解线性规划问题提出了一个原始对偶内点法.本文将这个长步法延伸到凸二次规划.在线性规划情形时,原始空间和对偶空间中的尺度Newton方向是正交的,而在二次规划情形时这是不成立的.本文将处理这个问题并且证明多项式复杂性,并且得到复杂性的上界为O(n√log n log (n/ε)).

Polynomial Complexity of Primal-dual Interior-point Methods for Convex Quadratic Programming with Self-regular Proximity

Recently Peng et al. have proposed a primal-dual interiorpoint method with new search directions and self-regular proximity for LP.We extend this large-update method to convex quadratic programming (QP).In the case of LP,the scaled Newton directions in the primal and dual spaces are orthogonal.Note that this is not true in the case of QP.In this paper we deal with the problem and polynomial complexity is proved,and the iteration bound is O(√nlog n log (n/ε)).