Geometry and combinatorics of the cutting angle method

Abstract

Lower approximation of Lipschitz functions plays an important role in deterministic global optimization. This article examines in detail the lower piecewise linear approximation which arises in the cutting angle method. All its local minima can be explicitly enumerated, and a special data structure was designed to process them very efficiently, improving previous results by several orders of magnitude. Further, some geometrical properties of the lower approximation have been studied, and regions on which this function is linear have been identified explicitly. Connection to a special distance function and Voronoi diagrams was established. An application of these results is a black-box multivariate random number generator, based on acceptance–rejection approach.

Keywords:

• Lipschitz optimization
• Global optimization
• Cutting angle method
• Random number generator
• Saw tooth cover
• Mathematics Subject Classifications 2000: 65K05
• 90C59