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

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

作　　者：刘中意[1,2] 

机构地区：[1]南京师范大学数学与计算机科学学院,江苏南京210097 [2]河海大学理学院,江苏南京210098

出　　处：《应用数学》2009年第2期326-334,共9页Mathematica Applicata

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

关 键 词：凸二次规划 内点法 原始对偶 长步法 多项式复杂性 自正则度量 

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