# 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

## Access Full Article

top## Abstract

top## How to cite

topPinar, 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- M.X. Goemans and D.P. Williamson, Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems using Semidefinite Programming. J. ACM42 (1995) 1115–1145. Zbl0885.68088
- J.-B. Hiriart-Urruty, Conditions for Global Optimality, in Handbook for Global Optimization. Kluwer Academic Publishers, Dordrecht, Holland (1999) 1–26.
- J.-B. Hiriart-Urruty, Conditions for Global Optimality 2. J. Global Optim.13 (1998) 349–367.
- J.-B. Hiriart-Urruty, Global Optimality Conditions in Maximizing a Convex Quadratic Function under Convex Quadratic Constraints. J. Global Optim.21 (2001) 445–455.
- R.A. Horn and C.R. Johnson, Matrix Analysis. Cambridge University Press, Cambridge (1985). Zbl0576.15001
- 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). Zbl1206.90178
- 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). Zbl1131.90060
- J.-B. Lasserre, Global Optimization with Polynomials and the problem of moments. SIAM J. Optim.11 (2001) 796–817. Zbl1010.90061
- J.-B. Lasserre, GloptiPoly: Global Optimization over Polynomials with Matlab and SeDuMi. ACM Trans. Math. Software29 (2003) 165–194. Zbl1070.65549
- M. Laurent, A comparison of the Sherali-Adams, Lovasz-Schrijver and Lasserre relaxations for 0-1 programming. Math. Oper. Res.28 (2003) 470–496. Zbl1082.90084
- L. Lovasz and A. Schrijver, Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim.1 (1991) 166–190. Zbl0754.90039
- Y. Nesterov, Semidefinite Relaxation and Non-convex Quadratic Optimization. Optim. Methods Softw.12 (1997) 1–20.
- 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.
- R.T. Rockafellar, Convex Analysis. Princeton University Press, Princeton, NJ (1970). Zbl0193.18401
- N.Z. Shor, On a bounding method for quadratic extremal problems with 0-1 variables. Kibernetika2 (1985) 48–50.
- H. Wolkowicz, R. Saigal and L. Vandenberghe (Editors), Handbook of semidefinite programming: Theory, Algorithms, and Applications. Kluwer Academic Publishers, Boston, MA (2000). Zbl0951.90001
- Y. Ye, Approximating Quadratic Programming with Bound and Quadratic Constraints. Math. Program.84 (1999) 219–226. Zbl0971.90056
- S. Zhang, Quadratic Maximization and Semidefinite Relaxation. Math. Program.87 (2000) 453–465. Zbl1009.90080

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.