6. Quasi-Newton Methods

son·2023년 2월 4일
0

개요

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

mk(p)=fk+fkTp+12pTBkpm_k(p)=f_k+\nabla f^T_kp+\frac{1}{2}p^TB_kp

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

pk=Bk1fkp_k=-B^{-1}_k\nabla f_k

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

xk+1=xk+αkpkx_{k+1}=x_k+\alpha_kp_k

로 update 한다.

BFGS Method

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

mk+1(p)=fk+1+fk+1Tp+12pTBk+1pm_{k+1}(p)=f_{k+1}+\nabla f^T_{k+1}p+\frac{1}{2}p^TB_{k+1}p

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

mk+1(αkpk)=fk+1αkBk+1pk=fk\nabla m_{k+1}(-\alpha_k p_k)=\nabla f_{k+1}-\alpha_k B_{k+1}p_k=\nabla f_k

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

sk=xk+1xk=αkpkyk=fk+1fks_k=x_{k+1}-x_k=\alpha_kp_k\\y_k=\nabla f_{k+1}-\nabla f_k

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

Bk+1sk=ykB_{k+1}s_k=y_k

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

skTyk>0s^T_ky_k>0

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

ykTsk(c21)αkfkTpky^T_k s_k \geq (c_2-1)\alpha_k \nabla f^T_k p_k

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

(DFP)

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

minBBBksubject toB=BT,Bsk=yk\min_B\|B-B_k\|\\\text{subject to}\quad B=B^T,\quad Bs_k=y_k

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

AW=W1/2AW1/2F\|A\|_W=\|W^{1/2}AW^{1/2}\|_F

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

Bk+1=(IρkykskT)Bk(IρkskykT)+ρkykykTρk=1ykTskB_{k+1}=(I-\rho_k y_k s^T_k)B_k(I-\rho_k s_k y^T_k) + \rho_k y_k y^T_k\\ \rho_k=\frac{1}{y^T_ks_k}

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

Hk+1=HkHkykykTHkykTHkyk+skskTykTskH_{k+1}=H_k-\frac{H_ky_ky^T_kH_k}{y^T_kH_ky_k}+\frac{s_ks^T_k}{y^T_ks_k}

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

(BFGS)

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

minHHHksubject toH=HT,Hyk=sk\min_H\|H-H_k\|\\\text{subject to}\quad H=H^T,\quad Hy_k=s_k

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

Hk+1=(IρkskykT)Bk(IρkykskT)+ρkskskTH_{k+1}=(I-\rho_k s_k y^T_k)B_k(I-\rho_k y_k s^T_k)+\rho_k s_k s^T_k

BFGS를 이용한 Hessian approximation 식은

Bk+1=BkBkskskTBkskTBksk+ykykTykTskB_{k+1}=B_k-\frac{B_ks_ks^T_kB_k}{s^T_kB_ks_k}+\frac{y_ky^T_k}{y^T_ks_k}

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

HkH_k가 PD면 Hk+1H_{k+1}도 PD이다.

zTHk+1z=wTHkw+ρk(zTsk)20z^TH_{k+1}z=w^TH_kw+\rho_k(z^Ts_k)^2\geq 0

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

SR1 Method

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

SR1의 update 식은

Bk+1=Bk+σvvTB_{k+1}=B_k + \sigma vv^T

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

yk=Bksk+[σvTsk]vy_k=B_ks_k+[\sigma v^T s_k]v

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

(ykBksk)=σδ2[skT(ykBksk)](ykBksk)(y_k-B_ks_k)=\sigma \delta^2[s^T_k(y_k-B_ks_k)](y_k-B_ks_k)

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

σ=sign[skT(ykBksk)]δ=±skT(ykBksk)1/2\sigma = \text{sign}\left[ s^T_k(y_k-B_ks_k)\right]\\ \delta = \pm|s^T_k(y_k-B_ks_k)|^{-1/2}

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

Bk+1=Bk+(ykBksk)(ykBksk)T(ykBksk)TskB_{k+1}=B_k+\frac{(y_k-B_ks_k)(y_k-B_ks_k)^T}{(y_k-B_ks_k)^Ts_k}

이에 따른 inverse Hessian approxmiation은

Hk+1=Hk+(skHkyk)(skHkyk)T(skHkyk)TykH_{k+1}=H_k+\frac{(s_k-H_ky_k)(s_k-H_ky_k)^T}{(s_k-H_ky_k)^Ty_k}

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

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

  1. (ykBksk)Tsk0(y_k-B_ks_k)^Ts_k \neq 0이면 문제없이 SR1을 적용하면 된다.
  2. yk=Bksky_k=B_ks_k면 secant equation을 만족시키는 유일한 update는 Bk+1=BkB_{k+1}=B_k이다.
  3. ykBksky_k \neq B_ks_k이고 (ykBksk)Tsk=0(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한다.

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

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

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


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

pk=Hkfk,xk+1=xk+pkp_k=-H_k\nabla f_k, \quad x_{k+1}=x_k+p_k

Theorem 6.1

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

  • 증명

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

    Hkyj=sj,j=0,1,,k1H_ky_j=s_j, \quad j=0,1,\dots,k-1

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

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

    (skHkyk)Tyj=skTyjykT(Hkyj)=skTyjykTsj=0,j<k(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에 대해 yi=Asiy_i=As_i 이기 때문이다. (이 부분이 갑자기 튀어나와서 이해 안갔는데, 계산해보니까 그렇긴 하다. f(x)=b+Ax\nabla f(x) = b + Ax이니, yk=fk+1fk=Axk+1Axk=Asiy_k=\nabla f_{k+1}- \nabla f_k=Ax_{k+1}-Ax_k=As_i이다. 이를 3번째 식에 대입하면 두 term이 서로 같다.) 이를 SR1 update 식에 대입하면

    Hk+1yj=Hkyj=sjj<kH_{k+1}y_j=H_k y_j=s_j \quad \forall j<k

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

    nn step을 진행하고 {sj}\{s_j\}들이 linearly independent하면

    sj=Hnyj=HnAsjs_j=H_ny_j=H_nAs_j

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

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

    sk=ξ0s0++ξk1sk1s_k=\xi_0 s_0+\cdots + \xi_{k-1}s_{k-1}

    이다.

    Hkyk=HkAsk=ξ0HkAs0++ξk1HkAsk1=ξ0Hky0++ξk1Hkyk1=ξ0s0++ξk1sk1=skH_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

    여기서 yk=fk+1fky_k=\nabla f_{k+1}-\nabla f_k 이고 sk=pk=Hkfks_k=p_k=-H_k\nabla f_k이므로

    Hk(fk+1fk)=HkfkH_k(\nabla f_{k+1}-\nabla f_k)=-H_k\nabla f_k

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

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

Theorem 6.2

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

limkBk2f(x)=0\lim_{k\rarr \infty} \|B_k-\nabla^2 f(x^\ast)\|=0
  • Uniformly linearly independent step 한줄 요약하자면 step이 nn보다 작은 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

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

    maxp+1pp+mxTepcx\max_{p'+1\leq p \leq p'+m} |x^Te^p|\geq c\|x\|
    이 정의는 모든 mm개의 연속된 vector로부터 nn개를 골랐을 때
    det(ep1,,epn)c|\det (e^{p_1},\dots, e^{p_n})|\geq c'
    을 만족시키는 c>0c'>0이 존재한다와 동치이다.

Broyden Class

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

Bk+1=BkBkskskTBkskTBksk+ykykTykTsk+ϕk(skTBksk)vkvkT(6.32)B_{k+1}=B_k - \frac{B_ks_ks^T_kB_k}{s^T_kB_ks_k} + \frac{y_ky^T_k}{y^T_k s_k} + \phi_k(s^T_kB_ks_k)v_kv^T_k\tag{6.32}

ϕk\phi_k는 scalar parameter이고,

vk=[ykykTskBkskskTBksk]v_k=\left[\frac{y_k}{y^T_k s_k}-\frac{B_ks_k}{s^T_kB_ks_k} \right]

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

Bk+1=(1ϕk)Bk+1BFGS+ϕkBk+1DFPB_{k+1}=(1-\phi_k)B^{\text{BFGS}}_{k+1}+\phi_kB^{\text{DFP}}_{k+1}

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

pk=Bk1fk,xk+1=xk+pkp_k=-B^{-1}_k\nabla f_k, \quad x_{k+1}=x_k+p_k

로 두고 분석해보자.

Theorem 6.3

f:RnRf:\mathbb{R}^n\rarr \mathbb{R}이 strongly convex quadratic function f(x)=bTx+12xTAxf(x)=b^Tx+\frac{1}{2}x^TAx라고 하자. 이 때 AA는 symmetric PD. x0x_0을 임의의 시작점, B0B_0을 임의의 시작 symmetric PD matrix, BkB_k가 restricted Broyden formula (6.32)에 의해 (ϕk[0,1]\phi_k\in[0,1]) update된다 하자. λ1kλ2kλnk\lambda^k_1\leq\lambda^k_2\leq\dots\leq\lambda^k_n이 matrix

A12Bk1A12A^{\frac{1}{2}}B^{-1}_kA^{\frac{1}{2}}

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

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

이는 ϕk[0,1]\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)

ARn×nA\in\mathbb{R}^{n\times n}을 symmetric matrix라고 하고 eigenvalue λ1,λ2,,λn\lambda_1,\lambda_2,\dots,\lambda_n

λ1λ2λn\lambda_1\geq \lambda_2\geq \cdots \geq \lambda_n

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

λ1λ1λ2λ2λnλn\lambda^{\ast}_1\geq \lambda_1\geq\lambda^{\ast}_2\geq \lambda_2\geq\cdots\geq\lambda^{\ast}_n\geq \lambda_n

이며,

i=1nλiλi=α\sum^n_{i=1}\lambda^\ast_i-\lambda_i=\alpha

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

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

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

ϕk=skTykskTykskTBksk\phi_k=\frac{s^T_ky_k}{s^T_ky_k-s^T_kB_ks_k}

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

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

ϕkc=11μkμk=(ykTBk1yk)(skTBksk)(ykTsk)2\phi^c_k=\frac{1}{1-\mu_k}\\\mu_k=\frac{(y^T_kB^{-1}_ky_k)(s^T_kB_ks_k)}{(y^T_ks_k)^2}

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

Line search가 정확할 때, 모든 Broyden class에 의해 ϕkϕkc\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)=bTx+12xTAxf(x)=b^Tx+\frac{1}{2}x^TAx에 적용되었다고 가정하자. x0x_0은 starting point이고, B0B_0은 임의의 symmetric PD matrix이다. 모든 kk에 대해 αk\alpha_k가 exact step length이고, ϕkϕkc\phi_k\geq \phi^c_k라고 가정하자. 그러면 다음의 진술들은 참이다.

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

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

    Bksj=yj,j=1,2,,k1B_ks_j=y_j, \quad j=1,2,\cdots,k-1
  3. 만약 starting matrix가 B0=IB_0=I라면, iteration이 CG와 동일하다. 특히 search direction이 conjugate하다. 즉,

    siTAsj=0,for ijs^T_iAs_j=0, \quad \text{for } i\neq j
  4. 만약 nn번 iteration 했으면, Bn=AB_n=A이다.

(i), (ii), (iv)는 Theorem 6.1에서 했던 얘기를 반복한 것이다. Theorem 6.4의 내용은 사실 Hessian approximation이 PD일 필요 없이 nonsingular이기만 하면 적용된다 (따라서 singular matrix가 되지 않도록 조심하면서 ϕk<ϕkc\phi_k<\phi^c_k를 택할 수도 있다.). (iii)의 내용은 starting matrix가 임의의 matrix여도 B0B_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)G(x)로 적는다.

BFGS

Assumption 6.1

  1. Objective function ff가 twice continuously differentiable이다.

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

    mz2zTG(x)zMz2m\|z\|^2\leq z^TG(x)z\leq M\|z\|^2

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

Average Hessian Gˉk\bar{G}_k과 Taylor’s theorem에 의해 yk=Gˉkαkpk=Gˉksky_k=\bar{G}_k\alpha_kp_k=\bar{G}_ks_k인 것을 이용하면,

ykTskskTsk=skTGˉkskskTskm\frac{y^T_ks_k}{s^T_ks_k}=\frac{s^T_k\bar{G}_ks_k}{s^T_ks_k}\geq m

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

ykTykykTsk=skTGˉk2skskTGˉksk=zkTGˉkzkzkTzkM\frac{y^T_ky_k}{y^T_ks_k}=\frac{s^T_k\bar G^2_k s_k}{s^T_k\bar G_k s_k}= \frac{z^T_k\bar G_k z_k}{z^T_kz_k}\leq M

이제 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

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

  • 증명
    mk=ykTskskTskMk=ykTykykTskm_k=\frac{y^T_ks_k}{s^T_ks_k}\\M_k=\frac{y^T_ky_k}{y^T_ks_k}
    라고 정의하자. 그러면 mkmm_k\geq m이고 MkMM_k \leq M이다. BFGS update 식에 trace를 적용하면
    trace(Bk+1)=trace(Bk)Bksk2skTBksk+yk2ykTsk\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(Bk+1)=det(Bk)ykTskskTBksk\det (B_{k+1}) = \det (B_k)\frac{y^T_ks_k}{s^T_kB_ks_k}
    이다.
    cosθk=skTBkskskBkskqk=skTBkskskTsk\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}
    를 정의하면
    Bksk2skTBksk=sk2Bksk2(skTBksk)2skTBksksk2=qkcos2θ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(Bk+1)=det(Bk)ykTskskTskskTskskTBksk=det(Bk)mkqk\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 BB에 대한 함수를 다음과 같이 정의하자.
    ψ(B)=trace(B)ln(det(B))\psi(B)=\text{trace}(B)-\ln(\det(B))
    자연스레 ψ(B)>0\psi(B)>0이다. 이제 지금까지 진행한 것들을 종합하면
    ψ(Bk+1)=trace(Bk)+Mkqkcos2θkln(det(Bk))lnmk+lnqk=ψ(Bk)+(Mklnmk1)+[1qkcos2θk+lnqkcos2θk]+lncos2θk\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)=1t+lnth(t)=1-t+\ln t가 모든 t>0t>0에 대해 nonpositive 이므로
    0<ψ(Bk+1)ψ(B0)+c(k+1)+j=0klncos2θj0<\psi(B_{k+1})\leq \psi(B_0)+c(k+1)+\sum^k_{j=0}\ln \cos^2\theta_j
    이 때, c=Mlnm1c=M-\ln m -1 은 positive 한 상수이다. 이제 section 3.2에서 얻은 결과 관련지어보자. sk=αkBk1fks_k=-\alpha_kB^{-1}_k\nabla f_k이므로 cosθk\cos\theta_k는 steepest direction과 search direction 사이의 각도이다. 우리는 cosθj0\cos\theta_j\rarr 0이지만 않으면 fk\|\nabla f_k\|가 0으로 수렴한다는 것을 알고 있다. cosθj0\cos\theta_j\rarr 0을 가정하고 귀류법을 사용하자. 가정에 의해 j>k1j>k_1이면
    lncos2θj<2c\ln \cos^2\theta_j<-2c
    를 만족하는 k1>0k_1>0이 존재할 것이다. 이에 따라, ψ(Bk+1)\psi(B_{k+1})에 대한 부등식을 k1k_1에 따라 나눠서 적을 수 있는데
    0<ψ(B0)+c(k+1)+j=0k1lncos2θj+j=k1+1k(2c)=ψ(B0)+j=0k1lncos2θj+2ck1+cck0<\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
    그런데 kk가 커짐에 따라 우변이 음수가 될 수 있고 모순이 발생한다. 따라서 cosθjkδ>0\cos\theta_{jk}\geq\delta>0을 만족하는 indices들의 subsequence {jk}k=1,2,\{j_k\}_{k=1,2,\dots}가 존재하고, Zoutendijk’s theorem에 의해 fk0\|\nabla f_k\|\rarr 0이다. 문제가 strongly convex하므로 이는 xkxx_k\rarr x^\ast임을 의미한다.

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

k=1xkx<(6.52)\sum^\infty_{k=1}\|x_k-x^\ast\|<\infty\tag{6.52}

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

Superlinear convergence of the BFGS method

Assumption 6.2

Hessian matrix GGxx^\ast에서 Lipschitz continuous 하다. 즉, 모든 xx^\ast에 이웃한 xx와 positive constant LL에 대해

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

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

s~k=G1/2sky~k=G1/2ykB~k=G1/2BkG1/2\tilde{s}_k=G^{1/2}_\ast s_k\\\tilde y_k=G^{-1/2}_\ast y_k \\ \tilde B_k= G^{-1/2}_\ast B_k G^{-1/2}_\ast

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

cosθ~k=s~kTB~ks~ks~kB~ks~kq~k=s~kTB~ks~ks~k2M~k=y~k2y~kTs~km~k=y~kTs~ks~kTs~k\cos \tilde\theta_k=\frac{\tilde s^T_k \tilde B_k \tilde s_k}{\|\tilde s_k\|\|\tilde B_k\tilde s_k\|}\\ \tilde q_k=\frac{\tilde s^T_k\tilde B_k \tilde s_k}{\|\tilde s_k\|^2} \\ \tilde M_k=\frac{\|\tilde y_k\|^2}{\tilde y_k^T \tilde s_k}\\ \tilde m_k = \frac{\tilde y^T_k \tilde s_k}{\tilde s^T_k \tilde s_k}

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

B~k+1=B~kB~ks~ks~kTB~ks~kTB~ks~k+y~ky~kTy~kTs~k\tilde B_{k+1}=\tilde B_k-\frac{\tilde B_k\tilde s_k \tilde s^T_k\tilde B_k}{\tilde s^T_k\tilde B_k\tilde s_k}+\frac{\tilde y_k\tilde y^T_k}{\tilde y^T_k\tilde s_k}

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

ψ(B~k+1)=ψ(B~k)+(M~klnm~k1)+[1q~kcos2θ~k+lnq~kcos2θ~k]+lncos2θ~k(6.53)\psi(\tilde B_{k+1})=\psi(\tilde B_{k})+(\tilde{M}_k-\ln \tilde m_k -1)+\left[1-\frac{\tilde q_k}{\cos^2 \tilde \theta_k} + \ln \frac{\tilde q_k}{\cos^2\tilde \theta_k} \right] +\ln \cos ^2\tilde \theta_k\tag{6.53}

Average Hessian Gˉk\bar{G}_k과 Taylor’s theorem에 의해 yk=Gˉkαkpk=Gˉksky_k=\bar{G}_k\alpha_kp_k=\bar{G}_ks_k인 것을 이용하면,

ykGsk=(GˉkG)sky_k-G_\ast s_k=(\bar G_k-G_\ast)s_k

이므로

y~ks~k=G1/2(GˉkG)G1/2s~k\tilde y_k - \tilde s_k=G^{-1/2}_\ast (\bar G_k -G_\ast)G^{-1/2}_\ast \tilde s_k

이다. Assumption 6.2에 의해

y~ks~kG1/22s~kGˉkGG1/22s~kLϵk\|\tilde y_k-\tilde s_k\|\leq \|G^{-1/2}_\ast\|^2 \|\tilde s_k\|\|\bar G_k-G_\ast\|\leq \|G^{-1/2}_\ast\|^2\|\tilde s_k\|L\epsilon_k

이 때, ϵk\epsilon_k

ϵk=max{xk+1x,xkx}\epsilon_k=\max \{ \|x_{k+1}-x^\ast\|,\|x_k-x^\ast\|\}

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

y~ks~ks~kcˉϵk(6.54)\frac{\|\tilde y_k-\tilde s_k\|}{\|\tilde s_k\|}\leq \bar c\epsilon_k\tag{6.54}

Theorem 6.6

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

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

그러면 xkx_kxx^\ast로 suplinearly converge한다.

  • 증명

    Triangular inequality에 의해

    y~ks~kcˉϵks~ks~ky~kcˉϵks~k\|\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\|

    즉,

    (1cˉϵk)s~ky~k(1+cˉϵk)s~k(6.55)(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)를 이용하면,

    (1cˉϵk)2s~k22y~kTs~k+s~k2y~k22y~kTs~k+s~k2cˉ2ϵk2s~k2(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

    이고, 따라서

    2y~kTs~k2(1cˉϵk)s~k22\tilde y^T_k \tilde s_k\geq2 (1-\bar c \epsilon_k)\|\tilde s_k\|^2

    Definition에 의해

    m~k1cˉϵk\tilde m_k\geq 1-\bar c\epsilon_k

    이고, 따라서

    M~k1+cˉϵk1cˉϵk\tilde M_k\leq \frac{1+\bar c\epsilon_k}{1-\bar c \epsilon_k}

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

    M~k1+2cˉ1cˉϵk1+cϵk\tilde M_k\leq 1+\frac{2\bar c}{1-\bar c \epsilon_k}\leq 1+c\epsilon_k

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

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

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

    ln(1cˉϵk)cˉϵk1cˉϵk2cˉϵk\ln (1-\bar c\epsilon_k)\geq \frac{-\bar c\epsilon_k}{1-\bar c \epsilon_k}\geq -2\bar c\epsilon_k

    즉 충분히 큰 kk에 대해

    lnm~kln(1cˉϵk)2cˉϵk>2cϵk\ln\tilde m_k\geq \ln (1-\bar c \epsilon_k)\geq -2\bar c\epsilon_k>-2c\epsilon_k

    이제 (6.53)을 이용하면

    0<ψ(B~k+1)ψ(B~k)+3cϵk+lncos2θ~k+[1q~kcos2θ~k+lnq~kcos2θ~k]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)의 가정이 성립한다고 하면,

    j=0(ln1cos2θ~j[1q~kcos2θ~k+lnq~kcos2θ~k])ψ(B~0)+3cj=0ϵj<+\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/cos2θ~j)0\ln (1/\cos^2\tilde \theta_j)\geq 0이므로 다음의 두 limit을 얻는다.

    limjln1cos2θ~j=0limj(1q~jcos2θ~j+lnq~jcos2θ~j)=0\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

    이는

    limjcosθ~j=1limjq~j=1\lim_{j\rarr\infty}\cos\tilde\theta_j=1 \\ \lim_{j\rarr\infty} \tilde q_j=1

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

    G1/2(BkG)sk2G1/2sk2=(B~kI)s~k2s~k2=B~ks~k22s~kTB~ks~k+s~kTs~ks~kTs~k=q~k2cosθ~k22q~k+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으로 수렴하므로

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

    이다. step length αk=1\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 BkB_k가 위로 bounded되어 있으면, 결과는 (n+1)(n+1)-step에 xx^\ast로 superlinearly converge한다고 한다. 게다가 trust-region subproblem의 최적해를 찾을 필요도 없다.

Theorem 6.7

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

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

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

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

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

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

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

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

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

0개의 댓글