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

Scheduled Maintenance - May 20th Between 0600 and 0800 GMT (0700 - 0900 BST) on May 20th 2012, there will be some disruption to normal CJO service. This is due to some scheduled maintenance work. Normal service will resume shortly after that.

RAIRO - Operations Research

RAIRO - Operations Research July 2006 40 : pp 253-265
© EDP Sciences, 2006
DOI: http://dx.doi.org/10.1051/ro:2006023 (About DOI)
Published online by Cambridge University Press: 18 March 2011

Table of Contents - July 2006 - Volume 40, Issue 03

Research Article

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

Article author query
pinar mç [Google Scholar]
teboulle m [Google Scholar]

Mustafa Ç. Pinar^a1 and Marc Teboulle^a2

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

Abstract

We consider the non-convex quadratic maximization problem subject to the l₁ 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.

(Received June 25 2005)

(Accepted January 26 2006)

(Online publication November 8 2006)

Key Words:

Non-convex quadratic optimization;
L1-norm constraint;
semidefinite programming relaxation;
duality.

Blog This Article

Copy and paste this code to insert a reference to this article in your blog or online community profile:

Highlight all

<div style="background: #FFFFFF; margin: 0 10px 10px 0; padding: 0 10px 0 0; text-align: left; font-family: Arial, Helvetica, sans-serif; line-height: 1em;"><div style="font-size: 11px; padding: 0px 0px 10px 0px; font-weight:bold; color: #045989;">On semidefinite bounds for maximization  of a non-convex quadratic objective over the <i>l<sub>1</sub>                </i> unit ball</div><div style="font-size: 11px;"><b>				
					 
					
						 
					
				Mustafa Ç. Pinar				
					 
					
						 
					
				 and Marc Teboulle (2006).</b><br />
<a href="http://journals.cambridge.org/action/displayJournal?jid=ROE">RAIRO - Operations Research</a>, <a href="http://journals.cambridge.org/action/displayJournal?jid=ROE&volumeId=40&bVolume=y#loc40>

">Volume 40</a>, 
<a href="http://journals.cambridge.org/action/displayIssue?jid=ROE&volumeId=40&issueId=03&seriesId=0"> Issue 03</a>, July 2006 pp 253-265 <br/>
<a href="http://journals.cambridge.org/action/displayAbstract?aid=8224182">http://journals.cambridge.org/action/displayAbstract?aid=8224182</a></div></div>

The code will display like this

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

Mustafa Ç. Pinar and Marc Teboulle (2006)
RAIRO - Operations Research, , Volume 40, Issue 03 , July 2006 pp 253-265
http://www.rairo-ro.org/10.1051/ro:2006023

Welcome to Cambridge Journals Online

RAIRO - Operations Research

Research Article

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

Mustafa Ç. Pinara1 and Marc Teboullea2

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

Mustafa Ç. Pinar^a1 and Marc Teboulle^a2