TY - CONF
AB - 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.
AU - Brattka, Vasco
AU - Ziegler, Martin
ID - 18168
T2 - Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01)
TI - Turing Computability of (Non-)Linear Optimization
ER -