Global optimization

Last updated January 31, 2024

Global optimization is a branch of applied mathematics and numerical analysis that attempts to find the global minima or maxima of a function or a set of functions on a given set. It is usually described as a minimization problem because the maximization of the real-valued function $g(x)$ is equivalent to the minimization of the function $f(x):=(-1)\cdot g(x)$ .

Applications
Deterministic methods
Inner and outer approximation
Cutting-plane methods
Branch and bound methods
Interval methods
Methods based on real algebraic geometry
Stochastic methods
Direct Monte-Carlo sampling
Stochastic tunneling
Parallel tempering
Heuristics and metaheuristics
Response surface methodology-based approaches
See also
Footnotes
References
External links

Given a possibly nonlinear and non-convex continuous function $f:\Omega \subset \mathbb {R} ^{n}\to \mathbb {R}$ with the global minima $f^{*}$ and the set of all global minimizers $X^{*}$ in $\Omega$ , the standard minimization problem can be given as

\min _{x\in \Omega }f(x),

that is, finding $f^{*}$ and a global minimizer in $X^{*}$ ; where $\Omega$ is a (not necessarily convex) compact set defined by inequalities $g_{i}(x)\geqslant 0,i=1,\ldots ,r$ .

Global optimization is distinguished from local optimization by its focus on finding the minimum or maximum over the given set, as opposed to finding local minima or maxima. Finding an arbitrary local minimum is relatively straightforward by using classical local optimization methods. Finding the global minimum of a function is far more difficult: analytical methods are frequently not applicable, and the use of numerical solution strategies often leads to very hard challenges.

Applications

Typical examples of global optimization applications include:

Protein structure prediction (minimize the energy/free energy function)
Computational phylogenetics (e.g., minimize the number of character transformations in the tree)
Traveling salesman problem and electrical circuit design (minimize the path length)
Chemical engineering (e.g., analyzing the Gibbs energy)
Safety verification, safety engineering (e.g., of mechanical structures, buildings)
Worst-case analysis
Mathematical problems (e.g., the Kepler conjecture)
Object packing (configuration design) problems
The starting point of several molecular dynamics simulations consists of an initial optimization of the energy of the system to be simulated.
Spin glasses
Calibration of radio propagation models and of many other models in the sciences and engineering
Curve fitting like non-linear least squares analysis and other generalizations, used in fitting model parameters to experimental data in chemistry, physics, biology, economics, finance, medicine, astronomy, engineering.
IMRT radiation therapy planning

Deterministic methods

The most successful general exact strategies are:

Inner and outer approximation

In both of these strategies, the set over which a function is to be optimized is approximated by polyhedra. In inner approximation, the polyhedra are contained in the set, while in outer approximation, the polyhedra contain the set.

Cutting-plane methods

The cutting-plane method is an umbrella term for optimization methods which iteratively refine a feasible set or objective function by means of linear inequalities, termed cuts. Such procedures are popularly used to find integer solutions to mixed integer linear programming (MILP) problems, as well as to solve general, not necessarily differentiable convex optimization problems. The use of cutting planes to solve MILP was introduced by Ralph E. Gomory and Václav Chvátal.

Branch and bound methods

Branch and bound (BB or B&B) is an algorithm design paradigm for discrete and combinatorial optimization problems. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm.

Interval methods

Interval arithmetic, interval mathematics, interval analysis, or interval computation, is a method developed by mathematicians since the 1950s and 1960s as an approach to putting bounds on rounding errors and measurement errors in mathematical computation and thus developing numerical methods that yield reliable results. Interval arithmetic helps find reliable and guaranteed solutions to equations and optimization problems.

Methods based on real algebraic geometry

Real algebra is the part of algebra which is relevant to real algebraic (and semialgebraic) geometry. It is mostly concerned with the study of ordered fields and ordered rings (in particular real closed fields) and their applications to the study of positive polynomials and sums-of-squares of polynomials. It can be used in convex optimization

Stochastic methods

Several exact or inexact Monte-Carlo-based algorithms exist:

Direct Monte-Carlo sampling

In this method, random simulations are used to find an approximate solution.

Example: The traveling salesman problem is what is called a conventional optimization problem. That is, all the facts (distances between each destination point) needed to determine the optimal path to follow are known with certainty and the goal is to run through the possible travel choices to come up with the one with the lowest total distance. However, let's assume that instead of wanting to minimize the total distance traveled to visit each desired destination, we wanted to minimize the total time needed to reach each destination. This goes beyond conventional optimization since travel time is inherently uncertain (traffic jams, time of day, etc.). As a result, to determine our optimal path we would want to use simulation - optimization to first understand the range of potential times it could take to go from one point to another (represented by a probability distribution in this case rather than a specific distance) and then optimize our travel decisions to identify the best path to follow taking that uncertainty into account.

Stochastic tunneling

Stochastic tunneling (STUN) is an approach to global optimization based on the Monte Carlo method-sampling of the function to be objectively minimized in which the function is nonlinearly transformed to allow for easier tunneling among regions containing function minima. Easier tunneling allows for faster exploration of sample space and faster convergence to a good solution.

Parallel tempering

Parallel tempering, also known as replica exchange MCMC sampling, is a simulation method aimed at improving the dynamic properties of Monte Carlo method simulations of physical systems, and of Markov chain Monte Carlo (MCMC) sampling methods more generally. The replica exchange method was originally devised by Swendsen,^[1] then extended by Geyer^[2] and later developed, among others, by Giorgio Parisi.,^[3]^[4] Sugita and Okamoto formulated a molecular dynamics version of parallel tempering:^[5] this is usually known as replica-exchange molecular dynamics or REMD.

Essentially, one runs N copies of the system, randomly initialized, at different temperatures. Then, based on the Metropolis criterion one exchanges configurations at different temperatures. The idea of this method is to make configurations at high temperatures available to the simulations at low temperatures and vice versa. This results in a very robust ensemble which is able to sample both low and high energy configurations. In this way, thermodynamical properties such as the specific heat, which is in general not well computed in the canonical ensemble, can be computed with great precision.

Heuristics and metaheuristics

Other approaches include heuristic strategies to search the search space in a more or less intelligent way, including:

Ant colony optimization (ACO)
Simulated annealing, a generic probabilistic metaheuristic
Tabu search, an extension of local search capable of escaping from local minima
Evolutionary algorithms (e.g., genetic algorithms and evolution strategies)
Differential evolution, a method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality
Swarm-based optimization algorithms (e.g., particle swarm optimization, social cognitive optimization, multi-swarm optimization and ant colony optimization)
Memetic algorithms, combining global and local search strategies
Reactive search optimization (i.e. integration of sub-symbolic machine learning techniques into search heuristics)
Graduated optimization, a technique that attempts to solve a difficult optimization problem by initially solving a greatly simplified problem, and progressively transforming that problem (while optimizing) until it is equivalent to the difficult optimization problem.^[6]^[7]^[8]

Response surface methodology-based approaches

IOSO Indirect Optimization based on Self-Organization
Bayesian optimization, a sequential design strategy for global optimization of black-box functions using Bayesian statistics ^[9]

Footnotes

↑ Swendsen RH and Wang JS (1986) Replica Monte Carlo simulation of spin glasses Physical Review Letters 57 : 2607–2609
↑ C. J. Geyer, (1991) in Computing Science and Statistics, Proceedings of the 23rd Symposium on the Interface, American Statistical Association, New York, p. 156.
↑ Marco Falcioni and Michael W. Deem (1999). "A Biased Monte Carlo Scheme for Zeolite Structure Solution". J. Chem. Phys. 110 (3): 1754–1766. arXiv: cond-mat/9809085 . Bibcode:1999JChPh.110.1754F. doi:10.1063/1.477812. S2CID 13963102.
↑ David J. Earl and Michael W. Deem (2005) "Parallel tempering: Theory, applications, and new perspectives", Phys. Chem. Chem. Phys., 7, 3910
↑ Y. Sugita and Y. Okamoto (1999). "Replica-exchange molecular dynamics method for protein folding". Chemical Physics Letters. 314 (1–2): 141–151. Bibcode:1999CPL...314..141S. doi:10.1016/S0009-2614(99)01123-9.
↑ Thacker, Neil; Cootes, Tim (1996). "Graduated Non-Convexity and Multi-Resolution Optimization Methods". Vision Through Optimization.
↑ Blake, Andrew; Zisserman, Andrew (1987). Visual Reconstruction. MIT Press. ISBN 0-262-02271-0.^{[ page needed ]}
↑ Hossein Mobahi, John W. Fisher III. On the Link Between Gaussian Homotopy Continuation and Convex Envelopes, In Lecture Notes in Computer Science (EMMCVPR 2015), Springer, 2015.
↑ Jonas Mockus (2013). Bayesian approach to global optimization: theory and applications. Kluwer Academic.

Related Research Articles

Mathematical optimization or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfields: discrete optimization and continuous optimization. Optimization problems arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.

Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve problems that might be deterministic in principle. They are often used in physical and mathematical problems and are most useful when it is difficult or impossible to use other approaches. Monte Carlo methods are mainly used in three problem classes: optimization, numerical integration, and generating draws from a probability distribution.

Simulated annealing (SA) is a probabilistic technique for approximating the global optimum of a given function. Specifically, it is a metaheuristic to approximate global optimization in a large search space for an optimization problem. For large numbers of local optima, SA can find the global optima. It is often used when the search space is discrete. For problems where finding an approximate global optimum is more important than finding a precise local optimum in a fixed amount of time, simulated annealing may be preferable to exact algorithms such as gradient descent or branch and bound.

Gradient descent is a method for unconstrained mathematical optimization. It is a first-order iterative algorithm for finding a local minimum of a differentiable multivariate function

In numerical analysis, hill climbing is a mathematical optimization technique which belongs to the family of local search. It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better solution by making an incremental change to the solution. If the change produces a better solution, another incremental change is made to the new solution, and so on until no further improvements can be found.

In numerical analysis, stochastic tunneling (STUN) is an approach to global optimization based on the Monte Carlo method-sampling of the function to be objective minimized in which the function is nonlinearly transformed to allow for easier tunneling among regions containing function minima. Easier tunneling allows for faster exploration of sample space and faster convergence to a good solution.

In computer science and mathematical optimization, a metaheuristic is a higher-level procedure or heuristic designed to find, generate, tune, or select a heuristic that may provide a sufficiently good solution to an optimization problem or a machine learning problem, especially with incomplete or imperfect information or limited computation capacity. Metaheuristics sample a subset of solutions which is otherwise too large to be completely enumerated or otherwise explored. Metaheuristics may make relatively few assumptions about the optimization problem being solved and so may be usable for a variety of problems.

Stochastic gradient descent is an iterative method for optimizing an objective function with suitable smoothness properties. It can be regarded as a stochastic approximation of gradient descent optimization, since it replaces the actual gradient by an estimate thereof. Especially in high-dimensional optimization problems this reduces the very high computational burden, achieving faster iterations in exchange for a lower convergence rate.

Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets. Many classes of convex optimization problems admit polynomial-time algorithms, whereas mathematical optimization is in general NP-hard.

Quantum annealing (QA) is an optimization process for finding the global minimum of a given objective function over a given set of candidate solutions, by a process using quantum fluctuations. Quantum annealing is used mainly for problems where the search space is discrete with many local minima; such as finding the ground state of a spin glass or the traveling salesman problem. The term "quantum annealing" was first proposed in 1988 by B. Apolloni, N. Cesa Bianchi and D. De Falco as a quantum-inspired classical algorithm. It was formulated in its present form by T. Kadowaki and H. Nishimori in 1998 though an imaginary-time variant without quantum coherence had been discussed by A. B. Finnila, M. A. Gomez, C. Sebenik and J. D. Doll in 1994.

The cross-entropy (CE) method is a Monte Carlo method for importance sampling and optimization. It is applicable to both combinatorial and continuous problems, with either a static or noisy objective.

A stochastic simulation is a simulation of a system that has variables that can change stochastically (randomly) with individual probabilities.

Stochastic optimization (SO) methods are optimization methods that generate and use random variables. For stochastic problems, the random variables appear in the formulation of the optimization problem itself, which involves random objective functions or random constraints. Stochastic optimization methods also include methods with random iterates. Some stochastic optimization methods use random iterates to solve stochastic problems, combining both meanings of stochastic optimization. Stochastic optimization methods generalize deterministic methods for deterministic problems.

In computational physics, variational Monte Carlo (VMC) is a quantum Monte Carlo method that applies the variational method to approximate the ground state of a quantum system.

Multi-objective optimization or Pareto optimization is an area of multiple-criteria decision making that is concerned with mathematical optimization problems involving more than one objective function to be optimized simultaneously. Multi-objective is a type of vector optimization that has been applied in many fields of science, including engineering, economics and logistics where optimal decisions need to be taken in the presence of trade-offs between two or more conflicting objectives. Minimizing cost while maximizing comfort while buying a car, and maximizing performance whilst minimizing fuel consumption and emission of pollutants of a vehicle are examples of multi-objective optimization problems involving two and three objectives, respectively. In practical problems, there can be more than three objectives.

Variable neighborhood search (VNS), proposed by Mladenović & Hansen in 1997, is a metaheuristic method for solving a set of combinatorial optimization and global optimization problems. It explores distant neighborhoods of the current incumbent solution, and moves from there to a new one if and only if an improvement was made. The local search method is applied repeatedly to get from solutions in the neighborhood to local optima. VNS was designed for approximating solutions of discrete and continuous optimization problems and according to these, it is aimed for solving linear program problems, integer program problems, mixed integer program problems, nonlinear program problems, etc.

Derivative-free optimization, is a discipline in mathematical optimization that does not use derivative information in the classical sense to find optimal solutions: Sometimes information about the derivative of the objective function f is unavailable, unreliable or impractical to obtain. For example, f might be non-smooth, or time-consuming to evaluate, or in some way noisy, so that methods that rely on derivatives or approximate them via finite differences are of little use. The problem to find optimal points in such situations is referred to as derivative-free optimization, algorithms that do not use derivatives or finite differences are called derivative-free algorithms.

Simulation-based optimization integrates optimization techniques into simulation modeling and analysis. Because of the complexity of the simulation, the objective function may become difficult and expensive to evaluate. Usually, the underlying simulation model is stochastic, so that the objective function must be estimated using statistical estimation techniques.

References

Deterministic global optimization:

R. Horst, H. Tuy, Global Optimization: Deterministic Approaches, Springer, 1996.
R. Horst, P.M. Pardalos and N.V. Thoai, Introduction to Global Optimization, Second Edition. Kluwer Academic Publishers, 2000.
A.Neumaier, Complete Search in Continuous Global Optimization and Constraint Satisfaction, pp. 271–369 in: Acta Numerica 2004 (A. Iserles, ed.), Cambridge University Press 2004.
M. Mongeau, H. Karsenty, V. Rouzé and J.-B. Hiriart-Urruty, Comparison of public-domain software for black box global optimization. Optimization Methods & Software 13(3), pp. 203–226, 2000.
J.D. Pintér, Global Optimization in Action - Continuous and Lipschitz Optimization: Algorithms, Implementations and Applications. Kluwer Academic Publishers, Dordrecht, 1996. Now distributed by Springer Science and Business Media, New York. This book also discusses stochastic global optimization methods.
L. Jaulin, M. Kieffer, O. Didrit, E. Walter (2001). Applied Interval Analysis. Berlin: Springer.
E.R. Hansen (1992), Global Optimization using Interval Analysis, Marcel Dekker, New York.

For simulated annealing:

Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P. (1983-05-13). "Optimization by Simulated Annealing". Science. American Association for the Advancement of Science (AAAS). 220 (4598): 671–680. Bibcode:1983Sci...220..671K. doi:10.1126/science.220.4598.671. ISSN 0036-8075. PMID 17813860. S2CID 205939.

For reactive search optimization:

Roberto Battiti, M. Brunato and F. Mascia, Reactive Search and Intelligent Optimization, Operations Research/Computer Science Interfaces Series, Vol. 45, Springer, November 2008. ISBN 978-0-387-09623-0

For stochastic methods:

A. Zhigljavsky. Theory of Global Random Search. Mathematics and its applications. Kluwer Academic Publishers. 1991.
Hamacher, K (2006). "Adaptation in stochastic tunneling global optimization of complex potential energy landscapes". Europhysics Letters (EPL). IOP Publishing. 74 (6): 944–950. Bibcode:2006EL.....74..944H. doi:10.1209/epl/i2006-10058-0. ISSN 0295-5075. S2CID 250761754.
Hamacher, K.; Wenzel, W. (1999-01-01). "Scaling behavior of stochastic minimization algorithms in a perfect funnel landscape". Physical Review E. 59 (1): 938–941. arXiv: physics/9810035 . Bibcode:1999PhRvE..59..938H. doi:10.1103/physreve.59.938. ISSN 1063-651X. S2CID 119096368.
Wenzel, W.; Hamacher, K. (1999-04-12). "Stochastic Tunneling Approach for Global Minimization of Complex Potential Energy Landscapes". Physical Review Letters. American Physical Society (APS). 82 (15): 3003–3007. arXiv: physics/9903008 . Bibcode:1999PhRvL..82.3003W. doi:10.1103/physrevlett.82.3003. ISSN 0031-9007. S2CID 5113626.

For parallel tempering:

Hansmann, Ulrich H.E. (1997). "Parallel tempering algorithm for conformational studies of biological molecules". Chemical Physics Letters. Elsevier BV. 281 (1–3): 140–150. arXiv: physics/9710041 . Bibcode:1997CPL...281..140H. doi:10.1016/s0009-2614(97)01198-6. ISSN 0009-2614. S2CID 14137470.

For continuation methods:

Zhijun Wu. The effective energy transformation scheme as a special continuation approach to global optimization with application to molecular conformation. Technical Report, Argonne National Lab., IL (United States), November 1996.

For general considerations on the dimensionality of the domain of definition of the objective function:

Hamacher, Kay (2005). "On stochastic global optimization of one-dimensional functions". Physica A: Statistical Mechanics and Its Applications. Elsevier BV. 354: 547–557. Bibcode:2005PhyA..354..547H. doi:10.1016/j.physa.2005.02.028. ISSN 0378-4371.

For strategies allowing one to compare deterministic and stochastic global optimization methods

External links

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Swendsen RH and Wang JS (1986) Replica Monte Carlo simulation of spin glasses Physical Review Letters 57 : 2607–2609

[2] C. J. Geyer, (1991) in Computing Science and Statistics, Proceedings of the 23rd Symposium on the Interface, American Statistical Association, New York, p. 156.

[3] Marco Falcioni and Michael W. Deem (1999). "A Biased Monte Carlo Scheme for Zeolite Structure Solution". J. Chem. Phys. 110 (3): 1754–1766. arXiv: cond-mat/9809085 . Bibcode:1999JChPh.110.1754F. doi:10.1063/1.477812. S2CID 13963102.

[4] David J. Earl and Michael W. Deem (2005) "Parallel tempering: Theory, applications, and new perspectives", Phys. Chem. Chem. Phys., 7, 3910

[5] Y. Sugita and Y. Okamoto (1999). "Replica-exchange molecular dynamics method for protein folding". Chemical Physics Letters. 314 (1–2): 141–151. Bibcode:1999CPL...314..141S. doi:10.1016/S0009-2614(99)01123-9.

[6] Thacker, Neil; Cootes, Tim (1996). "Graduated Non-Convexity and Multi-Resolution Optimization Methods". Vision Through Optimization.

[7] Blake, Andrew; Zisserman, Andrew (1987). Visual Reconstruction. MIT Press. ISBN 0-262-02271-0.^{[ page needed ]}

[mobahi2015-8] Hossein Mobahi, John W. Fisher III. On the Link Between Gaussian Homotopy Continuation and Convex Envelopes, In Lecture Notes in Computer Science (EMMCVPR 2015), Springer, 2015.

[9] Jonas Mockus (2013). Bayesian approach to global optimization: theory and applications. Kluwer Academic.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]