Types

McCormick.MCType
struct MC{N, T<:RelaxTag} <: Real

MC{N, T <: RelaxTag} <: Real is the McCormick (w/ (sub)gradient) structure which is used to overload standard calculations. The fields are:

  • cv::Float64

    Convex relaxation

  • cc::Float64

    Concave relaxation

  • Intv::Interval{Float64}

    Interval bounds

  • cv_grad::SVector{N, Float64} where N

    (Sub)gradient of convex relaxation

  • cc_grad::SVector{N, Float64} where N

    (Sub)gradient of concave relaxation

  • cnst::Bool

    Boolean indicating whether the relaxations are constant over the domain. True if bounding an interval/constant. False, otherwise. This may change over the course of a calculation cnst for zero(x) is true even if x.cnst is false.

McCormick.RelaxTagType
abstract type RelaxTag

An abstract type the subtypes of which define the manner of relaxation that will be performed for each operator applied to the MC object. Currently, the struct NS which specifies that standard (Mitsos 2009) are to be used is fully supported. Limited support is provided for differentiable McCormick relaxations specified by struct Diff (Khan 2017) and struct MV struct MV (Tsoukalas 2011.) A rounding-safe implementation of the standard McCormick relaxations is specified by the struct NSSafe which is work in progress.

Constructors for MC

McCormick.MCMethod

MC{N,T}(y::Interval{Float64})

Constructs McCormick relaxation with convex relaxation equal to y.lo and concave relaxation equal to y.hi.

MC{N,T}(y::Float64)

Constructs McCormick relaxation with convex relaxation equal to y and concave relaxation equal to y.

MC{N,T}(cv::Float64, cc::Float64)

Constructs McCormick relaxation with convex relaxation equal to cv and concave relaxation equal to cc.

MC{N,T}(val::Float64, Intv::Interval{Float64}, i::Int64)

Constructs McCormick relaxation with convex relaxation equal to val, concave relaxation equal to val, interval bounds of Intv, and a unit subgradient with nonzero's ith dimension of length N.

Internal Utilities

McCormick.mid3Function
mid3(x::Float64, y::Float64, z::Float64) -> Tuple{Float64, Int64}

Calculates the middle of three numbers returning the value and the index where x >= y.

McCormick.mid3vFunction
mid3v(x::Float64, y::Float64, z::Float64) -> Float64

Calculates the middle of three numbers (x,y,z) returning the value where x <= y.

McCormick.mid_gradFunction
mid_grad(cc_grad::SArray{Tuple{N}, Float64, 1, N}, cv_grad::SArray{Tuple{N}, Float64, 1, N}, id::Int64) -> Any

Takes the concave relaxation gradient 'ccgrad', the convex relaxation gradient 'cvgrad', and the index of the midpoint returned 'id' and outputs the appropriate gradient according to McCormick relaxation rules.

McCormick.dline_segFunction
dline_seg(f::Function, df::Function, x::Float64, xL::Float64, xU::Float64) -> Tuple{Any, Any}

Calculates the value of the slope line segment between (xL, f(xL)) and (xU, f(xU)) defaults to evaluating the derivative of the function if the interval is tight.

McCormick.seed_gradientFunction
seed_gradient(j::Int64, x::Val{N}) -> Any

Creates a x::SVector{N,Float64} object that is one at x[j] and zero everywhere else.

McCormick.cutFunction
cut(xL::Float64, xU::Float64, cv::Float64, cc::Float64, cv_grad::SArray{Tuple{N}, Float64, 1, N}, cc_grad::SArray{Tuple{N}, Float64, 1, N}) -> Tuple{Float64, Float64, Any, Any}

Refines convex/concave relaxations cv and cc with associated subgradients cv_grad and cc_grad by intersecting them with the interval boudns xL and xU.

McCormick.secantFunction
secant(x0::Float64, x1::Float64, xL::Float64, xU::Float64, f::Function, envp1::Float64, envp2::Float64) -> Tuple{Float64, Bool}

Defines a local 1D secant method to solve for the root of f between the bounds xL and xU using x0 and x1 as a starting points. The inputs envp1 and envp2 are the envelope calculation parameters.

McCormick.newtonFunction
newton(x0::Float64, xL::Float64, xU::Float64, f::Function, df::Function, envp1::Float64, envp2::Float64) -> Tuple{Any, Bool}

Defines a local 1D newton method to solve for the root of f between the bounds xL and xU using x0 as a starting point. The derivative of f is df. The inputs envp1 and envp2 are the envelope calculation parameters.

McCormick.golden_section_itFunction
golden_section_it(init::Int64, a::Float64, fa::Float64, b::Float64, fb::Float64, c::Float64, fc::Float64, f::Function, envp1::Float64, envp2::Float64) -> Float64

Define iteration used in golden section method. The inputs fa,fb, and fc, are the function f evaluated at a,b, and c respectively. The inputs envp1 and envp2 are the envelope calculation parameters. The value init is the iteration number of the golden section method.

McCormick.golden_sectionFunction
golden_section(xL::Float64, xU::Float64, f::Function, envp1::Float64, envp2::Float64) -> Float64

Defines a local 1D golden section method to solve for the root of f between the bounds xL and xU using x0 as a starting point. Define iteration used in golden section method. The inputs envp1 and envp2 are the envelope calculation parameters.

(Under development) MCNoGrad

A handful of applications make use of McCormick relaxations directly without the need for subgradients. We are currently adding support for a McCormick struct which omits subgradient propagation in favor of return a MCNoGrad object and associated derivative information. This is currently under development and likely lacking key functionality.

McCormick.MCNoGradType
struct MCNoGrad <: Real

MCNoGrad <: Real is a McCormick structure without RelaxType Tag or subgradients. This structure is used for source-code transformation approaches to constructing McCormick relaxations. Methods definitions and calls should specify the relaxation type used (i.e.) +(::NS, x::MCNoGrad, y::MCNoGrad).... Moreover, the kernel associated with this returns all intermediate calculations necessary to compute subgradient information whereas the overloading calculation simply returns the MCNoGrad object. For univariate calculations without tiepoints such as we log2(::NS, x::MCNoGrad)::MCNoGrad whereas log2_kernel(::NS, x::MCNoGrad, ::Bool) = (::MCNoGrad, cv_id::Int, cc_id::Int, dcv, dcc). Univariate NS functions follow convention (MCNoGrad, cvid, ccid, dcv, dcc, tp1cv, tp1cc, .... tpncv, tpncc) where cv_id is the subgradient selected (1 = cv, 2 = cc, 3 = 0), dcv and dcc are derivatives (or elements of subdifferential) of the outside function evaluated per theorem at the point being evaluated and tpicv, tpicc are the ith tiepoints associated with computing the envelope of the outside function. .

  • cv::Float64

    Convex relaxation

  • cc::Float64

    Concave relaxation

  • Intv::Interval{Float64}

    Interval bounds

  • cnst::Bool

    Boolean indicating whether the relaxations are constant over the domain. True if bounding an interval/constant. False, otherwise. This may change over the course of a calculation cnst for zero(x) is true even if x.cnst is false.

McCormick.MCNoGradMethod

MCNoGrad(y::Float64)

Constructs McCormick relaxation with convex relaxation equal to y and concave relaxation equal to y.

McCormick.MCNoGradMethod

MCNoGrad(y::Interval{Float64})

Constructs McCormick relaxation with convex relaxation equal to y.lo and concave relaxation equal to y.hi.

McCormick.MCNoGradMethod

MCNoGrad(cv::Float64, cc::Float64)

Constructs McCormick relaxation with convex relaxation equal to cv and concave relaxation equal to cc.