基于自适应参数校正策略求解SDP的二阶Mehrotra型内点算法  

A SECOND ORDER MEHROTRA-TYPE INTERIOR-POINT ALGORITHM FOR SDP BASED ON A NEW ADAPTIVE UPDATING TECHNIQUE OF BARRIER PARAMETER

作　　者：黄方艳[1] 张明望[1] 黄正伟[2] 

机构地区：[1]三峡大学理学院,湖北宜昌443002 [2]三峡大学经济与管理学院,湖北宜昌443002

出　　处：《南阳理工学院学报》2015年第6期118-124,共7页Journal of Nanyang Institute of Technology

基　　金：国家自然科学基金项目(71471102)

摘　　要：最近,Salahi提出了一种求解线性规划的基于自适应参数校正策略的二阶Mehrotra型预估-校正算法,并在不使用安全策略的情况下证明了其迭代的多项式复杂性。本文将这一算法推广到半定规划。通过利用Zhang的对称化技术,同样在不使用安全策略的情况下,证明了算法的多项式迭代复杂界。Recently,Salahi presented a second order Mehrotra-type predictor-corrector algorithm based on a new adaptive updating technique of barrier parameter for linear program,and derived the iteration complexity bound without any safeguard. This paper extends this algorithm to sem-idefinite program. By using Zhang' s general symmetrization scheme,the polynomial iteration complexity bound of the algorithm is obtained without a safeguards.

关 键 词：Mehrotra型预估—校正算法 半定规划 对称化技术 多项式复杂性 

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