Complex Systems
Highlight
Current Research
Research Accomplishments
HIGHLIGHT - Advances in Global Optimization
Fig. 1: Shubert function, used for benchmarking global optimization methods. |
Optimization problems are ubiquitous and extremely consequential. Their theoretical and practical interest has continued to grow from the first recorded instance of Queen Dido's problem, to present day forays into complexity theory, biology, material sciences, geophysics, industrial technology, and economics. The formulation of the Global Optimization Problem (GOP) is deceptively simple: find the absolute minimum (maximum) of a given function or functional over the allowed range of its variables. Often, the function to be optimized is not specified in analytic form, and must be evaluated point-wise by a computer program, a physical device, or other construct. Such a black-box is called an oracle. Of course, the brute force approach of evaluating the function on its whole domain is either impossible - if the variables are continuous - or prohibitively expensive - if the variables are discrete, but have wide ranges in high dimensional spaces. Since, in general, each oracle invocation (function evaluation) involves an expensive computational sequence, the number of function evaluations needs to be kept to a minimum. The number of invocations of the oracle measures the query complexity of the problem, and gives a fair - albeit by no means unique - idea of its difficulty or "hardness".
Fig.2: Stack energy global optimization is used to focus seismic images. Focus quality expressed in terms of coherence factor. Initial (blue) and final (red) coherence results (and corresponding stack values) are shown for a large-scale (417 seismic lines) problem. |
The primary difficulty in solving GOPs stems from the fact that the familiar condition for determining local extrema - namely, annulment of the gradient of the function - is only necessary for GOPs and local, i.e., it does not distinguish between local and global extrema. Our original approach combined two innovative concepts, sub-energy tunneling and non-Lipschitzian terminal repellers, to ensure escape from local minima in a fast, reliable, and computationally efficient manner. The methodology was embodied into the TRUST (terminal repeller unconstrained subenergy tunneling) code, and was shown to produce considerably faster and more accurate results than previously reported global optimization techniques. To further advance the applicability of TRUST to high dimensional problems, a stochastic tunneling algorithm was subsequently developed. It uses a rejection-based, stochastic Pijavski bounding procedure to locate new local minima and reject unpromising regions in the search space.
Recently, we have investigated the entwined roles that additional information and quantum algorithms play in reducing the complexity of a class of global optimization problems. We were able to show that: (i) a modest amount of additional information is sufficient to map the continuous GOP into the (discrete) Grover problem; (ii) while this additional information is actually available in some GOPs, it cannot be taken advantage of within the framework of classical optimization algorithms; and (iii) quantum algorithms offer a natural framework for the efficient use of this information, resulting in considerable speedup of the solution of the GOP.
Research by: J. Barhen, V. Protopopescu, D. Reister, and E. Oblow; selected references: Science, 276, 1094-1097 (1997); R&D 100 Award (1998); U. S. Patent No. 6,188,964 (February 2001); Journal of Global Optimization, 20, 195-212 (2001); Geophysics, 66, 320-326 (2001); Physics Lett., A 295 (in press, 2002).
|
Current Research
|
Research Accomplishments
|
