On semidefinite bounds for maximization of a non-convex quadratic objective over the ℓ 1 unit ball
RAIRO - Operations Research - Recherche Opérationnelle, Tome 40 (2006) no. 3, pp. 253-265.

We consider the non-convex quadratic maximization problem subject to the ℓ 1 unit ball constraint. The nature of the l 1 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.

DOI : 10.1051/ro:2006023
Mots-clés : non-convex quadratic optimization, L1-norm constraint, semidefinite programming relaxation, duality 
@article{RO_2006__40_3_253_0,
     author = {Pinar, Mustafa \c{C}. and Teboulle, Marc},
     title = {On semidefinite bounds for maximization of a non-convex quadratic objective over the $\ell _1$ unit ball},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {253--265},
     publisher = {EDP-Sciences},
     volume = {40},
     number = {3},
     year = {2006},
     doi = {10.1051/ro:2006023},
     mrnumber = {2276158},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro:2006023/}
}
TY  - JOUR
AU  - Pinar, Mustafa Ç.
AU  - Teboulle, Marc
TI  - On semidefinite bounds for maximization of a non-convex quadratic objective over the $\ell _1$ unit ball
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2006
SP  - 253
EP  - 265
VL  - 40
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro:2006023/
DO  - 10.1051/ro:2006023
LA  - en
ID  - RO_2006__40_3_253_0
ER  - 
%0 Journal Article
%A Pinar, Mustafa Ç.
%A Teboulle, Marc
%T On semidefinite bounds for maximization of a non-convex quadratic objective over the $\ell _1$ unit ball
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2006
%P 253-265
%V 40
%N 3
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro:2006023/
%R 10.1051/ro:2006023
%G en
%F RO_2006__40_3_253_0
Pinar, Mustafa Ç.; Teboulle, Marc. On semidefinite bounds for maximization of a non-convex quadratic objective over the $\ell _1$ unit ball. RAIRO - Operations Research - Recherche Opérationnelle, Tome 40 (2006) no. 3, pp. 253-265. doi : 10.1051/ro:2006023. http://www.numdam.org/articles/10.1051/ro:2006023/

[1] M.X. Goemans and D.P. Williamson, Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems using Semidefinite Programming. J. ACM 42 (1995) 1115-1145. | Zbl

[2] J.-B. Hiriart-Urruty, Conditions for Global Optimality, in Handbook for Global Optimization. Kluwer Academic Publishers, Dordrecht, Holland (1999) 1-26. | Zbl

[3] J.-B. Hiriart-Urruty, Conditions for Global Optimality 2. J. Global Optim. 13 (1998) 349-367. | Zbl

[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). | MR | Zbl

[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). | MR

[8] J.-B. Lasserre, Global Optimization with Polynomials and the problem of moments. SIAM J. Optim. 11 (2001) 796-817. | Zbl

[9] J.-B. Lasserre, GloptiPoly: Global Optimization over Polynomials with Matlab and SeDuMi. ACM Trans. Math. Software 29 (2003) 165-194. | Zbl

[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. | Zbl

[11] L. Lovasz and A. Schrijver, Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim. 1 (1991) 166-190. | Zbl

[12] Y. Nesterov, Semidefinite Relaxation and Non-convex Quadratic Optimization. Optim. Methods Softw. 12 (1997) 1-20. | Zbl

[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). | MR | Zbl

[15] N.Z. Shor, On a bounding method for quadratic extremal problems with 0-1 variables. Kibernetika 2 (1985) 48-50. | Zbl

[16] H. Wolkowicz, R. Saigal and L. Vandenberghe (Editors), Handbook of semidefinite programming: Theory, Algorithms, and Applications. Kluwer Academic Publishers, Boston, MA (2000). | MR | Zbl

[17] Y. Ye, Approximating Quadratic Programming with Bound and Quadratic Constraints. Math. Program. 84 (1999) 219-226. | Zbl

[18] S. Zhang, Quadratic Maximization and Semidefinite Relaxation. Math. Program. 87 (2000) 453-465. | Zbl

Cité par Sources :