A gentle, geometric introduction to copositive optimization. (English) Zbl 1327.90162
Author’s abstract: This paper illustrates the fundamental connection between nonconvex quadratic optimization and copositive optimization – a connection that allows the reformulation of nonconvex quadratic problems as convex ones in a unified way. We focus on examples having just a few variables or a few constraints for which the quadratic problem can be formulated as a copositive-style problem, which itself can be recast in terms of linear, second-order-cone, and semidefinite optimization. A particular highlight is the role played by the geometry of the feasible set.
Reviewer: Stephan Dempe (Freiberg)
MSC:
| 90C20 | Quadratic programming |
| 90C22 | Semidefinite programming |
| 90C25 | Convex programming |
| 90C30 | Nonlinear programming |
Keywords:
global optimum of nonconvex optimization problems; copositive optimization; valid cuts; nonconvex optimization; semidefinite optimizationReferences:
| [1] | Anstreicher, K.M., Burer, S.: Computable representations for convex hulls of low-dimensional quadratic forms. Math. Program. Ser. B 124, 33-43 (2010) · Zbl 1198.90311 · doi:10.1007/s10107-010-0355-9 |
| [2] | 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 · doi:10.1007/s10107-011-0462-2 |
| [3] | Berman, A., Shaked-Monderer, N.: Completely Positive Matrices. World Scientific, London (2003) · Zbl 1030.15022 · doi:10.1142/5273 |
| [4] | Bienstock, D.: A note on polynomial solvability of the cdt problem. Preprint, Department of Industrial Engineering and Operations Research, Columbia University, New York, NY. Revised 2014. Submitted (2013) · Zbl 1382.90083 |
| [5] | Bienstock D., Michalka A.: Polynomial solvability of variants of the trust-region subproblem. In: Proceedings of the 25th ACM-SIAM symposium on discrete algorithms (SODA 2014), pp. 380-390, (2014) · Zbl 1334.90130 |
| [6] | Bomze, I., Schachinger, W., Uchida, G.: Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization. J. Glob. Optim. 52, 423-445 (2012) · Zbl 1268.90051 · doi:10.1007/s10898-011-9749-3 |
| [7] | Bomze, I.M.: Copositive optimization-recent developments and applications. Eur. J. Oper. Res. 216(3), 509-520 (2012) · Zbl 1262.90129 · doi:10.1016/j.ejor.2011.04.026 |
| [8] | Bomze, I.M., Dür, M., Teo, C.-P.: Copositive optimization. Optima 89, 2-8 (2012) |
| [9] | Burer, S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math Program 120, 479-495 (2009) · Zbl 1180.90234 · doi:10.1007/s10107-008-0223-z |
| [10] | Burer S.: Copositive programming. In: Anjos, M., Lasserre, J. (eds.) Handbook of Semidefinite, Cone and Polynomial Optimization: Theory, Algorithms, Software and Applications, International Series in Operational Research and Management Science, pp. 201-218. Springer, New York (2011) · Zbl 1334.90098 |
| [11] | Burer, S., Anstreicher, K.M.: Second-order-cone constraints for extended trust-region subproblems. SIAM J. Optim. 23(1), 432-451 (2013) · Zbl 1298.90062 · doi:10.1137/110826862 |
| [12] | Burer S., Yang B.: The trust region subproblem with non-intersecting linear constraints. Manuscript, Department of Management Sciences, University of Iowa, Iowa City, IA, USA, February 2013. Math. Program. Ser. A 149, 253-264 (2015) · Zbl 1308.90121 |
| [13] | Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-Region Methods. MPS/SIAM Series on Optimization. SIAM, Philadelphia (2000) · Zbl 0958.65071 · doi:10.1137/1.9780898719857 |
| [14] | Dür, M.; Diehl, M. (ed.); Glineur, F. (ed.); Jarlebring, E. (ed.); Michiels, W. (ed.), Copositive programming—a survey, 3-20 (2010), New York · doi:10.1007/978-3-642-12598-0_1 |
| [15] | Eichfelder, G., Jahn, J.: Set-semidefinite optimization. J. Convex Anal. 15, 767-801 (2008) · Zbl 1172.90013 |
| [16] | Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, vol. 2. Springer, New York (1988) · Zbl 0634.05001 |
| [17] | Hiriart-Urruty, J.B., Seeger, A.: A variational approach to copositive matrices. SIAM Rev. 52(4), 593-629 (2010) · Zbl 1207.15037 · doi:10.1137/090750391 |
| [18] | Jeyakumar, V., Li, G.: Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization. Math. Program. (2013). doi:10.1007/s10107-013-0716-2 · Zbl 1297.90105 |
| [19] | Laurent, M.; Putinar, M. (ed.); Sullivant, S. (ed.), Sums of squares, moment matrices and optimization over polynomials, 157-270 (2009), New York · Zbl 1163.13021 · doi:10.1007/978-0-387-09686-5_7 |
| [20] | Maxfield, J.E., Minc, H.: On the matrix equation \[X^{\prime } X=A\] X′X=A. Proc. Edinburgh Math. Soc. 2(13), 125-129 (1962/1963) · Zbl 0112.25101 |
| [21] | McCormick, G.P.: Computability of global solutions to factorable nonconvex programs. I. Convex underestimating problems. Math. Program. 10(2), 147-175 (1976) · Zbl 0349.90100 · doi:10.1007/BF01580665 |
| [22] | Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3(3), 411-430 (1990) · Zbl 0712.90050 · doi:10.1137/0403036 |
| [23] | Sturm, J.F., Zhang, S.: On cones of nonnegative quadratic functions. Math. Oper. Res. 28(2), 246-267 (2003) · Zbl 1082.90086 · doi:10.1287/moor.28.2.246.14485 |
| [24] | Yang, B., Burer, S.: A two-variable analysis of the two-trust-region subproblem. Manuscript, Department of Management Sciences, University of Iowa, Iowa City, IA, USA, November 2013. Revised October (2014) · Zbl 1172.90013 |
| [25] | Ye, Y., Zhang, S.: New results on quadratic minimization. SIAM J. Optim. 14(1), 245-267 (2003). (electronic) · Zbl 1043.90064 · doi:10.1137/S105262340139001X |
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.
