Optimization Online


A fresh CP look at mixed-binary QPs: New formulations and relaxations

Immanuel Bomze(immanuel.bomze***at***univie.ac.at)
Jianqiang Cheng(jcheng***at***sandia.gov)
Peter J.C. Dickinson(p.j.c.dickinson***at***utwente.nl)
Abdel Lisser(lisser***at***lri.fr)

Abstract: Triggered by Burer's seminal characterization from 2009, many copositive (CP) reformulations of mixed-binary QPs have been discussed by now. Most of them can be used as proper relaxations, if the intractable co(mpletely )positive cones are replaced by tractable approximations. While the widely used approximation hierarchies have the disadvantage to use positive-semidefinite (psd) matrices of orders which rapidly increase with the level of approximation, alternatives focus on the problem of keeping psd matrix orders small, with the aim to avoid memory problems in the interior point algorithms. This work is the first to treat the various variants from a common theoretical perspective, using concise arguments and discussing conic duality.

Keywords: Copositivity, Completely positive, Conic optimization, Quadratic optimization, Reformulations, Nonlinear optimization, Nonconvex optimization

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 2: Nonlinear Optimization (Quadratic Programming )


Download: [PDF]

Entry Submitted: 05/21/2016
Entry Accepted: 05/21/2016
Entry Last Modified: 05/21/2016

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