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

A mehrotra-type algorithm for SDP based on a new adap-tive updating technique of barrier parameter

最近,Salahi对线性规划提出了一个基于新的自适应参数校正策略的Mehrotra型预估-校正算法,该策略使其在不使用安全策略的情况下,证明了算法的多项式迭代复杂界.本文将这一算法推广到半定规划的情形.通过利用Zhang的对称化技术,得到了算法的多项式迭代复杂界,这与求解线性规划的相应算法有相同的迭代复杂性阶.

Salahi in his recent work proposed a Mehrotra-type predictor-corrector algorithm based on a new adaptive updating technique of barrier parameter for linear program, which enables him to derive the iteration complexity bound of Mehrotra-type algorithm without a safeguard. This paper extends the Mehrotra-type algorithm to semidefinite program. By using Zhang′s general symmetrization scheme, the polynomial iteration complexity bound of the algorithm is obtained, which is of the same order as that of the corresponding algorithm for linear program.