On the complexity of testing attainment of the optimal value in nonlinear optimization. (English) Zbl 1451.90176
Summary: We prove that unless P = NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can test whether the optimal value of a nonlinear optimization problem where the objective and constraints are given by low-degree polynomials is attained. If the degrees of these polynomials are fixed, our results along with previously-known “Frank-Wolfe type” theorems imply that exactly one of two cases can occur: either the optimal value is attained on every instance, or it is strongly NP-hard to distinguish attainment from non-attainment. We also show that testing for some well-known sufficient conditions for attainment of the optimal value, such as coercivity of the objective function and closedness and boundedness of the feasible set, is strongly NP-hard. As a byproduct, our proofs imply that testing the Archimedean property of a quadratic module is strongly NP-hard, a property that is of independent interest to the convergence of the Lasserre hierarchy. Finally, we give semidefinite programming (SDP)-based sufficient conditions for attainment of the optimal value, in particular a new characterization of coercive polynomials that lends itself to an SDP hierarchy.
MSC:
| 90C60 | Abstract computational complexity for mathematical programming problems |
| 90C30 | Nonlinear programming |
Keywords:
existence of solutions in mathematical programs; Frank-Wolfe-type theorems; coercive polynomials; computational complexity; semidefinite programming; Archimedean quadratic modulesReferences:
| [1] | Ahmadi, AA; Hall, G., DC decomposition of nonconvex polynomials with algebraic techniques, Math. Program., 169, 69-94 (2015) · Zbl 1390.90418 |
| [2] | Ahmadi, AA; Olshevsky, A.; Parrilo, PA; Tsitsiklis, JN, NP-hardness of deciding convexity of quartic polynomials and related problems, Math. Program., 137, 1-2, 453-476 (2013) · Zbl 1274.90516 |
| [3] | Andronov, V.; Belousov, E.; Shironin, V., On solvability of the problem of polynomial programming, Izvestija Akadem. Nauk SSSR Tekhnicheskaja Kibernetika, 4, 194-197 (1982) · Zbl 0531.90078 |
| [4] | Bajbar, T., Behrends, S.: How fast do coercive polynomials grow? Technical report, Instituts für Numerische und Angewandte Mathematik, Georg-August-Universität Göttingen (2017) |
| [5] | Bajbar, T.; Stein, O., Coercive polynomials and their Newton polytopes, SIAM J. Optim., 25, 3, 1542-1570 (2015) · Zbl 1322.90092 |
| [6] | Basu, S.; Roy, M-F, Bounding the radii of balls meeting every connected component of semi-algebraic sets, J. Symb. Comput., 45, 12, 1270-1279 (2010) · Zbl 1200.14107 |
| [7] | Belousov, EG; Klatte, D., A Frank-Wolfe type theorem for convex polynomial programs, Comput. Optim. Appl., 22, 1, 37-48 (2002) · Zbl 1029.90054 |
| [8] | Bertsekas, DP, Nonlinear Programming (1999), Belmont: Athena Scientific, Belmont · Zbl 1015.90077 |
| [9] | Bertsekas, DP; Tseng, P., Set intersection theorems and existence of optimal solutions, Math. Program., 110, 2, 287-314 (2007) · Zbl 1133.90009 |
| [10] | Blekherman, G.; Parrilo, PA; Thomas, RR, Semidefinite Optimization and Convex Algebraic Geometry (2012), Philadelphia: SIAM, Philadelphia |
| [11] | Frank, M.; Wolfe, P., An algorithm for quadratic programming, Naval Res. Logist. (NRL), 3, 1-2, 95-110 (1956) |
| [12] | Garey, MR; Johnson, DS, Computers and Intractability (2002), New York: WH Freeman, New York |
| [13] | Gorin, EA, Asymptotic properties of polynomials and algebraic functions of several variables, Russ. Math. Surv., 16, 1, 93-119 (1961) · Zbl 0102.25401 |
| [14] | Greuet, A., Safey El Din, M.: Deciding reachability of the infimum of a multivariate polynomial. In: Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation, pp. 131-138. ACM (2011) · Zbl 1323.65074 |
| [15] | Greuet, A.; Safey El Din, M., Probabilistic algorithm for polynomial optimization over a real algebraic set, SIAM J. Optim., 24, 3, 1313-1343 (2014) · Zbl 1327.90232 |
| [16] | Jeyakumar, V.; Lasserre, JB; Li, G., On polynomial optimization over non-compact semi-algebraic sets, J. Optim. Theory Appl., 163, 3, 707-718 (2014) · Zbl 1302.90208 |
| [17] | Krivine, J-L, Anneaux préordonnés, Journal d’analyse mathématique, 12, 1, 307-326 (1964) · Zbl 0134.03902 |
| [18] | Lasserre, JB, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11, 3, 796-817 (2001) · Zbl 1010.90061 |
| [19] | Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. In: Emerging Applications of Algebraic Geometry, pp. 157-270. Springer (2009) · Zbl 1163.13021 |
| [20] | Lombardi, H., Perrucci, D., Roy, M.-F.: An elementary recursive bound for effective Positivstellensatz and Hilbert’s 17th problem (2014). arXiv:1404.2338 · Zbl 1465.14001 |
| [21] | Luo, Z-Q; Zhang, S., On extensions of the Frank-Wolfe theorems, Comput. Optim. Appl., 13, 1-3, 87-110 (1999) · Zbl 1040.90536 |
| [22] | Marshall, M., Optimization of polynomial functions, Can. Math. Bull., 46, 4, 575-587 (2003) · Zbl 1063.14071 |
| [23] | Nie, J., Optimality conditions and finite convergence of the Lasserre hierarchy, Math. Program., 146, 1-2, 97-121 (2014) · Zbl 1300.65041 |
| [24] | Nie, J.; Demmel, J.; Sturmfels, B., Minimizing polynomials via sum of squares over the gradient ideal, Math. Program., 106, 3, 587-606 (2006) · Zbl 1134.90032 |
| [25] | Parrilo, PA, Semidefinite programming relaxations for semialgebraic problems, Math. Program., 96, 2, 293-320 (2003) · Zbl 1043.14018 |
| [26] | Porkolab, L.; Khachiyan, L., On the complexity of semidefinite programs, J. Glob. Optim., 10, 4, 351-365 (1997) · Zbl 0881.90127 |
| [27] | Prestel, A.; Delzell, CN, Positive Polynomials: From Hilbert’s 17th Problem to Real Algebra. Springer Monographs in Mathematics (2001), Berlin: Springer, Berlin · Zbl 0987.13016 |
| [28] | Putinar, M., Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J., 42, 3, 969-984 (1993) · Zbl 0796.12002 |
| [29] | Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, pp. 216-226. ACM (1978) · Zbl 1282.68143 |
| [30] | Seidenberg, A., A new decision method for elementary algebra, Ann. Math., 60, 365-374 (1954) · Zbl 0056.01804 |
| [31] | Stengle, G., A Nullstellensatz and a Positivstellensatz in semialgebraic geometry, Math. Ann., 207, 2, 87-97 (1974) · Zbl 0253.14001 |
| [32] | Tarski, A.: A decision method for elementary algebra and geometry. In: Quantifier Elimination and Cylindrical Algebraic Decomposition, pp. 24-84. Springer (1998) · Zbl 0900.03045 |
| [33] | Wagner, S.: Archimedean quadratic modules: a decision problem for real multivariate polynomials. Ph.D. thesis, University of Konstanz (2009) |
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.
