On semidefinite bounds for maximization of a non-convex quadratic objective over the l1 unit ball

Mustafa Ç. Pinar; Marc Teboulle

RAIRO - Operations Research (2006)

  • Volume: 40, Issue: 3, page 253-265
  • ISSN: 0399-0559

Abstract

top
We consider the non-convex quadratic maximization problem subject to the l1 unit ball constraint. The nature of the l1 norm structure makes this problem extremely hard to analyze, and as a consequence, the same difficulties are encountered when trying to build suitable approximations for this problem by some tractable convex counterpart formulations. We explore some properties of this problem, derive SDP-like relaxations and raise open questions.

How to cite

top

Pinar, Mustafa Ç., and Teboulle, Marc. "On semidefinite bounds for maximization of a non-convex quadratic objective over the l1 unit ball." RAIRO - Operations Research 40.3 (2006): 253-265. <http://eudml.org/doc/249741>.

@article{Pinar2006,
abstract = { We consider the non-convex quadratic maximization problem subject to the l1 unit ball constraint. The nature of the l1 norm structure makes this problem extremely hard to analyze, and as a consequence, the same difficulties are encountered when trying to build suitable approximations for this problem by some tractable convex counterpart formulations. We explore some properties of this problem, derive SDP-like relaxations and raise open questions. },
author = {Pinar, Mustafa Ç., Teboulle, Marc},
journal = {RAIRO - Operations Research},
keywords = {Non-convex quadratic optimization; L1-norm constraint; semidefinite programming relaxation; duality.; non-convex quadratic optimization; -norm constraint; duality},
language = {eng},
month = {11},
number = {3},
pages = {253-265},
publisher = {EDP Sciences},
title = {On semidefinite bounds for maximization of a non-convex quadratic objective over the l1 unit ball},
url = {http://eudml.org/doc/249741},
volume = {40},
year = {2006},
}

TY - JOUR
AU - Pinar, Mustafa Ç.
AU - Teboulle, Marc
TI - On semidefinite bounds for maximization of a non-convex quadratic objective over the l1 unit ball
JO - RAIRO - Operations Research
DA - 2006/11//
PB - EDP Sciences
VL - 40
IS - 3
SP - 253
EP - 265
AB - We consider the non-convex quadratic maximization problem subject to the l1 unit ball constraint. The nature of the l1 norm structure makes this problem extremely hard to analyze, and as a consequence, the same difficulties are encountered when trying to build suitable approximations for this problem by some tractable convex counterpart formulations. We explore some properties of this problem, derive SDP-like relaxations and raise open questions.
LA - eng
KW - Non-convex quadratic optimization; L1-norm constraint; semidefinite programming relaxation; duality.; non-convex quadratic optimization; -norm constraint; duality
UR - http://eudml.org/doc/249741
ER -

References

top
  1. M.X. Goemans and D.P. Williamson, Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems using Semidefinite Programming. J. ACM42 (1995) 1115–1145.  
  2. J.-B. Hiriart-Urruty, Conditions for Global Optimality, in Handbook for Global Optimization. Kluwer Academic Publishers, Dordrecht, Holland (1999) 1–26.  
  3. J.-B. Hiriart-Urruty, Conditions for Global Optimality 2. J. Global Optim.13 (1998) 349–367.  
  4. J.-B. Hiriart-Urruty, Global Optimality Conditions in Maximizing a Convex Quadratic Function under Convex Quadratic Constraints. J. Global Optim.21 (2001) 445–455.  
  5. R.A. Horn and C.R. Johnson, Matrix Analysis. Cambridge University Press, Cambridge (1985).  
  6. V. Jeyakumar, A.M. Rubinov and Z.Y. Wu, Non-convex Quadratic Minimization Problems with Quadratic Constraints: Global Optimality Conditions. Technical Report AMR05/19, University of South Wales, School of Mathematics (2005).  
  7. V. Jeyakumar, A.M. Rubinov and Z.Y. Wu, Sufficient Global Optimality Conditions for Non-convex Quadratic Minimization Problems with Box Constraints. Technical Report AMR05/20, University of South Wales, School of Mathematics (2005).  
  8. J.-B. Lasserre, Global Optimization with Polynomials and the problem of moments. SIAM J. Optim.11 (2001) 796–817.  
  9. J.-B. Lasserre, GloptiPoly: Global Optimization over Polynomials with Matlab and SeDuMi. ACM Trans. Math. Software29 (2003) 165–194.  
  10. M. Laurent, A comparison of the Sherali-Adams, Lovasz-Schrijver and Lasserre relaxations for 0-1 programming. Math. Oper. Res.28 (2003) 470–496.  
  11. L. Lovasz and A. Schrijver, Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim.1 (1991) 166–190.  
  12. Y. Nesterov, Semidefinite Relaxation and Non-convex Quadratic Optimization. Optim. Methods Softw.12 (1997) 1–20.  
  13. Y. Nesterov, Global Quadratic Optimization via Conic Relaxation, in Handbook of Semidefinite Programming, edited by H. Wolkowicz, R. Saigal and L. Vandenberghe. Kluwer Academic Publishers, Boston (2000) 363–384.  
  14. R.T. Rockafellar, Convex Analysis. Princeton University Press, Princeton, NJ (1970).  
  15. N.Z. Shor, On a bounding method for quadratic extremal problems with 0-1 variables. Kibernetika2 (1985) 48–50.  
  16. H. Wolkowicz, R. Saigal and L. Vandenberghe (Editors), Handbook of semidefinite programming: Theory, Algorithms, and Applications. Kluwer Academic Publishers, Boston, MA (2000).  
  17. Y. Ye, Approximating Quadratic Programming with Bound and Quadratic Constraints. Math. Program.84 (1999) 219–226.  
  18. S. Zhang, Quadratic Maximization and Semidefinite Relaxation. Math. Program.87 (2000) 453–465.  

NotesEmbed ?

top

You must be logged in to post comments.