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).