On standard quadratic programs with exact and inexact doubly nonnegative relaxations. (English) Zbl 1491.90111
Summary: The problem of minimizing a (nonconvex) quadratic form over the unit simplex, referred to as a standard quadratic program, admits an exact convex conic formulation over the computationally intractable cone of completely positive matrices. Replacing the intractable cone in this formulation by the larger but tractable cone of doubly nonnegative matrices, i.e., the cone of positive semidefinite and componentwise nonnegative matrices, one obtains the so-called doubly nonnegative relaxation, whose optimal value yields a lower bound on that of the original problem. We present a full algebraic characterization of the set of instances of standard quadratic programs that admit an exact doubly nonnegative relaxation. This characterization yields an algorithmic recipe for constructing such an instance. In addition, we explicitly identify three families of instances for which the doubly nonnegative relaxation is exact. We establish several relations between the so-called convexity graph of an instance and the tightness of the doubly nonnegative relaxation. We also provide an algebraic characterization of the set of instances for which the doubly nonnegative relaxation has a positive gap and show how to construct such an instance using this characterization.
MSC:
| 90C20 | Quadratic programming |
| 90C22 | Semidefinite programming |
| 90C26 | Nonconvex programming, global optimization |
Keywords:
standard quadratic programs; copositive cone; completely positive cone; doubly nonnegative relaxationReferences:
| [1] | Afonin, A., Hildebrand, R., Dickinson, P.J.C.: The extreme rays of the \(6 \times 6\) copositive cone. J. Glob. Optim. (2020). doi:10.1007/s10898-020-00930-y. (To appear) · Zbl 1465.90066 |
| [2] | Baumert, L., Extreme copositive quadratic forms, Pac. J. Math., 19, 2, 197-204 (1966) · Zbl 0145.25501 · doi:10.2140/pjm.1966.19.197 |
| [3] | Bomze, IM, On standard quadratic optimization problems, J. Global Optim., 13, 4, 369-387 (1998) · Zbl 0916.90214 · doi:10.1023/A:1008369322970 |
| [4] | Bomze, IM, Regularity versus degeneracy in dynamics, games, and optimization: a unified approach to different aspects, SIAM Rev., 44, 394-414 (2002) · Zbl 1021.91007 · doi:10.1137/S00361445003756 |
| [5] | Bomze, IM; De Klerk, E., Solving standard quadratic optimization problems via linear, semidefinite and copositive programming, J. Glob. Optim., 24, 2, 163-185 (2002) · Zbl 1047.90038 · doi:10.1023/A:1020209017701 |
| [6] | Bomze, IM; Dür, M.; de Klerk, E.; Roos, C.; Quist, AJ; Terlaky, T., On copositive programming and standard quadratic optimization problems, J. Glob. Optim., 18, 4, 301-320 (2000) · Zbl 0970.90057 · doi:10.1023/A:1026583532263 |
| [7] | Bundfuss, S.; Dür, M., An adaptive linear approximation algorithm for copositive programs, SIAM J. Optim., 20, 1, 30-53 (2009) · Zbl 1187.90187 · doi:10.1137/070711815 |
| [8] | Chudnovsky, M.; Cornuéjols, G.; Liu, X.; Seymour, PD; Vuskovic, K., Recognizing Berge graphs, Combinatorica, 25, 2, 143-186 (2005) · Zbl 1089.05027 · doi:10.1007/s00493-005-0012-8 |
| [9] | Chudnovsky, M.; Robertson, N.; Seymour, P.; Thomas, R., The strong perfect graph theorem, Ann. Math., 164, 51-229 (2006) · Zbl 1112.05042 · doi:10.4007/annals.2006.164.51 |
| [10] | De Klerk, E.; Pasechnik, DV, Approximation of the stability number of a graph via copositive programming, SIAM J. Optim., 12, 4, 875-892 (2002) · Zbl 1035.90058 · doi:10.1137/S1052623401383248 |
| [11] | Diananda, PH, On non-negative forms in real variables some or all of which are non-negative, Math. Proc. Cambridge Philos. Soc., 58, 1, 17-25 (1962) · Zbl 0108.04803 · doi:10.1017/S0305004100036185 |
| [12] | Dickinson, PJ; Dür, M.; Gijben, L.; Hildebrand, R., Irreducible elements of the copositive cone, Linear Algebra Appl., 439, 6, 1605-1626 (2013) · Zbl 1305.15074 · doi:10.1016/j.laa.2012.10.014 |
| [13] | Dickinson, PJC; 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 |
| [14] | Gibbons, LE; Hearn, DW; Pardalos, PM; Ramana, MV, Continuous characterizations of the maximum clique problem, Math. Oper. Res., 22, 3, 754-768 (1997) · Zbl 0883.90098 · doi:10.1287/moor.22.3.754 |
| [15] | Gouveia, J.; Pong, TK; Saee, M., Inner approximating the completely positive cone via the cone of scaled diagonally dominant matrices, J. Glob. Optim., 76, 383-405 (2020) · Zbl 1435.90114 · doi:10.1007/s10898-019-00861-3 |
| [16] | Grötschel, M.; Lovász, L.; Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1, 2, 169-197 (1981) · Zbl 0492.90056 · doi:10.1007/BF02579273 |
| [17] | Hall, M.; Newman, M., Copositive and completely positive quadratic forms, Math. Proc. Cambridge Philos. Soc., 59, 2, 329-339 (1963) · Zbl 0124.25302 · doi:10.1017/S0305004100036951 |
| [18] | Hildebrand, R., The extreme rays of the \(5 \times 5\) copositive cone, Linear Algebra Appl., 437, 7, 1538-1547 (2012) · Zbl 1259.15045 · doi:10.1016/j.laa.2012.04.017 |
| [19] | Jiaquan, L.; Tiantai, S.; Dingzhu, D., On the necessary and sufficient condition of the local optimal solution of quadratic programming, Chin. Ann. Math. Ser. B, 3, 5, 625-630 (1982) · Zbl 0514.90068 |
| [20] | Kim, S.; Kojima, M.; Toh, KC, Doubly nonnegative relaxations are equivalent to completely positive reformulations of quadratic optimization problems with block-clique graph structures, J. Glob. Optim., 77, 513-541 (2020) · Zbl 1444.90090 · doi:10.1007/s10898-020-00879-y |
| [21] | Kingman, JFC, A mathematical problem in population genetics, Proc. Cambridge Philos. Soc., 57, 3, 574 (1961) · Zbl 0104.38202 · doi:10.1017/S0305004100035635 |
| [22] | Lasserre, JB, New approximations for the cone of copositive matrices and its dual, Math. Program., 144, 1-2, 265-276 (2014) · Zbl 1292.15034 · doi:10.1007/s10107-013-0632-5 |
| [23] | Lovász, L., On the Shannon capacity of a graph, IEEE Trans. Inf. Theory, 25, 1, 1-7 (1979) · Zbl 0395.94021 · doi:10.1109/TIT.1979.1055985 |
| [24] | Majthay, A., Optimality conditions for quadratic programming, Math. Program., 1, 1, 359-365 (1971) · Zbl 0246.90038 · doi:10.1007/BF01584097 |
| [25] | Markowitz, H., Portfolio selection, J. Financ., 7, 1, 77-91 (1952) |
| [26] | Moon, JW; Moser, L., On cliques in graphs, Isr. J. Math., 3, 1, 23-28 (1965) · Zbl 0144.23205 · doi:10.1007/BF02760024 |
| [27] | Motzkin, TS; Straus, EG, Maxima for graphs and a new proof of a theorem of Turán, Can. J. Math., 17, 533-540 (1965) · Zbl 0129.39902 · doi:10.4153/CJM-1965-053-6 |
| [28] | Murty, KG; Kabadi, SN, Some NP-complete problems in quadratic and nonlinear programming, Math. Program., 39, 2, 117-129 (1987) · Zbl 0637.90078 · doi:10.1007/BF02592948 |
| [29] | Parrilo, P.A.: Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph.D. thesis, California Institute of Technology (2000) |
| [30] | Pena, J.; Vera, J.; Zuluaga, LF, Computing the stability number of a graph via linear and semidefinite programming, SIAM J. Optim., 18, 1, 87-105 (2007) · Zbl 1176.90611 · doi:10.1137/05064401X |
| [31] | Rosgen, B.; Stewart, L., Complexity results on graphs with few cliques, Discret. Math. Theor. Comput. Sci., 9, 1, 1 (2007) · Zbl 1153.05333 |
| [32] | Sağol, G.; Yıldırım, EA, Analysis of copositive optimization based linear programming bounds on standard quadratic optimization, J. Glob. Optim., 63, 1, 37-59 (2015) · Zbl 1321.90096 · doi:10.1007/s10898-015-0269-4 |
| [33] | Schrijver, A., A comparison of the Delsarte and Lovász bounds, IEEE Trans. Inf. Theory, 25, 4, 425-429 (1979) · Zbl 0444.94009 · doi:10.1109/TIT.1979.1056072 |
| [34] | Shaked-Monderer, N., SPN graphs: when copositive = SPN, Linear Algebra Appl., 509, 82-113 (2016) · Zbl 1345.05111 · doi:10.1016/j.laa.2016.07.018 |
| [35] | Shaked-Monderer, N.; Berman, A.; Dür, M.; Kannan, MR, SPN completable graphs, Linear Algebra Appl., 498, 58-73 (2016) · Zbl 1334.15069 · doi:10.1016/j.laa.2014.10.021 |
| [36] | Yıldırım, EA, On the accuracy of uniform polyhedral approximations of the copositive cone, Optim. Methods Softw., 27, 1, 155-173 (2012) · Zbl 1247.90215 · doi:10.1080/10556788.2010.540014 |
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.
