{
  "id": "1803.07683",
  "version": "v1",
  "published": "2018-03-20T22:54:29.000Z",
  "updated": "2018-03-20T22:54:29.000Z",
  "title": "On the Complexity of Testing Attainment of the Optimal Value in Nonlinear Optimization",
  "authors": [
    "Amir Ali Ahmadi",
    "Jeffrey Zhang"
  ],
  "comment": "18 pages",
  "categories": [
    "math.OC",
    "cs.CC",
    "math.AG",
    "math.NA"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-03-20T22:54:29.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "90C60",
      "90C30",
      "G.1.6"
    ],
    "keywords": [
      "optimal value",
      "testing attainment",
      "strongly np-hard",
      "complexity",
      "well-known sufficient conditions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}