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 |
| _version_ | 1811071889830838272 |
|---|---|
| author | Rogaway, Phillip |
| author_facet | Rogaway, Phillip |
| author_sort | Rogaway, Phillip |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T08:57:34Z |
| id | mit-1721.1/149179 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T08:57:34Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1491792023-03-30T04:15:50Z The Complexity of Continuous Optimization Rogaway, Phillip 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. 2023-03-29T14:35:09Z 2023-03-29T14:35:09Z 1991-06 https://hdl.handle.net/1721.1/149179 24101730 MIT-LCS-TM-452 application/pdf |
| spellingShingle | Rogaway, Phillip The Complexity of Continuous Optimization |
| title | The Complexity of Continuous Optimization |
| title_full | The Complexity of Continuous Optimization |
| title_fullStr | The Complexity of Continuous Optimization |
| title_full_unstemmed | The Complexity of Continuous Optimization |
| title_short | The Complexity of Continuous Optimization |
| title_sort | complexity of continuous optimization |
| url | https://hdl.handle.net/1721.1/149179 |
| work_keys_str_mv | AT rogawayphillip thecomplexityofcontinuousoptimization AT rogawayphillip complexityofcontinuousoptimization |