1
$\begingroup$

I was reading this book specially theorem 8.4 on page 210.

Suppose that a method in the Broyden class is applied to a strongly convex quadratic function $f : R^n \rightarrow R$, where $x_0$ is the starting point and $B_0$ is any symmetric and positive definite matrix. Assume that $\alpha_k$ is the exact step length and that $\phi_k \geq \phi_{kc}$ for all $k$. Then the following statements are true.

  1. The iterates converge to the solution in at most $n$ iterations.
  2. The secant equation is satisfied for all previous search directions ($B_ks_j=y_j $ for all $j = k-1,\dots,1$)
  3. If the starting matrix is $B_0 = I$, then the iterates are identical to those generated by the conjugate gradient method (see Chapter 5). In particular, the search directions are conjugate, that is, $s_iAs_j = 0$ for all $i \not = j$.
  4. If $n$ iterations are performed, we have $B_{n+1} = A$.

There is no proof of this theorem but there is some ideas given how to prove 1,2,4. What is am not understanding is 3, as it says that BFGS and CG have the same iterates. I wrote out the the first few directions of both methods and I got that BFGS is like preconditioned BFGS or vise versa that CG is like BFGS without memory, which seems contradictory to this theorem. I would really appreciate other people thoughts and maybe a proof (of part 3) of this interesting theorem would be deeply appreciated.

Here is my scratch work on the search directions

Here I examine BFGS and CG-HS step by step assuming: $H_0 = I$ and $\gamma = \frac{1}{s_k^Ty_k}$, and exact linesearch ($g_{k+1}^Tp_k = 0$) \

Step 0 \begin{align} p_{0,bfgs} &= -g_0 \end{align}

\begin{align} p_{0,cg} &= -g_0 \end{align}

Step 1

\begin{align} p_{1,bfgs} &= -H_1g_1\\ &= - \left ( (I - \gamma s_0 y_0^T)(I - \gamma y_0 s_0 ) +\gamma s_0s_0^T \right )g_1\\ &= - \left (I -\gamma y_0 s_0^T - \gamma s_0 y_0^T + \gamma^2 s_0y_0^Ty_0s_0^T \right )g_1\\ &= -\left (g_1 - \frac{s_0y_0^T}{s_0^Ty_0} g_1 \right )\\ & = -g_1 + \frac{y_0^Tg_1}{p_0^Ty_0}p_0 \qquad \text{using $s_0 = \alpha_0 p_0$} \end{align} similarly computing for cg (conjugate gradient Hestenes-Stiefel), note: $\beta_k = \frac{g_k^T(g_k-g_{k-1})}{(g_k-g_{k-1})^Tp_{k-1}}$

\begin{align} p_{1,cg} &= -g_1 + \beta_1 p_0\\ &= -g_1 + \frac{g_1^T(g_1-g_0)}{(g_1-g_0)^Tp_0} p_0\\ & = -g_1 + \frac{g_1^T(y_0)}{y_0^Tp_0}p_0\\ & = -g_1 + \frac{y_0^Tg_1}{p_0^Ty_0}p_0 \end{align}

Step 2 \begin{align} p_{2,bfgs} &= -H_2 g_2\\ & = - \left ((I-\gamma s_1y_1^T)H_1(I - \gamma y_1s_1^T) +\gamma s_1s_1^T \right )g_2\\ & = - \left ((I-\gamma s_1y_1^T)(H_1 - \gamma H_1y_1s_1^T) +\gamma s_1s_1^T \right )g_2\\ & = - \left ( H_1 - \gamma H_1y_1s_1^T -\gamma s_1y_1^TH_1 + \gamma^2 s_1y_1^TH_1y_1s_1^T\right )g_2\\ & = - H_1g_2 + \frac{s_1y_1^TH_1}{s_1^Ty_1}g_2\\ & = - H_1g_2 + \frac{p_1y_1^TH_1}{p_1^Ty_1}g_2\\ & = - H_1g_2 + \frac{\langle y_1,H_1g_2 \rangle}{\langle p_1,y_1 \rangle}p_1 \end{align}

\begin{align} p_{2,cg} &= -g_2 + \beta_2 p_1\\ &= -g_2 + \frac{g_2^T(g_2-g_1)}{(g_2-g_1)^Tp_1} p_1\\ & = -g_2 + \frac{g_2^T(y_1)}{y_1^Tp_1}p_1\\ & = -g_2 + \frac{y_1^Tg_1}{p_1^Ty_1}p_1\\ & = - g_2 + \frac{\langle y_1,g_2 \rangle}{\langle p_1,y_1 \rangle}p_1 \end{align}

This is in general true for any $k$-th iteration. Thus bfgs $k$-th iteration $\cong$ $k$-th iteration of conjugate gradient (Hestenes-Stiefel) preconditioned by $H_{k-1}$.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.