Optimization Online


On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets

Gabriele Eichfelder (Gabriele.Eichfelder***at***am.uni-erlangen.de)
Janez Povh (janez.povh***at***fis.unm.si)

Abstract: In the paper we prove that any nonconvex quadratic problem over some set $K\subset \mathbb{R}^n$ with additional linear and binary constraints can be rewritten as linear problem over the cone, dual to the cone of K-semidefinite matrices. We show that when K is defined by one quadratic constraint or by one concave quadratic constraint and one linear inequality, then the resulting K-semidefinite problem is actually a semidefinite programming problem. This generalizes a results obtained by Sturm and Zhang ([J.F. Sturm and S. Zhang, On cones of nonnegative quadratic functions. Math. Oper. Res. 28 (2003)]), since we can handle problems with many linear and binary constraints. Our result also generalizes the well-known completely positive representation result from Burer ([S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120 (Ser. A) (2009), pp. 479–-495]), which is actually a special instance of our result with $K=\mathbb{R}^n$.

Keywords: set-positivity, semidefinite programming, copositive programming, mixed integer programming.

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Nonlinear Optimization (Quadratic Programming )

Category 3: Convex and Nonsmooth Optimization

Citation: Preprint No. 349, Preprint-Series of the Institute of Applied Mathematics, Univ. Erlangen-Nürnberg, Germany, 2011. See also published version in Optimization Letters DOI: 10.1007/s11590-012-0450-3

Download: [PDF]

Entry Submitted: 06/30/2011
Entry Accepted: 07/03/2011
Entry Last Modified: 02/20/2012

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