×

zbMATH — the first resource for mathematics

Completely positive reformulations for polynomial optimization. (English) Zbl 1328.90114
Summary: Polynomial optimization encompasses a very rich class of problems in which both the objective and constraints can be written in terms of polynomials on the decision variables. There is a well established body of research on quadratic polynomial optimization problems based on reformulations of the original problem as a conic program over the cone of completely positive matrices, or its conic dual, the cone of copositive matrices. As a result of this reformulation approach, novel solution schemes for quadratic polynomial optimization problems have been designed by drawing on conic programming tools, and the extensively studied cones of completely positive and of copositive matrices. In particular, this approach has been applied to solve key combinatorial optimization problems. Along this line of research, we consider polynomial optimization problems that are not necessarily quadratic. For this purpose, we use a natural extension of the cone of completely positive matrices; namely, the cone of completely positive tensors. We provide a general characterization of the class of polynomial optimization problems that can be formulated as a conic program over the cone of completely positive tensors. As a consequence of this characterization, it follows that recent related results for quadratic problems can be further strengthened and generalized to higher order polynomial optimization problems. Also, we show that the conditions underlying the characterization are conceptually the same, regardless of the degree of the polynomials defining the problem. To illustrate our results, we discuss in further detail special and relevant instances of polynomial optimization problems.

MSC:
90C26 Nonconvex programming, global optimization
90C20 Quadratic programming
Software:
QuadProgBB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Amaral, P; Bomze, IM; Júdice, J, Copositivity and constrained fractional quadratic problems, Math. Program., 146, 325-350, (2014) · Zbl 1312.90049
[2] Anjos, M., Lasserre, J.B. (eds.): Handbook on Semidefinite, Conic and Polynomial Optimization Handbook on Semidefinite, Conic and Polynomial Optimization, volume 166 of International Series in Operations Research & Management Science. Springer, Berlin (2012) · Zbl 1235.90002
[3] Arima, N., Kim, S., Kojima, M. A Quadratically Constrained Quadratic Optimization Model for Completely Positive Cone Programming. Technical Report B-468, Dept. of Math. and Comp. Sciences, Tokyo Institute of Technology. http://www.optimization-online.org/DB_FILE/2012/09/3600.pdf (2012) · Zbl 1304.90152
[4] Bai, L., Mitchell, J.E., Pang, J.: On QPCCs, QCQPs and Copositive Programs. Technical report, Rensselaer Polytechnic Institute. http://eaton.math.rpi.edu/faculty/Mitchell/papers/QCQP_QPCC.html (2012) · Zbl 1346.90624
[5] Bertsekas, D.P.: Non-linear Programming. Athena Scientific, Belmont, MA (1995) · Zbl 0935.90037
[6] Bertsimas, D; Popescu, I, On the relation between option and stock prices: an optimization approach, Oper. Res., 50, 358-374, (2002) · Zbl 1163.91382
[7] Bertsimas, D; Popescu, I, Optimal inequalities in probability theory: a convex optimization approach, SIAM J. Optim., 15, 780-804, (2005) · Zbl 1077.60020
[8] Blekherman, G., Parrilo, P., and Thomas, R. (eds): Semidefinite Optimization and Convex Algebraic Geometry, volume 13 of MOS-SIAM Series on Optimization. SIAM, Philadelphia (2012) · Zbl 1260.90006
[9] Bomze, I; Klerk, E, Solving standard quadratic optimization problems via semidefinite and copositive programming, J. Global Optim., 24, 163-185, (2002) · Zbl 1047.90038
[10] Bomze, I; Jarre, F, A note on burer’s copositive representation of mixed-binary qps, Optim. Lett., 4, 465-472, (2010) · Zbl 1200.90134
[11] Bomze, IM; Floudas, CA (ed.); Pardalos, PM (ed.), Copositive optimization, 561-564, (2009), Berlin
[12] Bomze, I.M.: Copositive Relaxation Beats Lagrangian Dual Bounds In Quadratically And Linearly Constrained QPs. Technical Report NI13064-POP, Isaac Newton Institute (2013) · Zbl 1151.65032
[13] Bomze, I.M.: Copositive-Based Approximations for Binary and Ternary Fractional Quadratic Optimization. Technical Report NI14043-POP, Isaac Newton Institute (2014)
[14] Bomze, IM; Dür, M; Klerk, E; Roos, C; Quist, AJ; Terlaky, T, On copositive programming and standard quadratic optimization problems, J. Glob. Optim., 18, 301-320, (2000) · Zbl 0970.90057
[15] Bomze, IM; Jarre, F; Rendl, F, Quadratic factorization heuristics for copositive programming, Math. Program. Comput., 3, 37-57, (2011) · Zbl 1219.90134
[16] Bundfuss, S.: Copositive Matrices, Copositive Programming, and Applications. Ph.D. thesis, TU Darmstadt (2009) · Zbl 1170.65047
[17] Bundfuss, S; Dür, M, An adaptive linear approximation algorithm for copositive programs, SIAM J. Optim., 20, 30-53, (2009) · Zbl 1187.90187
[18] Burer, S, On the copositive representation of binary and continuous nonconvex quadratic programs, Math. Program., 120, 479-495, (2009) · Zbl 1180.90234
[19] Burer, S; Dong, H, Representing quadratically constrained quadratic programs as generalized copositive programs, Oper. Res. Lett., 40, 203-206, (2012) · Zbl 1245.90080
[20] Burer, S., Kim, S., Kojima, M.: Faster, but weaker, relaxations for quadratically constrained quadratic programs. Comput. Optim. Appl. 59(1-2), 27-45 (2014) · Zbl 1303.90077
[21] Chen, J; Burer, S, Globally solving nonconvex quadratic programming problems via completely positive programming, Math. Program. Comput., 4, 33-52, (2012) · Zbl 1257.90065
[22] Klerk, E; Laurent, M; Parrilo, PA, A PTAS for the minimization of polynomials of fixed degree over the simplex, Theor. Comput. Sci., 361, 210-225, (2006) · Zbl 1115.90042
[23] Klerk, E; Pasechnik, D, Approximation of the stability number of a graph via copositive programming, SIAM J. Optim., 12, 875-892, (2002) · Zbl 1035.90058
[24] Dickinson, P.J., Eichfelder, G., Povh, J.: Erratum to: On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets [optim. letters, 2012]. Optim. Lett. 7(6), 1387-1397 (2013) · Zbl 1298.90063
[25] Doherty, AC; Parrilo, PA; Spedalieri, FM, An inequality for circle packings proved by semidefinite programming, Phys. Rev. A, 69, 022308, (2004)
[26] Dong, H, Symmetric tensor approximation hierarchies for the completely positive cone, SIAM J. Optim., 23, 1850-1866, (2013) · Zbl 1291.90129
[27] Dong, H; Anstreicher, K, Separating doubly nonnegative and completely positive matrices, Math. Program. Ser. A, 137, 131-153, (2013) · Zbl 1263.90064
[28] Dukanovic, I; Rendl, F, Copositive programming motivated bounds on the stability and the chromatic numbers, Math. Program., 121, 249-268, (2010) · Zbl 1194.90109
[29] Dür, M; Diehl, M (ed.); Glineur, F (ed.); Jarlebring, E (ed.); Michiels, W (ed.), Copositive programming-a survey, 3-20, (2010), Berlin
[30] Eichfelder, G; Povh, J, On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets, Optim. Lett., 6, 1-14, (2012)
[31] Genin, Y., Hachez, Y., Nesterov, Y., and Dooren, P. V.: Convex optimization over positive polynomials and filter design. In: Proceedings of UKACC Intenational Conference on Control (2000) · Zbl 1055.90058
[32] Gouveia, J; Parrilo, PA; Thomas, RR, Theta bodies for polynomial ideals, SIAM J. Optim., 20, 2097-2118, (2010) · Zbl 1213.90190
[33] Gvozdenović, N., Laurent, M.: Semidefinite bounds for the stability number of a graph via sums of squares of polynomials. Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science 3509, 136-151 (2005) · Zbl 1245.90080
[34] Gvozdenović, N; Laurent, M, The operator \(ψ \) for the chromatic number of a graph, SIAM J. Optim., 19, 572-591, (2008) · Zbl 1213.05080
[35] Kim, S., Kojima, M., Toh, K.: A Lagrangian-DDN Relaxation: A Fast Method for Computing Tight Lower Bounds for a Class of Quadratic Optimization Problems. Technical report. http://www.optimizationonlineorg/DBHTML/2013/10/4073.html (2013) · Zbl 1342.90123
[36] Lasserre, J, Global optimization problems with polynomials and the problem of moments, SIAM J. Optim., 11, 796-817, (2001) · Zbl 1010.90061
[37] Lasserre, J, Bounds on measures satisfying moment conditions, Ann. Appl. Probab., 12, 1114-1137, (2002) · Zbl 1073.90534
[38] Lasserre, JB, An explicit equivalent positive semidefinite program for nonlinear 0-1 programs, SIAM J. Optim., 12, 756-769, (2002) · Zbl 1007.90046
[39] Laurent, M, A comparison of the Sherali-Adams, lovász-schrijver, and Lasserre relaxations for 0-1 integer programming, Math. Oper. Res., 28, 470-496, (2003) · Zbl 1082.90084
[40] Laurent, M.: Lower bound for the number of iterations in semidefinite relaxations for the cut polytope. Math. Oper. Res. 28(4), 871-883 (2003b) · Zbl 1082.90085
[41] Laurent, M, Copositive vs. moment hierarchies for stable sets, Optima, 89, 8-10, (2012)
[42] Lovász, L, On the Shannon capacity of a graph, IEEE Trans. Inf. Theory, 25, 1-7, (1979) · Zbl 0395.94021
[43] Natarajan, K; Teo, CP; Zheng, Z, Mixed 0-1 linear programs under objective uncertainty: a completely positive representation, Oper. Res., 59, 713-728, (2011) · Zbl 1231.90304
[44] Nesterov, Y.: Structure of Non-negative Polynomials and Optimization Problems. Technical Report 9749, CORE (1997) · Zbl 1077.60020
[45] Nie, J, Sum of squares method for sensor network localization, Comput. Optim. Appl., 43, 151-179, (2009) · Zbl 1170.90510
[46] Papachristodoulou, A; Peet, MM; Lall, S, Analysis of polynomial systems with time delays via the sum of squares decomposition, IEEE Trans. Autom. Control, 54, 1058-1064, (2009) · Zbl 1367.93476
[47] Parrilo, P.: Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. Ph.D. thesis, Department of Control and Dynamical Systems, California Institute of Technology, Pasadena, CA (2000) · Zbl 1312.90049
[48] Parrilo, PA; Jadbabaie, A, Approximation of the joint spectral radius using sum of squares, Linear Algebra Appl., 428, 2385-2402, (2008) · Zbl 1151.65032
[49] Peña, J; Vera, J; Zuluaga, L, Computing the stability number of a graph via linear and semidefinite programming, SIAM J. Optim., 18, 87-105, (2007) · Zbl 1176.90611
[50] Pólya, G.: Üher positive Darstellung von Polynomen. Vierteljschr. Naturforsch. Ges. Zürich 73, 141-145. (also Collected Papers, vol. 2, 309-313, MIT Press, Cambridge, MA, 1974) (1928) · Zbl 0444.94009
[51] Povh, J; Rendl, F, A copositive programming approach to graph partitioning, SIAM J. Optim., 18, 223-241, (2007) · Zbl 1143.90025
[52] Povh, J; Rendl, F, Copositive and semidefinite relaxations of the quadratic assignment problem, Discret. Optim., 6, 231-241, (2009) · Zbl 1167.90597
[53] Reznick, B.: On Hilbert’s Construction of Positive Polynomials. Technical report, University of Illinois at Urbana-Champaign. www.math.uiuc.edu/reznick/paper53.pdf (2007) · Zbl 1163.91382
[54] Rockafellar, T.: Convex Analysis. Princeton University Press, Princeton (1970) · Zbl 0193.18401
[55] Rockafellar, T., Wets, R.: Variational Analysis. Springer, Berlin (1998) · Zbl 0888.49001
[56] Schmüdgen, K, The K-moment problem for compact semi-algebraic sets, Math. Ann., 289, 203-206, (1991) · Zbl 0744.44008
[57] Schrijver, A, A comparison of the delsarte and lovász bounds, IEEE Trans. Inf. Theory, 25, 425-429, (1979) · Zbl 0444.94009
[58] Schweighofer, M, An algorithmic approach to schmüdgen’s positivstellensatz, J. Pure Appl. Algebra, 166, 307-319, (2002) · Zbl 1015.14031
[59] Shor, N, Class of global minimum bounds of polynomial functions, Cybernetics, 23, 731-734, (1987) · Zbl 0648.90058
[60] Zuluaga, L., Vera, J., Peña, J.: LMI approximations for cones of positive semidefinite forms. SIAM J. Optim. 16, 1076-1091 (2006) · 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.