半定规划的一种Mehrotra型预估-校正算法  

A Mehrotra-type Predictor-corrector Algorithm for Semidefinite Optimization

作　　者：陈华平[1] 

机构地区：[1]六盘水师范学院数学系,贵州六盘水553004

出　　处：《重庆师范大学学报（自然科学版）》2015年第3期11-16,共6页Journal of Chongqing Normal University:Natural Science

基　　金：贵州省科学技术基金(No.黔科合J字LKLS[2013]14)

摘　　要：将一种Mehrotra型预估-校正算法推广到半定规划。首先给出了半定规划基于Mehrotra型预估-校正算法的一些基本理论,尤其是对称化技术;随后通过分析这种算法的迭代复杂性,给出算法的重要思想:在校长步中采用安全策略,给出新算法的最大预估步长的上界,算法过程中对最大预估步长进行削减策略:当最大预估步长大于某个阈值时,对此步长进行削减(可重复),从而得到合适的校正步长下界;最终通过采用以上策略及NT搜索方向,得到了该算法的多项式复杂界。The extension of Mehrotra-type predictor-corrector algorithm which was proposed by Salahi for linear optimization is ob- tained for semidefinite optimization. Firstly, the basic theories of algorithm based on Mehrotra-type predietor-corrector algorithm for Semi-definite are introduced, especially the selection of symmetrical technique. Then followed by giving the iteration complexity analysis of this algorithm, the important thought of the algorithm is explained： the safeguard strategy is used in the algorithm; the above bound on the maximum feasible step in the predictor step is given. A cut strategy for the maximum feasible step in the predictor step is provided： when the maximum prediction step size is greater than a certain threshold, this step is cut （repeated）, so the lower bound in the corrector step is obtained. Based on these strategies and the NT search direction, the polynomial complexity of new algorithm is obtained.

关 键 词：大步校正算法 Mehrotra型预估-校正算法 半定规划 多项式复杂性 

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