×

zbMATH — the first resource for mathematics

Local minima and convergence in low-rank semidefinite programming. (English) Zbl 1099.90040
Summary: The low-rank semidefinite programming problem \(\text{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 \(\text{LRSDP}_r\) is equivalent to SDP if \(r\) is not too small. In this paper, we classify the local minima of \(\text{LRSDP}_r\) and prove the optimal convergence of a slight variant of the successful, yet experimental, algorithm of Burer and Monteiro [5], which handles \(\text{LRSDP}_r\) via the nonconvex change of variables \(X = RR^T\). 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.

MSC:
90C22 Semidefinite programming
90C27 Combinatorial optimization
Software:
QAPLIB; SDPLR
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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) · Zbl 0911.65047
[2] K.M. Anstreicher. Recent advances in the solution of quadratic assignment problems. Mathematical Programming (Series B), 97 (1–2), 27–42 (2003) · Zbl 1035.90067
[3] Barker, G.P., Carlson, D.: Cones of diagonally dominant matrices. Pacific Journal of Mathematics, 57 (1), 15–32 (1975) · Zbl 0283.52005
[4] Burer, S.: Semidefinite programming in the space of partial positive semidefinite matrices. SIAM Journal on Optimization, 14 (1), 139–172 (2003) · Zbl 1075.90059
[5] 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) · Zbl 1030.90077
[6] Burer, S., Monteiro, R.D.C., Zhang. Y.: Solving a class of semidefinite programs via nonlinear programming. Mathematical Programming, 93, 97–122 (2002) · Zbl 1007.90045
[7] Burkard, R.E., Karisch, S., Rendl, F.: QAPLIB – a quadratic assignment problem library. European Journal of Operational Research, 55,115–119 (1991) · Zbl 0729.90993
[8] Helmberg, C.: Semidefinite programming for combinatorial optimization. ZIB-Report 00-34, Konrad-Zuse-Zentrum für Informationstechnik Berlin, October 2000.
[9] Helmberg, C., Rendl, F.: A spectral bundle method for semidefinite programming. SIAM Journal on Optimization, 10, 673–696 (2000) · Zbl 0960.65074
[10] Helmberg, C., Rendl, F., Vanderbei, R.J., Wolkowicz, H.: An interior-point method for semidefinite programming. SIAM Journal on Optimization, 6, 342–361 (1996) · Zbl 0853.65066
[11] 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.
[12] Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, New York, 1985. · Zbl 0576.15001
[13] 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) · Zbl 0872.90098
[14] 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.
[15] Monteiro, R.D.C.: First- and second-order methods for semidefinite programming. Mathematical Programming, 97, 209–244 (2003) · Zbl 1035.90057
[16] Monteiro, R.D.C.: Primal-dual path following algorithms for semidefinite programming. SIAM Journal on Optimization, 7, 663–678 (1997) · Zbl 0913.65051
[17] 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) · Zbl 0919.90109
[18] 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.
[19] 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) · Zbl 0977.90051
[20] 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. · Zbl 0957.90531
[21] Rendl, F., Sotirov, R.: Bounds for the quadratic assignment problem using the bundle method. Manuscript, University of Klagenfurt, August 2003. · Zbl 1278.90303
[22] Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton, NJ, 1970. · Zbl 0193.18401
[23] De Simone, C.: The cut polytope and the boolean quadric polytope. Discrete Mathematics, 79, 71–75 (1989) · Zbl 0683.90068
[24] Toh, K.C.: Solving large scale semidefinite programs via an iterative solver on the agumented systems. SIAM Journal on Optimization, 14, 670–698 (2004) · Zbl 1071.90026
[25] Toh, K.C., Kojima, M.: Solving some large scale semidefinite programs via the conjugate residual method. SIAM Journal on Optimization, 12, 669–691 (2002) · Zbl 1008.90043
[26] Zhang, Y.: On extending some primal–dual interior–point algorithms from linear programming to semidefinite programming. SIAM Journal on Optimization, 8, 365–386 (1998) · Zbl 0913.65050
[27] 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) · Zbl 0904.90145
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.