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

Issue		RAIRO Oper. Res. Volume 40, Number 3, July-September 2006


Page(s)		253 - 265
DOI		10.1051/ro:2006023
Published online		08 November 2006

RAIRO Oper. Res. 40 (2006) 253-265
DOI: 10.1051/ro:2006023

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

Mustafa Ç. Pinar¹ and Marc Teboulle²

¹ Department of Industrial Engineering,Bilkent University, 06533 Ankara, Turkey; mustafap@bilkent.edu.tr
² School of Mathematical Sciences, Tel-Aviv University, Ramat-Aviv 69978, Israel; teboulle@math.tau.ac.il

(Received June 25, 2005. Accepted January 26, 2006. Published online 8 November 2006.)

Abstract
We consider the non-convex quadratic maximization problem subject to the $\ell_1$ unit ball constraint. The nature of the l₁ 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.

Key words: Non-convex quadratic optimization, L1-norm constraint, semidefinite programming relaxation, duality.

© EDP Sciences 2006

What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.

If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.