6. Quasi-Newton Methods

개요

Quasi-Newton method는 steepest descent 처럼 objective function의 gradient만을 필요로 하는데, 이 gradient의 변화를 이용한 objective function의 모델링으로 superlinear convergence를 만들어낸다.

Quadratic 모델에 대해 얘기해보자. 여기서 $B_k$는 $n\times n$ symmetric PD matrix이며 각 iteration마다 update된다. Minimizer $p_k$는 explicit하게

로 나타내어진다. 이를 search direction으로 사용하면, Wolfe condition을 만족하는 step length $\alpha_k$에 대해

로 update 한다.

BFGS Method

Update된 $x_{k+1}$로 다시 모델을 구성하고자 한다.

마지막 step에서 얻은 정보로 $B_{k+1}$에 어떤 requirement를 요구해야할까? Gradient를 이용해서, 마지막 두 iteration $x_{k}$와 $x_{k+1}$에서 $f$의 gradient와 $m_{k+1}$의 gradient가 일치하도록 만들 수 있다. $x_{k+1}$에서는 자연히 만족하므로 $x_{k}$에서 만족하는 조건에 대해서만 적어보자면

식을 정리하고, 아래 두 notation을 추가하면

우리가 secant equation이라 부르는 것을 얻는다.

$B_{k+1}$이 PD 이므로 secant equation의 왼쪽에 $s^T_k$를 곱해보면 solution이 존재하기 위해서는 다음의 curvature condition을 만족해야 하는 것을 알 수 있다.

$f$가 strongly convex이면 항상 성립하지만, nonconvex일 경우는 성립하게 만들기 위해서 line search와 step length를 고르는 과정에 제약을 걸어야한다. Strong Wolfe condition을 걸면

$c_2<1$이고 $p_k$가 descent direction이니 우측의 term이 양수이고 curvature condition이 성립하는 것을 볼 수 있다. 이제 curvature condtion이 만족하도록 만들 수 있게되었고 따라서 secant equation도 solution을 가질 것이다. 그런데 $B_{k+1}$의 DoF는 $n(n+1)/2$인데 secant equation이 가하는 condition은 $n$개 이므로 무한히 많은 solution이 존재할 것이다.

(DFP)

그래서 모든 가능한 $B_{k+1}$ 중 $B_{k}$와 가장 가까운 것을 찾는다.

사용된 norm의 종류에 따라 다른 quasi-Newton method가 된다. Solution을 찾기 쉽고 scale-invariant하도록 만들어주는 것은 weighted Frobenius norm이다.

Weight matrix $W$는 $Wy_k=s_k$를 만족하는 어떤 matrix도 될 수 있고, 그냥 딱 정하자면 average Hessian $\bar{G}_k$에 대해 $W=\bar{G}^{-1}_k$로 잡을 수 있다 (Taylor’s theorem에 의해 $y_k=\bar{G}_k\alpha_kp_k=\bar{G}_ks_k$). 이렇게 잡으면 norm이 non-dimensional해 문제의 unit과 독립적이 되어서 좋다. 이 weighting matrix와 norm 대해 유일해는

이다. Chapter 2 개요에서 필요한건 $H_k=B^{-1}_k$인데 $B_k$를 구하고 역행렬 계산하는 대신 바로 $H_k$를 구한다고 언급한 적 있다 (알다시피 $p_k=-B^{-1}_k\nabla f_k$니까). 그러면

왼쪽 두 항이 각각 rank-one matrix니까 $H_k$는 rank-two modification을 하는 것이다.

(BFGS)

이제 그 유명한 BFGS이다. BFGS는 $B_{k+1}$과 $B_k$가 가깝도록 하는 대신 $H_{k+1}$과 $H_k$에 직접적으로 조건을 건다.

norm은 DFP와 똑같은 걸 사용한다. 그럼 업데이트 식은

BFGS를 이용한 Hessian approximation 식은

그런데 initial $H_0$은 어떻게 정해야할까? $x_0$에서 finite difference 이용해서 inverse Hessian을 approximation할 수도 있고, 그냥 identity matrix로 할 수도 있다.

$H_k$가 PD면 $H_{k+1}$도 PD이다.

각 iteration의 계산 복잡도는 $O(n^2)$이다. Robust하고 superlinearly converge한다. Newton’s method는 quadratic하게 converge하긴 해도 second derivative를 계산해야한다. Naive implementation은 $B_kp_k=-\nabla f_k$를 계산해야해서 계산 복잡도가 $O(n^3)$인데 B_k의 Cholesky factor를 잘 쓰면 줄일 수 있다. 만약 $H_k$의 approximation이 정확하지 않아도 BFGS는 몇 iteration안에 꽤 잘 self-correction 한다 (단, Wolfe line search condition을 만족할 때만)(DFP는 이런 능력이 부족).

SR1 Method

Symmetric-rank-1 (SR1)은 update된 matrix가 PD일 것이라 보장해주지 못한다. 그래도 결과가 괜찮다 한다.

SR1의 update 식은

이 때, $\sigma$ 는 $+1$ 이거나 $-1$이고, $\sigma$와 $v$는 $B_{k+1}$이 secant equation을 만족하도록 선택된다. 양변의 우측에 $s_k$를 곱하고 secant equation을 이용하면

괄호 안의 term은 scalar이므로, $v$는 $y_k-B_ks_k$의 multiple이 되어서 scalar $\delta$에 대해 $v=\delta(y_k-B_ks_k)$로 적을 수 있다. 그러면

이 식은 다음의 경우 (오직 그 경우에만) 만족한다.

이를 반영해 secant equation이 성립하도록 SR1의 update식을 다시 적으면

이에 따른 inverse Hessian approxmiation은

SR1은 이전 iteration에 $B_k$가 PD였다 하더라도 $B_{k+1}$이 PD일 것이라는 보장을 해주지 못한다. 이 부분이 line search에서는 문제가 되는데 trust-region 방식을 사용하면 오히려 장점으로 작용한다고 한다.

SR1의 가장 큰 단점은 update 식의 분모가 0에 가까워질 수 있다는 것이다. Objective function이 convex quadratic할 때마저 secant equation을 만족시키는 SR1 update가 존재하지 않을 수 있다.

1. $(y_k-B_ks_k)^Ts_k \neq 0$이면 문제없이 SR1을 적용하면 된다.
2. $y_k=B_ks_k$면 secant equation을 만족시키는 유일한 update는 $B_{k+1}=B_k$이다.
3. $y_k \neq B_ks_k$이고 $(y_k-B_ks_k)^Ts_k=0$이면, secant equation을 만족시키는 SR1 update는 없다.

마지막 경우가 문제가 된다. 그냥 BFGS를 쓰는게 낫겠다 생각이 들 수 있지만 SR1을 다루는 이유가 있다.

1. 간단한 safeguard 만으로도 numerical instability나 breakdown을 예방할 수 있다.
2. Hessian matrix를 꽤 잘 approximation 한다. (일반적으로 BFGS보다 나음)
3. Constrained problem이나 partially separable function의 경우 curvature condition을 사용할 수 없어 BFGS를 적용하기 어렵다. 또 이런 경우에는 true Hessian이 indefinite하므로 SR1의 indefinite함이 오히려 좋다.

1번에서 말한 safeguard란 분모가 너무 작은 update를 skip 하는 것이다. 즉 다음을 만족할때만 update한다.

만약 만족하지 못하면 $B_{k+1}=B_k$를 사용한다. 이때 $r=10^{-8}$정도로 매우 작은 숫자이다. 대부분 implementation들이 이런 종류의 방법을 쓴다.

왜 이런 방식의 skip을 하는가? 첫번째로 이런 상황은 두 벡터가 수직해야하는데, 잘 일어나지 않는 상황이다. 또, skip하는 조건은 $s^T_k\bar{G}s_k\approx s^T_kB_ks_k$를 함의하는데, $\bar{G}$가 average Hessian이니 $B_k$가 이미 $s_k$에 대해 꽤 정확하다는 것을 의미한다. BFGS에서는 왜 skip을 안했는가? Skip 함으로써 Wolfe condition을 만족하지 않는다면 curvature condition이 만족하지 않을 수 있고, Hessian approximation의 퀄리티가 떨어질 것이다.


이제 Quadratic function에 대해 SR1이 얼마나 잘 Hessian을 approximation하는지 살펴보자.

Theorem 6.1

$f:\mathbb{R}^n\rarr \mathbb{R}$이 strongly convex quadratic function $f(x)=b^Tx+\frac{1}{2}x^TAx$라고 하자. 이 때 $A$는 symmetric PD. 그러면, 모든 $k$에 대해 $(s_k-H_ky_k)^Ty_k\neq0$이라는 가정하에, 임의의 시작점 $x_0$과 임의의 symmetric 시작 matrix $H_0$에 대해 SR1으로 생성된 $\{x_k\}$은 최대 $n$ step안에 minimizer로 수렴한다. 또한 $n$ step이 수행되었고, search direction $p_i$들이 linearly independent하다면 $H_n=A^{-1}$이다.

• 증명

  $(s_k-H_ky_k)^Ty_k\neq0$를 가정했으니 SR1은 매 step 잘 정의 된다. 이제 귀납적으로

  $H_ky_j=s_j, \quad j=0,1,\dots,k-1$

  임을 보이자. 다시말해, secant equation이 마지막 search direction 뿐만 아니라 모든 지난 direction에 대해 만족한다는 것이다.

  정의에 의해 SR1 update는 secant equation을 만족시키므로 $H_1y_0=s_0$이다. 위 식이 $k>1$에 대해 만족할 때 $k+1$에 대해서도 만족함을 보이자.

  $(s_k-H_ky_k)^Ty_j=s^T_ky_j-y^T_k(H_ky_j)=s^T_ky_j-y^T_ks_j=0, \quad \forall j<k$

  마지막 등호는 quadratic function에 대해 $y_i=As_i$ 이기 때문이다. (이 부분이 갑자기 튀어나와서 이해 안갔는데, 계산해보니까 그렇긴 하다. $\nabla f(x) = b + Ax$이니, $y_k=\nabla f_{k+1}- \nabla f_k=Ax_{k+1}-Ax_k=As_i$이다. 이를 3번째 식에 대입하면 두 term이 서로 같다.) 이를 SR1 update 식에 대입하면

  $H_{k+1}y_j=H_k y_j=s_j \quad \forall j<k$

  를 얻을 수 있다. secant equation에 의해 $H_{k+1}y_k=s_k$이므로 $\forall j\leq k$에 대해 위 식이 성립한다.

  $n$ step을 진행하고 $\{s_j\}$들이 linearly independent하면

  $s_j=H_ny_j=H_nAs_j$

  이므로 $H_nA=I$, 다시말해 $H_n=A^{-1}$이다. 따라서 $x_n$에 취해진 step은 Newton step이고 $x_{n+1}$이 solution이 되어서 알고리즘이 종료할 것이다.

  Step들이 linearly dependent 하게 되는 경우를 생각해보자. $s_k$가 지난 step 들의 linear combination이라 하면, scalar $\xi_i$에 대해

  $s_k=\xi_0 s_0+\cdots + \xi_{k-1}s_{k-1}$

  이다.

  $H_ky_k=H_kAs_k=\xi_{0}H_{k}As_{0}+\cdots+\xi_{k-1}H_{k}As_{k-1}\\=\xi_{0}H_{k}y_{0}+\cdots+\xi_{k-1}H_{k}y_{k-1}\\=\xi_0s_0+\cdots+\xi_{k-1}s_{k-1}\\=s_k$

  여기서 $y_k=\nabla f_{k+1}-\nabla f_k$ 이고 $s_k=p_k=-H_k\nabla f_k$이므로

  $H_k(\nabla f_{k+1}-\nabla f_k)=-H_k\nabla f_k$

  여기서 $H_k$가 nonsingular 이므로, $\nabla f_{k+1}=0$이고, 따라서 $x_{k+1}$가 solution이다.

Theorem 6.1의 증명과정에서 우리는 $f$가 quadratic할 때 line search 방법에 무관하게, secant equation이 모든 지난 search direction에 대해 만족함을 보였다. BFGS에서는 이 것이 line search가 정확할 때만 성립한다. General nonlinear function에 대해서는 특정 condition 하에서 Hessian을 잘 approximate한다.

Theorem 6.2

$f$가 twice continuously differentiable하고, Hessian이 bounded 되어 있으며 point $x^\ast$의 neighborhood에서 Lipschitz continuous하다고 가정하자. $\{x_k\}$를 어떤 $x^\ast\in\mathbb{R}^n$에 대해 $x_{k}\rarr x^\ast$인 sequence라 하자. 또, 모든 $k$와 어떤 $r\in(0,1)$에 대해 (6.26)의 safeguard condition inequality가 만족하고, step $s_k$가 uniformly linearly independent하다고 가정하자. SR1에 의해 생성되는 matrix $B_k$는 다음을 만족한다.

$\lim_{k\rarr \infty} \|B_k-\nabla^2 f(x^\ast)\|=0$

• Uniformly linearly independent step 한줄 요약하자면 step이 $n$보다 작은 dimension의 subspace에 떨어지지 않는 경향(tend to)이 있다. (이게 무슨 소리야?) R. M. Elkin, Convergence theorems for Gauss-Seidel and other minimization algorithms, Ph.D. Thesis, Univ. of Maryland, College Park, Md., 1966. 을 참조하면

  Uniformly linearly independent

  $\|e^p\|=1$인 vector들의 sequence $\{e^p\}$는 다음을 만족하는 $m\geq n$과 $c>0$이 존재할 때 uniformly linearly independent라고 한다. 임의의 $p'$와 임의의 $x\in E^n$에 대해

  $\max_{p'+1\leq p \leq p'+m} |x^Te^p|\geq c\|x\|$

  이 정의는 모든 $m$개의 연속된 vector로부터 $n$개를 골랐을 때
  $|\det (e^{p_1},\dots, e^{p_n})|\geq c'$
  을 만족시키는 $c'>0$이 존재한다와 동치이다.

Broyden Class

Broyden class는 다음 식을 통해서 update되는 방식들을 통칭한다.

$\phi_k$는 scalar parameter이고,

$\phi_k=0$이면 BFGS이고 $\phi_k=1$이면 DFP가 되므로, BFGS와 DFP는 Broyden class에 속한다. Broyden class를 이 두 method들의 linear combination이라고 생각할 수도 있다.

따라서, Broyden class는 secant equation을 만족시키고, $0\leq \phi_k \leq 1$인 경우 $s^T_ky_k>0$일 때 Hessian approximation이 PD이다. $0\leq \phi_k \leq 1$인 경우를 restricted Broyden class라고 부른다.

로 두고 분석해보자.

Theorem 6.3

$f:\mathbb{R}^n\rarr \mathbb{R}$이 strongly convex quadratic function $f(x)=b^Tx+\frac{1}{2}x^TAx$라고 하자. 이 때 $A$는 symmetric PD. $x_0$을 임의의 시작점, $B_0$을 임의의 시작 symmetric PD matrix, $B_k$가 restricted Broyden formula (6.32)에 의해 ($\phi_k\in[0,1]$) update된다 하자. $\lambda^k_1\leq\lambda^k_2\leq\dots\leq\lambda^k_n$이 matrix

$A^{\frac{1}{2}}B^{-1}_kA^{\frac{1}{2}}$

의 eigenvalue라고 하자. 그러면 모든 $k$에 대해

$\min\{\lambda^k_i, 1\}\leq \lambda ^{k+1}_i\leq \max\{\lambda^k_i,1\},\quad i=1,2,\dots,n$

이는 $\phi_k \notin [0,1]$일 때는 성립하지 않는다.

• 증명

  책에서는 증명 없이 넘어가는데 Fletcher, Roger. "A new approach to variable metric algorithms." The computer journal 13.3 (1970): 317-322. 의 6. Some Theorems를 참조하자. 6장의 Lemma 1의 더 general한 버전이 Nocedal 책의 appendix의 Theorem A.1 Interlacing Eigenvalue Theorem에 있다. 이 글 뒷부분의 논의를 위해서도 필요해 따로 언급해두고 넘어가자

Theorem A.1 (Interlacing Eigenvalue Theorem)

$A\in\mathbb{R}^{n\times n}$을 symmetric matrix라고 하고 eigenvalue $\lambda_1,\lambda_2,\dots,\lambda_n$이

$\lambda_1\geq \lambda_2\geq \cdots \geq \lambda_n$

을 만족하며, vector $z\in\mathbb{R}^n$가 $\|z\|=1$을 만족하고, $\alpha\in\mathbb{R}$이 scalar라고 하자. $A^\ast=A+\alpha zz^T$의 eigenvalue를 $\lambda_1^{\ast},\lambda_2^{\ast},\dots,\lambda^{\ast}_n$ (똑같이 descending order)라고 하면, $\alpha>0$일 때,

$\lambda^{\ast}_1\geq \lambda_1\geq\lambda^{\ast}_2\geq \lambda_2\geq\cdots\geq\lambda^{\ast}_n\geq \lambda_n$

이며,

$\sum^n_{i=1}\lambda^\ast_i-\lambda_i=\alpha$

이다. $\alpha<0$일 때는 eigenvalue들의 순서만 바뀌어서

$\lambda_1\geq \lambda^{\ast}_1\geq\lambda_2\geq \lambda^{\ast}_2\geq\cdots\geq\lambda_n\geq \lambda^{\ast}_n$

이다.

• 증명

  G. H. GOLUB AND C. F. VAN LOAN, Matrix Computations, The Johns Hopkins University Press, Baltimore, third ed., 1996.의 theorem 8.1.8에 있다고 하는데 여기서도 증명 안하고 Wilkinson (1965) the algebraic eigenvalue problem을 인용한다.

만약에 eigenvalue가 모두 1이라면, Hessian approximation $B_k$가 true Hessian $A$와 동일할 것이다 (Theorem 6.3 증명에 언급한 Fletcher를 보면, Property 1에 approximation matrix $B_k$와 Hessian $A$와의 차이는 $K=A^{\frac{1}{2}}B^{-1}_kA^{\frac{1}{2}}$과 identity matrix의 차이로 측정될 수 있다고 한다. Eigenvalue가 모두 1이더라도 identity matrix가 아닐 수 있지 않을까 의문이었는데, $K$가 symmetric이기 때문에 해결된다.). 이 경우는 이상적인 상황이고, 우리는 eigenvalue가 최대한 1에 가깝기를 바란다. Theorem 6.3은 $\{\lambda^k_i\}$가 monotonically 1로 converge 한다는 것을 말해준다.

SR1도 $\phi_k$가 다음과 같을 때 유도되기 때문에 Boryden class에 속한다.

단 $\phi_k$가 $[0,1]$에서 벗어날 수 있기 때문에 restricted Broyden class에 속하지는 않는다.

$B_k$가 PD함을 유지하기 위한 $\phi_k$의 범위에 대해 얘기해보자. (6.32)의 마지막 term은 rank-one correction인데, interlacing eigenvalue theorem에 의하면 $\phi_k$가 positive일 때 matrix의 eigenvalue를 증가시킨다. 따라서 $B_{k+1}$은 모든 $\phi_{k}\geq 0$에 대해 PD이다. 반면, $\phi_k<0$이면 eigenvalue가 감소하니 matrix가 singular, indefinite하게 될 수 있을 것이다. 계산해보면 $B_{k+1}$은 $\phi_k$가

일 때 singular하게 된다. Cauchy-Schwarz inequality를 적용하면 $\mu_k\geq 1$이고 $\phi^c_k\leq 0$임을 알 수 있다. 따라서, 최초의 Hessian approximation $B_0$이 symmetric, PD이고, 각 $k$에 대해 curvature condition $s^T_ky_k>0$이 만족되고 $\phi_k>\phi^c_k$이면, Broyden’s formula (6.32)에 의해 생성되는 모든 $B_k$는 symmetric이고 PD이다.

Line search가 정확할 때, 모든 Broyden class에 의해 $\phi_k\geq \phi^c_k$로 생성되는 sequence는 동일하다. General nonlinear function에 적용될 때도 line search가 정확할 때 Broyden class에 의해 생성되는 direction은 길이에만 차이가 있다.

정확한 line search로 quadratic function에 적용될 때 Broyden class가 같는 성질을 몇가지 살펴보자.

Theorem 6.4

Broyden class의 method가 strongly convex quadratic function $f(x)=b^Tx+\frac{1}{2}x^TAx$에 적용되었다고 가정하자. $x_0$은 starting point이고, $B_0$은 임의의 symmetric PD matrix이다. 모든 $k$에 대해 $\alpha_k$가 exact step length이고, $\phi_k\geq \phi^c_k$라고 가정하자. 그러면 다음의 진술들은 참이다.

1. Iteration은 $\phi_k$와 independent하고 최대 $n$ step안에 solution으로 converge한다.

2. Secant equation이 모든 지난 search direction에 대해 만족한다. 즉,

   $B_ks_j=y_j, \quad j=1,2,\cdots,k-1$

3. 만약 starting matrix가 $B_0=I$라면, iteration이 CG와 동일하다. 특히 search direction이 conjugate하다. 즉,

   $s^T_iAs_j=0, \quad \text{for } i\neq j$

4. 만약 $n$번 iteration 했으면, $B_n=A$이다.

(i), (ii), (iv)는 Theorem 6.1에서 했던 얘기를 반복한 것이다. Theorem 6.4의 내용은 사실 Hessian approximation이 PD일 필요 없이 nonsingular이기만 하면 적용된다 (따라서 singular matrix가 되지 않도록 조심하면서 $\phi_k<\phi^c_k$를 택할 수도 있다.). (iii)의 내용은 starting matrix가 임의의 matrix여도 $B_0$이 preconditioner인 preconditioned CG로 바꿔말할 수 있다.

물론 여기까지 내용은 현실적으로 어려운 exact line search인 경우의 얘기이다.

Convergence Analysis

BFGS와 SR1의 현실적인 implementation에 대해 global, local convergence를 분석해보자. 둘 다 실제로 해보면 놀라울정도로 robust하지만 general nonlinear objective function에 대해 global convergence를 증명할 수는 없다. 실제로 이런 성질이 있는지도 아직 모른다. 여기서는 objective function이 convex하거나 최소한 convex한 구간에서 iterate 하는 경우에 대해서 얘기한다. 이런 local한 영역에서는 suplinearly convergence한다. 이 section에서는 Hessian matrix를 $G(x)$로 적는다.

BFGS

Assumption 6.1

1. Objective function $f$가 twice continuously differentiable이다.

2. Level set $\mathcal{L}=\{x\in\mathbb{R}^n | f(x)\leq f(x_0)\}$이 convex하며, 다음을 만족시키는 양의 상수 $m$과 $M$이 존재한다. 모든 $z\in\mathbb{R}^n$과 $x\in\mathcal{L}$에 대해

   $m\|z\|^2\leq z^TG(x)z\leq M\|z\|^2$

(ii)는 $G(x)$가 $\mathcal{L}$에서 PD이고 $f$가 $\mathcal{L}$에서 unique minimizer $x^\ast$를 갖는다는 것을 의미한다.

Average Hessian $\bar{G}_k$과 Taylor’s theorem에 의해 $y_k=\bar{G}_k\alpha_kp_k=\bar{G}_ks_k$인 것을 이용하면,

이다. Assumption에 의해 $\bar{G}_k$가 PD이고 따라서 square root가 잘 정의된다. $z_k=\bar{G}^{1/2}_ks_k$로 정의하면

이제 BFGS의 global convergence를 보일 준비가 되었다. Section 3.2에서 Quasi-Newton의 convergence 분석을 할 때처럼 Hessian approximation의 condition number을 제한할 수는 없다. 대신 Hessian approximation의 제일 큰 eigenvalue와 제일 작은 eigenvalue를 추정하기 위해 trace와 determinant를 이용한다. (trace는 eigenvalue들의 sum이고, determinant는 eigenvalue들의 곱임을 기억하자)

Theorem 6.5

$B_0$이 임의의 symmetric PD initial matrix라고 하고, $x_0$이 Assumption 6.1을 만족하는 시작점이라 하자. 그렇다면 $\epsilon=0$인 BFGS에 의해 생성되는 sequence $\{x_k\}$는 $f$의 minimizer $x^\ast$로 converge한다.

• 증명
  $m_k=\frac{y^T_ks_k}{s^T_ks_k}\\M_k=\frac{y^T_ky_k}{y^T_ks_k}$
  라고 정의하자. 그러면 $m_k\geq m$이고 $M_k \leq M$이다. BFGS update 식에 trace를 적용하면
  $\text{trace}(B_{k+1})=\text{trace}(B_k)-\frac{\|B_ks_k\|^2}{s^T_kB_ks_k}+\frac{\|y_k\|^2}{y^T_ks_k}$
  이다. 또 determinant를 적용하면
  $\det (B_{k+1}) = \det (B_k)\frac{y^T_ks_k}{s^T_kB_ks_k}$
  이다.
  $\cos \theta_k=\frac{s^T_kB_ks_k}{\|s_k\|\|B_ks_k\|}\\ q_k = \frac{s^T_kB_ks_k}{s^T_ks_k}$
  를 정의하면
  $\frac{\|B_ks_k\|^2}{s^T_kB_ks_k}=\frac{\|s_k\|^2\|B_ks_k\|^2}{(s^T_kB_ks_k)^2}\frac{s^T_kB_ks_k}{\|s_k\|^2}=\frac{q_k}{\cos^2\theta_k}$
  또,
  $\det (B_{k+1}) = \det (B_k)\frac{y^T_ks_k}{s^T_ks_k}\frac{s^T_ks_k}{s^T_kB_ks_k}=\det (B_k)\frac{m_k}{q_k}$
  Trace와 determinant를 합치기 위해 PD matrix $B$에 대한 함수를 다음과 같이 정의하자.
  $\psi(B)=\text{trace}(B)-\ln(\det(B))$
  자연스레 $\psi(B)>0$이다. 이제 지금까지 진행한 것들을 종합하면
  $\psi(B_{k+1})=\text{trace}(B_k)+M_k-\frac{q_k}{\cos^2\theta_k}-\ln(\det(B_k))-\ln m_k+\ln q_k \\ =\psi(B_k)+(M_k-\ln m_k-1) + \left[ 1-\frac{q_k}{\cos^2\theta_k}+\ln \frac{q_k}{\cos^2\theta_k} \right] +\ln \cos^2\theta_k$
  Function $h(t)=1-t+\ln t$가 모든 $t>0$에 대해 nonpositive 이므로
  $0<\psi(B_{k+1})\leq \psi(B_0)+c(k+1)+\sum^k_{j=0}\ln \cos^2\theta_j$
  이 때, $c=M-\ln m -1$ 은 positive 한 상수이다. 이제 section 3.2에서 얻은 결과 관련지어보자. $s_k=-\alpha_kB^{-1}_k\nabla f_k$이므로 $\cos\theta_k$는 steepest direction과 search direction 사이의 각도이다. 우리는 $\cos\theta_j\rarr 0$이지만 않으면 $\|\nabla f_k\|$가 0으로 수렴한다는 것을 알고 있다. $\cos\theta_j\rarr 0$을 가정하고 귀류법을 사용하자. 가정에 의해 $j>k_1$이면
  $\ln \cos^2\theta_j<-2c$
  를 만족하는 $k_1>0$이 존재할 것이다. 이에 따라, $\psi(B_{k+1})$에 대한 부등식을 $k_1$에 따라 나눠서 적을 수 있는데
  $0<\psi(B_0)+c(k+1)+\sum^{k_1}_{j=0}\ln \cos^2\theta_j+\sum^k_{j=k_1+1}(-2c)\\=\psi(B_0)+\sum^{k_1}_{j=0}\ln \cos^2\theta_j+2ck_1+c-ck$
  그런데 $k$가 커짐에 따라 우변이 음수가 될 수 있고 모순이 발생한다. 따라서 $\cos\theta_{jk}\geq\delta>0$을 만족하는 indices들의 subsequence $\{j_k\}_{k=1,2,\dots}$가 존재하고, Zoutendijk’s theorem에 의해 $\|\nabla f_k\|\rarr 0$이다. 문제가 strongly convex하므로 이는 $x_k\rarr x^\ast$임을 의미한다.
  

이 결과는 DFP를 제외한 모든 Broyden class에 적용된다. 결과를 확장하면 convergence 속도가 linear 함을 보일 수 있다. 특히 sequence $\|x_k-x^\ast\|$가 0으로 충분히 빠르게 수렴해서

이다. 이 것을 증명하지는 않고, 이 것이 만족하다면 실제로는 convergence가 superlinear하다는 것을 보인다.

Superlinear convergence of the BFGS method

Assumption 6.2

Hessian matrix $G$가 $x^\ast$에서 Lipschitz continuous 하다. 즉, 모든 $x^\ast$에 이웃한 $x$와 positive constant $L$에 대해

$\|G(x)-G(x^\ast)\|\leq L\|x-x^\ast\|$

다음의 값들을 먼저 정의하자.

여기서 $G_\ast=G(x^\ast)$이다. 또,

BFGS update식의 앞 뒤에 $G^{-1/2}_\ast$를 곱하고 정리하면

변수만 바꿔썼고 BFGS랑 똑같은 형태이므로 아까 Theorem 6.5의 증명의 내용을 이용하면

Average Hessian $\bar{G}_k$과 Taylor’s theorem에 의해 $y_k=\bar{G}_k\alpha_kp_k=\bar{G}_ks_k$인 것을 이용하면,

이므로

이다. Assumption 6.2에 의해

이 때, $\epsilon_k$는

즉, 임의의 상수 $\bar c$에 대해

Theorem 6.6

$f$가 twice continuously differentiable 하고 BFGS의 결과가 Assumption 6.2를 만족하는 minimizer $x^\ast$로 수렴한다고 가정하자. 또한, (6.52)가 성립한다고 가정하자. 즉,

$\sum^\infty_{k=1}\|x_k-x^\ast\|<\infty$

그러면 $x_k$는 $x^\ast$로 suplinearly converge한다.

• 증명

  Triangular inequality에 의해

  $\|\tilde y_k\|-\|\tilde s_k\|\leq \bar c \epsilon_k \|\tilde s_k\|\\ \|\tilde s_k\|-\|\tilde y_k\|\leq \bar c\epsilon_k\|\tilde s_k\|$

  즉,

  $(1-\bar c\epsilon_k)\|\tilde s_k\|\leq \|\tilde y_k\|\leq (1+\bar c\epsilon_k)\|\tilde s_k\|\tag{6.55}$

  (6.54)를 제곱하고 (6.55)를 이용하면,

  $(1-\bar c \epsilon_k)^2 \|\tilde s_k\|^2 - 2\tilde y^T_k\tilde s_k +\|\tilde s_k\|^2\leq \|\tilde y_k\|^2-2\tilde y^T_k\tilde s_k+\|\tilde s_k\|^2\leq \bar c^2\epsilon^2_k\|\tilde s_k\|^2$

  이고, 따라서

  $2\tilde y^T_k \tilde s_k\geq2 (1-\bar c \epsilon_k)\|\tilde s_k\|^2$

  Definition에 의해

  $\tilde m_k\geq 1-\bar c\epsilon_k$

  이고, 따라서

  $\tilde M_k\leq \frac{1+\bar c\epsilon_k}{1-\bar c \epsilon_k}$

  이다. $x_k\rarr x^\ast$ 이므로 $\epsilon_k\rarr 0$이고 앞의 식에 의해 충분히 큰 모든 $k$에 대해 다음의 부등식을 만족하는 양의 상수 $c>\bar c$가 존재한다.

  $\tilde M_k\leq 1+\frac{2\bar c}{1-\bar c \epsilon_k}\leq 1+c\epsilon_k$

  $h(t)=1-t+\ln t$가 $t>0$일 때 nonpositive 하다는 성질을 이용하면

  $\frac{-x}{1-x}-\ln (1-x)=h\left(\frac{1}{1-x}\right)\leq 0$

  이제 $k$가 $\bar c \epsilon_k < \frac{1}{2}$를 만족시킬만큼 충분히 크다고 가정하자.

  $\ln (1-\bar c\epsilon_k)\geq \frac{-\bar c\epsilon_k}{1-\bar c \epsilon_k}\geq -2\bar c\epsilon_k$

  즉 충분히 큰 $k$에 대해

  $\ln\tilde m_k\geq \ln (1-\bar c \epsilon_k)\geq -2\bar c\epsilon_k>-2c\epsilon_k$

  이제 (6.53)을 이용하면

  $0<\psi(\tilde B_{k+1})\leq \psi(\tilde B_k)+3c\epsilon_k+\ln \cos ^2\tilde\theta_k+\left[1-\frac{\tilde q_k}{\cos^2 \tilde \theta_k} + \ln \frac{\tilde q_k}{\cos^2\tilde \theta_k} \right]$

  이제 (6.52)의 가정이 성립한다고 하면,

  $\sum^\infty_{j=0}\left(\ln\frac{1}{\cos^2\tilde \theta_j}-\left[1-\frac{\tilde q_k}{\cos^2 \tilde \theta_k} + \ln \frac{\tilde q_k}{\cos^2\tilde \theta_k} \right] \right)\leq \psi(\tilde B_0)+3c\sum^\infty_{j=0}\epsilon_j<+\infty$

  대괄호 안의 term들은 nonpositive이고 $\ln (1/\cos^2\tilde \theta_j)\geq 0$이므로 다음의 두 limit을 얻는다.

  $\lim_{j\rarr\infty}\ln \frac{1}{\cos^2\tilde\theta_j}=0\\ \lim_{j\rarr\infty}\left( 1-\frac{\tilde q_j}{\cos^2 \tilde \theta_j} + \ln \frac{\tilde q_j}{\cos^2\tilde \theta_j}\right)=0$

  이는

  $\lim_{j\rarr\infty}\cos\tilde\theta_j=1 \\ \lim_{j\rarr\infty} \tilde q_j=1$

  임을 의미한다. 중요한 부분은 끝났고 의미만 파악하면 된다.

  $\frac{G^{-1/2}_\ast (B_k-G_\ast)s_k\|^2}{\|G^{1/2}_\ast s_k\|^2}=\frac{\|(\tilde B_k-I)\tilde s_k\|^2}{\|\tilde s_k\|^2}\\ =\frac{\|\tilde B_k\tilde s_k\|^2-2\tilde s^T_k\tilde B_k \tilde s_k+\tilde s^T_k\tilde s_k}{\tilde s^T_k\tilde s_k}\\=\frac{\tilde q^2_k}{\cos\tilde\theta^2_k}-2\tilde q_k+1$

  이 식이 0으로 수렴하므로

  $\lim_{k\rarr \infty}\frac{\|(B_k-G_\ast)s_k\|}{\|s_k\|}=0$

  이다. step length $\alpha_k=1$은 언제나 solution 주변에서 Wolfe condition을 만족할 것이며 따라서 convergence는 superlinear하다. (Theorem 3.6 참조)
  

Convergence analysis of the SR1 method

SR1 method는 quadratic function에 대한 것 말고는 BFGS처럼 분석된 결과가 없다. 다만 trust-region SR1의 경우, objective function이 unique stationary point를 가지고, trust region condition이 매 step 지켜지고 (SR1 update가 skip되지 않음), Hessian approximation $B_k$가 위로 bounded되어 있으면, 결과는 $(n+1)$-step에 $x^\ast$로 superlinearly converge한다고 한다. 게다가 trust-region subproblem의 최적해를 찾을 필요도 없다.

Theorem 6.7

Trust-region SR1 method에 의해 생성된 $x_k$에 대해 다음의 조건이 성립한다고 가정하자.

1. Iteration은 종료하지 않고, closed, bounded, convex set $D$에 머문다. $D$에서 function $f$는 twice continuously differentiable이고, $f$는 unique stationary point $x^\ast$를 갖는다.

2. Hessian $\nabla^2 f(x^\ast)$가 PD이고 $\nabla^2 f(x)$가 $x^\ast$의 neighborhood에서 Lipschitz continuous하다.

3. Matrix의 sequence $\{B_k\}$가 norm 관점에서 bounded되어 있다.

4. 어떤 상수 $r\in(0,1)$에 대해, trust region 조건이 만족한다.

   $|(y_k-B_ks_k)^Ts_k|\geq r\|y_k-B_ks_k\|\|s_k\|\tag{6.26}$

그러면, $\lim_{k\rarr \infty}x_k=x^\ast$이고,

$\lim_{k\rarr\infty}\frac{\|x_{k+n+1}-x^\ast\|}{\|x_k-x^\ast\|}=0$

흥미롭게도 Theorem 6.7의 assumption들이 만족될 때, SR1의 Hessian approximation은 대부분의 경우 PD라고 한다.