개요
Quasi-Newton method는 steepest descent 처럼 objective function의 gradient만을 필요로 하는데, 이 gradient의 변화를 이용한 objective function의 모델링으로 superlinear convergence를 만들어낸다.
mk(p)=fk+∇fkTp+21pTBkp
Quadratic 모델에 대해 얘기해보자. 여기서 Bk는 n×n symmetric PD matrix이며 각 iteration마다 update된다. Minimizer pk는 explicit하게
pk=−Bk−1∇fk
로 나타내어진다. 이를 search direction으로 사용하면, Wolfe condition을 만족하는 step length αk에 대해
xk+1=xk+αkpk
로 update 한다.
BFGS Method
Update된 xk+1로 다시 모델을 구성하고자 한다.
mk+1(p)=fk+1+∇fk+1Tp+21pTBk+1p
마지막 step에서 얻은 정보로 Bk+1에 어떤 requirement를 요구해야할까? Gradient를 이용해서, 마지막 두 iteration xk와 xk+1에서 f의 gradient와 mk+1의 gradient가 일치하도록 만들 수 있다. xk+1에서는 자연히 만족하므로 xk에서 만족하는 조건에 대해서만 적어보자면
∇mk+1(−αkpk)=∇fk+1−αkBk+1pk=∇fk
식을 정리하고, 아래 두 notation을 추가하면
sk=xk+1−xk=αkpkyk=∇fk+1−∇fk
우리가 secant equation이라 부르는 것을 얻는다.
Bk+1sk=yk
Bk+1이 PD 이므로 secant equation의 왼쪽에 skT를 곱해보면 solution이 존재하기 위해서는 다음의 curvature condition을 만족해야 하는 것을 알 수 있다.
skTyk>0
f가 strongly convex이면 항상 성립하지만, nonconvex일 경우는 성립하게 만들기 위해서 line search와 step length를 고르는 과정에 제약을 걸어야한다. Strong Wolfe condition을 걸면
ykTsk≥(c2−1)αk∇fkTpk
c2<1이고 pk가 descent direction이니 우측의 term이 양수이고 curvature condition이 성립하는 것을 볼 수 있다. 이제 curvature condtion이 만족하도록 만들 수 있게되었고 따라서 secant equation도 solution을 가질 것이다. 그런데 Bk+1의 DoF는 n(n+1)/2인데 secant equation이 가하는 condition은 n개 이므로 무한히 많은 solution이 존재할 것이다.
(DFP)
그래서 모든 가능한 Bk+1 중 Bk와 가장 가까운 것을 찾는다.
Bmin∥B−Bk∥subject toB=BT,Bsk=yk
사용된 norm의 종류에 따라 다른 quasi-Newton method가 된다. Solution을 찾기 쉽고 scale-invariant하도록 만들어주는 것은 weighted Frobenius norm이다.
∥A∥W=∥W1/2AW1/2∥F
Weight matrix W는 Wyk=sk를 만족하는 어떤 matrix도 될 수 있고, 그냥 딱 정하자면 average Hessian Gˉk에 대해 W=Gˉk−1로 잡을 수 있다 (Taylor’s theorem에 의해 yk=Gˉkαkpk=Gˉksk). 이렇게 잡으면 norm이 non-dimensional해 문제의 unit과 독립적이 되어서 좋다. 이 weighting matrix와 norm 대해 유일해는
Bk+1=(I−ρkykskT)Bk(I−ρkskykT)+ρkykykTρk=ykTsk1
이다. Chapter 2 개요에서 필요한건 Hk=Bk−1인데 Bk를 구하고 역행렬 계산하는 대신 바로 Hk를 구한다고 언급한 적 있다 (알다시피 pk=−Bk−1∇fk니까). 그러면
Hk+1=Hk−ykTHkykHkykykTHk+ykTskskskT
왼쪽 두 항이 각각 rank-one matrix니까 Hk는 rank-two modification을 하는 것이다.
(BFGS)
이제 그 유명한 BFGS이다. BFGS는 Bk+1과 Bk가 가깝도록 하는 대신 Hk+1과 Hk에 직접적으로 조건을 건다.
Hmin∥H−Hk∥subject toH=HT,Hyk=sk
norm은 DFP와 똑같은 걸 사용한다. 그럼 업데이트 식은
Hk+1=(I−ρkskykT)Bk(I−ρkykskT)+ρkskskT
BFGS를 이용한 Hessian approximation 식은
Bk+1=Bk−skTBkskBkskskTBk+ykTskykykT
그런데 initial H0은 어떻게 정해야할까? x0에서 finite difference 이용해서 inverse Hessian을 approximation할 수도 있고, 그냥 identity matrix로 할 수도 있다.
Hk가 PD면 Hk+1도 PD이다.
zTHk+1z=wTHkw+ρk(zTsk)2≥0
각 iteration의 계산 복잡도는 O(n2)이다. Robust하고 superlinearly converge한다. Newton’s method는 quadratic하게 converge하긴 해도 second derivative를 계산해야한다. Naive implementation은 Bkpk=−∇fk를 계산해야해서 계산 복잡도가 O(n3)인데 B_k의 Cholesky factor를 잘 쓰면 줄일 수 있다. 만약 Hk의 approximation이 정확하지 않아도 BFGS는 몇 iteration안에 꽤 잘 self-correction 한다 (단, Wolfe line search condition을 만족할 때만)(DFP는 이런 능력이 부족).
SR1 Method
Symmetric-rank-1 (SR1)은 update된 matrix가 PD일 것이라 보장해주지 못한다. 그래도 결과가 괜찮다 한다.
SR1의 update 식은
Bk+1=Bk+σvvT
이 때, σ 는 +1 이거나 −1이고, σ와 v는 Bk+1이 secant equation을 만족하도록 선택된다. 양변의 우측에 sk를 곱하고 secant equation을 이용하면
yk=Bksk+[σvTsk]v
괄호 안의 term은 scalar이므로, v는 yk−Bksk의 multiple이 되어서 scalar δ에 대해 v=δ(yk−Bksk)로 적을 수 있다. 그러면
(yk−Bksk)=σδ2[skT(yk−Bksk)](yk−Bksk)
이 식은 다음의 경우 (오직 그 경우에만) 만족한다.
σ=sign[skT(yk−Bksk)]δ=±∣skT(yk−Bksk)∣−1/2
이를 반영해 secant equation이 성립하도록 SR1의 update식을 다시 적으면
Bk+1=Bk+(yk−Bksk)Tsk(yk−Bksk)(yk−Bksk)T
이에 따른 inverse Hessian approxmiation은
Hk+1=Hk+(sk−Hkyk)Tyk(sk−Hkyk)(sk−Hkyk)T
SR1은 이전 iteration에 Bk가 PD였다 하더라도 Bk+1이 PD일 것이라는 보장을 해주지 못한다. 이 부분이 line search에서는 문제가 되는데 trust-region 방식을 사용하면 오히려 장점으로 작용한다고 한다.
SR1의 가장 큰 단점은 update 식의 분모가 0에 가까워질 수 있다는 것이다. Objective function이 convex quadratic할 때마저 secant equation을 만족시키는 SR1 update가 존재하지 않을 수 있다.
- (yk−Bksk)Tsk=0이면 문제없이 SR1을 적용하면 된다.
- yk=Bksk면 secant equation을 만족시키는 유일한 update는 Bk+1=Bk이다.
- yk=Bksk이고 (yk−Bksk)Tsk=0이면, secant equation을 만족시키는 SR1 update는 없다.
마지막 경우가 문제가 된다. 그냥 BFGS를 쓰는게 낫겠다 생각이 들 수 있지만 SR1을 다루는 이유가 있다.
- 간단한 safeguard 만으로도 numerical instability나 breakdown을 예방할 수 있다.
- Hessian matrix를 꽤 잘 approximation 한다. (일반적으로 BFGS보다 나음)
- Constrained problem이나 partially separable function의 경우 curvature condition을 사용할 수 없어 BFGS를 적용하기 어렵다. 또 이런 경우에는 true Hessian이 indefinite하므로 SR1의 indefinite함이 오히려 좋다.
1번에서 말한 safeguard란 분모가 너무 작은 update를 skip 하는 것이다. 즉 다음을 만족할때만 update한다.
∣(yk−Bksk)Tsk∣≥r∥yk−Bksk∥∥sk∥(6.26)
만약 만족하지 못하면 Bk+1=Bk를 사용한다. 이때 r=10−8정도로 매우 작은 숫자이다. 대부분 implementation들이 이런 종류의 방법을 쓴다.
왜 이런 방식의 skip을 하는가? 첫번째로 이런 상황은 두 벡터가 수직해야하는데, 잘 일어나지 않는 상황이다. 또, skip하는 조건은 skTGˉsk≈skTBksk를 함의하는데, Gˉ가 average Hessian이니 Bk가 이미 sk에 대해 꽤 정확하다는 것을 의미한다. BFGS에서는 왜 skip을 안했는가? Skip 함으로써 Wolfe condition을 만족하지 않는다면 curvature condition이 만족하지 않을 수 있고, Hessian approximation의 퀄리티가 떨어질 것이다.
이제 Quadratic function에 대해 SR1이 얼마나 잘 Hessian을 approximation하는지 살펴보자.
pk=−Hk∇fk,xk+1=xk+pk
Theorem 6.1
f:Rn→R이 strongly convex quadratic function f(x)=bTx+21xTAx라고 하자. 이 때 A는 symmetric PD. 그러면, 모든 k에 대해 (sk−Hkyk)Tyk=0이라는 가정하에, 임의의 시작점 x0과 임의의 symmetric 시작 matrix H0에 대해 SR1으로 생성된 {xk}은 최대 n step안에 minimizer로 수렴한다. 또한 n step이 수행되었고, search direction pi들이 linearly independent하다면 Hn=A−1이다.
-
증명
(sk−Hkyk)Tyk=0를 가정했으니 SR1은 매 step 잘 정의 된다. 이제 귀납적으로
Hkyj=sj,j=0,1,…,k−1
임을 보이자. 다시말해, secant equation이 마지막 search direction 뿐만 아니라 모든 지난 direction에 대해 만족한다는 것이다.
정의에 의해 SR1 update는 secant equation을 만족시키므로 H1y0=s0이다. 위 식이 k>1에 대해 만족할 때 k+1에 대해서도 만족함을 보이자.
(sk−Hkyk)Tyj=skTyj−ykT(Hkyj)=skTyj−ykTsj=0,∀j<k
마지막 등호는 quadratic function에 대해 yi=Asi 이기 때문이다. (이 부분이 갑자기 튀어나와서 이해 안갔는데, 계산해보니까 그렇긴 하다. ∇f(x)=b+Ax이니, yk=∇fk+1−∇fk=Axk+1−Axk=Asi이다. 이를 3번째 식에 대입하면 두 term이 서로 같다.) 이를 SR1 update 식에 대입하면
Hk+1yj=Hkyj=sj∀j<k
를 얻을 수 있다. secant equation에 의해 Hk+1yk=sk이므로 ∀j≤k에 대해 위 식이 성립한다.
n step을 진행하고 {sj}들이 linearly independent하면
sj=Hnyj=HnAsj
이므로 HnA=I, 다시말해 Hn=A−1이다. 따라서 xn에 취해진 step은 Newton step이고 xn+1이 solution이 되어서 알고리즘이 종료할 것이다.
Step들이 linearly dependent 하게 되는 경우를 생각해보자. sk가 지난 step 들의 linear combination이라 하면, scalar ξi에 대해
sk=ξ0s0+⋯+ξk−1sk−1
이다.
Hkyk=HkAsk=ξ0HkAs0+⋯+ξk−1HkAsk−1=ξ0Hky0+⋯+ξk−1Hkyk−1=ξ0s0+⋯+ξk−1sk−1=sk
여기서 yk=∇fk+1−∇fk 이고 sk=pk=−Hk∇fk이므로
Hk(∇fk+1−∇fk)=−Hk∇fk
여기서 Hk가 nonsingular 이므로, ∇fk+1=0이고, 따라서 xk+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∗의 neighborhood에서 Lipschitz continuous하다고 가정하자. {xk}를 어떤 x∗∈Rn에 대해 xk→x∗인 sequence라 하자. 또, 모든 k와 어떤 r∈(0,1)에 대해 (6.26)의 safeguard condition inequality가 만족하고, step sk가 uniformly linearly independent하다고 가정하자. SR1에 의해 생성되는 matrix Bk는 다음을 만족한다.
k→∞lim∥Bk−∇2f(x∗)∥=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
∥ep∥=1인 vector들의 sequence {ep}는 다음을 만족하는 m≥n과 c>0이 존재할 때 uniformly linearly independent라고 한다. 임의의 p′와 임의의 x∈En에 대해
p′+1≤p≤p′+mmax∣xTep∣≥c∥x∥
이 정의는 모든 m개의 연속된 vector로부터 n개를 골랐을 때∣det(ep1,…,epn)∣≥c′ 을 만족시키는 c′>0이 존재한다와 동치이다.
Broyden Class
Broyden class는 다음 식을 통해서 update되는 방식들을 통칭한다.
Bk+1=Bk−skTBkskBkskskTBk+ykTskykykT+ϕk(skTBksk)vkvkT(6.32)
ϕk는 scalar parameter이고,
vk=[ykTskyk−skTBkskBksk]
ϕk=0이면 BFGS이고 ϕk=1이면 DFP가 되므로, BFGS와 DFP는 Broyden class에 속한다. Broyden class를 이 두 method들의 linear combination이라고 생각할 수도 있다.
Bk+1=(1−ϕk)Bk+1BFGS+ϕkBk+1DFP
따라서, Broyden class는 secant equation을 만족시키고, 0≤ϕk≤1인 경우 skTyk>0일 때 Hessian approximation이 PD이다. 0≤ϕk≤1인 경우를 restricted Broyden class라고 부른다.
pk=−Bk−1∇fk,xk+1=xk+pk
로 두고 분석해보자.
Theorem 6.3
f:Rn→R이 strongly convex quadratic function f(x)=bTx+21xTAx라고 하자. 이 때 A는 symmetric PD. x0을 임의의 시작점, B0을 임의의 시작 symmetric PD matrix, Bk가 restricted Broyden formula (6.32)에 의해 (ϕk∈[0,1]) update된다 하자. λ1k≤λ2k≤⋯≤λnk이 matrix
A21Bk−1A21
의 eigenvalue라고 하자. 그러면 모든 k에 대해
min{λik,1}≤λik+1≤max{λik,1},i=1,2,…,n
이는 ϕk∈/[0,1]일 때는 성립하지 않는다.
Theorem A.1 (Interlacing Eigenvalue Theorem)
A∈Rn×n을 symmetric matrix라고 하고 eigenvalue λ1,λ2,…,λn이
λ1≥λ2≥⋯≥λn
을 만족하며, vector z∈Rn가 ∥z∥=1을 만족하고, α∈R이 scalar라고 하자. A∗=A+αzzT의 eigenvalue를 λ1∗,λ2∗,…,λn∗ (똑같이 descending order)라고 하면, α>0일 때,
λ1∗≥λ1≥λ2∗≥λ2≥⋯≥λn∗≥λn
이며,
i=1∑nλi∗−λi=α
이다. α<0일 때는 eigenvalue들의 순서만 바뀌어서
λ1≥λ1∗≥λ2≥λ2∗≥⋯≥λn≥λ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 Bk가 true Hessian A와 동일할 것이다 (Theorem 6.3 증명에 언급한 Fletcher를 보면, Property 1에 approximation matrix Bk와 Hessian A와의 차이는 K=A21Bk−1A21과 identity matrix의 차이로 측정될 수 있다고 한다. Eigenvalue가 모두 1이더라도 identity matrix가 아닐 수 있지 않을까 의문이었는데, K가 symmetric이기 때문에 해결된다.). 이 경우는 이상적인 상황이고, 우리는 eigenvalue가 최대한 1에 가깝기를 바란다. Theorem 6.3은 {λik}가 monotonically 1로 converge 한다는 것을 말해준다.
SR1도 ϕk가 다음과 같을 때 유도되기 때문에 Boryden class에 속한다.
ϕk=skTyk−skTBkskskTyk
단 ϕk가 [0,1]에서 벗어날 수 있기 때문에 restricted Broyden class에 속하지는 않는다.
Bk가 PD함을 유지하기 위한 ϕk의 범위에 대해 얘기해보자. (6.32)의 마지막 term은 rank-one correction인데, interlacing eigenvalue theorem에 의하면 ϕk가 positive일 때 matrix의 eigenvalue를 증가시킨다. 따라서 Bk+1은 모든 ϕk≥0에 대해 PD이다. 반면, ϕk<0이면 eigenvalue가 감소하니 matrix가 singular, indefinite하게 될 수 있을 것이다. 계산해보면 Bk+1은 ϕk가
ϕkc=1−μk1μk=(ykTsk)2(ykTBk−1yk)(skTBksk)
일 때 singular하게 된다. Cauchy-Schwarz inequality를 적용하면 μk≥1이고 ϕkc≤0임을 알 수 있다. 따라서, 최초의 Hessian approximation B0이 symmetric, PD이고, 각 k에 대해 curvature condition skTyk>0이 만족되고 ϕk>ϕkc이면, Broyden’s formula (6.32)에 의해 생성되는 모든 Bk는 symmetric이고 PD이다.
Line search가 정확할 때, 모든 Broyden class에 의해 ϕk≥ϕkc로 생성되는 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+21xTAx에 적용되었다고 가정하자. x0은 starting point이고, B0은 임의의 symmetric PD matrix이다. 모든 k에 대해 αk가 exact step length이고, ϕk≥ϕkc라고 가정하자. 그러면 다음의 진술들은 참이다.
-
Iteration은 ϕk와 independent하고 최대 n step안에 solution으로 converge한다.
-
Secant equation이 모든 지난 search direction에 대해 만족한다. 즉,
Bksj=yj,j=1,2,⋯,k−1
-
만약 starting matrix가 B0=I라면, iteration이 CG와 동일하다. 특히 search direction이 conjugate하다. 즉,
siTAsj=0,for i=j
-
만약 n번 iteration 했으면, Bn=A이다.
(i), (ii), (iv)는 Theorem 6.1에서 했던 얘기를 반복한 것이다. Theorem 6.4의 내용은 사실 Hessian approximation이 PD일 필요 없이 nonsingular이기만 하면 적용된다 (따라서 singular matrix가 되지 않도록 조심하면서 ϕk<ϕkc를 택할 수도 있다.). (iii)의 내용은 starting matrix가 임의의 matrix여도 B0이 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
-
Objective function f가 twice continuously differentiable이다.
-
Level set L={x∈Rn∣f(x)≤f(x0)}이 convex하며, 다음을 만족시키는 양의 상수 m과 M이 존재한다. 모든 z∈Rn과 x∈L에 대해
m∥z∥2≤zTG(x)z≤M∥z∥2
(ii)는 G(x)가 L에서 PD이고 f가 L에서 unique minimizer x∗를 갖는다는 것을 의미한다.
Average Hessian Gˉk과 Taylor’s theorem에 의해 yk=Gˉkαkpk=Gˉksk인 것을 이용하면,
skTskykTsk=skTskskTGˉksk≥m
이다. Assumption에 의해 Gˉk가 PD이고 따라서 square root가 잘 정의된다. zk=Gˉk1/2sk로 정의하면
ykTskykTyk=skTGˉkskskTGˉk2sk=zkTzkzkTGˉkzk≤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
B0이 임의의 symmetric PD initial matrix라고 하고, x0이 Assumption 6.1을 만족하는 시작점이라 하자. 그렇다면 ϵ=0인 BFGS에 의해 생성되는 sequence {xk}는 f의 minimizer x∗로 converge한다.
- 증명
mk=skTskykTskMk=ykTskykTyk 라고 정의하자. 그러면 mk≥m이고 Mk≤M이다. BFGS update 식에 trace를 적용하면trace(Bk+1)=trace(Bk)−skTBksk∥Bksk∥2+ykTsk∥yk∥2 이다. 또 determinant를 적용하면det(Bk+1)=det(Bk)skTBkskykTsk 이다.cosθk=∥sk∥∥Bksk∥skTBkskqk=skTskskTBksk 를 정의하면skTBksk∥Bksk∥2=(skTBksk)2∥sk∥2∥Bksk∥2∥sk∥2skTBksk=cos2θkqk 또,det(Bk+1)=det(Bk)skTskykTskskTBkskskTsk=det(Bk)qkmk Trace와 determinant를 합치기 위해 PD matrix B에 대한 함수를 다음과 같이 정의하자.ψ(B)=trace(B)−ln(det(B)) 자연스레 ψ(B)>0이다. 이제 지금까지 진행한 것들을 종합하면ψ(Bk+1)=trace(Bk)+Mk−cos2θkqk−ln(det(Bk))−lnmk+lnqk=ψ(Bk)+(Mk−lnmk−1)+[1−cos2θkqk+lncos2θkqk]+lncos2θk Function h(t)=1−t+lnt가 모든 t>0에 대해 nonpositive 이므로0<ψ(Bk+1)≤ψ(B0)+c(k+1)+j=0∑klncos2θj 이 때, c=M−lnm−1 은 positive 한 상수이다. 이제 section 3.2에서 얻은 결과 관련지어보자. sk=−αkBk−1∇fk이므로 cosθk는 steepest direction과 search direction 사이의 각도이다. 우리는 cosθj→0이지만 않으면 ∥∇fk∥가 0으로 수렴한다는 것을 알고 있다. cosθj→0을 가정하고 귀류법을 사용하자. 가정에 의해 j>k1이면lncos2θj<−2c 를 만족하는 k1>0이 존재할 것이다. 이에 따라, ψ(Bk+1)에 대한 부등식을 k1에 따라 나눠서 적을 수 있는데0<ψ(B0)+c(k+1)+j=0∑k1lncos2θj+j=k1+1∑k(−2c)=ψ(B0)+j=0∑k1lncos2θj+2ck1+c−ck 그런데 k가 커짐에 따라 우변이 음수가 될 수 있고 모순이 발생한다. 따라서 cosθjk≥δ>0을 만족하는 indices들의 subsequence {jk}k=1,2,…가 존재하고, Zoutendijk’s theorem에 의해 ∥∇fk∥→0이다. 문제가 strongly convex하므로 이는 xk→x∗임을 의미한다.
이 결과는 DFP를 제외한 모든 Broyden class에 적용된다. 결과를 확장하면 convergence 속도가 linear 함을 보일 수 있다. 특히 sequence ∥xk−x∗∥가 0으로 충분히 빠르게 수렴해서
k=1∑∞∥xk−x∗∥<∞(6.52)
이다. 이 것을 증명하지는 않고, 이 것이 만족하다면 실제로는 convergence가 superlinear하다는 것을 보인다.
Superlinear convergence of the BFGS method
Assumption 6.2
Hessian matrix G가 x∗에서 Lipschitz continuous 하다. 즉, 모든 x∗에 이웃한 x와 positive constant L에 대해
∥G(x)−G(x∗)∥≤L∥x−x∗∥
다음의 값들을 먼저 정의하자.
s~k=G∗1/2sky~k=G∗−1/2ykB~k=G∗−1/2BkG∗−1/2
여기서 G∗=G(x∗)이다. 또,
cosθ~k=∥s~k∥∥B~ks~k∥s~kTB~ks~kq~k=∥s~k∥2s~kTB~ks~kM~k=y~kTs~k∥y~k∥2m~k=s~kTs~ky~kTs~k
BFGS update식의 앞 뒤에 G∗−1/2를 곱하고 정리하면
B~k+1=B~k−s~kTB~ks~kB~ks~ks~kTB~k+y~kTs~ky~ky~kT
변수만 바꿔썼고 BFGS랑 똑같은 형태이므로 아까 Theorem 6.5의 증명의 내용을 이용하면
ψ(B~k+1)=ψ(B~k)+(M~k−lnm~k−1)+[1−cos2θ~kq~k+lncos2θ~kq~k]+lncos2θ~k(6.53)
Average Hessian Gˉk과 Taylor’s theorem에 의해 yk=Gˉkαkpk=Gˉksk인 것을 이용하면,
yk−G∗sk=(Gˉk−G∗)sk
이므로
y~k−s~k=G∗−1/2(Gˉk−G∗)G∗−1/2s~k
이다. Assumption 6.2에 의해
∥y~k−s~k∥≤∥G∗−1/2∥2∥s~k∥∥Gˉk−G∗∥≤∥G∗−1/2∥2∥s~k∥Lϵk
이 때, ϵk는
ϵk=max{∥xk+1−x∗∥,∥xk−x∗∥}
즉, 임의의 상수 cˉ에 대해
∥s~k∥∥y~k−s~k∥≤cˉϵk(6.54)
Theorem 6.6
f가 twice continuously differentiable 하고 BFGS의 결과가 Assumption 6.2를 만족하는 minimizer x∗로 수렴한다고 가정하자. 또한, (6.52)가 성립한다고 가정하자. 즉,
k=1∑∞∥xk−x∗∥<∞
그러면 xk는 x∗로 suplinearly converge한다.
-
증명
Triangular inequality에 의해
∥y~k∥−∥s~k∥≤cˉϵk∥s~k∥∥s~k∥−∥y~k∥≤cˉϵk∥s~k∥
즉,
(1−cˉϵk)∥s~k∥≤∥y~k∥≤(1+cˉϵk)∥s~k∥(6.55)
(6.54)를 제곱하고 (6.55)를 이용하면,
(1−cˉϵk)2∥s~k∥2−2y~kTs~k+∥s~k∥2≤∥y~k∥2−2y~kTs~k+∥s~k∥2≤cˉ2ϵk2∥s~k∥2
이고, 따라서
2y~kTs~k≥2(1−cˉϵk)∥s~k∥2
Definition에 의해
m~k≥1−cˉϵk
이고, 따라서
M~k≤1−cˉϵk1+cˉϵk
이다. xk→x∗ 이므로 ϵk→0이고 앞의 식에 의해 충분히 큰 모든 k에 대해 다음의 부등식을 만족하는 양의 상수 c>cˉ가 존재한다.
M~k≤1+1−cˉϵk2cˉ≤1+cϵk
h(t)=1−t+lnt가 t>0일 때 nonpositive 하다는 성질을 이용하면
1−x−x−ln(1−x)=h(1−x1)≤0
이제 k가 cˉϵk<21를 만족시킬만큼 충분히 크다고 가정하자.
ln(1−cˉϵk)≥1−cˉϵk−cˉϵk≥−2cˉϵk
즉 충분히 큰 k에 대해
lnm~k≥ln(1−cˉϵk)≥−2cˉϵk>−2cϵk
이제 (6.53)을 이용하면
0<ψ(B~k+1)≤ψ(B~k)+3cϵk+lncos2θ~k+[1−cos2θ~kq~k+lncos2θ~kq~k]
이제 (6.52)의 가정이 성립한다고 하면,
j=0∑∞(lncos2θ~j1−[1−cos2θ~kq~k+lncos2θ~kq~k])≤ψ(B~0)+3cj=0∑∞ϵj<+∞
대괄호 안의 term들은 nonpositive이고 ln(1/cos2θ~j)≥0이므로 다음의 두 limit을 얻는다.
j→∞limlncos2θ~j1=0j→∞lim(1−cos2θ~jq~j+lncos2θ~jq~j)=0
이는
j→∞limcosθ~j=1j→∞limq~j=1
임을 의미한다. 중요한 부분은 끝났고 의미만 파악하면 된다.
∥G∗1/2sk∥2G∗−1/2(Bk−G∗)sk∥2=∥s~k∥2∥(B~k−I)s~k∥2=s~kTs~k∥B~ks~k∥2−2s~kTB~ks~k+s~kTs~k=cosθ~k2q~k2−2q~k+1
이 식이 0으로 수렴하므로
k→∞lim∥sk∥∥(Bk−G∗)sk∥=0
이다. step length α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 Bk가 위로 bounded되어 있으면, 결과는 (n+1)-step에 x∗로 superlinearly converge한다고 한다. 게다가 trust-region subproblem의 최적해를 찾을 필요도 없다.
Theorem 6.7
Trust-region SR1 method에 의해 생성된 xk에 대해 다음의 조건이 성립한다고 가정하자.
-
Iteration은 종료하지 않고, closed, bounded, convex set D에 머문다. D에서 function f는 twice continuously differentiable이고, f는 unique stationary point x∗를 갖는다.
-
Hessian ∇2f(x∗)가 PD이고 ∇2f(x)가 x∗의 neighborhood에서 Lipschitz continuous하다.
-
Matrix의 sequence {Bk}가 norm 관점에서 bounded되어 있다.
-
어떤 상수 r∈(0,1)에 대해, trust region 조건이 만족한다.
∣(yk−Bksk)Tsk∣≥r∥yk−Bksk∥∥sk∥(6.26)
그러면, limk→∞xk=x∗이고,
k→∞lim∥xk−x∗∥∥xk+n+1−x∗∥=0
흥미롭게도 Theorem 6.7의 assumption들이 만족될 때, SR1의 Hessian approximation은 대부분의 경우 PD라고 한다.