Directions

Table of Contents

• Fixed-point residual
• Restarted Broyden
• Anderson's Acceleration
• Full Broyden

Fixed-point residual

This is the most trivial choice where $d_k = -Rx_k$, but typically does not lead to high performance.

Restarted Broyden

Directions are computed according to the following procedure:

1. Inputs: $y=y_k$, $r=Rx_k$, $s=s_k$, $\bar{\theta}$, $m$ (memory)
2. Buffer: $(\mathbf{s}, \mathbf{u})$
3. Returns: Direction $d_\star$ (and updates the $(\mathbf{s}, \mathbf{u})$-buffer)
4. $d_\star \gets -r$
5. $s_\star \gets y$
6. $m'\gets$ current cursor position

1. for $i=0,\ldots, m'-1$,
   1. $s_\star \gets s_\star + \langle \mathbf{s}_i, s_\star\rangle \mathbf{u}_i$
   2. $d_\star \gets d_\star + \langle \mathbf{s}_i, d_\star\rangle \mathbf{u}_i$
2. $\theta \gets \begin{cases}1,&\text{if } |\langle s, s_\star \rangle| \geq \bar{\theta} \|s\|^2\\ \frac{\|s\|^2(1-\mathrm{sgn}(\langle s, s_\star \rangle) \bar{\theta})}{\|s\|^2-\langle s, s_\star \rangle},&\text{otherwise}\end{cases}$
3. $s_\star \gets (1-\theta)s + \theta s_\star$
4. $u_\star \gets \frac{s-s_\star}{\langle s, s_\star \rangle}$ and push it into the buffer
5. $d_\star \gets d_\star + \langle s, d_\star\rangle u_\star$
6. Add $s$ into the buffer and move the cursor forward or empty/reset it if it is full

Anderson's Acceleration

In Anderson's acceleration, we update a cache of past values of vectors $y_i$ and $s_i$.

We need to solve a linear system whose LHS matrix is $l\times m$, where $m$ is the memory length. We do so using the SVD decomposition.

The direction is computed by

$$\begin{eqnarray*} d_k = -Rx_k - (S_k-Y_k)t_k, \end{eqnarray*}$$

where $t_k$ is a solution of the linear system $Y_kt_k = Rx_k$, or, if the system does not have a solution, a solution of the corresponding least-squares problem (solved using SVD).

Matrices $Y_k$ and $S_k$ are buffers of past vectors $y_k$ and $s_k$ respectively, that is

$$\begin{eqnarray*} S_k = \begin{bmatrix} s_k & s_{k-1} & \cdots & s_{k-m+1} \end{bmatrix}\\ Y_k = \begin{bmatrix} y_k & y_{k-1} & \cdots & y_{k-m+1} \end{bmatrix} \end{eqnarray*}$$

Lastly, $R$ is the fixed point operator.

Note

All directions which require a finite-memory cache are supported by scs_direction_cache.

Full Broyden

Full Broyden method (for experimental purposes only, not recommended unless the problem is of very low dimension).