EAGO: Easy-Advanced Global Optimization
EAGO is an open-source development environment for robust and global optimization in Julia.
EAGO's Optimizer Capabilities
EAGO is a deterministic global optimizer designed to address a wide variety of optimization problems by propagating McCormick relaxations along the factorable structure of each expression in the NLP. Most operators supported by modern AD packages (e.g. +, sin, cosh) are supported by EAGO and a number utilities for sanitizing native Julia code and generating relaxations on a wide variety of user-defined functions have been included. Currently, EAGO supports problems that have aprior variable bounds defined and have differentiable constraints. That is problems should be specified in the generic form below:
For each nonlinear term EAGO makes use of factorable representation to construct bounds and relaxations. In the case of F = y(y-1)sin(y), a list is generated and rules for constructing McCormick relaxations are used to formulate relaxations in the original Y decision space1:
- v1 = y
- v2 = v1 - 5
- v3 = sin(v1)
- v4 = v1v2
- v5 = v4v3
- F = v5
Either these original relaxations, differentiable McCormick relaxations2, or affine relaxations thereof can be used to construct relaxations of optimization problems useful in branch and bound routines for global optimization. Utilities are included to combine these with algorithms for relaxing implicit functions3 and forward-reverse propagation of McCormick arithmetic4.
EAGO makes use of the JuMP modeling language to. Consider the familiar "process" problem instance5:
This model can be formulated using JuMP code as
using JuMP, EAGO m = Model(EAGO.Optimizer) # Define bounded variables xL = [10.0; 0.0; 0.0; 0.0; 0.0; 85.0; 90.0; 3.0; 1.2; 145.0] xU = [2000.0; 16000.0; 120.0; 5000.0; 2000.0; 93.0; 95.0; 12.0; 4.0; 162.0] @variable(m, xL[i] <= x[i=1:10] <= xU[i]) # Define nonlinear constraints @NLconstraint(m, e1, -x*(1.12+0.13167*x-0.00667* (x)^2)+x == 0.0) @NLconstraint(m, e3, -0.001*x*x*x/(98-x)+x == 0.0) @NLconstraint(m, e4, -(1.098*x-0.038* (x)^2)-0.325*x+x == 57.425) @NLconstraint(m, e5, -(x+x)/x+x == 0.0) # Define linear constraints @constraint(m, e2, -x+1.22*x-x == 0.0) @constraint(m, e6, x+0.222*x == 35.82) @constraint(m, e7, -3*x+x == -133.0) # Define nonlinear objective @NLobjective(m, Max, 0.063*x*x - 5.04*x - 0.035*x - 10*x - 3.36*x) # Solve the optimization problem JuMP.optimize!(m)
Special handling has been included for linear/quadratic functions defined using the
@constraint macro in JuMP and these can generally be expected to perform better than specifying quadratic or linear terms with the
A Cautionary Note on Global Optimization
As a global optimization platform, EAGO's solvers can be used to find solutions of general nonconvex problems with a guaranteed certificate of optimality. However, global solvers suffer from the curse of dimensionality and therefore their performance is outstripped by convex solvers. For users interested in large-scale applications, be warned that problems generally larger than a few variables may prove challenging for certain types of global optimization problems.
The EAGO package has numerous features: a solver accessible from JuMP/MathOptInterface, domain reduction routines, McCormick relaxations, and specialized non-convex semi-infinite program solvers. A full description of all EAGO features is available in the documentation website. A series of example have been provided in the form of Jupyter notebooks in the separate EAGO-notebooks repository
- 6/14/2019: EAGO v0.2.0 has been tagged. This update creates a number of breaking changes to the EAGO API. Please review the use cases provided in the documentation to update examples.
- Updated to support Julia 1.0+, MathOptInterface (MOI), and MOI construction of subproblems.
- Additional domain reduction routines available.
- Support for specialized handling of linear and quadratic terms.
- Significant performance improvements due to pre-allocation of Wengert tapes and MOI support.
- A more intuitive API for McCormick relaxation construction.
- 7/5/2019: EAGO v0.2.1 has been tagged. This contains fixes for a few minor issues.
- Bug fix for explicit SIP solving routine that occurred for uncertainty sets of dimension greater than 1.
- Bug fix for Max objective sense.
- 11/1/2019: EAGO v0.3.0 has been tagged. This update is intended to be the last to create a large number of breaking changes to the EAGO API. Please review the use cases provided in the documentation to update examples.
- A number of performance improvements have been made to the underlying McCormick relaxation library.
- The optimizer used to construct relaxations is now modified in place.
- All subproblem storage has been moved to the Optimizer object and storage types (e.g. LowerInfo) have been removed.
- A MinMax heap structure is now used to store nodes.
- Speed and aesthetics for logging and printing utilities have been updated.
- Subroutines are now customized by creating a subtype of 'ExtensionType' and defining subroutines which dispatch on this new structure.
- Parametric interval methods and the Implicit optimizer have been move to a separate package (to be tagged shortly.)
- JIT compilation time has been reduced sub
- 6/7/2020: EAGO v0.4.0 is on the master.
- Support for new MOI/JuMP
RawParameterinput and a number of new attributes.
- Separates McCormick and ReverseMcCormick libraries (now McCormick.jl and ReverseMcCormick.jl) from main package. McCormick.jl is reexported.
- Relaxation calculations now return NaN values on a domain violation.
- Tolerance based validation of cuts has been added to generate numerically safe cuts.
- Significantly simplify internal codebase for
EAGO.Optimizer(no changes to API): fully decouples input problem specifications from the formulation used internally, stack only stores variables that are branched on, and a number of internal rearrangements to clearly delineate different routines.
- Add problem classification preprocessing that throws to simpler routines if LP problem types are detected (enables future support for SOCP, MILP, MISOCP, and Convex forms).
- Fix multiple bugs and add more transparent error codes.
- Support for new MOI/JuMP
For a full list of EAGO release news, see click here
EAGO is registered Julia package. It can be installed using the Julia package manager. From the Julia REPL, type ] to enter the Pkg REPL mode and run the following command
pkg> add EAGO
Currently, EAGO is tied to a 0.19+ or greater version of JuMP. This allows a replication of some of the internal features shared by EAGO and JuMP's AD scheme aka generation of Wergert Tapes pass evaluators between JuMP and EAGO etc.
pkg> add JuMP
EAGO v0.4.0 is the current tagged version and requires Julia 1.2+. Use with version 1.4 is recommended as the majority of in-house testing has occurred using this version of Julia. The user is directed to the High-Performance Configuration for instructions on how to install a high performance version of EAGO (rather than the basic entirely open-source version). If any issues are encountered when loading EAGO (or when using it), please submit an issue using the Github issue tracker.
Bug reporting, support and feature requests
Please report bugs or feature requests by opening an issue using the Github issue tracker. All manners of feedback are encouraged.
- Nonlinear handling assumes that box-constraints of nonlinear terms are available or can be inferred from bounds-tightening.
- Only currently supports continuous functions. Support for mixed-integer problems is forthcoming.
Work In Progress
- Extensions for nonconvex dynamic global & robust optimization.
- Provide support for mixed-integer problems.
- Update EAGO to support nonsmooth problems (requires: a nonsmooth local nlp optimizer or lexiographic AD, support for relaxations is already included).
- Performance assessment of nonlinear (differentiable) relaxations and incorporation into main EAGO routine.
- Evaluation and incorporation of implicit relaxation routines in basic solver.
Wilhelm, Matthew; Stuber, Matthew (October 2017) Easy Advanced Global Optimization (EAGO): An Open-Source Platform for Robust and Global Optimization in Julia. Presented at the AIChE Annual Meeting in Minneapolis, MN.
- ValidatedNumerics.jl, a Julia library for validated interval calculations, including basic interval extensions, constraint programming, and interval contactors
- MC++: A mature McCormick relaxation package in C++ that also includes McCormick-Taylor, Chebyshev Polyhedral and Ellipsoidal arithmetics.
- A. Mitsos, B. Chachuat, and P. I. Barton. McCormick-based relaxations of algorithms. SIAM Journal on Optimization, 20(2):573–601, 2009.
- K.A. Khan, HAJ Watson, P.I. Barton. Differentiable McCormick relaxations. Journal of Global Optimization, 67(4):687-729 (2017).
- Stuber, M.D., Scott, J.K., Barton, P.I.: Convex and concave relaxations of implicit functions. Optim. Methods Softw. 30(3), 424–460 (2015)
- A., Wechsung JK Scott, HAJ Watson, and PI Barton. Reverse propagation of McCormick relaxations. Journal of Global Optimization 63(1):1-36 (2015).
- Bracken, Jerome and McCormick, Garth P. Selected Applications of Nonlinear Programming, John Wiley and Sons, New York, 1968.