|
|
Turing Computability of (Non-)Linear Optimization
Vasco Brattka and Martin Ziegler,
in: 13th Canadian Conference on
Computational Geometry, CCCG 2001,
University of Waterloo, 181-184, August 13-15, 2001.
Abstract
We consider the classical LINEAR OPTIMIZATION problem, but in the Turing
rather than the RealRAM model. Asking for mere computability of a functions's maximum over some closed domain, we show that the common presumptions
`full-dimensional' and `bounded' in fact cannot be ommited: 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 otimizable
Electronical Versions