On the Non-Computability of Convex Optimization Problems
Research output: Contribution to book/Conference proceedings/Anthology/Report › Conference contribution › Contributed › peer-review
Contributors
Abstract
This paper explores the computability of the optimal point in convex problems with inequality constraints. It is shown that feasible sets, defined by computable convex functions, can yield non-computable optimal points for strictly convex and computable objective functions. Additionally, the optimal point of the Lagrangian dual problem associated with such convex constraints is also proven to be non-computable. Despite converging sequences of computable numbers towards the Lagrangian's optimal point, algorithmic control of the approximation error is shown to be impossible.
Details
| Original language | English |
|---|---|
| Title of host publication | 2024 IEEE International Symposium on Information Theory, ISIT 2024 - Proceedings |
| Publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| Pages | 3083-3088 |
| Number of pages | 6 |
| ISBN (electronic) | 9798350382846 |
| Publication status | Published - 2024 |
| Peer-reviewed | Yes |
Publication series
| Series | IEEE International Symposium on Information Theory - Proceedings |
|---|---|
| ISSN | 2157-8095 |
Conference
| Title | 2024 IEEE International Symposium on Information Theory |
|---|---|
| Abbreviated title | ISIT 2024 |
| Duration | 7 - 12 July 2024 |
| Website | |
| Location | InterContinental Athenaeum |
| City | Athens |
| Country | Greece |
External IDs
| ORCID | /0000-0002-1702-9075/work/175771088 |
|---|