×

Analysis of copositive optimization based linear programming bounds on standard quadratic optimization. (English) Zbl 1321.90096

Summary: The problem of minimizing a quadratic form over the unit simplex, referred to as a standard quadratic optimization problem, admits an exact reformulation as a linear optimization problem over the convex cone of completely positive matrices. This computationally intractable cone can be approximated in various ways from the inside and from the outside by two sequences of nested tractable convex cones of increasing accuracy. In this paper, we focus on the inner polyhedral approximations due to the second author [Optim. Methods Softw. 27, No. 1, 155–173 (2012; Zbl 1247.90215)] and the outer polyhedral approximations due to [E. de Klerk and D. V. Pasechnik, SIAM J. Optim. 12, No. 4, 875–892 (2002; Zbl 1035.90058)]. We investigate the sequences of upper and lower bounds on the optimal value of a standard quadratic optimization problem arising from these two hierarchies of inner and outer polyhedral approximations. We give complete algebraic descriptions of the sets of instances on which upper and lower bounds are exact at any given finite level of the hierarchy. We identify the structural properties of the sets of instances on which upper and lower bounds converge to the optimal value only in the limit. We present several geometric and topological properties of these sets. Our results shed light on the strengths and limitations of these inner and outer polyhedral approximations in the context of standard quadratic optimization.

MSC:

90C20 Quadratic programming
90C05 Linear programming
90C26 Nonconvex programming, global optimization

References:

[1] Berman, A., Shaked-Monderer, N.: Completely Positive Matrices. World Scientific, River Edge, NJ (2003) · Zbl 1030.15022
[2] Bomze, I.M.: On standard quadratic optimization problems. J. Global Optim. 13(4), 369-387 (1998) · Zbl 0916.90214 · doi:10.1023/A:1008369322970
[3] Bomze, I.M., de Klerk, E.: Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J. Global Optim. 24, 163-185 (2002) · Zbl 1047.90038 · doi:10.1023/A:1020209017701
[4] Bomze, I.M., Dür, M., de Klerk, E., Roos, C., Quist, A., Terlaky, T.: On copositive programming and standard quadratic optimization problems. J. Global Optim. 18(4), 301-320 (2000) · Zbl 0970.90057 · doi:10.1023/A:1026583532263
[5] Bomze, I.M., Dür, M., Teo, C.-P.: Copositive optimization. Optima 89, 2-8 (2012)
[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 · doi:10.1137/070711815
[7] 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
[8] de Klerk, E., Pasechnik, D.V.: 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
[9] Dickinson, P.J.C.: Geometry of the copositive and completely positive cones. J. Math. Anal. Appl. 380, 377-395 (2011) · Zbl 1229.90195 · doi:10.1016/j.jmaa.2011.03.005
[10] 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
[11] Dür, M., Still, G.: Interior points of the completely positive cone. Electr. J. Linear Algebra 17, 48-53 (2008) · Zbl 1151.15019
[12] Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3), 796-817 (2001) · Zbl 1010.90061 · doi:10.1137/S1052623400366802
[13] Lasserre, J.B.: 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
[14] Motzkin, T.S., Straus, E.G.: 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
[15] 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
[16] Parrilo, P.A.: Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. PhD thesis, California Institute of Technology, Pasadena, CA (2000) · Zbl 1247.90215
[17] Peña, J., Vera, J., Zuluaga, L.F.: 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
[18] Sponsel, J., Bundfuss, S., Dür, M.: An improved algorithm to test copositivity. J. Global Optim. 52, 537-551 (2012) · Zbl 1250.65061 · doi:10.1007/s10898-011-9766-2
[19] Vavasis, S.: Quadratic programming is in NP. Inf. Process. Lett. 36(2), 73-77 (1990) · Zbl 0719.90052 · doi:10.1016/0020-0190(90)90100-C
[20] Yıldırım, E.A.: 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.