Solvers

General case

The solvers in this package are based upon the approach of [1]. Suppose we are given the general regularized problem

\[\underset{x \in \mathbb{R}^n}{\text{minimize}} \quad f(x) + h(x),\]

where $f : \mathbb{R}^n \mapsto \mathbb{R}$ is continuously differentiable and $h : \mathbb{R}^n \mapsto \mathbb{R} \cup \{\infty\}$ is lower semi-continuous. Instead of solving the above directly, which is often impossible, we will solve a simplified version of it repeatedly until we reach a stationary point of the problem above. To do so, suppose we are given an iterate $x_0 \in \mathbb{R}^n$, we wish to compute a step, $s_0 \in \mathbb{R}^n$ and improve our iterate with $x_1 := x_0 + s_0$. Now, we are going to approximate the functions $f$ and $h$ around $x_0$ with simpler functions (models), which we denote respectively $\varphi(\cdot; x_0)$ and $\psi(\cdot; x_0)$ so that

\[\varphi(s; x_0) \approx f(x_0 + s) \quad \text{and} \quad \psi(s; x_0) \approx h(x_0 + s). \]

We then wish to compute the step as

\[s_0 \in \underset{s \in \mathbb{R}^n}{\argmin} \ \varphi(s; x_0) + \psi(s; x_0).\]

In order to ensure convergence and to handle the potential nonconvexity of the objective function, we either add a trust-region constraint,

\[s_0 \in \underset{s \in \mathbb{R}^n}{\argmin} \ \varphi(s; x_0) + \psi(s; x_0) \quad \text{subject to} \ \|s\| \leq \Delta,\]

or a quadratic regularization

\[s_0 \in \underset{s \in \mathbb{R}^n}{\argmin} \ \varphi(s; x_0) + \psi(s; x_0) + \tfrac{1}{2} \sigma \|s\|^2_2.\]

Solvers that work with a trust-region are TR and TRDH and the ones working with a quadratic regularization are R2, R2N and R2DH

The models for the smooth part f in this package are always quadratic models of the form

\[\varphi(s; x_0) = f(x_0) + \nabla f(x_0)^T s + \tfrac{1}{2} s^T H(x_0) s,\]

where $H(x_0)$ is a symmetric matrix that can be either $0$, the Hessian of $f$ (if it exists) or a quasi-Newton approximation. Some solvers require a specific structure for $H$, for an overview, refer to the table below.

The following table gives an overview of the available solvers in the general case.

Nonlinear least-squares

This package provides two solvers, LM and LMTR, specialized for regularized, nonlinear least-squares, i.e., problems of the form

\[\underset{x \in \mathbb{R}^n}{\text{minimize}} \quad \tfrac{1}{2}\|F(x)\|_2^2 + h(x),\]

where $F : \mathbb{R}^n \mapsto \mathbb{R}^m$ is continuously differentiable and $h : \mathbb{R}^n \mapsto \mathbb{R} \cup \{\infty\}$ is lower semi-continuous. In that case, the model $\varphi$ is defined as

\[\varphi(s; x) = \tfrac{1}{2}\|F(x) + J(x)s\|_2^2,\]

where $J(x)$ is the Jacobian of $F$ at $x$. Similar to the solvers in the previous section, we either add a quadratic regularization to the model (LM) or a trust-region (LMTR). These solvers are described in [4].

Constrained Optimization

For constrained, regularized optimization,

\[\underset{x \in \mathbb{R}^n}{\text{minimize}} \quad f(x) + h(x) \quad \text{subject to} \ l \leq x \leq u \ \text{and} \ c(x) = 0,\]

an augmented Lagrangian method is provided, AL.