Deterministic global optimization is a branch of numerical optimization which focuses on finding the global solutions of an optimization problem whilst providing theoretical guarantees that the reported solution is indeed the global one, within some predefined tolerance. The term "deterministic global optimization" typically refers to complete or rigorous (see below) optimization methods. Rigorous methods converge to the global optimum in finite time. Deterministic global optimization methods are typically used when locating the global solution is a necessity (i.e. when the only naturally occurring state described by a mathematical model is the global minimum of an optimization problem), when it is extremely difficult to find a feasible solution, or simply when the user desires to locate the best possible solution to a problem.
Neumaier[1] classified global optimization methods in four categories, depending on their degree of rigour with which they approach the optimum, as follows:
An incomplete method uses clever intuitive heuristics for searching but has no safeguards if the search gets stuck in a local minimum
An asymptotically complete method reaches a global minimum with certainty or at least with probability one if allowed to run indefinitely long, but has no means to know when a global minimizer has been found.
A complete method reaches a global minimum with certainty, assuming exact computations and indefinitely long run time, and knows after a finite time that an approximate global minimizer has been found (to within prescribed tolerances).
A rigorous method reaches a global minimum with certainty and within given tolerances even in the presence of rounding errors, except in near-degenerate cases, where the tolerances may be exceeded.
Deterministic global optimization methods typically belong to the last two categories. Note that building a rigorous piece of software is extremely difficult as the process requires that all the dependencies are also coded rigorously.
Deterministic global optimization methods require ways to rigorously bound function values over regions of space. One could say that a main difference between deterministic and non-deterministic methods in this context is that the former perform calculations over regions of the solution space, whereas the latter perform calculations on single points. This is either done by exploiting particular functional forms (e.g. McCormick relaxations[2]), or using interval analysis in order to work with more general functional forms. In any case bounding is required, which is why deterministic global optimization methods cannot give a rigorous result when working with black-box code, unless that code is explicitly written to also return function bounds. For this reason, it is common for problems in deterministic global optimization to be represented using a computational graph, as it is straightforward to overload all operators such that the resulting function values or derivatives yield interval (rather than scalar) results.
Classes of deterministic global optimization problemsedit
Linear programming problems are a highly desirable formulation for any practical problem. The reason is that, with the rise of interior-point algorithms, it is possible to efficiently solve very large problems (involving hundreds of thousands or even millions of variables) to global optimality. Linear programming optimization problems strictly fall under the category of deterministic global optimization.
Much like linear programming problems, MILPs are very important when solving decision-making models. Efficient algorithms for solving complex problems of this type are known and are available in the form of solvers such as CPLEX.
Non-linear programming problems are extremely challenging in deterministic global optimization. The order of magnitude that a modern solver can be expected to handle in reasonable time is roughly 100 to a few hundreds of non-linear variables. At the time of this writing, there exist no parallel solvers for the deterministic solution of NLPs, which accounts for the complexity gap between deterministic LP and NLP programming.
Even more challenging than their NLP counterparts, deterministically solving an MINLP problem can be very difficult. Techniques such as integer cuts, or branching a problem on its integer variables (hence creating NLP sub-problems which can in turn be solved deterministically), are commonly used.
Zero-order methodsedit
Zero-order methods consist of methods which make use of zero-order interval arithmetic.[3] A representative example is interval bisection.
First-order methodsedit
First-order methods consist of methods which make use of first-order information, e.g., interval gradients or interval slopes.
Second-order methodsedit
Second-order methods make use of second-order information, usually eigenvalue bounds derived from interval Hessian matrices. One of the most general second-order methodologies for handling problems of general type is the αΒΒ algorithm.
Deterministic global optimization solversedit
ANTIGONE: Algorithms for coNTinuous / Integer Global Optimization of Nonlinear Equations).[4] It is a proprietary software, available through ANTIGONE the GAMS modelling platform.[5]
Couenne: Convex Over and Under ENvelopes for Nonlinear Estimation (Couenne) is an open-source library [8]
EAGO: Easy-Advanced Global Optimization (EAGO) [9] is an open-source solver in Julia (programming language). It is developed by the University of Connecticut.[10]
LINDO (Linear, Interactive, and Discrete Optimizer) includes global optimization capabilities.[11]
MAiNGO: McCormick-based Algorithm for mixed-integer Nonlinear Global Optimization (MAiNGO) [12] is a C++ package with MPI and openMP parallelization and provided open-source [13] under Eclipse Public License - v 2.0.
Octeract Engine is a proprietary solver with parallelization capabilities. It is developed and licensed by Octeract [14]
SCIP: SCIP is an open-source suite of optimization solvers which among others solves mixed integer nonlinear programming (MINLP) [15]
Referencesedit
^Complete Search in Continuous Global Optimization and Constraint Satisfaction, Acta Numerica 2004 (A. Iserles, ed.), Cambridge University Press 2004
^Computability of global solutions to factorable nonconvex programs: Part I – Convex underestimating problems, Mathematical Programming, 1976, 1(10), 147–175
^Hansen, E.R. Global optimization using interval analysis, Marcel Dekker Inc, New York 1992
^Misener, Ruth; Floudas, Christodoulos A. (2014). "ANTIGONE: Algorithms for coNTinuous / Integer Global Optimization of Nonlinear Equations". Journal of Global Optimization. 59 (2–3): 503–526. doi:10.1007/s10898-014-0166-2. hdl:10044/1/15506. S2CID 41823802.
^ANTIGONE documentation in GAMS, 16 Apr 2013, retrieved 27 July 2019
^. Archived from the original on 2013-06-29. Retrieved 2016-01-26.
^Wilhelm, M. E.; Stuber, M. D. (2020). "EAGO.jl: easy advanced global optimization in Julia". Optimization Methods and Software. 37 (2): 425–450. doi:10.1080/10556788.2020.1786566. S2CID 225503302.
deterministic, global, optimization, branch, numerical, optimization, which, focuses, finding, global, solutions, optimization, problem, whilst, providing, theoretical, guarantees, that, reported, solution, indeed, global, within, some, predefined, tolerance, . Deterministic global optimization is a branch of numerical optimization which focuses on finding the global solutions of an optimization problem whilst providing theoretical guarantees that the reported solution is indeed the global one within some predefined tolerance The term deterministic global optimization typically refers to complete or rigorous see below optimization methods Rigorous methods converge to the global optimum in finite time Deterministic global optimization methods are typically used when locating the global solution is a necessity i e when the only naturally occurring state described by a mathematical model is the global minimum of an optimization problem when it is extremely difficult to find a feasible solution or simply when the user desires to locate the best possible solution to a problem Contents 1 Overview 2 Classes of deterministic global optimization problems 2 1 Linear programming problems LP 2 2 Mixed integer linear programming problems MILP 2 3 Non linear programming problems NLP 2 4 Mixed integer non linear programming problems MINLP 3 Zero order methods 4 First order methods 5 Second order methods 6 Deterministic global optimization solvers 7 ReferencesOverview editNeumaier 1 classified global optimization methods in four categories depending on their degree of rigour with which they approach the optimum as follows An incomplete method uses clever intuitive heuristics for searching but has no safeguards if the search gets stuck in a local minimum An asymptotically complete method reaches a global minimum with certainty or at least with probability one if allowed to run indefinitely long but has no means to know when a global minimizer has been found A complete method reaches a global minimum with certainty assuming exact computations and indefinitely long run time and knows after a finite time that an approximate global minimizer has been found to within prescribed tolerances A rigorous method reaches a global minimum with certainty and within given tolerances even in the presence of rounding errors except in near degenerate cases where the tolerances may be exceeded Deterministic global optimization methods typically belong to the last two categories Note that building a rigorous piece of software is extremely difficult as the process requires that all the dependencies are also coded rigorously Deterministic global optimization methods require ways to rigorously bound function values over regions of space One could say that a main difference between deterministic and non deterministic methods in this context is that the former perform calculations over regions of the solution space whereas the latter perform calculations on single points This is either done by exploiting particular functional forms e g McCormick relaxations 2 or using interval analysis in order to work with more general functional forms In any case bounding is required which is why deterministic global optimization methods cannot give a rigorous result when working with black box code unless that code is explicitly written to also return function bounds For this reason it is common for problems in deterministic global optimization to be represented using a computational graph as it is straightforward to overload all operators such that the resulting function values or derivatives yield interval rather than scalar results Classes of deterministic global optimization problems editLinear programming problems LP edit Linear programming problems are a highly desirable formulation for any practical problem The reason is that with the rise of interior point algorithms it is possible to efficiently solve very large problems involving hundreds of thousands or even millions of variables to global optimality Linear programming optimization problems strictly fall under the category of deterministic global optimization Mixed integer linear programming problems MILP edit Much like linear programming problems MILPs are very important when solving decision making models Efficient algorithms for solving complex problems of this type are known and are available in the form of solvers such as CPLEX Non linear programming problems NLP edit Non linear programming problems are extremely challenging in deterministic global optimization The order of magnitude that a modern solver can be expected to handle in reasonable time is roughly 100 to a few hundreds of non linear variables At the time of this writing there exist no parallel solvers for the deterministic solution of NLPs which accounts for the complexity gap between deterministic LP and NLP programming Mixed integer non linear programming problems MINLP edit Even more challenging than their NLP counterparts deterministically solving an MINLP problem can be very difficult Techniques such as integer cuts or branching a problem on its integer variables hence creating NLP sub problems which can in turn be solved deterministically are commonly used Zero order methods editZero order methods consist of methods which make use of zero order interval arithmetic 3 A representative example is interval bisection First order methods editFirst order methods consist of methods which make use of first order information e g interval gradients or interval slopes Second order methods editSecond order methods make use of second order information usually eigenvalue bounds derived from interval Hessian matrices One of the most general second order methodologies for handling problems of general type is the aBB algorithm Deterministic global optimization solvers editANTIGONE Algorithms for coNTinuous Integer Global Optimization of Nonlinear Equations 4 It is a proprietary software available through ANTIGONE the GAMS modelling platform 5 BARON BARON is available under the AIMMS AMPL and GAMS modeling language and on the NEOS Server 6 It is a proprietary software 7 Couenne Convex Over and Under ENvelopes for Nonlinear Estimation Couenne is an open source library 8 EAGO Easy Advanced Global Optimization EAGO 9 is an open source solver in Julia programming language It is developed by the University of Connecticut 10 LINDO Linear Interactive and Discrete Optimizer includes global optimization capabilities 11 MAiNGO McCormick based Algorithm for mixed integer Nonlinear Global Optimization MAiNGO 12 is a C package with MPI and openMP parallelization and provided open source 13 under Eclipse Public License v 2 0 Octeract Engine is a proprietary solver with parallelization capabilities It is developed and licensed by Octeract 14 SCIP SCIP is an open source suite of optimization solvers which among others solves mixed integer nonlinear programming MINLP 15 References edit Complete Search in Continuous Global Optimization and Constraint Satisfaction Acta Numerica 2004 A Iserles ed Cambridge University Press 2004 Computability of global solutions to factorable nonconvex programs Part I Convex underestimating problems Mathematical Programming 1976 1 10 147 175 Hansen E R Global optimization using interval analysis Marcel Dekker Inc New York 1992 Misener Ruth Floudas Christodoulos A 2014 ANTIGONE Algorithms for coNTinuous Integer Global Optimization of Nonlinear Equations Journal of Global Optimization 59 2 3 503 526 doi 10 1007 s10898 014 0166 2 hdl 10044 1 15506 S2CID 41823802 ANTIGONE documentation in GAMS 16 Apr 2013 retrieved 27 July 2019 BARON on the NEOS Server Archived from the original on 2013 06 29 Retrieved 2016 01 26 The optimization firm P Belotti C Kirches S Leyffer J Linderoth J Luedtke and A Mahajan 2013 Mixed integer nonlinear optimization Acta Numerica 22 pp 1 131 doi 10 1017 S0962492913000032 http journals cambridge org abstract S0962492913000032 Wilhelm M E Stuber M D 2020 EAGO jl easy advanced global optimization in Julia Optimization Methods and Software 37 2 425 450 doi 10 1080 10556788 2020 1786566 S2CID 225503302 EAGO source code GitHub Linus E Schrage Linear Integer and Quadratic Programming with Lindo Scientific Press 1986 ISBN 0894260901 http permalink avt rwth aachen de id 729717 McCormick based Algorithm for mixed integer Nonlinear Global Optimization MAiNGO a href Template Cite web html title Template Cite web cite web a Check url value help https git rwth aachen de avt svt public maingo MAiNGO source code a href Template Cite web html title Template Cite web cite web a Check url value help https octeract com documentation Octeract a href Template Cite web html title Template Cite web cite web a Check url value help http https www scipopt org SCIP optimization suite a href Template Cite web html title Template Cite web cite web a Check url value help Retrieved from https en wikipedia org w index php title Deterministic global optimization amp oldid 1160984992, wikipedia, wiki, book, books, library,
