Abstract.
The low-rank semidefinite programming problem LRSDP r is a restriction of the semidefinite programming problem SDP in which a bound r is imposed on the rank of X, and it is well known that LRSDP r is equivalent to SDP if r is not too small. In this paper, we classify the local minima of LRSDP r and prove the optimal convergence of a slight variant of the successful, yet experimental, algorithm of Burer and Monteiro [5], which handles LRSDP r via the nonconvex change of variables X=RRT. In addition, for particular problem classes, we describe a practical technique for obtaining lower bounds on the optimal solution value during the execution of the algorithm. Computational results are presented on a set of combinatorial optimization relaxations, including some of the largest quadratic assignment SDPs solved to date.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alizadeh, F., Haeberly, J.-P.A., Overton. M.L.: Primal-dual interior-point methods for semidefinite programming: convergence rates, stability and numerical results. SIAM Journal on Optimization, 8, 746–768 (1998)
K.M. Anstreicher. Recent advances in the solution of quadratic assignment problems. Mathematical Programming (Series B), 97 (1–2), 27–42 (2003)
Barker, G.P., Carlson, D.: Cones of diagonally dominant matrices. Pacific Journal of Mathematics, 57 (1), 15–32 (1975)
Burer, S.: Semidefinite programming in the space of partial positive semidefinite matrices. SIAM Journal on Optimization, 14 (1), 139–172 (2003)
Burer, S., Monteiro, R.D.C.: A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathematical Programming (Series B), 95, 329–357 (2003)
Burer, S., Monteiro, R.D.C., Zhang. Y.: Solving a class of semidefinite programs via nonlinear programming. Mathematical Programming, 93, 97–122 (2002)
Burkard, R.E., Karisch, S., Rendl, F.: QAPLIB – a quadratic assignment problem library. European Journal of Operational Research, 55,115–119 (1991)
Helmberg, C.: Semidefinite programming for combinatorial optimization. ZIB-Report 00-34, Konrad-Zuse-Zentrum für Informationstechnik Berlin, October 2000.
Helmberg, C., Rendl, F.: A spectral bundle method for semidefinite programming. SIAM Journal on Optimization, 10, 673–696 (2000)
Helmberg, C., Rendl, F., Vanderbei, R.J., Wolkowicz, H.: An interior-point method for semidefinite programming. SIAM Journal on Optimization, 6, 342–361 (1996)
Hiriart-Urruty, J.-B., Lemaréchal, C., Convex analysis and minimization algorithms. I, volume 305 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, 1993.
Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, New York, 1985.
Kojima, M., Shindoh, S., Hara, S.: Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices. SIAM Journal on Optimization, 7, 86–125 (1997)
Lin, C-J., Saigal, R.: On solving large scale semidefinite programming problems: a case study of quadratic assigment problem. Technical Report, Dept. of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, MI 48109-2177, 1997.
Monteiro, R.D.C.: First- and second-order methods for semidefinite programming. Mathematical Programming, 97, 209–244 (2003)
Monteiro, R.D.C.: Primal-dual path following algorithms for semidefinite programming. SIAM Journal on Optimization, 7, 663–678 (1997)
Monteiro, R.D.C., Zhang, Y.: A unified analysis for a class of path-following primal-dual interior-point algorithms for semidefinite programming. Mathematical Programming, 81, 281–299 (1998)
Nakata, K., Fujisawa, K., Kojima, M.: Using the conjugate gradient method in interior-points for semidefinite programs. Proceedings of the Institute of Statistical Mathematics, 46, 297–316 (1998) In Japanese.
Pataki, G.: On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues. Mathematics of Operations Research, 23, 339–358 (1998)
Pataki, G.: The geometry of semidefinite programming. In H. Wolkowicz, R. Saigal, L. Vandenberghe, (eds.), Handbook of Semidefinite Programming: Theory, Algorithms, and Applications. Kluwer Academic Publishers, 2000.
Rendl, F., Sotirov, R.: Bounds for the quadratic assignment problem using the bundle method. Manuscript, University of Klagenfurt, August 2003.
Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton, NJ, 1970.
De Simone, C.: The cut polytope and the boolean quadric polytope. Discrete Mathematics, 79, 71–75 (1989)
Toh, K.C.: Solving large scale semidefinite programs via an iterative solver on the agumented systems. SIAM Journal on Optimization, 14, 670–698 (2004)
Toh, K.C., Kojima, M.: Solving some large scale semidefinite programs via the conjugate residual method. SIAM Journal on Optimization, 12, 669–691 (2002)
Zhang, Y.: On extending some primal–dual interior–point algorithms from linear programming to semidefinite programming. SIAM Journal on Optimization, 8, 365–386 (1998)
Zhao, Q., Karisch, S.E., Rendl, F., Wolkowicz, H.: Semidefinite programming relaxations for the quadratic assignment problem. Journal of Combinatorial Optimization, 2, 71–109 (1998)
Author information
Authors and Affiliations
Corresponding author
Additional information
This author was supported in part by NSF Grant CCR-0203426.
This author was supported in part by NSF Grants CCR-0203113 and INT-9910084 and ONR grant N00014-03-1-0401.
Rights and permissions
About this article
Cite this article
Burer, S., Monteiro, R. Local Minima and Convergence in Low-Rank Semidefinite Programming. Math. Program. 103, 427–444 (2005). https://doi.org/10.1007/s10107-004-0564-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-004-0564-1