Primal--Dual Path-Following Algorithms for Semidefinite Programming

DOI10.1137/S1052623495293056MaRDI QIDQ4377581zbMATH OpenFDO

Publication date 10 February 1998

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S1052623495293056

interior-point methods path-following methods polynomial complexity primal-dual algorithms semidefinite programming

Global methods, including homotopy approaches to the numerical solution of nonlinear equations (65H20) Numerical mathematical programming methods (65K05) Complexity and performance of numerical algorithms (65Y20) Convex programming (90C25) Nonlinear programming (90C30)

Review text

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 \textit{M. Kojima, S. Shindoh} and \textit{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 \textit{M. Kojima, S. Mizuno} and \textit{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 \textit{R. D. C. Monteiro} and \textit{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 \textit{Y. E. Nesterov} and \textit{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.

Recommendations

Cited in

(only showing first 100 items - show all)

This page was built for publication: Primal--Dual Path-Following Algorithms for Semidefinite Programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4377581)