Draft:Compact Representation (Optimization)

The compact representation for quasi-Newton methods is a matrix decomposition, which is typically used in gradient based optimization algorithms or for solving nonlinear systems. The decomposition uses a low-rank representation for the direct and/or inverse Hessian or the Jacobian of a nonlinear system. Because of this, the compact representation is particularly suited for large problems and constrained optimization.

The compact representation (right) of a dense Hessian approximation (left) is a initial matrix (typically diagonal) plus low rank decomposition. It has a small memory footprint (shaded areas) and enables efficient matrix computations

Definition

The compact representation of a quasi-Newton matrix for the inverse Hessian $H_{k}$ or direct Hessian $B_{k}$ of a nonlinear objective function $f(x):\mathbb {R} ^{n}\to \mathbb {R}$ is based on expressing a sequence of recursive rank-1 or rank-2 matrix updates as one rank-$k$ or rank-$2k$ update of an initial matrix . Because it is derived from quasi-Newton updates, it uses differences of iterates and gradients $\nabla f(x_{k})=g_{k}$ in its definition $\{s_{i-1}=x_{i}-x_{i-1},y_{i-1}=g_{i}-g_{i-1}\}_{i=1}^{k}$. In particular, for $r=k$ or $r=2k$ the rectangular $n\times r$ matrices $U_{k},J_{k}$ and the $r\times r$ square symmetric systems $M_{k},N_{k}$ depend on the $s_{i},y_{i}$'s and define the quasi-Newton representations

$H_{k}=H_{0}+U_{k}M_{k}^{-1}U_{k}^{T},\quad {\text{ and }}\quad B_{k}=B_{0}+J_{k}N_{k}^{-1}J_{k}^{T}$

Applications

Because of the special matrix decomposition the compact representation is implemented in state-of-the-art optimization software . When combined with limited-memory techniques it is a popular technique for constrained optimization with gradients . Linear algebra operations can be done efficiently, like mat-vecs, solves or eigendecompositions. It can be combined with line-search and trust region techniques, and the representation has been developed for many quasi-Newton updates. For instance, the matrix vector product with the direct quasi-Newton Hessian and an arbitrary vector $g\in \mathbb {R} ^{n}$ is:

${\begin{aligned}p_{k}^{(0)}&=J_{k}^{T}g\\{\text{solve}}\quad N_{k}p_{k}^{(1)}&=p_{k}^{(0)}\quad \quad {\text{(}}N_{k}{\text{ is small)}}\\p_{k}^{(2)}&=J_{k}p_{k}^{(1)}\\p_{k}^{(3)}&=H_{0}g\\p_{k}^{\phantom {(4)}}&=p_{k}^{(2)}+p_{k}^{(3)}\end{aligned}}$

Background

Walker showed that a product of Householder transformations (an identity plus rank-1) can be expressed as a compact matrix formula. This result led the authors in to derive an explicit matrix expression for the product of $k$ identity plus rank-1 matrices. Specifically, for ${\textstyle S_{k}={\begin{bmatrix}s_{0}&s_{1}&\ldots s_{k-1}\end{bmatrix}},}$ $~Y_{k}={\begin{bmatrix}y_{0}&y_{1}&\ldots y_{k-1}\end{bmatrix}},$ $~(R_{k})_{ij}=s_{i-1}^{T}y_{j-1},$ $~\rho _{i-1}=1/s_{i-1}^{T}y_{i-1}$ and ${\textstyle ~V_{i}=I-\rho _{i-1}y_{i-1}s_{i-1}^{T}}$ when $1\leq i\leq j\leq k$ the product of $k$ rank-1 updates to the identity is $$\prod _{i=1}^{k}V_{i-1}=\left(I-\rho _{0}y_{0}s_{0}^{T}\right)\cdots \left(I-\rho _{k-1}y_{k-1}s_{k-1}^{T}\right)=I-Y_{k}R_{k}^{-1}S_{k}^{T}$$ The BFGS update can be expressed in terms of products of the $V_{i}$'s, which have a compact matrix formula. Therefore, the BFGS recursion can exploit these block matrix representations

$${\begin{aligned}H_{k}&=V_{k-1}H_{k-1}V_{k-1}^{T}+\rho _{k-1}s_{k-1}s_{k-1}^{T}\\&=\left(V_{k-1}\cdots V_{1}V_{0})H_{0}(V_{0}^{T}V_{1}^{T}\cdots V_{k-1}^{T}\right)+\\&{\phantom {=}}\rho _{0}\left(V_{k-1}\cdots V_{1}\right)s_{0}s_{0}^{T}\left(V_{1}^{T}\cdots V_{k-1}^{T}\right)+\\&{\phantom {=}}\quad \vdots \\&{\phantom {=}}\rho _{k-2}V_{k-1}s_{k-2}s_{k-2}^{T}V_{k-1}^{T}+\\&{\phantom {=}}\rho _{k-1}s_{k-1}s_{k-1}^{T}\end{aligned}}$$ (1)

Recursive quasi-Newton updates

A parametric family of quasi-Newton updates includes many of the most known formulas . For arbitrary vectors $v_{k}$ and $c_{k}$ such that $v_{k}^{T}y_{k}\neq 0$ and $c_{k}^{T}s_{k}\neq 0$ general recursive update formulas for the inverse and direct Hessian estimates are

$$H_{k+1}=H_{k}+{\frac {(s_{k}-H_{k}y_{k})v_{k}^{T}+v_{k}(s_{k}-H_{k}y_{k})^{T}}{v_{k}^{T}y_{k}}}-{\frac {(s_{k}-H_{k}y_{k})^{T}y_{k}}{(v_{k}^{T}y_{k})^{2}}}v_{k}v_{k}^{T}$$ (2)

$$B_{k+1}=B_{k}+{\frac {(y_{k}-B_{k}s_{k})c_{k}^{T}+c_{k}(y_{k}-B_{k}s_{k})^{T}}{c_{k}^{T}s_{k}}}-{\frac {(y_{k}-B_{k}s_{k})^{T}s_{k}}{(c_{k}^{T}s_{k})^{2}}}c_{k}c_{k}^{T}$$ (3)

By making specific choices for the parameter vectors $v_{k}$ and $c_{k}$ well known methods are recovered

Table 1: Quasi-Newton updates parametrized by vectors $v_{k}$ and $c_{k}$

$v_{k}$	${\text{method}}$	$c_{k}$	${\text{method}}$
$s_{k}$	BFGS	$s_{k}$	PSB (Powell Symmetric Broyden)
$y_{k}$	${\text{Greenstadt's}}$	$y_{k}$	DFP
$s_{k}-H_{k}y_{k}$	SR1	$y_{k}-B_{k}s_{k}$	SR1
		$P_{k}^{\text{S}}s_{k}$	MSS (Multipoint-Symmetric-Secant)

Compact Representations

Since many quasi-Newton methods follow from the general updates in (2) and (3) the compact representation of these updates consequently give the representation of most QN formulas. Define

$$S_{k}={\begin{bmatrix}s_{0}&s_{1}&\ldots &s_{k-1}\end{bmatrix}},$$ $$Y_{k}={\begin{bmatrix}y_{0}&y_{1}&\ldots &y_{k-1}\end{bmatrix}},$$ $$V_{k}={\begin{bmatrix}v_{0}&v_{1}&\ldots &v_{k-1}\end{bmatrix}},$$ $$C_{k}={\begin{bmatrix}c_{0}&c_{1}&\ldots &c_{k-1}\end{bmatrix}},$$

upper triangular

$${\big (}R_{k}{\big )}_{ij}:={\big (}R_{k}^{\text{SY}}{\big )}_{ij}=s_{i-1}^{T}y_{j-1},\quad {\big (}R_{k}^{\text{VY}}{\big )}_{ij}=v_{i-1}^{T}y_{j-1},\quad {\big (}R_{k}^{\text{CS}}{\big )}_{ij}=c_{i-1}^{T}s_{j-1},\quad \quad {\text{ for }}1\leq i\leq j\leq k$$

lower triangular

$${\big (}L_{k}{\big )}_{ij}:={\big (}L_{k}^{\text{SY}}{\big )}_{ij}=s_{i-1}^{T}y_{j-1},\quad {\big (}L_{k}^{\text{VY}}{\big )}_{ij}=v_{i-1}^{T}y_{j-1},\quad {\big (}L_{k}^{\text{CS}}{\big )}_{ij}=c_{i-1}^{T}s_{j-1},\quad \quad {\text{ for }}1\leq j<i\leq k$$

and diagonal

$$(D_{k})_{ij}:={\big (}D_{k}^{\text{SY}}{\big )}_{ij}=s_{i-1}^{T}y_{j-1},\quad \quad {\text{ for }}1\leq i=j\leq k$$

With these definitions the compact representations of the general rank-2 updates in (2) and (3) have been developed in Brust . The formula for the inverse update is

$$H_{k}=H_{0}+U_{k}M_{k}^{-1}U_{k}^{T},$$

(4)

$$U_{k}={\begin{bmatrix}V_{k}&S_{k}-H_{0}Y_{k}\end{bmatrix}}$$

$$M_{k}={\begin{bmatrix}0_{k\times k}&R_{k}^{\text{VY}}\\{\big (}R_{k}^{\text{VY}}{\big )}^{T}&R_{k}+R_{k}^{T}-(D_{k}+Y_{k}^{T}H_{0}Y_{k})\end{bmatrix}}$$

and the formula for the direct Hessian is

$$B_{k}=B_{0}+J_{k}N_{k}^{-1}J_{k}^{T},$$

(5)

$$J_{k}={\begin{bmatrix}C_{k}&Y_{k}-B_{0}S_{k}\end{bmatrix}}$$

$$N_{k}={\begin{bmatrix}0_{k\times k}&R_{k}^{\text{CS}}\\{\big (}R_{k}^{\text{CS}}{\big )}^{T}&R_{k}+R_{k}^{T}-(D_{k}+S_{k}^{T}B_{0}S_{k})\end{bmatrix}}$$

For instance, when $V_{k}=S_{k}$ the representation in (4) is the compact formula for the BFGS recursion in (1). The validity of these expressions can be simply checked by numerically comparing the difference between, e.g., (2) and (4) for the same $k$.

Representations without general recurrences (eqs. (2), (3))

Prior to the development of the compact representations of (2) and (3), equivalent representations have been discovered for most known updates (see Table 1).

BFGS

An equivalent compact representation for the BFGS (Broyden-Fletcher-Goldfarb-Shanno) was developed in . Along with the SR1 these were the first compact formulas known. In particular, the inverse representation is given by

$H_{k}=H_{0}+U_{k}M_{k}^{-1}U_{k}^{T},\quad U_{k}={\begin{bmatrix}S_{k}&H_{0}Y_{k}\end{bmatrix}},\quad M_{k}^{-1}=\left[{\begin{smallmatrix}R_{k}^{-T}(D_{k}+Y_{k}^{T}H_{0}Y_{k})R_{k}^{-1}&-R_{k}^{-T}\\-R_{k}^{-1}&0\end{smallmatrix}}\right]$

After simplification, this formula is exactly (4) with $V_{k}=S_{k}$.

The direct Hessian approximation can be found by applying the Sherman-Morrison-Woodbury identity to the inverse Hessian:

$B_{k}=B_{0}+J_{k}N_{k}^{-1}J_{k}^{T},\quad J_{k}={\begin{bmatrix}B_{0}S_{k}&Y_{k}\end{bmatrix}},\quad N_{k}=\left[{\begin{smallmatrix}S^{T}B_{0}S_{k}&L_{k}\\L_{k}^{T}&-D_{k}\end{smallmatrix}}\right]$

SR1

The SR1 (Symmetric Rank-1) compact representation was first proposed in . Using the definitions of $D_{k},L_{k}$ and $R_{k}$ from above, the inverse Hessian formula is given by

$H_{k}=H_{0}+U_{k}M_{k}^{-1}U_{k}^{T},\quad U_{k}=S_{k}-H_{0}Y_{k},\quad M_{k}=R_{k}+R_{k}^{T}-D_{k}-Y_{k}^{T}H_{0}Y_{k}$

The direct Hessian is obtained by the Sherman-Morrison-Woodbury identity and has the form

$B_{k}=B_{0}+J_{k}N_{k}^{-1}J_{k}^{T},\quad J_{k}=Y_{k}-B_{0}S_{k},\quad N_{k}=D_{k}+L_{k}+L_{k}^{T}-S_{k}^{T}B_{0}S_{k}$

MSS

The multipoint symmetric secant (MSS) method is a method that aims to satisfy multiple secant equations. The recursive update formula was originally developed by Burdakov . The compact representation for the direct Hessian was derived in

$B_{k}=B_{0}+J_{k}N_{k}^{-1}J_{k}^{T},\quad J_{k}={\begin{bmatrix}S_{k}&Y_{k}-B_{0}S_{k}\end{bmatrix}},\quad N_{k}=\left[{\begin{smallmatrix}W_{k}(S_{k}^{T}B_{0}S_{k}-(R_{k}-D_{k}+R_{k}^{T}))W_{k}&W_{k}\\W_{k}&0\end{smallmatrix}}\right]^{-1},\quad W_{k}=(S_{k}^{T}S_{k})^{-1}$

Another equivalent compact representation for the MSS matrix is derived by rewriting $J_{k}$ in terms of $J_{k}={\begin{bmatrix}S_{k}&B_{0}Y_{k}\end{bmatrix}}$.

The inverse representation can be obtained by application for the Sherman-Morrison-Woodbury identity.

DFP

Since the DFP (Davidon Fletcher Powell) update is the dual of the BFGS formula (i.e., swapping $H_{k}\leftrightarrow B_{k}$, $H_{0}\leftrightarrow B_{0}$ and $y_{k}\leftrightarrow s_{k}$ in the BFGS update), the compact representation for DFP can be immediately obtained from the one for BFGS .

PSB

The PSB (Powell-Symmetric-Broyden) compact representation was developed for the direct Hessian approximation. It is equivalent to substituting $C_{k}=S_{k}$ in (5)

$B_{k}=B_{0}+J_{k}N_{k}^{-1}J_{k}^{T},\quad J_{k}={\begin{bmatrix}S_{k}&Y_{k}-B_{0}S_{k}\end{bmatrix}},\quad N_{k}=\left[{\begin{smallmatrix}0&R_{k}^{\text{SS}}\\(R_{k}^{\text{SS}})^{T}&R_{k}+R_{k}^{T}-(D_{k}+S_{k}^{T}B_{0}S_{k})\end{smallmatrix}}\right]$

Structured BFGS

For structured optimization problems in which the objective function can be decomposed into two parts $f(x)={\widehat {k}}(x)+{\widehat {u}}(x)$, where the gradients and Hessian of ${\widehat {k}}(x)$ are known but only the gradient of ${\widehat {u}}(x)$ is known, structured BFGS formulas exist. The compact representation of these methods has the general form of (5), with specific $J_{k}$ and $N_{k}$.

Reduced BFGS

The reduced compact representation (RCR) of BFGS is for linear equality constrained optimization ${\text{ minimize }}f(x){\text{ subject to: }}Ax=b$, where $A$ is underdetermined. In addition to the matrices $S_{k},Y_{k}$ the RCR also stores the projections of the $y_{i}$'s onto the nullspace of $A$

$$Z_{k}={\begin{bmatrix}z_{0}&z_{1}&\cdots z_{k-1}\end{bmatrix}},\quad z_{i}=Py_{i},\quad P=I-A(A^{T}A)^{-1}A^{T},\quad 0\leq i\leq k-1$$

For $B_{k}$ the compact representation of the BFGS matrix (with a multiple of the identity $B_{0}$) the (1,1) block of the inverse KKT matrix has the compact representation

$K_{k}={\begin{bmatrix}B_{k}&A^{T}\\A&0\end{bmatrix}},\quad B_{0}=\gamma _{k}I,\quad H_{0}={\frac {1}{\gamma _{k}}}I,\quad \gamma _{k}>0$

${\big (}K_{k}^{-1}{\big )}_{11}=H_{0}+U_{k}M_{k}^{-1}U_{k}^{T},\quad U_{k}={\begin{bmatrix}A^{T}&S_{k}&Z_{k}\end{bmatrix}},\quad M_{k}=\left[{\begin{smallmatrix}-\gamma _{k}AA^{T}&\\&G_{k}\end{smallmatrix}}\right],\quad G_{k}=\left[{\begin{smallmatrix}R_{k}^{-T}(D_{k}+Y_{k}^{T}H_{0}Y_{k})R_{k}^{-1}&-H_{0}R_{k}^{-T}\\-H_{0}R_{k}^{-1}&0\end{smallmatrix}}\right]^{-1}$

Limited Memory

The most common use of the compact representations is for the limited-memory setting where $m\ll n$ denotes the memory parameter, with typical values around $m\in [5,12]$ (see e.g., ). Then, instead of storing the history of all vectors one limits this to the $m$ most recent vectors $\{(s_{i},y_{i}\}_{i=k-m}^{k-1}$ and possibly $\{v_{i}\}_{i=k-m}^{k-1}$ or $\{c_{i}\}_{i=k-m}^{k-1}$. Further, typically the initialization is chosen as an adaptive multiple of the identity $H_{k}^{(0)}=\gamma _{k}I$, with $\gamma _{k}=y_{k-1}^{T}s_{k-1}/y_{k-1}^{T}y_{k-1}$ and $B_{k}^{(0)}={\frac {1}{\gamma _{k}}}I$. Limited-memory methods are frequently used for large-scale problems with many variables (i.e., $n$ can be large), in which the limited-memory matrices $S_{k}\in \mathbb {R} ^{n\times m}$ and $Y_{k}\in \mathbb {R} ^{n\times m}$ (and possibly $V_{k},C_{k}$) are tall and very skinny: $S_{k}={\begin{bmatrix}s_{k-l-1}&\ldots &s_{k-1}\end{bmatrix}}$ and $Y_{k}={\begin{bmatrix}y_{k-l-1}&\ldots &y_{k-1}\end{bmatrix}}$.

Implementations

Open source implementations include:

• ACM TOMS algorithm 1030 implements a L-SR1 solver
• R's optim general-purpose optimizer routine uses the L-BFGS-B method.
• SciPy's optimization module's minimize method also includes an option to use L-BFGS-B.
• IPOPT with first order information

Non open source implementations include:

• Artelys Knitro nonlinear programming (NLP) solver use compact quasi-Newton matrices
• L-BFGS-B (ACM TOMS algorithm 778)