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 a 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 results obtained by Sturm and Zhang (Math Oper Res 28:246–267, 2003). Our result also generalizes the well-known completely positive representation result from Burer (Math Program 120:479–495, 2009), which is actually a special instance of our result with \({K=\mathbb{R}^n_{+}}\).
Similar content being viewed by others
References
Anstreicher K.M., Burer S.: Computable representations for convex hulls of low dimensional quadratic forms. Math. Program. 124, 33–43 (2010)
Bomze I., Dür M., de Klerk E., Roos C., Quist A.J., Terlaky T.: On copositive programming and standard quadratic optimization problems. J. Glob. Optim. 18, 301–320 (2000)
Bomze, I., Eichfelder, G.: Copositivity detection by difference-of-convex decomposition and omega-subdivision, Preprint Series of the Institute of Applied Mathematics, University of Erlangen-Nuremberg, vol. 333 (2010)
Bomze I., Jarre F.: A note on Burer’s copositive representation of mixed-binary QPs. Optim. Lett. 4, 465–472 (2010)
Burer S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120, 479–495 (2009)
Burer, S.: Copositive Programming. In: Anjos, M., Lasserre, J.B. (eds.) Handbook of Semidefinite, Conic and Polynomial Optimization, Springer (2011)
Burer S., Anstreicher K.M., Dür M.: The difference between 5 × 5 doubly nonnegative and completely positive matrices. Linear Algebra Appl. 431, 1539–1552 (2009)
Burer, S., Dong, H.: Representing quadratically constrained quadratic programs as generalized copositive programs. http://www.optimization-online.org/DB_HTML/2011/07/3095.html (2011)
Bundfuss S., Dür M.: Algorithmic copositivity detection by simplicial partition. Linear Algebra Appl. 428, 1511–1523 (2008)
Bundfuss S., Dür M.: An adaptive linear approximation algorithm for copositive programs. SIAM J. Optim. 20, 30–53 (2009)
Eichfelder G., Jahn J.: Set-Semidefinite Optimization. J. Convex Anal. 15, 767–801 (2008)
Eichfelder, G., Jahn, J.: Foundations of Set-Semidefinite Optimization. In: Pardalos, P., Rassias, Th.M., Khan, A.A. (eds.) Nonlinear Analysis and Variational Problems, Chapter 18, pp. 259–284, Springer (2009)
Eichfelder G., Povh J.: On the set-semidefinite representation of non-convex quadratic programs with cone constraints. Croat. Oper. Res. Rev. 1, 26–39 (2011)
Jarre F., Schmallowsky K.: On the computation of C* certificates. J. Glob. Optim. 45, 281–296 (2009)
de Klerk E., Pasechnik D.V.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12, 875–892 (2002)
Pólik I., Terlaky T.: A survey of the S-lemma. SIAM Rev. 49, 371–418 (2007)
Povh J., Rendl F.: A copositive programming approach to graph partitioning. SIAM J. Optim. 18, 223–241 (2007)
Povh J., Rendl F.: Copositive and semidefinite relaxations of the quadratic assignment problem. Discret. Optim. 6, 231–241 (2009)
Sturm J.F., Zhang S.: On cones of nonnegative quadratic functions. Math. Oper. Res. 28, 246–267 (2003)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Eichfelder, G., Povh, J. On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets. Optim Lett 7, 1373–1386 (2013). https://doi.org/10.1007/s11590-012-0450-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-012-0450-3