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

Primal Dual Algorithm for Quadratic Semi-definite Programming

作　　者：徐凤敏[1] 徐成贤[1] 

机构地区：[1]西安交通大学理学院,西安710049

出　　处：《工程数学学报》2006年第4期590-598,共9页Chinese Journal of Engineering Mathematics

基　　金：Foundation item: This research was supported by the National Natural Science Foundation of China (10231060).

摘　　要：本文主要给出求解二次半定规划(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.

关 键 词：二次半定规划 内点算法 路径跟踪方法 NT方向 

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