TY - JOUR
T1 - On the complexity of testing attainment of the optimal value in nonlinear optimization
AU - Ahmadi, Amir Ali
AU - Zhang, Jeffrey
N1 - Funding Information:
We are grateful to Georgina Hall and two anonymous referees for their careful reading of this manuscript and very constructive feedback. We also thank Etienne de Klerk for offering a simplification of the construction in the proof of Theorem 2.1.
Funding Information:
This work was partially supported by the DARPA Young Faculty Award, the CAREER Award of the NSF, the Innovation Award of the School of Engineering and Applied Sciences at Princeton University, the MURI award of the AFOSR, the Google Faculty Award, and the Sloan Fellowship.
Publisher Copyright:
© 2019, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.
PY - 2020/11/1
Y1 - 2020/11/1
N2 - 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.
AB - 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.
KW - Archimedean quadratic modules
KW - Coercive polynomials
KW - Computational complexity
KW - Existence of solutions in mathematical programs
KW - Frank–Wolfe type theorems
KW - Semidefinite programming
UR - http://www.scopus.com/inward/record.url?scp=85068829886&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85068829886&partnerID=8YFLogxK
U2 - 10.1007/s10107-019-01411-1
DO - 10.1007/s10107-019-01411-1
M3 - Article
AN - SCOPUS:85068829886
SN - 0025-5610
VL - 184
SP - 221
EP - 241
JO - Mathematical Programming
JF - Mathematical Programming
IS - 1-2
ER -