Turing Computability of (Non-)Linear Optimization - Brattka, Vasco; Ziegler, Martin (Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), 2001)
We consider the classical LINEAR OPTIMIZATION Problem, but in the Turing rather than the RealRAM 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.
Keywords: conference paper