Computability of Optimizers

Yunseok Lee, Holger Boche, Gitta Kutyniok

Research output: Contribution to journalArticlepeer-review

Abstract

Optimization problems are a staple of today's scientific and technical landscape. However, at present, solvers of such problems are almost exclusively run on digital hardware. Using Turing machines as a mathematical model for any type of digital hardware, in this paper, we analyze fundamental limitations of this conceptual approach of solving optimization problems. Since in most applications, the optimizer itself is of significantly more interest than the optimal value of the corresponding function, we will focus on computability of the optimizer. In fact, we will show that in various situations the optimizer is unattainable on Turing machines and consequently on digital computers. Moreover, even worse, there does not exist a Turing machine, which approximates the optimizer itself up to a certain constant error. We prove such results for a variety of well-known problems from very different areas, including artificial intelligence, financial mathematics, and information theory, often deriving the even stronger result that such problems are not Banach-Mazur computable, also not even in an approximate sense.

Original languageEnglish
Pages (from-to)2967-2983
Number of pages17
JournalIEEE Transactions on Information Theory
Volume70
Issue number4
DOIs
StatePublished - 1 Apr 2024
Externally publishedYes

Keywords

  • Optimization
  • Turing machine
  • artificial intelligence
  • computability
  • digital computing
  • information theory

Fingerprint

Dive into the research topics of 'Computability of Optimizers'. Together they form a unique fingerprint.

Cite this