  


On the Complexity of Testing Attainment of the Optimal Value in Nonlinear Optimization
Amir Ali Ahmadi (a_a_aprinceton.edu) Abstract: We prove that unless P=NP, there exists no polynomial time (or even pseudopolynomial time) algorithm that can test whether the optimal value of a nonlinear optimization problem where the objective and constraints are given by lowdegree polynomials is attained. If the degrees of these polynomials are fixed, our results along with previouslyknown ``FrankWolfe type'' theorems imply that exactly one of two cases can occur: either the optimal value is attained on every instance, or it is strongly NPhard to distinguish attainment from nonattainment. We also show that testing for some wellknown 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 NPhard. As a byproduct, our proofs imply that testing the Archimedean property of a quadratic module is strongly NPhard, 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, FrankWolfe 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 (Semidefinite Programming ) Citation: Download: [PDF] Entry Submitted: 03/20/2018 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  