Optimization Online


Copositive relaxation beats Lagrangian dual bounds in quadratically and linearly constrained QPs

Immanuel M. Bomze (immanuel.bomze***at***univie.ac.at)

Abstract: We study non-convex quadratic minimization problems under (possibly non-convex) quadratic and linear constraints, and characterize both Lagrangian and Semi-Lagrangian dual bounds in terms of conic optimization. While the Lagrangian dual is equivalent to the SDP relaxation (which has been known for quite a while, although the presented form, incorporating explicitly linear constraints, seems to be novel), we show that the Semi-Lagrangian dual is equivalent to a natural copositive relaxation (and this has apparently not been observed before). This way, we arrive at conic bounds tighter than the usual Lagrangian dual (and thus than the SDP) bounds. Any of the known tractable inner approximations of the copositive cone can be used for this tightening, but in particular, above mentioned characterization with explicit linear constraints is a natural, much cheaper, relaxation than the usual zero-order approximation by doubly nonnegative (DNN) matrices, and still improves upon the Lagrangian dual bounds. These approximations are based on LMIs on matrices of basically the original order plus additional linear constraints (in contrast to more familiar sum-of-squares or moment approximation hierarchies), and thus may have merits in particular for large instances where it is important to employ only a few inequality constraints (eg., $n$ instead of $\frac{n(n-1)}2$ for the DNN relaxation). Further we specify sufficient conditions for tightness of the Semi-Lagrangian relaxation and show that copositivity of the slack matrix guarantees global optimality for KKT points of this problem, thus significantly improving upon a well-known second-order global optimality condition.

Keywords: Copositive matrices, non-convex optimization, polynomial optimization, quadratically constrained problem, approximation hierarchies, global optimality condition

Category 1: Nonlinear Optimization (Quadratic Programming )

Category 2: Global Optimization (Theory )

Category 3: Linear, Cone and Semidefinite Programming (Other )

Citation: Preprint NI13064-POP, Isaac Newton Institute for Mathematical Sciences, University of Cambridge UK, submitted

Download: [PDF]

Entry Submitted: 11/19/2013
Entry Accepted: 11/19/2013
Entry Last Modified: 04/25/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society