The Complexity of Continuous Optimization
Given a polynomial objective function f(x1,…,xn), we consider the problem of finding the maximum of this polynomial inside some convex set D = {x : Ax <= B}. We show that, under a complexity assumption, this extremum cannot be approximated by any polynomial-time algorithm, even exceedingly poorly...
| Main Author: | |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149179 |
| Summary: | Given a polynomial objective function f(x1,…,xn), we consider the problem of finding the maximum of this polynomial inside some convex set D = {x : Ax <= B}. We show that, under a complexity assumption, this extremum cannot be approximated by any polynomial-time algorithm, even exceedingly poorly. This represents an unusual interplay of discrete and continuous mathematics: using a combinatorial argument to get a hardness result for a continuous optimization problem. |
|---|