A geometric approach to global optimization

In this paper we consider the problem of optimizing a piecewise-linear obje ctive function over a non-convex domain. In particular we do not allow the solution to lie in the interior of a prespecified region R. We discuss the geometrical properties of this problems and present algorithms based on com binatorial arguments. In addition we show how we can construct quite compli cated shaped sets R while maintaining the combinatorial properties.