## 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 language | English (US) |
---|---|

Pages (from-to) | 221-241 |

Number of pages | 21 |

Journal | Mathematical Programming |

Volume | 184 |

Issue number | 1-2 |

DOIs | |

State | Published - Nov 1 2020 |

## All Science Journal Classification (ASJC) codes

- Software
- General Mathematics

## Keywords

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