Inner solvers

This page provides a high level overview of the inner solvers supported by alpaqa, and how to use them.

Forward-backward iterations

Both PANOC [4] and PANTR solve problems of the form

$$\begin{array}{}\text{(P)}& \begin{array}{r}\underset{x}{\text{minimize}}\psi (x)+h(x)\psi :{\mathrm{I}\mathrm{R}}^n\to \mathrm{I}\mathrm{R},h:{\mathrm{I}\mathrm{R}}^n\to \overline{\mathrm{I}\mathrm{R}}\end{array}\end{array}$$

where $\psi$ is (locally) Lipschitz-smooth and $h$ is proper, lowersemicontinuous and convex. Note that the (possibly nonsmooth) term $h$ can be used to encode constraints or include a regularization term.

A well-known strategy for solving $\text{(P)}$ consists of iteratively applying the forward-backward operator

$$\begin{array}{}\text{(FB)}& T_{\gamma }(x)={\mathbf{prox}}_{\gamma h}(x-\gamma \mathrm{\nabla }\psi (x)),\end{array}$$

where ${\mathbf{prox}}_{\gamma h}(x)={\mathbf{arg}\mathbf{min}}_u\{h(u)+\frac{1}{2\gamma }\Vert u-x{\Vert }^2\}$ denotes the proximal operator of $h$ with step size $\gamma$. Remark that this scheme only requires evaluations of $\mathrm{\nabla }\psi$ and ${\mathbf{prox}}_{\gamma h}$, which are assumed to be efficiently evaluated. Using the same oracle, both PANOC and PANTR aim to accelerate the standard forward-backward iterations $\text{(FB)}$.

PANOC

PANOC [4] combines forward-backward iterations $\text{(FB)}$ with a quasi-Newton linesearch procedure to attain fast asymptotic convergence.

TO DO: API

PANTR

PANTR is similar to PANOC, but replaces the quasi-Newton directions by solutions to trust-region subproblems, which can be seen as regularized Newton updates.

TO DO: API