TY - JOUR
T1 - Primal-dual interior-point methods for semidefinite programming
T2 - Convergence rates, stability and numerical results
AU - Alizadeh, Farid
AU - Haeberly, Jean Pierre A
AU - Overton, Michael L.
PY - 1998/8
Y1 - 1998/8
N2 - Primal-dual interior-point path-following methods for semidefinite programming are considered. Several variants are discussed, based on Newton's method applied to three equations: primal feasibility, dual feasibility, and some form of centering condition. The focus is on three such algorithms, called the XZ, XZ+ZX, and Q methods. For the XZ+ZX and Q algorithms, the Newton system is well defined and its Jacobian is nonsingular at the solution, under nondegeneracy assumptions. The associated Schur complement matrix has an unbounded condition number on the central path under the nondegeneracy assumptions and an additional rank assumption. Practical aspects are discussed, including Mehrotra predictor-corrector variants and issues of numerical stability. Compared to the other methods considered, the XZ+ZX method is more robust with respect to its ability to step close to the boundary, converges more rapidly, and achieves higher accuracy.
AB - Primal-dual interior-point path-following methods for semidefinite programming are considered. Several variants are discussed, based on Newton's method applied to three equations: primal feasibility, dual feasibility, and some form of centering condition. The focus is on three such algorithms, called the XZ, XZ+ZX, and Q methods. For the XZ+ZX and Q algorithms, the Newton system is well defined and its Jacobian is nonsingular at the solution, under nondegeneracy assumptions. The associated Schur complement matrix has an unbounded condition number on the central path under the nondegeneracy assumptions and an additional rank assumption. Practical aspects are discussed, including Mehrotra predictor-corrector variants and issues of numerical stability. Compared to the other methods considered, the XZ+ZX method is more robust with respect to its ability to step close to the boundary, converges more rapidly, and achieves higher accuracy.
KW - Convex programming
KW - Eigenvalue optimization
KW - Interior-point method
KW - Semidefinite programming
UR - http://www.scopus.com/inward/record.url?scp=0032327612&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0032327612&partnerID=8YFLogxK
U2 - 10.1137/S1052623496304700
DO - 10.1137/S1052623496304700
M3 - Article
AN - SCOPUS:0032327612
SN - 1052-6234
VL - 8
SP - 746
EP - 768
JO - SIAM Journal on Optimization
JF - SIAM Journal on Optimization
IS - 3
ER -