A fresh CP look at mixed-binary QPs: new formulations and relaxations. (English) Zbl 1386.90097
Summary: Triggered by Burer’s seminal characterization from 2009, many copositive 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 continues this approach, proposing new reformulations and relaxations. Moreover, we provide a thorough comparison of the respective duals and establish a monotonicity relation among their duality gaps. We also identify sufficient conditions for strong duality/zero duality gap in some of these formulations and generalize some of our observations to general conic problems.
MSC:
| 90C20 | Quadratic programming |
| 90C26 | Nonconvex programming, global optimization |
| 90C30 | Nonlinear programming |
Keywords:
copositivity; completely positive; conic optimization; quadratic optimization; reformulations; nonlinear optimization; nonconvex optimizationReferences:
| [1] | Arima, N., Kim, S., Kojima, M.: Simplified copositive and Lagrangian relaxations for linearly constrained quadratic optimization problems in continuous and binary variables. Pac. J. Optim. 10, 437-451 (2014) · Zbl 1327.90161 |
| [2] | Berman, A.: Cones, matrices and mathematical programming. In: Lecture Notes in Economics and Mathematical Systems. Vol. 79. Springer Verlag (1973) · Zbl 0256.90002 |
| [3] | Berman, A., Shaked-Monderer, N.: Completely Positive Matrices. World Scientific Publication, River Edge, NJ (2003) · Zbl 1030.15022 · doi:10.1142/5273 |
| [4] | Bomze, I.M.: Copositive optimization—recent developments and applications. Eur. J. Oper. Res. 216, 509-520 (2012) · Zbl 1262.90129 · doi:10.1016/j.ejor.2011.04.026 |
| [5] | Bomze, I.M.: Copositive relaxation beats Lagrangian dual bounds in quadratically and linearly constrained QPs. SIAM J. Optim. 25, 1249-1275 (2015) · Zbl 1317.90224 · doi:10.1137/140987997 |
| [6] | Bomze, I.M., 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) · Zbl 0970.90057 · doi:10.1023/A:1026583532263 |
| [7] | Bomze, I.M., Jarre, F.: A note on Burers copositive representation of mixed-binary QPs. Optim. Lett. 4, 465-472 (2010) · Zbl 1200.90134 · doi:10.1007/s11590-010-0174-1 |
| [8] | Bomze, I.M., Schachinger, W., Ullrich, R.: New lower bounds and asymptotics for the cp-rank. SIAM J. Matrix Anal. Appl. 36(1), 20-37 (2015) · Zbl 1326.15050 · doi:10.1137/140973207 |
| [9] | Bomze, I.M., 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 |
| [10] | Burer, S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120(2), 479-495 (2009) · Zbl 1180.90234 · doi:10.1007/s10107-008-0223-z |
| [11] | Burer, S.: Optimizing a polyhedral-semidefinite relaxation of completely positive programs. Math. Program. Comput. 2(1), 1-19 (2010) · Zbl 1190.90135 · doi:10.1007/s12532-010-0010-8 |
| [12] | Burer, S.; Anjos, MF (ed.); Lasserre, JB (ed.), Copositive programming, 201-218 (2012), New York · Zbl 1334.90098 · doi:10.1007/978-1-4614-0769-0_8 |
| [13] | Burer, S.: A gentle, geometric introduction to copositive optimization. Math. Program. 151, 89-116 (2015) · Zbl 1327.90162 · doi:10.1007/s10107-015-0888-z |
| [14] | Dickinson, P.J.C.: The copositive cone, the completely positive cone and their generalisations. Ph.D thesis, University of Groningen (2013) · Zbl 1326.15050 |
| [15] | Dickinson, P.J.C., Gijben, L.: On the computational complexity of membership problems for the completely positive cone and its dual. Comput. Optim. Appl. 57(2), 403-415 (2014) · Zbl 1330.90103 · doi:10.1007/s10589-013-9594-z |
| [16] | Dür, M.; Diehl, M. (ed.); Glineur, F. (ed.); Jarlebring, E. (ed.); Michiels, W. (ed.), Copositive programming-a survey, 3-20 (2010), Berlin · doi:10.1007/978-3-642-12598-0_1 |
| [17] | Gilbert, J.R., Heath, M.T.: Computing a sparse basis for the null space. SIAM J. Algebraic Discrete Methods 8(3), 446-459 (1987) · Zbl 0635.65037 · doi:10.1137/0608037 |
| [18] | Murty, K.G., Kabadi, S.N.: Some NP-complete problems in quadratic and nonlinear programming. Math. Program. 39(2), 117-129 (1987) · Zbl 0637.90078 · doi:10.1007/BF02592948 |
| [19] | Pataki, G.; Wolkowicz, H. (ed.); Saigal, R. (ed.); Vandenberghe, L. (ed.), The geometry of semidefinite programming, 29-65 (2000), Berlin · Zbl 0957.90531 · doi:10.1007/978-1-4615-4381-7_3 |
| [20] | Pataki, G.: On the closedness of the linear image of a closed convex cone. Math. Oper. Res. 32(2), 395-412 (2007) · Zbl 1341.90146 · doi:10.1287/moor.1060.0242 |
| [21] | Shaked-Monderer, N., Berman, A., Bomze, I.M., Jarre, F., Schachinger, W.: New results on the cp rank and related properties of co(mpletely )positive matrices. Linear Multilinear Algebra 63(2), 384-396 (2015) · Zbl 1310.15064 · doi:10.1080/03081087.2013.869591 |
| [22] | Shor, N.Z.: Quadratic optimization problems. Izv. Akad. Nauk SSSR Tekhn. Kibernet. 222(1), 128-139 (1987) · Zbl 0655.90055 |
| [23] | Trefethen, L.N., Bau III, D.: Numerical Linear Algebra, vol. 50. SIAM, Philadelphia (1997) · Zbl 0874.65013 · doi:10.1137/1.9780898719574 |
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.
