Efficient and reliable global optimization.

摘要

For quite some time, it has been held that no numerical algorithm could guarantee having found a global solution to the general nonlinear global optimization problem. The reasoning was: The function to be minimized can only be sampled at a finite number of points. Therefore, there is no way of knowing whether the function dips to some smaller value between sampled points. Although this argument is probably true using evaluations of functions at points, it is not true of methods which can produce asymptotically accurate lower bounds for the range of values of the function over compact sets.; Interval arithmetic, for example, provides asymptotically accurate upper and lower bounds on ranges of values of functions over continua (12, 11, 21, 22, 23, 24, 26, 32). Coding interval arithmetic in C++, the author has designed an ideal bounding mechanisms which is: (1) capable of producing reliable, "tight", and asymptotically accurate bounds; (2) efficient to compute; (3) applicable to any programmable function; (4) easy to generalize and automate; (5) convenient for an unsophisticated user to utilize. Using this mechanism, rigorous algorithms are presented which produce a list of "boxes" enclosing the set of all global minimizers and an interval trapping the minimum value.; The most basic algorithm does not even use differentiability. Using interval Newton methods, monotonicity tests, and convexity tests, improvements in efficiency are achieved for differentiable problems. For further improvements in efficiency, the algorithms are parallelized. Numerical examples illustrating the techniques are given.; The parallelization task is accomplished by distributing identical processes over a network of workstations. Each process performs the interval global optimization algorithm but with a different subregion of the initial search space. Communication overhead is minimized in order to maximize the speedup. Issues of distributed initialization, load balancing, and global termination detection are addressed. Finally, an analysis of the speedup is determined.