求解半定规划的原始对偶势下降内点算法研究  

Study on the Primal-Dual Potential Reduction Interior-Point Algorithm for Solving Semi-Definite Programming

作　　者：王永丽[1] 王鑫[1] 贺国平[1] 

机构地区：[1]山东科技大学信息科学与工程学院

出　　处：《山东科技大学学报（自然科学版）》2008年第6期84-87,共4页Journal of Shandong University of Science and Technology(Natural Science)

基　　金：国家自然科学基金项目(10571109);山东省科技厅科技攻关项目(2006GG3210009);山东省教育厅科技计划项目(J06P14)

摘　　要：介绍了半定规划的一般模型、最优性条件及求解半定规划问题的原始对偶势下降内点算法。借助两个形象的图形分析了势下降内点算法的迭代轨迹,并对求解半定规划的Filter势下降内点算法进行了研究,提出了Fil-ter的构造方法。在一定的条件下,该算法可避免Maratos效应和势函数海色矩阵不正定等问题的产生。This paper mainly presents the general model, optimal conditions of the semi-definite programming and its primal-dual potential reduction interior-point algorithm. In particular, two vivid figures are given to help under standing the trace of the iterative points. Moreover, the idea of combining interior-point algorithm with the Filter technique for solving SDP is inspired and the formulation of a practical filter is proposed. Under certain conditions, the new algorithm can avoid the Maratos effects and the non-positive definiteness of the Hessian matrix of potential function.

关 键 词：半定规划 FILTER 原始对偶 势下降内点算法 

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