二次半定规划的原始对偶预估校正内点算法

Primal-dual predictor-corrector interior point algorithm for quadratic semidefinite programming

将半定规划(Semidefinite Programming,SDP)的内点算法推广到二次半定规划(QuadraticSemidefinite Programming,QSDP),重点讨论了AHO搜索方向的产生方法.首先利用Wolfe对偶理论推导得到了求解二次半定规划的非线性方程组,利用牛顿法求解该方程组,得到了求解QSDP的内点算法的AHO搜索方向,证明了该搜索方向的存在唯一性,最后给出了求解二次半定规划的预估校正内点算法的具体步骤,并对基于不同搜索方向的内点算法进行了数值实验,结果表明基于NT方向的内点算法最为稳健.

This paper extends the interior point algorithm for solving Semidefinite Programming（SDP） to Quadratic Semidefinite Programming（QSDP） and especially discusses the generation of AHO search direction.Firstly,we derive the nonlinear equations for solving QSDP using Wolfe＇s dual theorem.The AHO search direction is got by applying Newton＇s method to the equations.Then we prove the existence and uniqueness of the search direction,and give the detaied steps of predictor-corrector interior-point algorithm.At last,this paper provides a numerical comparison of the algoritms using three different search directions and suggests the algorithm using NT direction is the most robust.