凸二次半定规划一个新的原始对偶路径跟踪算法

A New Primal-Dual Path-Following Algorithm for Convex Quadratic Semidefinite Programming

本文提出求解凸二次半定规划的一个新的原始对偶路径跟踪算法.在每次迭代中,通过求解一个线性方程组产生搜索方向.在一定条件下证明算法产生的迭代点列落在中心路径的邻域内,且算法至多经 O (n|log∈|)次迭代可得到一个∈-最优解.

In this paper, a new primal-dual path-following algorithm for convex quadratic semidef- inite programming is proposed. At each iteration, the search direction of the algorithm is generated by the solution of a system of linear equations. Under some conditions, the iteration points generated by the algorithm lie in the neighborhood of the central path, and an -optimal solution can be found at most O(n|logε|) iterations.