Turing computability of (non-)linear optimization.
Martin Ziegler, Vasco Brattka · 2001
We consider the classical LINEAR OPTIMIZATION problem, but in the Turing rather than the REAL-RAM model. Asking for mere computability of a function's maximum over some closed domain, we show that the common presumptions `full-dimensional' and `bounded' in fact cannot be omitted: The sound framework of Recursive Analysis enables us to rigorously prove this folkloristic observation! On the other hand, convexity of this domain may be weakened to connectedness, and even non-linear functions turn out to be effectively optimizable. 1 Motivation The gap between (theoretical) algorithm design and (practical) implementation reveals a particular challenge in Computational Geometry: Provably correct algorithms keep, upon implementation, reporting not only inaccurate but sometimes even entirely invalid results, especially upon input of degenerate configurations [9] --- for obvious reasons: Algorithms in Computational Geometry are most generally developed in the REAL-RAM model [1], capable of operating on real numbers exactly. Actual digital computers however can process in each step only a finite amount of information [2]. We therefore find it necessary to consider a different model of real number computation. In fact, Alan Turing himself introduced 'his' machine in order to study computability aspects over R [14] and thereby initiated the nowadays well-established field of RECURSIVE ANAL- YSIS [8, 12, 15]. Roughly speaking, a Turing machine is said to compute the real number r if it can output rational approximations of arbitrarily prescribable precision. Partially supported by DFG Grants Me872/7-3 and Br1807/4-1 It is straight forward to adopt this model to Computational Geometry. In fact [6] already did so in investigating Turing computability of the extreme points of ...