Nonlinear Modeling

Model()

The core datastructure for representing a nonlinear optimization problem.

It has the following fields:

• objective::Union{Nothing,Expression} : holds the nonlinear objective function, if one exists, otherwise nothing.
• expressions::Vector{Expression} : a vector of expressions in the model.
• constraints::OrderedDict{ConstraintIndex,Constraint} : a map from ConstraintIndex to the corresponding Constraint. An OrderedDict is used instead of a Vector to support constraint deletion.
• parameters::Vector{Float64} : holds the current values of the parameters.
• operators::OperatorRegistry : stores the operators used in the model.

ExpressionIndex

An index to a nonlinear expression that is returned by add_expression.

Given data::Model and ex::ExpressionIndex, use data[ex] to retrieve the corresponding Expression.

add_expression(model::Model, expr)::ExpressionIndex

Parse expr into a Expression and add to model. Returns an ExpressionIndex that can be interpolated into other input expressions.

expr must be a type that is supported by parse_expression.

Example

julia> model = MOI.Nonlinear.Model();

julia> x = MOI.VariableIndex(1);

julia> ex = MOI.Nonlinear.add_expression(model, :($x^2 + 1))
MathOptInterface.Nonlinear.ExpressionIndex(1)

julia> MOI.Nonlinear.set_objective(model, :(sqrt($ex)))

ParameterIndex

An index to a nonlinear parameter that is returned by add_parameter. Given data::Model and p::ParameterIndex, use data[p] to retrieve the current value of the parameter and data[p] = value to set a new value.

add_parameter(model::Model, value::Float64)::ParameterIndex

Add a new parameter to model with the default value value. Returns a ParameterIndex that can be interpolated into other input expressions and used to modify the value of the parameter.

Example

julia> model = MOI.Nonlinear.Model()
A Nonlinear.Model with:
 0 objectives
 0 parameters
 0 expressions
 0 constraints

julia> x = MOI.VariableIndex(1)
MOI.VariableIndex(1)

julia> p = MOI.Nonlinear.add_parameter(model, 1.2)
MathOptInterface.Nonlinear.ParameterIndex(1)

julia> c = MOI.Nonlinear.add_constraint(model, :($x^2 - $p), MOI.LessThan(0.0))
MathOptInterface.Nonlinear.ConstraintIndex(1)

set_objective(model::Model, obj)::Nothing

Parse obj into a Expression and set as the objective function of model.

obj must be a type that is supported by parse_expression.

To remove the objective, pass nothing.

Example

julia> model = MOI.Nonlinear.Model()
A Nonlinear.Model with:
 0 objectives
 0 parameters
 0 expressions
 0 constraints

julia> x = MOI.VariableIndex(1)
MOI.VariableIndex(1)

julia> MOI.Nonlinear.set_objective(model, :($x^2 + 1))

julia> MOI.Nonlinear.set_objective(model, x)

julia> MOI.Nonlinear.set_objective(model, nothing)

ConstraintIndex

An index to a nonlinear constraint that is returned by add_constraint.

Given data::Model and c::ConstraintIndex, use data[c] to retrieve the corresponding Constraint.

add_constraint(
    model::Model,
    func,
    set::Union{
        MOI.GreaterThan{Float64},
        MOI.LessThan{Float64},
        MOI.Interval{Float64},
        MOI.EqualTo{Float64},
    },
)

Parse func and set into a Constraint and add to model. Returns a ConstraintIndex that can be used to delete the constraint or query solution information.

Example

julia> model = MOI.Nonlinear.Model();

julia> x = MOI.VariableIndex(1);

julia> c = MOI.Nonlinear.add_constraint(model, :($x^2), MOI.LessThan(1.0))
MathOptInterface.Nonlinear.ConstraintIndex(1)

delete(model::Model, c::ConstraintIndex)::Nothing

Delete the constraint index c from model.

Example

julia> model = MOI.Nonlinear.Model()
A Nonlinear.Model with:
 0 objectives
 0 parameters
 0 expressions
 0 constraints

julia> x = MOI.VariableIndex(1)
MOI.VariableIndex(1)

julia> c = MOI.Nonlinear.add_constraint(model, :($x^2), MOI.LessThan(1.0))
MathOptInterface.Nonlinear.ConstraintIndex(1)

julia> model
A Nonlinear.Model with:
 0 objectives
 0 parameters
 0 expressions
 1 constraint

julia> MOI.Nonlinear.delete(model, c)

julia> model
A Nonlinear.Model with:
 0 objectives
 0 parameters
 0 expressions
 0 constraints

OperatorRegistry()

Create a new OperatorRegistry to store and evaluate univariate and multivariate operators.

DEFAULT_UNIVARIATE_OPERATORS

The list of univariate operators that are supported by default.

Example

julia> MOI.Nonlinear.DEFAULT_UNIVARIATE_OPERATORS
73-element Vector{Symbol}:
 :+
 :-
 :abs
 :sign
 :sqrt
 :cbrt
 :abs2
 :inv
 :log
 :log10
 ⋮
 :airybi
 :airyaiprime
 :airybiprime
 :besselj0
 :besselj1
 :bessely0
 :bessely1
 :erfcx
 :dawson

DEFAULT_MULTIVARIATE_OPERATORS

The list of multivariate operators that are supported by default.

Example

julia> MOI.Nonlinear.DEFAULT_MULTIVARIATE_OPERATORS
9-element Vector{Symbol}:
 :+
 :-
 :*
 :^
 :/
 :ifelse
 :atan
 :min
 :max

register_operator(
    model::Model,
    op::Symbol,
    nargs::Int,
    f::Function,
    [∇f::Function],
    [∇²f::Function],
)

Register the user-defined operator op with nargs input arguments in model.

Univariate functions

• f(x::T)::T must be a function that takes a single input argument x and returns the function evaluated at x. If ∇f and ∇²f are not provided, f must support any Real input type T.
• ∇f(x::T)::T is a function that takes a single input argument x and returns the first derivative of f with respect to x. If ∇²f is not provided, ∇f must support any Real input type T.
• ∇²f(x::T)::T is a function that takes a single input argument x and returns the second derivative of f with respect to x.

Multivariate functions

• f(x::T...)::T must be a function that takes a nargs input arguments x and returns the function evaluated at x. If ∇f and ∇²f are not provided, f must support any Real input type T.
• ∇f(g::AbstractVector{T}, x::T...)::T is a function that takes a cache vector g of length length(x), and fills each element g[i] with the partial derivative of f with respect to x[i].
• ∇²f(H::AbstractMatrix, x::T...)::T is a function that takes a matrix H and fills the lower-triangular components H[i, j] with the Hessian of f with respect to x[i] and x[j] for i >= j.

Notes for multivariate Hessians

• H has size(H) == (length(x), length(x)), but you must not access elements H[i, j] for i > j.
• H is dense, but you do not need to fill structural zeros.

register_operator_if_needed(
    registry::OperatorRegistry,
    op::Symbol,
    nargs::Int,
    f::Function;
)

Similar to register_operator, but this function warns if the function is not registered, and skips silently if it already is.

assert_registered(registry::OperatorRegistry, op::Symbol, nargs::Int)

Throw an error if op is not registered in registry with nargs arguments.

check_return_type(::Type{T}, ret::S) where {T,S}

Overload this method for new types S to throw an informative error if a user-defined function returns the type S instead of T.

eval_univariate_function(
    registry::OperatorRegistry,
    op::Union{Symbol,Integer},
    x::T,
) where {T}

Evaluate the operator op(x)::T, where op is a univariate function in registry.

If op isa Integer, then op is the index in registry.univariate_operators[op].

Example

julia> r = MOI.Nonlinear.OperatorRegistry();

julia> MOI.Nonlinear.eval_univariate_function(r, :abs, -1.2)
1.2

julia> r.univariate_operators[3]
:abs

julia> MOI.Nonlinear.eval_univariate_function(r, 3, -1.2)
1.2

eval_univariate_gradient(
    registry::OperatorRegistry,
    op::Union{Symbol,Integer},
    x::T,
) where {T}

Evaluate the first-derivative of the operator op(x)::T, where op is a univariate function in registry.

If op isa Integer, then op is the index in registry.univariate_operators[op].

Example

julia> r = MOI.Nonlinear.OperatorRegistry();

julia> MOI.Nonlinear.eval_univariate_gradient(r, :abs, -1.2)
-1.0

julia> r.univariate_operators[3]
:abs

julia> MOI.Nonlinear.eval_univariate_gradient(r, 3, -1.2)
-1.0

eval_univariate_function_and_gradient(
    registry::OperatorRegistry,
    op::Union{Symbol,Integer},
    x::T,
)::Tuple{T,T} where {T}

Evaluate the function and first-derivative of the operator op(x)::T, where op is a univariate function in registry.

If op isa Integer, then op is the index in registry.univariate_operators[op].

Example

julia> r = MOI.Nonlinear.OperatorRegistry();

julia> MOI.Nonlinear.eval_univariate_function_and_gradient(r, :abs, -1.2)
(1.2, -1.0)

julia> r.univariate_operators[3]
:abs

julia> MOI.Nonlinear.eval_univariate_function_and_gradient(r, 3, -1.2)
(1.2, -1.0)

eval_univariate_hessian(
    registry::OperatorRegistry,
    op::Union{Symbol,Integer},
    x::T,
) where {T}

Evaluate the second-derivative of the operator op(x)::T, where op is a univariate function in registry.

If op isa Integer, then op is the index in registry.univariate_operators[op].

Example

julia> r = MOI.Nonlinear.OperatorRegistry();

julia> MOI.Nonlinear.eval_univariate_hessian(r, :sin, 1.0)
-0.8414709848078965

julia> r.univariate_operators[16]
:sin

julia> MOI.Nonlinear.eval_univariate_hessian(r, 16, 1.0)
-0.8414709848078965

julia> -sin(1.0)
-0.8414709848078965

eval_multivariate_function(
    registry::OperatorRegistry,
    op::Symbol,
    x::AbstractVector{T},
) where {T}

Evaluate the operator op(x)::T, where op is a multivariate function in registry.

eval_multivariate_gradient(
    registry::OperatorRegistry,
    op::Symbol,
    g::AbstractVector{T},
    x::AbstractVector{T},
) where {T}

Evaluate the gradient of operator g .= ∇op(x), where op is a multivariate function in registry.

eval_multivariate_hessian(
    registry::OperatorRegistry,
    op::Symbol,
    H::AbstractMatrix,
    x::AbstractVector{T},
)::Bool where {T}

Evaluate the Hessian of operator ∇²op(x), where op is a multivariate function in registry.

The Hessian is stored in the lower-triangular part of the matrix H.

Returns a Bool indicating whether non-zeros were stored in the matrix.

eval_logic_function(
    registry::OperatorRegistry,
    op::Symbol,
    lhs::T,
    rhs::T,
)::Bool where {T}

Evaluate (lhs op rhs)::Bool, where op is a logic operator in registry.

eval_comparison_function(
    registry::OperatorRegistry,
    op::Symbol,
    lhs::T,
    rhs::T,
)::Bool where {T}

Evaluate (lhs op rhs)::Bool, where op is a comparison operator in registry.

Evaluator(
    model::Model,
    backend::AbstractAutomaticDifferentiation,
    ordered_variables::Vector{MOI.VariableIndex},
)

Create Evaluator, a subtype of MOI.AbstractNLPEvaluator, from Model.

AbstractAutomaticDifferentiation

An abstract type for extending Evaluator.

ExprGraphOnly() <: AbstractAutomaticDifferentiation

The default implementation of AbstractAutomaticDifferentiation. The only supported feature is :ExprGraph.

SparseReverseMode() <: AbstractAutomaticDifferentiation

An implementation of AbstractAutomaticDifferentiation that uses sparse reverse-mode automatic differentiation to compute derivatives. Supports all features in the MOI nonlinear interface.

SymbolicMode() <: AbstractAutomaticDifferentiation

A type for setting as the value of the MOI.AutomaticDifferentiationBackend() attribute to enable symbolic automatic differentiation.

struct Node
    type::NodeType
    index::Int
    parent::Int
end

A single node in a nonlinear expression tree. Used by Expression.

See the MathOptInterface documentation for information on how the nodes and values form an expression tree.

NodeType

An enum describing the possible node types. Each Node has a .index field, which should be interpreted as follows:

• NODE_CALL_MULTIVARIATE: the index into operators.multivariate_operators
• NODE_CALL_UNIVARIATE: the index into operators.univariate_operators
• NODE_LOGIC: the index into operators.logic_operators
• NODE_COMPARISON: the index into operators.comparison_operators
• NODE_MOI_VARIABLE: the value of MOI.VariableIndex(index) in the user's space of the model.
• NODE_VARIABLE: the 1-based index of the internal vector
• NODE_VALUE: the index into the .values field of Expression
• NODE_PARAMETER: the index into data.parameters
• NODE_SUBEXPRESSION: the index into data.expressions

struct Expression
    nodes::Vector{Node}
    values::Vector{Float64}
end

The core type that represents a nonlinear expression. See the MathOptInterface documentation for information on how the nodes and values form an expression tree.

struct Constraint
    expression::Expression
    set::Union{
        MOI.LessThan{Float64},
        MOI.GreaterThan{Float64},
        MOI.EqualTo{Float64},
        MOI.Interval{Float64},
    }
end

A type to hold information relating to the nonlinear constraint f(x) in S, where f(x) is defined by .expression, and S is .set.

adjacency_matrix(nodes::Vector{Node})

Compute the sparse adjacency matrix describing the parent-child relationships in nodes.

The element (i, j) is true if there is an edge from node[j] to node[i]. Since we get a column-oriented matrix, this gives us a fast way to look up the edges leaving any node (that is, the children).

parse_expression(data::Model, input)::Expression

Parse input into a Expression.

parse_expression(
    data::Model,
    expr::Expression,
    input::Any,
    parent_index::Int,
)::Expression

Parse input into a Expression, and add it to expr as a child of expr.nodes[parent_index]. Existing subexpressions and parameters are stored in data.

You can extend parsing support to new types of objects by overloading this method with a different type on input::Any.

convert_to_expr(data::Model, expr::Expression)

Convert the Expression expr into a Julia Expr.

• subexpressions are represented by a ExpressionIndex object.
• parameters are represented by a ParameterIndex object.
• variables are represented by an MOI.VariableIndex object.

convert_to_expr(
    evaluator::Evaluator,
    expr::Expression;
    moi_output_format::Bool,
)

Convert the Expression expr into a Julia Expr.

If moi_output_format = true:

• subexpressions will be converted to Julia Expr and substituted into the output expression.
• the current value of each parameter will be interpolated into the expression
• variables will be represented in the form x[MOI.VariableIndex(i)]

If moi_output_format = false:

• subexpressions will be represented by a ExpressionIndex object.
• parameters will be represented by a ParameterIndex object.
• variables will be represented by an MOI.VariableIndex object.

ordinal_index(evaluator::Evaluator, c::ConstraintIndex)::Int

Return the 1-indexed value of the constraint index c in evaluator.

Example

julia> model = MOI.Nonlinear.Model()
A Nonlinear.Model with:
 0 objectives
 0 parameters
 0 expressions
 0 constraints

julia> x = MOI.VariableIndex(1)
MOI.VariableIndex(1)

julia> c1 = MOI.Nonlinear.add_constraint(model, :($x^2), MOI.LessThan(1.0))
MathOptInterface.Nonlinear.ConstraintIndex(1)

julia> c2 = MOI.Nonlinear.add_constraint(model, :($x^2), MOI.LessThan(1.0))
MathOptInterface.Nonlinear.ConstraintIndex(2)

julia> evaluator = MOI.Nonlinear.Evaluator(model)
Nonlinear.Evaluator with available features:
  * :ExprGraph

julia> MOI.initialize(evaluator, Symbol[])

julia> MOI.Nonlinear.ordinal_index(evaluator, c2)  # Returns 2
2

julia> MOI.Nonlinear.delete(model, c1)

julia> evaluator = MOI.Nonlinear.Evaluator(model)
Nonlinear.Evaluator with available features:
  * :ExprGraph

julia> MOI.initialize(evaluator, Symbol[])

julia> MOI.Nonlinear.ordinal_index(evaluator, c2)  # Returns 1
1

simplify(f)

Return a simplified copy of the function f.

Example

julia> x = MOI.VariableIndex(1)
MOI.VariableIndex(1)

julia> f = MOI.ScalarNonlinearFunction(:^, Any[x, 1])
^(MOI.VariableIndex(1), (1))

julia> MOI.Nonlinear.SymbolicAD.simplify(f)
MOI.VariableIndex(1)

simplify!(f)

Simplify the function f in-place and return either the function f or a new object if f can be represented in a simpler type.

Example

julia> x = MOI.VariableIndex(1)
MOI.VariableIndex(1)

julia> f = MOI.ScalarNonlinearFunction(
           :+,
           Any[MOI.ScalarNonlinearFunction(:+, Any[1.0, x]), 2.0 * x + 3.0],
       )
+(+(1.0, MOI.VariableIndex(1)), 3.0 + 2.0 MOI.VariableIndex(1))

julia> MOI.Nonlinear.SymbolicAD.simplify!(f)
4.0 + 3.0 MOI.VariableIndex(1)

julia> f
+(1.0, MOI.VariableIndex(1), 3.0 + 2.0 MOI.VariableIndex(1))

simplify!(::Val{head}, f::MOI.ScalarNonlinearFunction)

Simplify the function f in-place and return either the function f or a new object if f can be represented in a simpler type.

Val

The head in Val{head} is taken from f.head. This function should be called as:

f = simplify!(Val(f.head), f)

Implementing a method that dispatches on head enables custom simplification rules for different operators without needing a giant switch statement.

Note

It is important that this function does not recursively call simplify!. Deal only with the immediate operator. The children arguments will already be simplified.

variables(f::Union{Real,MOI.AbstractScalarFunction})

Return a sorted list of the MOI.VariableIndex present in the function f.

Example

julia> x = MOI.VariableIndex.(1:3)
3-element Vector{MathOptInterface.VariableIndex}:
 MOI.VariableIndex(1)
 MOI.VariableIndex(2)
 MOI.VariableIndex(3)

julia> f = MOI.ScalarNonlinearFunction(:atan, Any[x[3], 2.0 * x[1]])
atan(MOI.VariableIndex(3), 0.0 + 2.0 MOI.VariableIndex(1))

julia> MOI.Nonlinear.SymbolicAD.variables(f)
2-element Vector{MathOptInterface.VariableIndex}:
 MOI.VariableIndex(1)
 MOI.VariableIndex(3)

derivative(f::Union{Real,MOI.AbstractScalarFunction}, x::MOI.VariableIndex)

Return an expression representing the partial derivative of f with respect to x.

Expression swelling

With few exceptions, the algorithm used to compute the derivative does not perform simplications. As a result, the returned expression may contain terms like *(false, g) that can be trivially simplified to false.

In most cases, you should call simplify!(derivative(f, x)) to return a simplified expression of the derivative.

Example

julia> x = MOI.VariableIndex(1)
MOI.VariableIndex(1)

julia> f = MOI.ScalarNonlinearFunction(:sin, Any[x])
sin(MOI.VariableIndex(1))

julia> df_dx = MOI.Nonlinear.SymbolicAD.derivative(f, x)
cos(MOI.VariableIndex(1))

gradient_and_hessian(
    [filter_fn::Function = x -> true,]
    f::MOI.AbstractScalarFunction,
)

Compute the symbolic gradient and Hessian of f, and return the result as a tuple of four elements:

1. x::Vector{MOI.VariableIndex}: the list of variables that appear in f
2. ∇f::Vector{Any}: a vector for the first partial derivative of f with respect to each element in x
3. H::Vector{Tuple{Int,Int}}: a vector of (row, column) tuples that list the non-zero entries in the Hessian of f
4. ∇²f::Vector{Any}: a vector of expressions, in the same order as H, for the non-zero entries in the Hessian of f

filter_fn

This argument is a function, filter_fn(::MOI.VariableIndex)::Bool that returns true if the gradient and Hessian of f should be computed with respect to it.

Use this argument to filter out constant parameters from decision variables.