×

A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinite programming. (English) Zbl 0919.90109

Summary: 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 path \(H_P(XS)\equiv [PXSP^{-1}+ (PXSP^{-1})^T]/2= \mu I\), introduced by Zhang. At an iterate \((X, S)\), we choose a scaling matrix \(P\) from the class of nonsingular matrices \(P\) such that \(PXSP^{-1}\) is symmetric. This class of matrices includes the three well-known choices, namely: \(P= S^{1/2}\) and \(P= X^{-1/2}\) proposed by Monteiro, and the matrix \(P\) corresponding 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.

MSC:

90C51 Interior-point methods
90C22 Semidefinite programming
90C46 Optimality conditions and duality in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] F. Alizadeh, Combinatorial Optimization with Interior Point Methods and Semi-Definite Matrices, Ph.D. Thesis, Computer Science Department, University of Minnesota, Minneapolis, 1991.
[2] F. Alizadeh, J.A. Haeberly, M. Overton, Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results, Technical report, Computer Science Department, New York University, New York, 1996. · Zbl 0911.65047
[3] C. Helmberg, F. Rendl, R.J. Vanderbei, H. Wolkowicz, An interior-point method for semidefinite programming, SIAM Journal on Optimization 6 (1996) 342–361. · Zbl 0853.65066
[4] R.A. Horn, C.R. Johnson, Topics in Matrix Analysis, Cambridge University Press, New York, 1991. · Zbl 0729.15001
[5] F. Jarre, An interior-point method for minimizing the maximum eigenvalue of a linear combination of matrices, SIAM Journal on Control and Optimization 31 (1993) 1360–1377. · Zbl 0780.65023
[6] M. Kojima, S. Mizuno, A. Yoshise, A primal-dual interior point method for linear programming, in: Nimrod Megiddo (Ed.), Progress in Mathematical Programming, Interior-Point and Related Methods, Springer, New York, 1989, pp. 29–47. · Zbl 0708.90049
[7] M. Kojima, M. Shida, S. Shindoh, Local convergence of predictor-corrector infeasible-interior-point algorithms for SDPs and SDLCPs, Mathematical Programming 80 (1998) 129–160. · Zbl 0897.90183
[8] M. Kojima, M. Shida, S. Shindoh, A note on the Nesterov-Todd and the Kojima-Shindoh-Hara search directions in semidefinite programming, Research Report #B-313, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology 2-12-1 Oh-Okayama, Meguro-ku, Tokyo 152, Japan, 1996. · Zbl 0957.90104
[9] M. Kojima, S. Shindoh, S. Hara, Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices, SIAM Journal on Optimization 7 (1997) 86–125. · Zbl 0872.90098
[10] C-J. Lin, R. Saigal, A predictor-corrector method for semi-definite programming, Working paper, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, Michigan 48109-2177, 1995.
[11] Z-Q. Luo, J.F. Sturm, S. Zhang, Superlinear convergence of a symmetric primal-dual path-following algorithms for semidefinite programming, Working paper, 1996 (to appear in SIAM Journal on Optimization).
[12] R.D.C. Monteiro, Primal-dual path-following algorithms for semidefinite programming, SIAM Journal on Optimization 7 (1997) 663–678. · Zbl 0913.65051
[13] R.D.C. Monteiro, Polynomial convergence of primal-dual algorithms for semidefinite programming based on Monteiro and Zhang family of directions, Manuscript, School of ISyE, Georgia Institute of Technology, Atlanta, GA 30332, USA, 1996.
[14] Y.E. Nesterov, A.S. Nemirovskii, A general approach to the design of optimal methods for smooth convex functions minimization, Ekonomika i Matem, Metody 24 (1988) 509–517 (In Russian; English transl. Matekon: Translations of Russian and East European Math. Economics.). · Zbl 0659.90068
[15] Y.E. Nesterov, A.S. Nemirovskii, Self-concordant functions and polynomial time methods in convex programming, Preprint, Central Economic & Mathematical Institute, USSR Acadamy of Science, Moscow, USSR, 1989.
[16] Y.E. Nesterov, A.S. Nemirovskii, Optimization over positive semidefinite matrices: Mathematical background and user’s manual, Technical report, Central Economic & Mathematical Institute, USSR Academy of Science Moscow, USSR, 1990.
[17] Y.E. Nesterov, A.S. Nemirovskii, Interior Point Methods in Convex Programming: Theory and Applications, Society for Industrial and Applied Mathematics, Philadelphia, 1994. · Zbl 0824.90112
[18] Y.E. Nesterov, M.J. Todd, Self-scaled barriers and interior-point methods for convex programming, Technical Report 1091, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, New York, 14853-3801, 1995.
[19] Y.E. Nesterov, M.J. Todd, Primal-dual interior-point methods for self-scaled cones, Mathematics of Operations Research 22 (1997) 1–42. · Zbl 0871.90064
[20] F.A. Potra, R. Sheng, A superlinearly convergent primal-dual infeasible-interior-point algorithm for semidefinite programming, Reports on Computational Mathematics, No. 78, Department of Mathematics, The University of Iowa, 1995. · Zbl 0917.65058
[21] M. Shida, S. Shindoh, M. Kojima, Existence of search directions in interior-point algorithms for the SDP and monotone SDLCP, Technical Report B-310, Department of Mathematical and Computer Science, Tokyo Institute of Technology, 1996 (to appear in SIAM Journal on Optimization). · Zbl 0913.90252
[22] J.F. Sturm, S. Zhang, Symmetric primal-dual path-following algorithms for semidefinite programming, Report 9554/A, Ecometric Institute, Erasmus University Rotterdam, The Netherlands, 1995. · Zbl 0956.90027
[23] J.F. Sturm, S. Zhang, On the long-step path-following method for semidefinite programming, Report 9638/A, Ecometric Institute, Erasmus University Rotterdam, The Netherlands, 1996. · Zbl 0911.90257
[24] M.J. Todd, K.C. Toh, R.H. Tütüncü, On the Nesterov-Todd direction in semidefinite programming, Technical Report, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY 14853, USA, 1996.
[25] L. Vandenberghe, S. Boyd, A primal-dual potential reduction method for problems involving matrix inequalities, Mathematical Programming 69 (1995) 205–236. · Zbl 0857.90104
[26] Y. Ye, A class of projective transformations for linear programming, SIAM Journal on Computing 19 (1990) 457–466.
[27] Y. Zhang, On extending some primal-dual interior-Point algorithms from linear programming to semidefinite programming, Technical Report, 1995 (to appear in SIAM Journal on Optimization).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.