 |
Sleipnir
A linearity-exploiting reverse mode autodiff library and nonlinear program solver DSL.
|
|
Sleipnir
A linearity-exploiting reverse mode autodiff library and nonlinear program solver DSL.
|
This section documents Sleipnir's diagnostic output when the diagnostics option is set to true. We'll show the diagnostics for the following problem:
First, Sleipnir prints the user-configured exit conditions.
The user-configurable exit conditions include the error tolerance, maximum iterations, and timeout passed to the solve() call; and iteration callbacks added to the Problem returning true.
Then, Sleipnir prints the problem's size and structure.
Then, Sleipnir prints the solver selected based on that information:
Available solvers include:
After the solver takes each step, it prints a row of iteration diagnostics in a table format.
The headings are defined as follows:
| Heading | Description |
|---|---|
| iter | Iteration number |
| type | Iteration type
|
| time (ms) | Duration of iteration in milliseconds |
| error | Infinity norm of scaled KKT condition errors |
| cost | Cost function value at current iterate |
| infeas. | Constraint infeasibility at current iterate |
| complement. | Complementary slackness at current iterate (sᵀz) |
| μ | Barrier parameter |
| reg | Iteration matrix regularization |
| primal α | Primal step size |
| dual α | Dual step size |
| ↩ | Number of line search backtracks |
At the end of the solve, the solver prints time traces of itself and the autodiff.
The function evaluations are defined as follows:
| Function | Description |
|---|---|
| f(x) | Cost function value |
| ∇f(x) | Cost function gradient |
| ∇²ₓₓL | Lagrangian Hessian |
| ∇²ₓₓL_c | Constraint part of Lagrangian Hessian |
| cₑ(x) | Equality constraint value |
| ∂cₑ/∂x | Equality constraint Jacobian |
| cᵢ(x) | Inequality constraint value |
| ∂cᵢ/∂x | Inequality constraint Jacobian |
Finally, the solver prints its exit status.
Possible exit statuses include:
| Status | Value | Description |
|---|---|---|
| SUCCESS | 0 | Solved the problem to the desired tolerance. |
| CALLBACK_REQUESTED_STOP | 1 | The solver returned its solution so far after the user requested a stop. |
| TOO_FEW_DOFS | -1 | The solver determined the problem to be overconstrained and gave up. |
| LOCALLY_INFEASIBLE | -2 | The solver determined the problem to be locally infeasible and gave up. |
| GLOBALLY_INFEASIBLE | -3 | The problem setup frontend determined the problem to have an empty feasible region. |
| FACTORIZATION_FAILED | -4 | The linear system factorization failed. |
| FEASIBILITY_RESTORATION_FAILED | -5 | The solver failed to reach the desired tolerance, and feasibility restoration failed to converge. |
| NONFINITE_INITIAL_GUESS | -6 | The solver encountered nonfinite initial cost, constraints, or derivatives and gave up. |
| DIVERGING_ITERATES | -7 | The solver encountered diverging primal iterates xₖ and/or sₖ and gave up. |
| MAX_ITERATIONS_EXCEEDED | -8 | The solver returned its solution so far after exceeding the maximum number of iterations. |
| TIMEOUT | -9 | The solver returned its solution so far after exceeding the maximum elapsed wall clock time. |
Negative values indicate errors.
Cost functions and constraints can have the following orders:
For nonlinear problems, the solver calculates the Hessian of the cost function and the Jacobians of the constraints at each iteration. However, problems with lower order cost functions and constraints can be solved faster. For example, the following only need to be computed once because they're constant:
A problem is constant if:
A problem is a linear program (LP) if:
A problem is a quadratic program (QP) if:
All other problems are nonlinear programs (NLPs).
Instead of using distance (2-norm) for the cost function, use sum-of-squares. The distance calculation's square root is nonlinear and has a limited domain, whereas sum-of-squares has the same minimum, is quadratic, and has no domain restriction. In other words, use minimize(x ** 2 + y ** 2 + z ** 2) instead of minimize(hypot(x, y, z)).
Store common subexpressions in intermediate variables and reuse them instead of writing out the subexpressions each time. This ensures common subexpressions in the expression tree are only traversed and updated once.
The obvious problem formulation for minimum-time problems uses one dt shared across all timesteps.
The nonzero initial value for dt avoids a degenerate case, and the upper bound prevents the solver exploiting discretization artifacts.
This formulation can have feasibility issues though per section 15.3 "Elimination of variables" of "Numerical Optimization, 2nd Ed.". Instead, we recommend using a separate dt for each timestep, with them all equality-constrained.
1.9.8