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

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

作　　者：黄静静[1,2] 商朋见[1] 王爱文[2] 

机构地区：[1]北京交通大学理学院,北京100044 [2]北京信息科技大学理学院,北京100192

出　　处：《北京交通大学学报》2011年第3期136-141,共6页JOURNAL OF BEIJING JIAOTONG UNIVERSITY

基　　金：国家自然科学基金资助项目(60772036;61071142);教育部博士点基金项目资助(20070004002);北京市教委面上项目资助(201110772019);北京信息科技大学校科研基金资助项目

摘　　要：将半定规划(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.

关 键 词：半定规划 二次半定规划 内点算法 搜索方向 牛顿法 

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