A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinite programming
A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinite programming
复制标题
DOI：
10.1007/bf01580085
复制
发表时间：
1998-05
影响因子：
2.7
通讯作者：
R. Monteiro;Yin Zhang
中科院分区：
文献类型：
--
作者：
R. Monteiro;Yin Zhang
本文给出了一类半定规划的长步原始-对偶路径跟踪算法的统一分析，其搜索方向是通过线性化中心路径HP(XS)≡[PxSP−1+(PxSP−1)T]/2=μi得到的。在迭代(X，S)处，我们从非奇异矩阵类P中选择一个尺度矩阵P，使得PXSP−1是对称的。这类矩阵包括蒙泰罗提出的三个著名的选择：P=S_1/2和P=X_−_(1/2)，以及与N-T方向对应的矩阵P。我们证明了在本文研究的这类算法中，基于Nester ov-Todd方向的算法具有可以从我们的分析中得到的最低可能的迭代复杂性界。更具体地说，它的迭代复杂度界与Kojima、Mizuno和Yoshise提出的求解线性规划的相应长步长原-对偶路径跟踪算法具有相同的数量级。©1998数学编程学会，Inc.，Elsevier Science B.V.出版
We present a unified analysis for a class of long-step primal-dual path-following algorithms for semidefinite programming whose search directions are obtained through linearization of the symmetrized equation of the central pathHP(XS) ≡ [PXSP−1+ (PXSP−1)T]/2 = μI, introduced by Zhang. At an iterate (X,S), we choose a scaling matrixPfrom the class of nonsingular matricesPsuch thatPXSP−1is symmetric. This class of matrices includes the three well-known choices, namely:P = S1/2andP = X−1/2proposed by Monteiro, and the matrixPcorresponding to the Nesterov—Todd direction. We show that within the class of algorithms studied in this paper, the one based on the Nesterov—Todd direction has the lowest possible iteration-complexity bound that can provably be derived from our analysis. More specifically, its iteration-complexity bound is of the same order as that of the corresponding long-step primal-dual path-following algorithm for linear programming introduced by Kojima, Mizuno and Yoshise. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.