On the Non-Computability of Convex Optimization Problems

Research output: Contribution to book/Conference proceedings/Anthology/ReportConference contributionContributedpeer-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 languageEnglish
Title of host publication2024 IEEE International Symposium on Information Theory, ISIT 2024 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages3083-3088
Number of pages6
ISBN (electronic)9798350382846
Publication statusPublished - 2024
Peer-reviewedYes

Publication series

SeriesIEEE International Symposium on Information Theory - Proceedings
ISSN2157-8095

Conference

Title2024 IEEE International Symposium on Information Theory
Abbreviated titleISIT 2024
Duration7 - 12 July 2024
Website
LocationInterContinental Athenaeum
CityAthens
CountryGreece

External IDs

ORCID /0000-0002-1702-9075/work/175771088