凸二次半定规划一个长步原始对偶路径跟踪算法  

A Long Step Primal-Dual Path-following Algorithm for Convex Quadratic Semidefinite Programming

作　　者：黎健玲[1] 王培培[1] 曾友芳[1] 简金宝 LI Jianling;WANG Peipei;ZENG Youfang;JIAN JlNBAO(College of Mathematics and Information Science,Guangxi University,Nanning 530004,China;College of Science,Guangxi University for Nationalities,Nanning 530006,China)

机构地区：[1]广西大学数学与信息科学学院,南宁530004 [2]广西民族大学理学院,南宁530006

出　　处：《应用数学学报》2020年第1期12-32,共21页Acta Mathematicae Applicatae Sinica

基　　金：国家自然科学基金(11561005);广西自然科学基金(2016GXNSFAA380248)资助项目

摘　　要：本文基于Nesterov-Todd方向,并引进中心路径测量函数以及原始对偶对数障碍函数,建立了一个求解凸二次半定规划的长步路径跟踪法.算法保证当迭代点落在中心路径附近时步长1被接受.算法至多迭代O(n|lnε|)次可得到一个ε最优解.论文最后报告了初步的数值试验结果.In this paper,based on Nesterov-Todd direction,and by introducing a measure for the central path and a primal-dual logarithmic barrier function,a long step primaldual path-following lgorithm for convex quadratic semidefinite programming is presented.The algorithm ensures that the step size 1 is accepted when the iterative point falls into the neighborhood of the central path.An ε-optimal solution is obtained after at most O(n|ln εε|)iterations.Some preliminary numerical results are reported.

关 键 词：凸二次半定规划 中心路径 Nesterov-Todd方向 路径跟踪算法 迭代复杂性 

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