Most alpaqa solvers deal with problems in the following form:
\[ \begin{equation}\tag{P}\label{eq:problem_main} \begin{aligned} & \underset{x}{\text{minimize}} & & f(x) &&&& f : \Rn \rightarrow \R \\ & \text{subject to} & & \underline{x} \le x \le \overline{x} \\ &&& \underline{z} \le g(x) \le \overline{z} &&&& g : \Rn \rightarrow \Rm \end{aligned} \end{equation} \]
\( f \) is called the cost or objective function, and \( g \) is the constraints function.
The solver needs to be able to evaluate the following required functions and derivatives:
Usually, automatic differentiation (AD) is used to evaluate the gradients and gradient-vector products. Many AD software packages are available, see e.g. https://autodiff.org/ for an overview.
Additionally, the solver needs to be able to project onto the rectangular sets
\[ \begin{equation} \begin{aligned} C &\;\defeq\; \defset{x \in \Rn}{\underline{x} \le x \le \overline{x}}, \\ D &\;\defeq\; \defset{z \in \Rm}{\underline{z} \le z \le \overline{z}}. \end{aligned} \end{equation} \]
The alpaqa solvers access the problem functions through the API outlined in alpaqa::TypeErasedProblem.
Usually, problems are defined using C++ structs, providing the evaluations described above as public member functions. These problem structs are structurally typed, which means that they only need to provide member functions with the correct names and signatures. Inheriting from a common base class is not required.
As an example, the following struct defines a problem that can be passed to the alpaqa solvers. Detailed descriptions of each function can be found in the alpaqa::TypeErasedProblem documentation.
Convenience classes with default implementations of some of these functions are provided for common use cases:
The user can simply inherit from these classes to inject the default implementations into their problem definition, as demonstrated in the following examples.
It is highly recommended to study the C++/CustomCppProblem/main.cpp example now to see how optimization problems can be formulated in practice, before we continue with some more specialized use cases.
Some solvers can exploit information about the Hessian of the (augmented) Lagrangian of the problem. To use these solvers, some of the following functions are required, they should be added as member functions to your problem struct.
Matrices can be stored in a dense format, in compressed sparse column storage (CCS) format, or in sparse coordinate list format (COO). Solvers convert the input to a format that they support, so some performance could be gained by choosing the appropriate storage type, because conversions may involve sorting indices and permuting the nonzero values. See alpaqa::sparsity for details. For sparse symmetric Hessian matrices, only the upper-triangular part is stored. Dense matrices are always stored in full, even if they are symmetric. The matrix evaluation functions only overwrite the nonzero values, vectorized by column.
Some solvers do not require the full Hessian matrices, but use Hessian-vector products only, for example when using Newton-CG. These products can often be computed efficiently using automatic differentiation, at a computational cost that's not much higher than a gradient evaluation.
The TypeErasedProblem class provides functions to query which optional problem functions are available. For example, provides_eval_jac_g returns true if the problem provides an implementation for eval_jac_g. Calling an optional function that is not provided results in an alpaqa::not_implemented_error exception being thrown.
In practice, the solvers do not always evaluate the functions \( f(x) \) and \( g(x) \) directly. Instead, they evaluate the Lagrangian and augmented Lagrangian functions of the problem. In many applications, such as single-shooting optimal control problems, some computations are common to the evaluation of both \( f(x) \) and \( g(x) \), and significant speedups can be achieved by providing implementations that evaluate both at the same time, or even compute the (augmented) Lagrangian directly. Similarly, when using automatic differentiation, evaluation of the gradient \( \nabla f(x) \) produces the function value \( f(x) \) as a byproduct, motivating the simultaneous evaluation of these quantities as well.
The full list of these combined evaluations can be found in the TypeErasedProblem documentation. They can be provided in the same fashion as eval_f above.
In addition to standard box constraints on the variables, some solvers also allow the addition of a possibly non-smooth, proximal term to the objective.
\[ \begin{equation}\tag{P-prox}\label{eq:problem_prox} \begin{aligned} & \underset{x}{\text{minimize}} & & f(x) + h(x) &&&& f : \Rn \rightarrow \R,\;\; h : \Rn \rightarrow \overline{\R} \\ & \text{subject to} & & \underline{z} \le g(x) \le \overline{z} &&&& g : \Rn \rightarrow \Rm \end{aligned} \end{equation} \]
By selecting
\[ h(x) = \delta_C(x) \;\defeq\; \begin{cases} 0 & \text{if } x \in C \\ +\infty & \text{otherwise,} \end{cases} \]
the standard NLP formulation \( \eqref{eq:problem_main} \) is recovered.
To add a custom function \( h(x) \) to the problem formulation, it suffices to implement the eval_prox_grad_step function, which computes a forward-backward step \( p = \prox_{\gamma h}\big(x - \gamma \nabla \psi(x)\big) - x \), where the current iterate \( x \), the gradient \( \nabla \psi(x) \) and a positive step size \( \gamma \) are given, and where \( \prox_{\gamma h}(z) \;\defeq\; \argmin_x \left\{ h(x) + \tfrac{1}{2\gamma} \normsq{x - z} \right\} \) denotes the proximal operator of \( h \) with step size \( \gamma \).
Note that in general, combining an arbitrary function \( h(x) \) with the box constraints \( x \in C \) is not possible. One notable exception is the \( \ell_1 \)-norm \( h(x) = \lambda\norm{x}_1 \). This choice for \( h \), in combination with the box constraints, is supported by the alpaqa::BoxConstrProblem class, by setting the alpaqa::BoxConstrProblem::l1_reg member.
The alpaqa::prox_step utility function can be used to implement eval_prox_grad_step. See Functions and operators for details.
alpaqa has a dependency-free, single-header C API that can be used to define problems in a shared library that can be dynamically loaded by the solvers.
The API is defined in dl-problem.h. The main entry point of your shared object should be a function called register_alpaqa_problem that returns a struct of type alpaqa_problem_register_t. This struct contains a pointer to the problem instance, a function pointer that will be called to clean up the problem instance, and a pointer to a struct of type alpaqa_problem_functions_t, which contains function pointers to all problem functions.
Additional user-defined arguments can be passed through a void pointer parameter of the register_alpaqa_problem function.
In C++, you could register a problem like this:
A full example can be found in problems/sparse-logistic-regression.cpp. While defining the register_alpaqa_problem in C++ is usually much more ergonomic than in plain C, the latter is also supported, as demonstrated in C++/DLProblem/main.cpp.
The problem can then be loaded using the alpaqa::dl::DLProblem class, or using the alpaqa-driver command line interface. For more details, see the two examples mentioned previously.
For interoperability with existing frameworks like CasADi and CUTEst, alpaqa provides the following problem adapters:
1.9.8