8
$\begingroup$

I am interested in deriving the unique solution to the following Quasi-Newton minimization problem $$ \min_{H}|| H-H_k||\\ H=H^\top,\quad Hy_k =s_k $$ The norm is the weighted Frobenius norm $$ ||A||_W \equiv ||W^{1/2}A W^{1/2}||_F $$where the weight matrix $W$ is any positive definite matrix that satisfies $Ws_k=y_k$, and $||\cdot||_F$ is defined by $||C||^2_F= \sum_{i,j}^n c^2_{ij}$. The quantity $H$ is the inverse hessian which is symmetric, positive definite and satisfies the secant equation above, $Hy_k=s_k$. We can assume that $W=G^{-1}_k $ where $G_k$ the average hessian is given by $$ G_k= \int_0^1 \nabla^2 f(x_k+\tau \alpha_k p_k)d\tau $$ The unique solution is given by $$ H_{k+1} = (1-\rho_k s_k y^\top_k)H_k (1-\rho_k y_k s^\top_k)+ \rho_k s_k s^\top_k $$ where $\rho_k = (y^\top_k s_k)^{-1}$. Note, this is an iterative scheme where $k$ represents the current iteration and $H_{k+1}$ is an approximation to the inverse hessian.

The notation I am using is directly from the book Nocedal & Wright - Numerical Optimization. I am not able to find a full derivation of this anywhere, everything written above is all that Nocedal/Wright has in regards to this topic. For a reference, this is in chapter 6 - Quasi Newton Methods, of their newest/2nd edition.

All links I have tried to google and other books also have no full derivation. I am not able to find anything more thorough than Nocedal & Wright however they still don't have a derivation. Thanks

$\endgroup$
3
  • $\begingroup$ What exactly is $H_{k+1}$. Is that an iterative scheme to find the minimum? $\endgroup$
    – Alex R.
    May 8 '17 at 18:07
  • $\begingroup$ @AlexR. An interative scheme to approximate the inverse hessian, an example of a quasi newton method. It can be applied to finding the minimum yes. $H_{k+1}$ is the updated approximation to the inverse Hessian. $\endgroup$ May 8 '17 at 18:08
  • 1
    $\begingroup$ A related (but currently unanswered) question about the DFP update formula: math.stackexchange.com/questions/2091867/… $\endgroup$
    – littleO
    May 10 '17 at 3:39
11
$\begingroup$

I'll outline the major steps. See the explanations and answers to the comments below.

  1. Introduce some notations $$ \hat H=W^{1/2}HW^{1/2},\quad \hat H_k=W^{1/2}H_kW^{1/2},\quad \hat s_k=W^{1/2}s_k,\quad \hat y_k=W^{-1/2}y_k.\tag{1} $$ Then the problem becomes $$ \min\|\hat H_k-\hat H\|_F\quad\text{subject to }\hat H\hat y_k=\hat y_k\ (=\hat s_k). $$
  2. To use the fact that $\hat y_k$ is the eigenvector of $\hat H$, let us introduce the new orthonormal basis $$ U=[u\ |\ u_\bot] $$ where $u$ is the normalized $\hat y_k$, i.e. $$u=\frac{\hat y_k}{\|\hat y_k\|}\tag{2},$$ and $u_\bot$ is any ON-complement to $u$. Since the Frobenius norm is unitary invariant (as it is the sum of squares of the singular values) we have $$ \|\hat H_k-\hat H\|_F=\|U^T\hat H_kU-U^T\hat HU\|_F= \left\|\begin{bmatrix}\color{blue}* & \color{blue}*\\\color{blue}* & \color{red}*\end{bmatrix}-\begin{bmatrix}\color{blue}1 & \color{blue}0\\\color{blue}0 & \color{red}*\end{bmatrix}\right\|_F. $$ The blue part cannot be affected by optimization, and to minimize the Frobenius norm, it is clear that we should make the red part become zero, that is, the optimal solution satisfies $$ \color{red}{u_\bot^T\hat Hu_\bot}=\color{red}{u_\bot^T\hat H_ku_\bot}. $$ It gives the optimal solution to be $$ \hat H=U\begin{bmatrix}\color{blue}1 & \color{blue}0\\\color{blue}0 & \color{red}{u_\bot^T\hat H_ku_\bot}\end{bmatrix}U^T. $$
  3. To write it more explicitly $$ \hat H=\begin{bmatrix}u & u_\bot\end{bmatrix}\begin{bmatrix}1 & 0\\0 & u_\bot^T\hat H_ku_\bot\end{bmatrix}\begin{bmatrix}u^T \\ u_\bot^T\end{bmatrix}=uu^T+u_\bot u_\bot^T\hat H_ku_\bot u_\bot^T= uu^T+(I-uu^T)\hat H_k(I-uu^T) $$ where we used the following representation of the projection operator to the complement of $u$ $$ u_\bot u_\bot^T=I-uu^T. $$
  4. Changing variables back to the original ones (1), (2) is straightforward.

Explanations:

Step 1. The convenience for $\hat H$ and $\hat H_k$ comes directly from the problem $$ \min\|\underbrace{W^{1/2}H_kW^{1/2}}_{\hat H_k}-\underbrace{W^{1/2}HW^{1/2}}_{\hat H}\|_F. $$ Then we have to rewrite the data too \begin{align} Hy_k=s_k\quad&\Leftrightarrow\quad \underbrace{\color{blue}{W^{1/2}}H\color{red}{W^{1/2}}}_{\hat H}\underbrace{\color{red}{W^{-1/2}}y_k}_{\hat y_k}=\underbrace{\color{blue}{W^{1/2}}s_k}_{\hat s_k},\\ Ws_k=y_k\quad&\Leftrightarrow\quad \underbrace{\color{red}{W^{-1/2}}Ws_k}_{\hat s_k}=\underbrace{\color{red}{W^{-1/2}}y_k}_{\hat y_k}. \end{align} Thus, $\hat H\hat y_k=\hat y_k$. It is also equal to $\hat s_k$.

Step 2. Since $\hat Hu=u$ we know that $u^T\hat Hu=u^Tu=1$ and $u_\bot^THu=u_\bot^Tu=0$, so we can represent the optimizing variable as $$ U^T\hat HU=\begin{bmatrix}u^T\\ u_\bot^T\end{bmatrix}\hat H\begin{bmatrix}u & u_\bot\end{bmatrix}= \begin{bmatrix}u^T\hat Hu & u^T\hat Hu_\bot\\u_\bot^T\hat Hu & u_\bot^T\hat Hu_\bot\end{bmatrix}= \begin{bmatrix}1 & 0\\0 & u_\bot^T\hat Hu_\bot\end{bmatrix}. $$ It gives the following \begin{align} U^T\hat H_kU-U^T\hat HU&=\begin{bmatrix}u^T\\ u_\bot^T\end{bmatrix}\hat H_k\begin{bmatrix}u & u_\bot\end{bmatrix}-\begin{bmatrix}u^T\\ u_\bot^T\end{bmatrix}\hat H\begin{bmatrix}u & u_\bot\end{bmatrix}=\\ &=\begin{bmatrix}\color{blue}{u^T\hat H_ku} & \color{blue}{u^T\hat H_ku_\bot}\\\color{blue}{u_\bot^T\hat H_ku} & \color{red}{u_\bot^T\hat H_ku_\bot}\end{bmatrix}-\begin{bmatrix}\color{blue}{1} & \color{blue}{0}\\\color{blue}{0} & \color{red}{u_\bot^T\hat Hu_\bot}\end{bmatrix}. \end{align} This particular structure of the optimizing variable was the whole idea to switch to the new basis. Because $\hat H$ has no freedom to vary in the blue part, we cannot change the corresponding blue part of $\hat H_k$, so it is fixed for all possible $\hat H$. The red part though can be changed as we wish, and the smallest Frobenius norm \begin{align} \|U^T(\hat H_k-\hat H)U\|_F^2&= \left\|\begin{bmatrix}\color{blue}{u^T\hat H_ku-1} & \color{blue}{u^T\hat H_ku_\bot}\\\color{blue}{u_\bot^T\hat H_ku} & \color{red}{u_\bot^T\hat H_ku_\bot-u_\bot^T\hat Hu_\bot}\end{bmatrix}\right\|_F^2=\\ &=\color{blue}{(u^T\hat H_ku-1)^2+\|u^T\hat H_ku_\bot\|_F^2+\|u_\bot^T\hat H_ku\|_F^2}+\color{red}{\|u_\bot^T\hat H_ku_\bot-u_\bot^T\hat Hu_\bot\|_F^2} \end{align} is obtained when the red part is zero.

Step 3. The matrix $U$ is orthogonal, hence, $$ I=UU^T=\begin{bmatrix}u & u_\bot\end{bmatrix}\begin{bmatrix}u^T \\ u_\bot^T\end{bmatrix}=uu^T+u_\bot u_\bot^T\quad\Leftrightarrow\quad u_\bot u_\bot^T=I-uu^T. $$

$\endgroup$
5
  • $\begingroup$ This is very helpful, thanks a lot. I will go through all the details now and be back shortly to ask the questions I have. I can see I may have a few. $\endgroup$ May 8 '17 at 22:06
  • $\begingroup$ Sounds like a plan, thanks! $\endgroup$ May 8 '17 at 22:08
  • $\begingroup$ Also, your second equation in the explanations of step 1: It should read $$W^{1/2}H W^{1/2}=\hat H$$, opposed to $\hat H_k$ as you have written. I think you just made a typo as you use $\hat H \hat y_k = \hat s_k$ right after so. Just wanted to let you know. This solution is GREAT. Thanks again!! $\endgroup$ May 10 '17 at 2:50
  • $\begingroup$ @Integrals The second one is a typo, thank you. The first one: the quantity $u^T\hat H_ku-1$ is a number, so $$\|u^T\hat H_ku-1\|_F^2=(u^T\hat H_ku-1)^2.$$ $\endgroup$
    – A.Γ.
    May 10 '17 at 3:29
  • $\begingroup$ @JeffFaraci Remember $\hat y_k=\hat s_k$ and $u=\frac{\hat y_k}{\|\hat y_k\|}$, hence, $uu^T=\frac{\hat y_k\hat y_k^T}{\|\hat y_k\|^2}$. The denominator is $$\hat y_k^T\hat y_k=\hat y_k^T\hat s_k=y_k^Ts_k.$$ $\endgroup$
    – A.Γ.
    May 13 '17 at 9:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.