Optimization Online


On the Complexity of Testing Attainment of the Optimal Value in Nonlinear Optimization

Amir Ali Ahmadi (a_a_a***at***princeton.edu)
Jeffrey Zhang (jeffz***at***princeton.edu)

Abstract: 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.

Keywords: Existence of solutions in mathematical programs, Frank-Wolfe type theorems, coercive polynomials, computational complexity, semidefinite programming, Archimedean quadratic modules

Category 1: Nonlinear Optimization

Category 2: Global Optimization (Theory )

Category 3: Linear, Cone and Semidefinite Programming (Semi-definite Programming )


Download: [PDF]

Entry Submitted: 03/20/2018
Entry Accepted: 03/20/2018
Entry Last Modified: 04/29/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society