Design choices and libraries' internals

This package is divided into three parts:

• Functions which represent different kinds of mathematical functions and their associated features (gradient, hessian, etc.).
• A problem class defining a whole optimization problem including some technical details (scaling).
• A solver hierarchy defining solvers that are working on a class of optimizations problem (for instance, a QP solver solves problems with a quadratic objective function and linear constraints).

The function hierarchy

The function hierarchy is an abstract hierarchy which defines meta-functions in the sense that the user has to derive from these classes to define its real function.

struct MyLinearFunction : public LinearFunction {
  // FIXME: some code is missing
};

struct MyDerivableFunction : public DerivableFunction {
  // FIXME: some code is missing
};
// etc...

Users can define as many functions as they want as long as they respect the constraints defined by the classes they inherit from:

• Any function must be able to be evaluated (through operator()).
• A derivable function has a gradient/Jacobian matrix.
• A twice-derivable function ( \(C^2\)) has a Hessian matrix.
• A quadratic function has the same constraints as a \(C^2\) function.
• A linear function has the same constraints except its Hessian matrix is null and computed automatically by the abstract class.

It is important to note that all of these functions are \(\mathbb{R}^n \rightarrow \mathbb{R}^m\) functions.

These functions have to be considered as m functions such that \(\mathbb{R}^n \rightarrow \mathbb{R}\). In particular, it means that in the gradient/Hessian methods, the second argument (integer) refers to which function you want to get the gradient/Hessian from.

It avoids useless computations when the whole Jacobian is not needed. Hence, it also avoids the use of a tensor as this structure is particularly costly and not built-in in Eigen (the matrix library the package relies on).

This set of meta-functions is completed by two generic implementations of quadratic and linear functions in respectively NumericQuadraticFunction and NumericLinearFunction. Those are real functions as the user is meant to instantiate them, not derive from them.

The problem class

The problem class defines a complete optimization problem. It is composed of:

• A \(\mathbb{R}^n \rightarrow \mathbb{R}\) cost (or objective) function.
• A set of functions constraints.
• Bounds on the input arguments.
• Bounds on the constraints functions output.
• Scaling on the input arguments.
• Scaling on the constraint functions output.

The problem class is templated by two parameters:

• The objective's function type (F).
• The set of constraint's types (C).

Those two parameters define a class of problem. For instance, a QP solver solvers problems where the objective function is quadratic and the constraints are linear.

Each class of problem matches a set of solvers designed to solve exactly those problems.

The copy constructor of the Problem class allows to make the problem more generic by replacing F or C by a more general type.

Examples:

• It is valid to convert a linear problem into a nonlinear problem and make a QP solve it.
• But, the opposite is not valid.

I.e.: you can always go higher in the function hierarchy but you cannot go deeper.

However, this transformation (as any dynamic typing) causes to forget specific information and might slow down the process. For example: solving a linear problem as a nonlinear one is slower than directly solving it with methods specific to linear problems.

The solver hierarchy

The solver hierarchy is divided into three parts:

• The generic solver.
• The solver for a class of problems.
• The bridges (the leaves in the hierarchy's tree).

Generic solver

The generic solver is an abstract class which is the root of the hierarchy. All the solvers have to inherit from this class directly or indirectly.

It only defines three methods:

• solve (virtual pure)
• getMinimum
• reset

The method solve has to fill the protected attribute result_. It is implemented by the bridges at the bottom of the hierarchy.

By default result_ contains an instance of the No_Solution class. It has to be changed to an instance of Result or SolverError.

• No_Solution: represents the fact that solve has never been called. A user should never retrieve an instance of No_Solution.
• Result: represents a valid result. Some non-critical problems might have happened and are specified in the warnings vector (minor numerical instabilities for instance).
• SolverError: indicates that the optimization has failed.

The solve method should rarely be called by the user. Instead, the user calls getMinimum which calls solve if required. If getMinimum is called several times, the problem is only solved once.

The reset method should be called when one wants to manually force the recomputation of the solution.

Solver

The Solver class is parametrized by two parameters as the Problem class. It defines an abstract solver for a class of optimization problems.

For instance, a QP should inherit from Solver<QuadraticFunction, LinearFunction>.

This level of the hierarchy integrates the notion of Problem, hence the problem method is defined to access the problem. Once a solver is created with a problem, the problem can never be modified again.

Bridges

The leaves of the hierarchy are bridges. The role of a bridge is to convert the generic representation of the problem into the solver's representation. It might also emulate some missing features of the back-end solver.

A bridge mainly implements the solve method. It may also expose the underlying solver's internal mechanism for fine tuning.