Skip to content

JuMP schemes ​

This page is for users and developers who want to know exactly which nonlinear program (NLP) a JuMP model of this package is, and how the model stores what is needed to read the state, the control and the costate back. It is not needed to use the package.

The OptimalControl modelings return the continuous problem; the discretization is chosen in solve and done by CTDirect. The JuMP modeling has no such layer: each JuMP model is an NLP. To compare JuMP and OptimalControl fairly, the JuMP models reproduce the NLP that CTDirect builds, scheme by scheme.

The continuous problem ​

Every problem is written in Bolza form, with state  , control   and a variable   (e.g. a free final time):

and are numbers or components of (free initial or final time).

The grid ​

With = grid_size, the grid is uniform:

When is free, depends on : the dynamics are then nonlinear in even for a linear system.

Indices start at on this page, as the JuMP containers do (x₁[0:N]). CTDirect counts from : its are here.

Unknowns and number of controls ​

The state is discretized at the   nodes:  . The number of controls depends on the scheme:

SchemeschemeControlsNumber of unknowns
Trapezoidal rule:trapeze (one per node)   
Explicit Euler:euler (one per step)   
Implicit Euler:euler_implicit (one per step)   
Midpoint rule:midpoint (one per step)   

For the one-step schemes, is the control on the step : there is no control "at ". With the trapezoidal rule the control is a value at each node. Everything that reads the controls back (accessors, plots, the construction of a solution) has to know which case applies.

The scheme of a JuMP model is chosen when it is built, with the names of OptimalControl.Collocation; the default is the trapezoidal rule:

julia
model = beam(JuMPBackend(); grid_size=100, scheme=:midpoint)
model[:scheme]      # :midpoint

Dynamics and cost, scheme by scheme ​

Write   and likewise. For   :

SchemeDynamicsLagrange cost
:trapeze     
:euler   
:euler_implicit   
:midpoint     

The Lagrange cost is added to the objective directly, by the quadrature of the scheme: no extra state is introduced. The Mayer term is .

The schemes as Butcher tableaux ​

The four schemes are Runge–Kutta methods, each given by its Butcher tableau with stages. A step reads

and the Lagrange cost uses the same quadrature, .

Scheme
:euler
:euler_implicit
:midpoint
:trapeze

The JuMP models have no stage unknowns: each stage is written with the nodes of its step,    . For a one-stage tableau,  , which gives , and for the explicit Euler, implicit Euler and midpoint rules; for a tableau of several stages, every stage must be a node of the step. A tableau with a stage inside the step (Hermite–Simpson, Gauss–Legendre, Radau) would need stage unknowns and is not supported.

Two properties of the tableau decide the rest:

  • stiffly accurate: the last row of is and  , so the last stage is ;

  • explicit first stage: the first row of is zero and  , so the first stage is .

A tableau with both is FSAL (First Same As Last): the last stage of a step is the first stage of the next one. Among the four schemes, only the trapezoidal rule is FSAL.

SchemeStiffly accurateExplicit first stageFSAL
:eulernoyesno
:euler_implicityesnono
:midpointnonono
:trapezeyesyesyes

With FSAL, the dynamics and the Lagrange integrand are evaluated once per node,   evaluations instead of , and the control of a stage is the control of its node, shared by the two steps around it: hence   controls. Without FSAL, each step has its own control: controls. The node used by the path constraints follows: the control of the step that starts at the node, except for a scheme whose only stage ends the step (implicit Euler), which takes the control of the step that ends at the node.

These properties are computed from the tableau, not declared, in ext/JuMPModels/schemes/tableaux.jl; the names follow the roadmap of CTDirect (CTDirect.jl#610), where the same tableaux, traits and specializations are planned.

Constraints ​

Box constraints on the state, the control and the variable are bounds of the unknowns, not constraints:   ,   ,   .

Path constraints are imposed at the   nodes, each with the control "at" that node:

SchemeNode uses
:trapeze
:euler, :midpoint for  , and at the last node
:euler_implicit at the first node, and for  

Boundary conditions    are constraints, even when they fix a component of the state (the variable is not fixed).

Exa and the number of controls

Under the :exa modeler of OptimalControl, the controls are declared at the   nodes for every scheme. For :euler, :midpoint and :euler_implicit the Exa NLP therefore has more unknowns than CTDirect's, used only by their bounds and by one extreme path constraint. See #284.

Order of the unknowns and of the constraints ​

The order of the unknowns and of the constraints changes the sparsity pattern seen by the linear solver. It is chosen when the model is built, with ordering:

  • :interleaved (default), CTDirect's order:

    • unknowns: node by node, the state then the control while there is one, (trapezoidal rule) or (one control per step), then ;

    • constraints: for each step   , the dynamics of the step then the path constraints at node ; then the path constraints at node ; then the boundary conditions.

  • :blocks, the same pieces grouped by kind:

    • unknowns: , then all the controls, then ;

    • constraints: all the dynamics, then the path constraints at the nodes , then the boundary conditions.

julia
model = beam(JuMPBackend(); grid_size=100, ordering=:blocks)
model[:ordering]    # :blocks

The NLP is the same in both orders, up to a permutation of the unknowns and of the constraints. The unknowns keep their names (x₁[3]), and model[:constraints] lists the constraints in CTDirect's order for both orderings, so the permutation can be computed from the model.

MOI groups the constraints by type

JuMP passes the constraints to the solver grouped by type: function (affine, quadratic, nonlinear) and set (equality, interval). The order of creation is kept only within a type. The dynamics, path constraints and boundary conditions of a problem are often of different types, so :blocks mostly changes the order of the unknowns.

In the code ​

A problem file declares data ​

A file of ext/JuMPModels/ fills a ProblemData and hands it to the scheme; it writes no discretization itself:

julia
data = ProblemData(;
    state=[Component("x₁"; lower=x₁_l, upper=x₁_u), Component("x₂")],
    control=[Component("u")],
    costate=["∂x₁", "∂x₂"],
    times=v -> (t0, tf),
    dynamics=(x, u, v, t) -> [x[2], u[1]],
    lagrange=(x, u, v, t) -> u[1]^2,
    boundary=[(x₁_t0, (x0, xf, v) -> x0[1], x₁_t0), (x₁_tf, (x0, xf, v) -> xf[1], x₁_tf)],
)
return build(data, grid_size, scheme, ordering, args...; init=init, kwargs...)
FieldMathematical object
state, control, variablethe components and their bounds (box constraints); the start values are those of the initial guess init of the metadata, at the nodes
times(v), numbers or expressions of
dynamics(x, u, v, t), at one node
lagrange(x, u, v, t), or nothing
cost(I, x0, xf, v)the objective given the discretized integral of (default: ), e.g. alone or  
path
boundary

The functions receive the vectors of JuMP variables of one node and return JuMP expressions: the scheme evaluates them at its stages (nodes or, for the midpoint rule, ).

Scaled models. A model written on scaled variables writes its dynamics on the scaled state, as the OptimalControl model does: for space_shuttle, with   , the dynamics of are . The JuMP NLP is then the NLP of CTDirect, row by row.

What the model stores ​

Besides the NLP, build stores in the JuMP model what is needed to read a solution back:

KeyContentUsed by
model[:x₁], … (one per state component)the unknowns of the component, a container indexed by 0:Nstate
model[:u], … (one per control component)the unknowns of the component, indexed by 0:N (trapezoidal rule) or 0:N-1 (one control per step, on )control
model[:tf], … (one per variable component)the unknownvariable, the time grid
model[:∂x₁], … (one per costate name)the dynamics constraints of the component, indexed by 1:Ncostate (their duals)
model[:scheme]the scheme, :trapeze, :euler, :euler_implicit or :midpointcontrol, solution
model[:ordering]the order of the unknowns and constraints, :interleaved or :blocksthe comparisons with CTDirect
model[:constraints]the constraints, in CTDirect's order whatever the orderingthe comparisons with CTDirect
model[:time_grid]a function returning , evaluated after the solve when is freetime_grid
model[:state_components], model[:control_components], model[:variable_components], model[:costate_components]the names above, in orderevery accessor

The accessors read these keys:

julia
model = beam(JuMPBackend(); grid_size=100)
JuMP.set_optimizer(model, Ipopt.Optimizer)
JuMP.optimize!(model)

T = time_grid(model)          # t_0, …, t_N
x = state(model)              # function of t, interpolating X_0, …, X_N
u = control(model)            # function of t: linear (trapeze) or piecewise constant
p = costate(model)            # function of t, from the duals of the dynamics constraints
objective(model), iterations(model)

The costate is read from the duals of the dynamics constraints of each component, one per step. JuMP.dual returns the MOI ConstraintDual, a convention fixed by MathOptInterface, independent of the solver and of the objective sense; the accessors return -JuMP.dual, the multiplier convention of rules/signs.md (ct-conventions, SGN1–SGN3) and of OptimalControl (#326). When the problem also exists in OptimalControl, solution(model, pb) builds a full CTModels.Solution from these values, which can be plotted like an OptimalControl solution.

With one control per step, the control is reported as CTDirect reports it: on , and again at , so that it is given at the   nodes of the grid.