A Forward McCormick Operator Library
PSOR Lab | Build Status |
---|---|
Documentation | Persistent DOI |
---|---|
McCormick.jl is a component package in the EAGO ecosystem and is reexported by EAGO.jl. It contains a library of forward McCormick operators (both nonsmooth and differentiable). Documentation for this is included in the EAGO.jl package and additional usage examples are included in EAGO-notebooks as Jupyter Notebooks.
Each McCormick object is associated with a
parameter T <: RelaxTag
which is either NS
for nonsmooth relaxations (Mitsos2009, Scott2011), MV
for multivariate relaxations (Tsoukalas2014, Najman2017),
or Diff
for differentiable relaxations (Khan2016, Khan2018, Khan2019). Conversion between NS
, MV
, and Diff
relax tags are not currently supported. Convex and concave envelopes are used to compute relaxations of univariate functions.
In addition to supporting the implicit relaxation routines of Stuber 2015, this package supports the computation of convex/concave relaxations (and associated subgradients) for expressions containing the following operations:
Common Algebraic Expressions: inv
, log
, log2
, log10
, exp
, exp2
, exp10
,
sqrt
, +
, -
, ^
, min
, max
, /
, *
, abs
, step
, sign
, deg2rad
, rad2deg
, abs2
, cbrt
, fma
, xlogx
, arh
, xexpax
Trigonometric Functions: sin
, cos
, tan
, asin
, acos
, atan
, sec
, csc
, cot
, asec
, acsc
, acot
, sind
, cosd
, tand
, asind
, acosd
, atand
, secd
, cscd
, cotd
, asecd
, acscd
, acotd
, sinpi
, cospi
Hyperbolic Functions: sinh
, cosh
, tanh
, asinh
, acosh
, atanh
, sech
, csch
, coth
, acsch
, acoth
Special Functions: erf
, erfc
, erfcinv
, erfc
Activation Functions: relu
, leaky_relu
, param_relu
, sigmoid
, bisigmoid
,
softsign
, softplus
, maxtanh
, pentanh
, gelu
,
elu
, selu
, swish1
Bound Specification Functions: positive
, negative
, lower_bnd
, upper_bnd
, bnd
Other Functions: one
, zero
, intersect
, real
, dist
, eps
, <
, <=
, ==
Differentiable relaxations (Diff <: RelaxTag
) are supported for the functions given in Khan2016, Khan2018, Khan2019. However, differentiable relaxations for other nonsmooth terms listed above have yet to be developed and as such have been omitted.
In order to bound a function using a McCormick relaxation, you first construct a McCormick object (x::MC
) that bounds the input variables, and then you pass these variables to the desired function.
In the example below, convex/concave relaxations of the function
$$f(x) = x (x - 5) \sin(x)$$
are calculated at $x = 2$ on the interval $X = [1, 4]$.
using McCormick
# Create MC object for x = 2.0 on [1.0, 4.0] for relaxing
# a function f(x) on the interval Intv
f(x) = x*(x - 5.0)*sin(x)
x = 2.0 # Value of independent variable x
Intv = Interval(1.0, 4.0) # Define interval to relax over
# Note that McCormick.jl reexports IntervalArithmetic.jl
# and StaticArrays. So no using statement for these is
# necessary.
# Create McCormick object
xMC = MC{1,NS}(x, Intv, 1)
fMC = f(xMC) # Relax the function
cv = fMC.cv # Convex relaxation
cc = fMC.cc # Concave relaxation
cvgrad = fMC.cv_grad # Subgradient/gradient of convex relaxation
ccgrad = fMC.cc_grad # Subgradient/gradient of concave relaxation
Iv = fMC.Intv # Retrieve interval bounds of f(x) on Intv
Plotting the results, we can easily visualize the convex and concave relaxations, interval bounds, and affine bounds constructed using the subgradient at the middle of $X$.
This can readily be extended to multivariate functions, for example:
$$ \begin{aligned} & f(x, y) = \big(4 - 2.1 x^{2} + \frac{x^{4}}{6} \big) x^{2} + x y + (-4 + 4 y^{2}) y^{2}\ & X = [-2, 0]\ & Y = [-0.5, 0.5] \end{aligned} $$
using McCormick
# Define function
f(x, y) = (4.0 - 2.1*x^2 + (x^4)/6.0)*x^2 + x*y + (-4.0 + 4.0*y^2)*y^2
# Define intervals for independent variables
n = 30
X = Interval{Float64}(-2, 0)
Y = Interval{Float64}(-0.5, 0.5)
xrange = range(X.lo, stop=X.hi, length=n)
yrange = range(Y.lo, stop=Y.hi, length=n)
# Calculate differentiable McCormick relaxation
for (i,x) in enumerate(xrange)
for (j,y) in enumerate(yrange)
z = f(x, y) # Calculate function values
xMC = MC{1,Diff}(x, X, 1) # Differentiable relaxation for x
yMC = MC{1,Diff}(y, Y, 2) # Differentiable relaxation for y
fMC = f(xMC, yMC) # Relax the function
cv = fMC.cv # Convex relaxation
cc = fMC.cc # Concave relaxation
end
end
McCormick.jl is a component of the EAGO.jl ecosystem. Please cite the following paper when using McCormick.jl:
M. E. Wilhelm & M. D. Stuber (2022) EAGO.jl: easy advanced global optimization in Julia,
Optimization Methods and Software, 37:2, 425-450, DOI: 10.1080/10556788.2020.1786566
While McCormick.jl generally supports Julia 1.1+, some functions may return an error for Julia versions less than 1.3. In particular, cbrt
will result in a StackOverflow when called. McCormick is unit tested using Julia versions 1.3 and beyond.