← Research

Computability of Optimizers

Yunseok Lee, Holger Boche, Gitta Kutyniok

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.

PDF ↗

Models

Loading
EVIDENCE / COMPARISON

Benchmarks

Explore every benchmark

Loading

These charts contain model-linked results. The charts above also include unlinked source profiles. Compare scores within each evaluation. Model quality, usage, transparency and system performance measure different things.

Install TensorTrace