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

Amir Ali Ahmadi, Jeffrey Zhang

Research output: Contribution to journalArticle

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.

Original languageEnglish (US)
JournalMathematical Programming
DOIs
StatePublished - Jan 1 2019

Fingerprint

Nonlinear Optimization
Polynomials
Testing
NP-complete problem
Semidefinite Programming
Polynomial
Imply
Coercivity
Sufficient Conditions
Polynomial-time Algorithm
Nonlinear Problem
Boundedness
Polynomial time
Coercive force
Objective function
Byproducts
Optimization Problem
Module
Theorem
Hierarchy

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Keywords

  • Archimedean quadratic modules
  • Coercive polynomials
  • Computational complexity
  • Existence of solutions in mathematical programs
  • Frank–Wolfe type theorems
  • Semidefinite programming

Cite this

@article{7846a73827be49c2834f919fb52292e6,
title = "On the complexity of testing attainment of the optimal value in nonlinear optimization",
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 = "Archimedean quadratic modules, Coercive polynomials, Computational complexity, Existence of solutions in mathematical programs, Frank–Wolfe type theorems, Semidefinite programming",
author = "Ahmadi, {Amir Ali} and Jeffrey Zhang",
year = "2019",
month = "1",
day = "1",
doi = "https://doi.org/10.1007/s10107-019-01411-1",
language = "English (US)",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer-Verlag GmbH and Co. KG",

}

On the complexity of testing attainment of the optimal value in nonlinear optimization. / Ahmadi, Amir Ali; Zhang, Jeffrey.

In: Mathematical Programming, 01.01.2019.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Ahmadi, Amir Ali

AU - Zhang, Jeffrey

PY - 2019/1/1

Y1 - 2019/1/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 - https://doi.org/10.1007/s10107-019-01411-1

DO - https://doi.org/10.1007/s10107-019-01411-1

M3 - Article

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

ER -