On the Non-Computability of Convex Optimization Problems

Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/GutachtenBeitrag in KonferenzbandBeigetragenBegutachtung

Beitragende

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

OriginalspracheEnglisch
Titel2024 IEEE International Symposium on Information Theory, ISIT 2024 - Proceedings
Herausgeber (Verlag)Institute of Electrical and Electronics Engineers Inc.
Seiten3083-3088
Seitenumfang6
ISBN (elektronisch)9798350382846
PublikationsstatusVeröffentlicht - 2024
Peer-Review-StatusJa

Publikationsreihe

ReiheIEEE International Symposium on Information Theory - Proceedings
ISSN2157-8095

Konferenz

Titel2024 IEEE International Symposium on Information Theory
KurztitelISIT 2024
Dauer7 - 12 Juli 2024
Webseite
OrtInterContinental Athenaeum
StadtAthens
LandGriechenland

Externe IDs

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