On the complexity of testing attainment of the optimal value in nonlinear optimization

  • PDF / 384,415 Bytes
  • 21 Pages / 439.37 x 666.142 pts Page_size
  • 93 Downloads / 157 Views

DOWNLOAD

REPORT


Series A

On the complexity of testing attainment of the optimal value in nonlinear optimization Amir Ali Ahmadi1

· Jeffrey Zhang1

Received: 20 March 2018 / Accepted: 17 June 2019 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2019

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 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 Mathematics Subject Classification 90C60 · 90C30

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.

B

Amir Ali Ahmadi [email protected] Jeffrey Zhang [email protected]

1

Department of Operations Research and Financial Engineering, Princeton University, Princeton, USA

123

A. A. Ahmadi, J. Zhang

1 Introduction Consider an optimization problem of the form inf

f (x)

subject to

x ∈ ,

x

(1)

where f : Rn → R and  ⊆ Rn . In this paper, we are interested in the complexity of checking whether we can replace the “inf” with a “min”. More precisely, suppose the optimal value f ∗ of this problem is finite, i.e., the problem is feasible and bounded below. We would like to test if the optimal value is attained, i.e., whether there exists a point x ∗ ∈  such that f (x ∗ ) ≤ f (x) ∀x ∈ , or equivalently, such that f ∗ = f (x ∗ ). Such a point x ∗ will be termed an optimal solution. Existence of optimal solutions is a fundamental question in optimization and its study has a long history, dating back to the nineteenth century with the extreme value theorem of Bolzano and Weierstrass. While the problem has been researched in depth from an analytical