Primal–dual path-following algorithms for semidefinite programming.

*(English)*Zbl 0913.65051The 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.

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 |