World Library  
Flag as Inappropriate
Email this Article

Global optimization

Article Id: WHEBN0000563854
Reproduction Date:

Title: Global optimization  
Author: World Heritage Encyclopedia
Language: English
Subject: Couenne, BARON, Hoàng Tụy, Reactive search optimization, SmartDO
Collection: Mathematical Optimization
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Global optimization

Global optimization is a branch of applied mathematics and numerical analysis that deals with the global optimization of a function or a set of functions according to some criteria. Typically, a set of bound and more general constraints is also present, and the decision variables are optimized considering also the constraints.

Global optimization is distinguished from regular optimization by its focus on finding the maximum or minimum over all input values, as opposed to finding local minima or maxima.

Contents

  • General 1
  • Applications 2
  • Deterministic methods 3
    • Inner and outer approximation 3.1
    • Cutting plane methods 3.2
    • Branch and bound methods 3.3
    • Interval methods 3.4
    • Methods based on real algebraic geometry 3.5
  • Stochastic methods 4
    • Simulated annealing 4.1
    • Direct Monte-Carlo sampling 4.2
    • Stochastic tunneling 4.3
    • Parallel tempering 4.4
  • Heuristics and metaheuristics 5
  • Response surface methodology based approaches 6
  • Software 7
  • See also 8
  • Footnotes 9
  • References 10
  • External links 11

General

A common (standard) model form is the minimization of one real-valued function f in the parameter-space \vec{x}\in P, or its specified subset \vec{x}\in D: here D denotes the set defined by the constraints.

(The maximization of a real-valued function g(x) is equivalent to the minimization of the function f(x):=(-1)\cdot g(x).)

In many nonlinear optimization problems, the objective function f has a large number of local minima and maxima. Finding an arbitrary local optimum is relatively straightforward by using classical local optimization methods. Finding the global minimum (or maximum) of a function is far more difficult: symbolic (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:

Deterministic methods

The most successful general strategies are:

Inner and outer approximation

In both of these strategies, 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.

(see interalg from OpenOpt and GlobSol)

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 Monte-Carlo-based algorithms exist:

Simulated annealing

Simulated annealing (SA)' is a generic probabilistic metaheuristic for the global optimization problem of locating a good approximation to the global optimum of a given function in a large search space. It is often used when the search space is discrete (e.g., all tours that visit a given set of cities). For certain problems, simulated annealing may be more efficient than exhaustive enumeration — provided that the goal is merely to find an acceptably good solution in a fixed amount of time, rather than the best possible solution.

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 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.

Parallel tempering

Parallel tempering, also known as replica exchange MCMC sampling, is a

  • A. Neumaier’s page on Global Optimization
  • Introduction to global optimization by L. Liberti
  • Free e-book by Thomas Weise

External links

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.
  • R.G. Strongin, Ya.D. Sergeyev (2000) Global optimization with non-convex constraints: Sequential and parallel algorithms, Kluwer Academic Publishers, Dordrecht.
  • Ya.D. Sergeyev, R.G. Strongin, D. Lera (2013) Introduction to global optimization exploiting space-filling curves, Springer, NY.

For simulated annealing:

  • S. Kirkpatrick, C.D. Gelatt, and M.P. Vecchi. Science, 220:671–680, 1983.

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.
  • K. Hamacher. Adaptation in Stochastic Tunneling Global Optimization of Complex Potential Energy Landscapes, Europhys.Lett. 74(6):944, 2006.
  • K. Hamacher and W. Wenzel. The Scaling Behaviour of Stochastic Minimization Algorithms in a Perfect Funnel Landscape. Phys. Rev. E, 59(1):938-941, 1999.
  • W. Wenzel and K. Hamacher. A Stochastic tunneling approach for global minimization. Phys. Rev. Lett., 82(15):3003-3007, 1999.

For parallel tempering:

  • U. H. E. Hansmann. Chem.Phys.Lett., 281:140, 1997.

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:

  • K. Hamacher. On Stochastic Global Optimization of one-dimensional functions. Physica A 354:547-557, 2005.

References

  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.  
  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: 141–151.  
  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.  
  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.

Footnotes

See also

  • LIONsolver
  • TOMLAB for Matlab
  • MIDACO Global optimization software (Excel, Matlab, Octave, Python, C/C++, R and Fortran)
  • Optimus platform
  • The NAG Numerical Library contains routines for both global and local optimization.
  • Demo global optimization software versions are available also for a number of commercial software products.
  • XTREME a single and multiple objective optimization software for nonlinear optimization (GUI, Excel, C/C++ API and Python)

2. Commercial:

1. Free and opensource:

Software

Response surface methodology based approaches

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

Main page: Metaheuristic

Heuristics and metaheuristics

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.

this is usually known as replica-exchange molecular dynamics or REMD. [5] version of parallel tempering:molecular dynamics Sugita and Okamoto formulated a [4][3]

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.