×

zbMATH — the first resource for mathematics

Primal–dual path-following algorithms for semidefinite programming. (English) Zbl 0913.65051
The author considers the semidefinite programming problem (SDP) of the form: \[ \min \{C\bullet X: A_{i}\bullet X = b_{i},\;i=1,2,\ldots ,m,\;X\succeq 0 \} \] and its associated dual SDP: \[ \max\Biggl\{ b^{T}y: \sum^{m}_{i=1} y_{i}A_{i}+S=C, S\succeq 0 \Biggr\}, \] where symmetric matrices \(C\in {\mathfrak R}^{n\times n}\), \(A_{i} \in {\mathfrak R}^{n\times n}\) for \(i=1,2,\ldots ,m\) and the vector \(b=(b_{1},b_{2},\ldots ,b_{m})^{T} \in {\mathfrak R}^{m}\) are the data, \(X \in {\mathcal S}^{(n)}_{+}\) and \((S,y)\in {\mathcal S}^{(n)}\times {\mathfrak R}^{m}\) are the primal and dual variables, respectively; the \(\bullet\) denotes the inner product, \({\mathcal S}^{(n)}\) denotes the set of all symmetric definite \(n\times n\) matrices, \({\mathcal S}^{(n)}_{+}\) denotes the set of all matrices in \({\mathcal S}^{(n)}\) which are positive semidefinite, \({\mathfrak R}^{m}\) is the \(m-\)dimensional Euclidean space. He studies primal-dual path-following algorithms for solving such SDP, based on a search direction proposed by M. Kojima, S. Shindoh and S. Hara [SIAM J. Optim. 7, No. 1, 86-125 (1997; Zbl 0872.90098)]. This algorithm is a natural extension of the algorithms for linear programming (LP) based on the scaling matrix \(X^{\frac{1}{2}}S^{-\frac{1}{2}}\). There exist two variants of primal-dual algorithm for LP using this scaling matrix: one proposed by M. Kojima, S. Mizuno and A. Yoshise [in: Progress in Mathematical Programming: Interior Point and Related Methods, 29-47 (Springer-Verlag, Berlin, New York) (1989; Zbl 0708.90049)], named long-step path-following method and another, developed independently by the same three authors [Math. Program., Ser. A 44, No. 1, 1-26 (1989; Zbl 0676.90087)] and by R. D. C. Monteiro and I. Adler [Math. Program., Ser. A 44, No. 1, 27-41 and 43-66 (1989; Zbl 0676.90038 and Zbl 0676.90039)], named short-step path-following method; the former one improves the worst-case iteration complexity of the long-step variant by a factor of \(\sqrt {n}\).
The short-step variant was extended onto the case of SDP problems by Kojima, Shindoh and Hara [loc. cit.] using a generalization of the known (for LP) interior-point method; other extensions based on the same idea were provided by Y. E. Nesterov and M. J. Todd [Primal-dual interior-point methods for self-scaled cones, Techn. Rep. 1125, School of Oper. Res. Industr. Eng., Cornell Univ., Ithaca, NY (1995)]; however, no extensions of the long-step variant were obtained. In this paper, a simplified polynomial convergence proof for a short-step path-following algorithm of Kojima, Shindoh and Hara is presented and, for the first time, a polynomially convergent long-step path-following algorithm for SDP is described. The author shows that also for SDP versions of the two variants of path-following algorithms the iteration-complexity of the long-step version increases by a factor of \(\sqrt{n}\) in relation to the short-step one.
Reviewer: S.Zabek (Lublin)

MSC:
65K05 Numerical mathematical programming methods
65H20 Global methods, including homotopy approaches to the numerical solution of nonlinear equations
65Y20 Complexity and performance of numerical algorithms
90C25 Convex programming
90C30 Nonlinear programming
PDF BibTeX XML Cite
Full Text: DOI