求解二次半定规划的原对偶内点算法(英文)

Primal Dual Algorithm for Quadratic Semi-definite Programming

本文主要给出求解二次半定规划(QSDP)基于NT方向的内点算法。利用尺度矩阵W对称化QSDP的互补松弛条件,牛顿法求解此条件得到NT方向,并且证明了NT方向的存在性和唯一性, 从而得到求解QSDP的原对偶内点算法。数值试验证明此方法是非常有效的。

A primal-dual interior point method for quadratic semi-definite programming problems （QSDP） was proposed. At each iteration of the algorithm, the NT algorithm is computed by applying the Newton method to the complementarity condition of QSDP and a scaling matrix W is employed to symmetrize the resulting Newton system of equations. Efficient ways to calculate the scaling matrix W and the NT search direction are presented. The detailed steps of the proposed short step path following algorithm are given. Numerical experiments show the efficiency of the proposed algorithm.