×

Representing quadratically constrained quadratic programs as generalized copositive programs. (English) Zbl 1245.90080

Summary: We show that any (nonconvex) quadratically constrained quadratic program (QCQP) can be represented as a generalized copositive program. In fact, we provide two representations: one based on the concept of completely positive (CP) matrices over second-order cones, and one based on CP matrices over the positive semidefinite cone.

MSC:

90C20 Quadratic programming
90C26 Nonconvex programming, global optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alizadeh, F.; Goldfarb, D., Second-order cone programming, Math. Program., 95, 1, Ser. B, 3-51 (2003), ISMP 2000, Part 3 (Atlanta, GA) · Zbl 1153.90522
[2] K. Anstreicher, On convex relaxations for quadratically constrained quadratic programming. Math. Program. (Ser. B) (2012) (in press).; K. Anstreicher, On convex relaxations for quadratically constrained quadratic programming. Math. Program. (Ser. B) (2012) (in press). · Zbl 1267.90103
[3] Bao, X.; Sahinidis, N. V.; Tawarmalani, M., Semidefinite relaxation for quadratically constrained quadratic programming: a review and comparisons, Math. Program. (Ser. B), 129, 1, 129-157 (2011) · Zbl 1232.49035
[4] Berman, A.; Shaked-Monderer, N., Completely Positive Matrices (2003), World Scientific · Zbl 1030.15022
[5] Bomze, I. M.; de Klerk, E., Solving standard quadratic optimization problems via linear, semidefinite and copositive programming, J. Global Optim., 24, 2, 163-185 (2002) · Zbl 1047.90038
[6] Bundfuss, S.; Dür, M., An adaptive linear approximation algorithm for copositive programs, SIAM J. Optim., 20, 1, 30-53 (2009) · Zbl 1187.90187
[7] Burer, S., On the copositive representation of binary and continuous nonconvex quadratic programs, Math. Program., 120, 479-495 (2009) · Zbl 1180.90234
[8] Burer, S., Copositive programming, (Anjos, M.; Lasserre, J., Handbook of Semidefinite, Cone and Polynomial Optimization: Theory, Algorithms, Software and Applications. Handbook of Semidefinite, Cone and Polynomial Optimization: Theory, Algorithms, Software and Applications, International Series in Operational Research and Management Science (2011), Springer), 201-218 · Zbl 1334.90098
[9] S. Burer, K.M. Anstreicher, Second-order-cone constraints for extended trust-region subproblems. Manuscript, Department of Management Sciences, Iowa City, IA, March 2011. SIAM J. Optim. (submitted for publication) Available at: http://www.optimization-online.org/DB_HTML/2011/03/2957.html; S. Burer, K.M. Anstreicher, Second-order-cone constraints for extended trust-region subproblems. Manuscript, Department of Management Sciences, Iowa City, IA, March 2011. SIAM J. Optim. (submitted for publication) Available at: http://www.optimization-online.org/DB_HTML/2011/03/2957.html · Zbl 1298.90062
[10] Burer, S.; Saxena, A., The MILP road to MIQCP, (Lee, J.; Leyffer, S., IMA Volumes in Mathematics and its Applications (2011), Springer), 373-406 · Zbl 1242.90122
[11] Eichfelder, G.; Jahn, J., Set-semidefinite optimization, J. Convex Anal., 15, 767-801 (2008) · Zbl 1172.90013
[12] Eichfelder, G.; Jahn, J., Foundations of set-semidefinite optimization, (Pardalos, P.; Rassias, T. M.; Khan, A. A., Nonlinear Analysis and Variational Problems (2009), Springer), 259-284, Chapter 18 · Zbl 1181.90213
[13] G. Eichfelder, J. Povh, On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets, Faculty of Information Studies, Slovenia, June 2011 (manuscript) Available at: http://www.optimization-online.org/DB_HTML/2011/07/3084.html; G. Eichfelder, J. Povh, On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets, Faculty of Information Studies, Slovenia, June 2011 (manuscript) Available at: http://www.optimization-online.org/DB_HTML/2011/07/3084.html · Zbl 1298.90064
[14] Hiriart-Urruty, J. B.; Seeger, A., A variational approach to copositive matrices, SIAM Rev., 52, 4, 593-629 (2010) · Zbl 1207.15037
[15] Linderoth, J., A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs, Math. Program., 103, 2, Ser. B, 251-282 (2005) · Zbl 1099.90039
[16] Maxfield, J. E.; Minc, H., On the matrix equation \(X^\prime X = A\), Proc. Edinb. Math. Soc. (2), 13, 125-129 (1962/1963) · Zbl 0112.25101
[17] P. Parrilo, Structured semidefinite programs and semi-algebraic geometry methods in robustness and optimization, Ph.D. Thesis, California Institute of Technology, 2000.; P. Parrilo, Structured semidefinite programs and semi-algebraic geometry methods in robustness and optimization, Ph.D. Thesis, California Institute of Technology, 2000.
[18] J. Peña, J.C. Vera, L.F. Zuluaga, Positive polynomials on unbounded equality-constrained domains, Carnegie Mellon University, Pittsburgh, PA, April 2011 (manuscript) Available at: http://www.optimization-online.org/DB_HTML/2011/05/3047.html; J. Peña, J.C. Vera, L.F. Zuluaga, Positive polynomials on unbounded equality-constrained domains, Carnegie Mellon University, Pittsburgh, PA, April 2011 (manuscript) Available at: http://www.optimization-online.org/DB_HTML/2011/05/3047.html
[19] Sturm, J. F.; Zhang, S., On cones of nonnegative quadratic functions, Math. Oper. Res., 28, 2, 246-267 (2003) · Zbl 1082.90086
[20] Zuluaga, L. F.; Vera, J.; Peña, J., LMI approximations for cones of positive semidefinite forms, SIAM J. Optim., 16, 4, 1076-1091 (2006), (electronic) · Zbl 1131.90040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.