Improving SDP bounds for minimizing quadratic functions over the l1-ball

Bomze, Immanuel M.; Frommlet, Florian; Rubey, Martin

Improving SDP bounds for minimizing quadratic functions over the l1-ball

Authors

Bomze, Immanuel M.

Frommlet, Florian

Rubey, Martin

Description

In this note, we establish superiority of the so-called copositive bound over a bound suggested by Nesterov for the quadratic problem to minimize a quadratic form over the l1-ball. We illustrate the improvement by simulation results. The copositive bound has the additional advantage that it can be easily extended to the inhomogeneous case of quadratic objectives including a linear term. We also indicate some improvements of the eigenvalue bound for the quadratic optimization over the lp-ball with 1<p<2, at least for p close to one.
12 pages, 4 figures, v2: Figure 2a corrected, minor changes