Title :
Convergent LMI relaxations for nonconvex quadratic programs
Author :
Lasserre, Jean B.
Author_Institution :
Lab. d´´Autom. et d´´Anal. des Syst., CNRS, Toulouse, France
Abstract :
We consider the general nonconvex quadratic programming problem and provide a series of convex positive semidefinite programs (or LMI relaxations) whose sequence of optimal values is monotone and converges to the optimal value of the original problem. It improves and includes as a special case the well-known Shor´s LMI formulation. Often, the optimal value is obtained at some particular early relaxation as shown on some nontrivial test problems from Floudas and Pardalos (1990)
Keywords :
convergence of numerical methods; matrix algebra; quadratic programming; relaxation theory; LMI relaxation; Shor formulation; convergence; linear matrix inequality; nonconvex quadratic programs; semidefinite programming; Jacobian matrices; NP-hard problem; Polynomials; Quadratic programming; Testing;
Conference_Titel :
Decision and Control, 2000. Proceedings of the 39th IEEE Conference on
Conference_Location :
Sydney, NSW
Print_ISBN :
0-7803-6638-7
DOI :
10.1109/CDC.2001.914738