Abstract
In this paper we consider the standard linear SDP problem, and its low rank nonlinear programming reformulation, based on a Gramian representation of a positive semidefinite matrix. For this nonconvex quadratic problem with quadratic equality constraints, we give necessary and sufficient conditions of global optimality expressed in terms of the Lagrangian function.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Barvinok A.: Problems of distance geometry and convex properties of quadratic maps. Discrete Comput. Geom. 13, 189–202 (1995)
Burer S., Monteiro R.D.C.: A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program. Ser. B 95, 329–357 (2003)
Burer S., Monteiro R.D.C.: Local minima and convergence in low-rank semidefinite programming. Math. Program. Ser. A 103, 427–444 (2005)
Goemans M.X., Williamson D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach. 42(6), 1115–1145 (1995)
Grippo, L., Palagi, L., Piccialli, V.: An unconstrained minimization method for solving low rank SDP relaxations of the max cut problem. DIS Technical Report. 07-07, Sapienza Università di Roma (2007)
Hiriart-Urruty J.B.: Conditions for global optimality 2. J. Glob. Optim. 13, 349–367 (1998)
Horn R.A., Johnson C.R.: Topics in Matrix Analysis. Cambridge University Press, New York (1986)
Jeyakumar V., Rubinov A.M., Wu Z.Y.: Non-convex quadratic minimization problems with quadratic constraints: global optimality conditions. Math. Program. Ser. A 110, 521–541 (2007)
Monteiro R.D.C.: First- and second-order methods for semidefinite programming. Math. Program. 97, 209–244 (2003)
Moré J.: Generalization of the trust region problem. Optim. Meth. Softw. 2, 189–209 (1993)
Pataki G.: On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues. Math. Oper. Res. 23, 339–358 (1998)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Grippo, L., Palagi, L. & Piccialli, V. Necessary and sufficient global optimality conditions for NLP reformulations of linear SDP problems. J Glob Optim 44, 339–348 (2009). https://doi.org/10.1007/s10898-008-9328-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-008-9328-4