半定规划上一种有效的内点法

An Efficient Interior-Point Algorithm for Semidefinite Programming

在半定规划的内点算法中,中心参数的选择对于算法的复杂性和有效性是尤为重要的。但以往半定规划的论文中,中心参数是固定的,这大幅增加了算法的复杂性并降低了有效性。文中基于宽邻域提出了一种有效可地行内点算法,使中心参数与步长成多项式的关系,这样中心参数会随着步长的变化而更新。从而每次迭代均取到最优参数,且在文中,基于NT方向,证明了该算法在理论上的复杂性和有效性均是最优的。

For interior-point algorithms in semidefinte programming,it is well-known that the selection of the center parameter is crucial for proving polynomility and for efficiency,However,for the previous semidefinte programming paper,the center parameter is fixed,so that this increase largely the complexity of the algorithms and reduce the effectiveness of the algorithms. In the paper,we propose an effective feasible interior point algorithm based on wide neighborhood,with a polynomial relationship between the centering parameter and search step size,and thus in each iteration,the center parameter not only changes with step size but also the optimal is found. It is also proven that the complexity and the effectiveness of the algorithm is optimal based on NT direction in the theory.