Geometry and combinatorics of the cutting angle method. (English) Zbl 1055.65071

Lower approximation of Lipschitz functions plays an important role in deterministic global optimization. This paper 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 is designed to process them very efficiently, improving previous results by several orders of magnitude. Also, some geometrical properties of the lower approximation are studied. Connection to a spectral distance function and Voronoi diagrams is established. An application of these results is a black-box multivariate random number generator, based on an acceptance-rejection approach.


65K05 Numerical mathematical programming methods
90C59 Approximation methods and heuristics in mathematical programming
65C10 Random number generation in numerical analysis
90C30 Nonlinear programming


Full Text: DOI


[1] DOI: 10.1016/S0893-9659(98)00179-7 · Zbl 0944.90063
[2] DOI: 10.1023/A:1019204407420 · Zbl 0990.90117
[3] Bagirov A., Convex Analysis and Global Optimization, of Nonconvex Optimization and its Applications 54 pp pp. 245–268– (2001)
[4] DOI: 10.1023/A:1020256900863 · Zbl 1047.90044
[5] DOI: 10.1007/PL00009366 · Zbl 0897.68113
[6] Devroye L., Non-uniform Random Variate Generation (1986) · Zbl 0593.65005
[7] Floudas C.A., Deterministic Global Optimization: Theory, Methods and Applications, of Nonconvex Optimization and its Applications 37 (2000)
[8] DOI: 10.2307/2986138 · Zbl 0893.62110
[9] Hansen P., Handbook of Global Optimization pp pp. 407–493– (1995)
[10] DOI: 10.1145/203082.203089 · Zbl 0887.65145
[11] Horst R., Introduction to Global Optimization (2000) · Zbl 0966.90073
[12] Horst R., Global Optimization: Deterministic Approaches (1993)
[13] Kelley J.E., J. of SIAM 8 pp 703– (1960)
[14] Lim K.F., Proceedings of the 3rd International Conference on Computational Science 4 pp 1040– (2003)
[15] DOI: 10.1007/BF01580583 · Zbl 0598.90075
[16] DOI: 10.1137/S0036144594278060 · Zbl 0939.92013
[17] DOI: 10.1016/0041-5553(72)90115-2 · Zbl 0282.65052
[18] Pintér J., Global Optimization in Action: Continuous and Lipschitz Optimization–Algorithms, Implementations and Applications, of Nonconvex Optimization and its Applications 6 (1996) · Zbl 0842.90110
[19] Rubinov A.M., Abstract Convexity and Global Optimization, of Nonconvex Optimization and its Applications 44 (2000) · Zbl 0985.90074
[20] DOI: 10.1137/0709036 · Zbl 0251.65052
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.