3. Line Search Methods

Nocedal의 Numerical Optimization을 읽으며 주로 번역이지만 일부 내 이해를 덧붙였다. 글이 좀 긴 편이라 복습할 때 정독하기 부담스러워 노션에 정리한 것인데 이 곳에도 올려본다. 앞 두 챕터는 개요라 생략.

개요

매 iteration 마다 direction과 step size 결정한다.

Wolfe condition

Sufficient decrease, curvature condition (기울기가 충분히 감소했는가)

이 때, $0 < c_{1}<c_{2}<1$. Strong Wolfe condition에서는 두번째 항이 다음으로 바뀐다.

즉, gradient의 크기가 작아야함.

Goldstein condition

sufficient decrease 하면서 너무 작은 step length는 제외하도록 만든 조건.

Backtracking

Sufficient decrease를 만족할 때까지 $\alpha$를 업데이트함. (조건을 만족하는 가장 큰 $\alpha$ 값이 선택됨.)

Convergence of line search method

Zoutendijk’s theorem

$x_{k+1}=x_{k}+\alpha_{k}p_{k}$ (이 때, $p_{k}$는 descent direction이고, $\alpha_{k}$는 Wolfe condition을 만족)을 iterate 할 때, $f$가 $\mathbb{R}^{n}$ 에서 아래로 bound 되어있고, $f$가 level set $\mathcal{L}=\{ x:f(x)\leq f(x_{0}) \}$ ($x_{0}$은 iteration의 시작점)을 포함하는 open set $Y \in \mathcal{N}$안에서 continuously differentiable 하다고 가정하자. 또, gradient $\nabla f$가 $\mathcal{N}$에서 Lipschitz continuous 하다고 가정하면

$\sum_{k \geq 0} \cos ^{2} \theta_{k} \vert\vert\nabla f_{k} \vert\vert^{2} < \infty$

• Lipschitz continuous

  $\vert\vert f(x)- f(\tilde{x}) \vert\vert \leq L \vert\vert x-\tilde{x}\vert\vert$

  을 모든 $x,\tilde{x} \in \mathcal{N}$에 대해 만족하는 상수 $L>0$이 존재

• 증명
  Wolfe condition의 curvature condition에 $x_{k+1}=x_{k}+\alpha_{k}p_{k}$임을 활용하면

  $(\nabla f_{k+1} - \nabla f_{k})^{T}p_{k} \geq (c_{2}-1) \nabla f^{T}_{k} p_{k}$

  또, Lipschitz continuous 하다는 점에서

  $(\nabla f_{k+1} - \nabla f_{k})^{T} p_{k} \leq \alpha_{k} L \vert\vert p_{k} \vert\vert^{2}$

  두 식을 합치면,

  $\alpha_{k} \geq \frac{c_{2}-1}{L}\frac{\nabla f^{T}_{k} p_{k}}{\vert\vert p_{k}\vert\vert^{2}}$

  이 결과를 다시 Wolfe condition의 sufficient decrease에 넣으면

  $f_{k+1}\leq f_{k} - c_{1}\frac{1-c_{2}}{L}\frac{(\nabla f^{T}_{k} p_{k})^{2}}{\vert\vert p_{k}\vert\vert^{2}}$

  steepest descent direction $-\nabla f_{k}$와 임의의 search direction $p_{k}$ 사이의 angle은

  $\cos \theta_{k} = \frac{-\nabla f^{T}_{k} p_{k}}{\vert\vert \nabla f_{k} \vert\vert \, \vert\vert p_{k} \vert\vert}$

  임을 활용하고, 임의의 상수들을 뭉뚱그려 $c$로 표현하면

  $f_{k+1} \leq f_{k} -c \cos^{2}\theta_{k}\vert\vert \nabla f_{k} \vert\vert ^{2}$

  따라서 $f_{k}$는 monotonic decreasing 한다. 그런데 $f_{k}$ 아래로 bound 되어 있으니,

  $\sum ^{\infty}_{k=0} \cos ^{2} \theta_{k} \vert\vert \nabla f_{k} \vert\vert ^{2} < \infty$

여기서 $\theta$가 90도에서 충분히 멀다면 $\cos \theta_{k}>0$ 이므로,

위 조건을 만족하는 알고리즘들을 globally convergent 하다고 한다. 하지만, 위 조건은 단순히 알고리즘이 stationary point로 converge 한다는 것만 보장하고 그 point가 minimizer일 것은 보장하지 못한다. 후자를 위해서는 curvature $\nabla^{2}f(x_{k})$가 negative 하다는 추가 조건이 필요하다.

Newton-like method에 위 결과를 적용해보자. (Newton-like method : $p=-B^{-1}\nabla f$) $B_{k}$가 positive definite 이고, uniformly conditioned condition number를 갖는다면 (즉, 모든 $k$에 대해 $\vert\vert B_{k}\vert\vert \, \vert\vert B^{-1}_{k}\vert\vert \leq M$)

• 증명

  $\cos(\theta)=-\frac{\nabla f^{T}p}{\vert\vert \nabla f \vert\vert\, \vert\vert p\vert\vert} = \frac{p^{T}Bp}{\vert\vert Bp\vert\vert \, \vert\vert p\vert\vert}$

  이 때, $\vert\vert Ax\vert\vert \geq \vert\vert A\vert\vert \, \vert\vert x\vert\vert$ (Cauchy-Schwarz inequality) 이므로

  $\cos(\theta) \geq \frac{p^{T}Bp}{\vert\vert B\vert\vert \, \vert\vert p\vert\vert^{2}} = \frac{p^{T}B^{1/2}B^{1/2}p}{\vert\vert B\vert\vert \, \vert\vert p\vert\vert^{2}} \\ = \frac{\vert\vert B^{1/2} p \vert\vert^{2}}{\vert\vert B\vert\vert \, \vert\vert p\vert\vert^{2}} \geq \frac{\vert\vert p \vert\vert^{2}}{\vert\vert B^{-1/2}\vert\vert^{2}\,\vert\vert B\vert\vert \, \vert\vert p\vert\vert^{2}} \\ = \frac{1}{\vert\vert B^{-1}\vert\vert\,\vert\vert B\vert\vert} \geq \frac{1}{M}$

  • Matrix root 참고

    Square real matrix $A$가 positive semidefinite이다와 어떤 matrix $B$에 대해 $A=B^TB$이다는 동치이다. 이런 matrix $B$는 여럿이 존재할 수 있는데 positive semidefinite한 것은 오직 하나만 존재할 수 있다. 그러한 $B$를 principal, non-negative, positive square root라고 부른다.
    

  따라서 동일하게 $\lim_{k \rarr \infty} \vert\vert \nabla f_{k} \vert\vert = 0$ 이다.

  그런데 conjugate gradient에서는 이것이 성립하지않고 약한 $\inf \lim_{k \rarr \infty} \vert\vert \nabla f_{k} \vert\vert = 0$ 까지만 성립한다.

• 증명
  만약 모든 $k>K$에 대해서 $\vert\vert \nabla f_{k}\vert\vert \geq \gamma$를 만족하는 $\gamma>0$이 존재하다면, $\cos\theta_{k}\rarr0$ 이다. 그런데, 0으로부터 떨어진 $\{ \cos \theta_{j} \}$ subseqeuence가 존재함을 보일 수 있으므로 모순이다.
  

위의 증명 테크닉을 응용하면 1) 매 iteration이 objective function을 감소시키고 2) 매 $m$ 번째 iteration이 steepest descent step이며 step size가 Wolfe condition이나 Goldstein condition을 만족시키는 모든 알고리즘에 대해서 gloabl convergence를 증명할 수 있다.

Rate of convergence

Global convergence를 위한 조건과 rapid convergence를 달성하는 알고리즘은 때로 서로 상충한다. Rate of convergence를 분석하기 위해 다음의 objective function을 가정하자.

이 때, $Q$는 symmetric, positive definite. Gradient는 $\nabla f(x)= Qx-b$ 이고, minimzer $x^{\ast}$는 $Qx=b$의 유일해다. Exact step size $\alpha_{k}$는 $f(x_{k}-\alpha \nabla f_{k})$의 미분값이 0이 되도록 계산하면 쉽게 얻을 수 있다.

Steepest descent method는 그럼 다음과 같다.

Convergence of steepest descent method

weighted norm $\vert\vert x\vert\vert^{2}_{Q}=x^{T}Qx$ 라고 정의하자. $Qx^{\ast}=b$ 이므로

따라서 $\vert\vert \cdot\vert\vert^{2}_{Q}$은 현재 objective function 값과 optimal 값의 차이의 측도이다. $x_{k}$와 $x_{k+1}$에 대해 위 식을 적용하면

• 증명
  $\vert\vert x_{k+1}-x^{\ast}\vert\vert^{2}_{Q}=(x_{k+1}- x^{\ast})^{T}Q(x_{k+1}-x^{\ast})\\=(x_{k}- x^{\ast}-\alpha\nabla f_{k})^{T}Q(x_{k}- x^{\ast}-\alpha\nabla f_{k}) \\= (x_{k}- x^{\ast})^{T}Q(x_{k}-x^{\ast})-2\alpha\nabla f^{T}_{k}Q(x_{k}-x^{\ast}) + \alpha^{2}\nabla f^{T}_{k}Q\nabla f_{k}\\= \vert\vert x_{k}-x^{\ast}\vert\vert^{2}_{Q}-2\alpha\nabla f^{T}_{k}Q(x_{k}-x^{\ast}) + \alpha^{2}\nabla f^{T}_{k}Q\nabla f_{k}$
  이 때, $\nabla f_{k}=Q(x_{k}-x^{\ast})$ 이고, $\alpha=\frac{\nabla f^{T}_{k} \nabla f_{k}}{\nabla f^{T}_{k}Q \nabla f_{k}}$ 이므로
  $\vert\vert x_{k+1}-x^{\ast}\vert\vert^{2}_{Q}= \vert\vert x_{k}-x^{\ast}\vert\vert^{2}_{Q} - 2\alpha\nabla f^{T}_{k}\nabla f_{k} + \alpha^{2}\nabla f^{T}_{k}Q\nabla f_{k} \\ =\vert\vert x_{k}-x^{\ast}\vert\vert^{2}_{Q} - 2\frac{(\nabla f^{T}_{k}\nabla f_{k})^{2}}{\nabla f^{T}_{k}Q\nabla f_{k}} + \frac{(\nabla f^{T}_{k}\nabla f_{k})^{2}}{\nabla f^{T}_{k}Q\nabla f_{k}} \\ = \vert\vert x_{k}-x^{\ast}\vert\vert^{2}_{Q} - \frac{(\nabla f^{T}_{k}\nabla f_{k})^{2}}{\nabla f^{T}_{k}Q\nabla f_{k}} \\ = \vert\vert x_{k}-x^{\ast}\vert\vert^{2}_{Q}\left[1- \frac{(\nabla f^{T}_{k}\nabla f_{k})^{2}}{\nabla f^{T}_{k}Q\nabla f_{k}\vert\vert x_{k}-x^{\ast}\vert\vert^{2}_{Q}}\right]$
  이 때, $\vert\vert x_{k}-x^{\ast}\vert\vert^{2}_{Q}=\nabla f^{T}_{k} Q^{-1}\nabla f_{k}$ 이므로
  $\vert\vert x_{k+1}-x^{\ast}\vert\vert^{2}_{Q} = \vert\vert x_{k}-x^{\ast}\vert\vert^{2}_{Q}\left[1- \frac{(\nabla f^{T}_{k}\nabla f_{k})^{2}}{(\nabla f^{T}_{k}Q\nabla f_{k})(\nabla f^{T}_{k}Q^{-1}\nabla f_{k})}\right]$

이를 바탕으로 다음의 theorem을 얻을 수 있다. (증명 생략)

이 때, $0<\lambda_{1}\leq \cdots \leq \lambda_{n}$ 는 $Q$의 eigen value이다. 모든 eigen value의 값이 같다면 한 iteration만에 converge 한다. $\lambda_{n}/\lambda_{1}$의 값이 커질수록 iteration할 때 지그재그로 움직이는 성질이 두드러진다.

위에서 가정했던 objective function이 아니어도, 일반적인 nonlinear objective function에도 똑같이 적용된다. $f:\mathbb{R}^{n}\rarr \mathbb{R}$ 이 twice continuously differentiable 하고, exact line search를 이용한 steepest descent가 $x^{\ast}$ ($\nabla^{2}f(x^{\ast})$는 positive definite)으로 수렴한다 가정하자. 그러면 모든 $k>K$에 대해

이 때, $r\in \left(\frac{\lambda_{n}-\lambda_{1}}{\lambda_{n}+\lambda_{1}},1 \right)$

Newton method

여기서 $\nabla^{2}f_{k}$가 positive definite이 아니라면 $p^{N}_{k}$가 descent direction이 아닐 수 있다. 그러면 Convergence of steepest descent method에서 나온 결과가 적용될 수 없다. 자세한 건 나중에 더 논의하고, 일단은 local rate-of-convergence에 대해 얘기하자. $\nabla^{2} f(x^{\ast})$가 positive definite인 $x^{\ast}$의 neighborhood 역시 Hessian이 positive definite 할 것이다. 이 영역에서 step length $\alpha_{k}$가 1이라면 Newton’s method는 quadratic하게 converge 한다.

Theorem 3.5

$f$가 twice differentiable이고, $x^{\ast}$($\nabla f(x^{\ast})=0$, $\nabla^{2}f(x^{\ast})$는 positive definite)의 neighborhood에서 $\nabla^{2}f(x)$가 Lipschitz continuous하고, $x_{k+1}=x_{k}+p^{N}_{k}$라 하자. 그러면

1. 시작점 $x_{0}$이 $x^{\ast}$에 충분히 가깝다면, $\{x_{k}\}$는 $x^{\ast}$로 수렴한다.
2. $\{x_{k}\}$의 rate of convergence는 quadratic이다.
3. gradient norm $\{ \vert\vert \nabla f_{k}\vert\vert \}$ 역시 0으로 quadratic하게 수렴한다.

• 증명

  $\nabla f_{\ast}=0$이니

  $x_{k}+p^{N}_{k}-x^{\ast}=x_{k}-x^{\ast}-\nabla^{2} f^{-1}_{k}\nabla f_{k}\\ =\nabla^{2} f^{-1}_{k}\left[ \nabla^{2}f_{k}(x_{k}-x^{\ast})-(\nabla f_{k}-\nabla f_{\ast} )\right]$

  이 때, Taylor’s theorem에 의해

  $\nabla f_{k} - \nabla f_{\ast}=\int^{1}_{0} \nabla^{2} f(x_{k}+ t(x^{\ast}-x_{k}))(x_{k}-x^{\ast})dt$

  이므로,

  $\vert\vert \nabla^{2} f(x_{k})(x_{k}-x^{\ast})-(\nabla f_{k}-\nabla f_{\ast}))\vert\vert \\ =\left\| \int^{1}_{0} [\nabla^{2}f(x_{k})-\nabla^{2}f(x_{k}+t(x^{\ast}-x_{k}))](x_{k}-x^{\ast})dt \right\| \\ \leq \int^{1}_{0} \|\nabla^{2}f(x_{k})-\nabla^{2}f(x_{k}+t(x^{\ast}-x_{k}))\| \|x_{k}-x^{\ast}\|dt \\ \leq \| x_{k}-x^{\ast}\|^{2} \int^{1}_{0} Lt \,dt = \frac{1}{2}L\|x_{k}-x^{\ast}\|^{2}$

  마지막 줄 부등호는 Lipschitz continuous에서 나왔다. $\nabla^{2} f(x^{\ast})$가 nonsingular (positive definite이면 nonsingular이다.)이므로 $\| x_{k}-x^{\ast} \| \leq r$인 모든 $x_{k}$에 대해 $\|\nabla^{2}f^{-1}_{k} \| \leq 2\|\nabla^{2} f_{\ast}^{-1}\|$을 만족하는 $r>0$이 존재한다. (https://math.stackexchange.com/questions/2846580/properties-of-norms-of-inverse-hessians-near-a-solution)

  $\| x_{k}+p^{N}_{k}-x^{\ast}\|\leq L\|\nabla^{2}f_{\ast}^{-1}\|\|x_{k}-x^{\ast}\|^{2}=\tilde{L}\|x_{k}-x^{\ast}\|^{2}$

  이 때, $\tilde{L}=L\|\nabla^{2}f^{-1}_{\ast}\|$이다. 초기값 $x_{0}$을 $\|x_{0}-x^{\ast}\|\leq \min (r, 1/(2\tilde{L}))$을 만족하도록 잡으면 sequence $\{x_{k} \}$는 $x^{\ast}$로 quadratic 하기 수렴한다. (min에서 정확히 $1/(2\tilde{L})$일 필요 없이 $1/\tilde{L}$보다 작은 값이면 될 것 같다.)

  이제 $\{\nabla f_{k} \}$가 0으로 수렴함을 보이자.

  $\|\nabla f_{k+1}\|= \|\nabla f_{k+1}-\nabla f_{k}- \nabla^{2}f_{k}p^{N}_{k}\| \\ =\left\| \int^{1}_{0} \nabla^{2}f (x_{k}+t p^{N}_{k})(x_{k+1}-x_{k})dt-\nabla^{2}f_{k}p^{N}_{k}\right\|\\ \leq \int^{1}_{0} \|\nabla^{2}f (x_{k}+t p^{N}_{k})-\nabla^{2} f_{k}\|\|p^{N}_{k}\|dt \\ \leq \frac{1}{2} L \|p^{N}_{k}\|^{2} \leq \frac{1}{2} L \|\nabla^{2} f(x_{k})^{-1}\|^{2}\|\nabla f_{k}\|^{2} \\ \leq 2L \|\nabla^{2} f(x^{\ast})^{-1}\|^{2}\|\nabla f_{k}\|^{2}$

Quasi-Newton method

Step length $\alpha_{k}$는 Wolfe condition을 만족하도록 back tracing을 통해 얻는 상황을 가정 ($\bar{\alpha_{k}}=1$).

Theorem 3.6

$f$가 twice continuously differentiable이라 가정하자. $x_{k+1}=x_{k}+\alpha_{k}p_{k}$를 통해서 업데이트하는데, 이 때, $p_{k}$가 descent direction이고 $\alpha_{k}$가 Wolfe condition을 $c_{1}\leq1/2$로 만족한다고 하자. 만약 $\{ x_{k} \}$가 $\nabla f(x^{\ast})=0$이고 $\nabla^{2}f(x^{\ast})$가 positive definite인 점 $x^{\ast}$로 수렴한다 가정하고, 또 만약 search direction $p_{k}$가

$\lim_{k\rarr \infty} \frac{\| \nabla f_{k} + \nabla^{2}f_{k}p_{k} \|}{\| p_{k} \|}=0$

을 만족하면

1. 모든 $k>k_{0}$에 대해 $a_{k}=1$이 허용되고,
2. 1의 경우 $\{ x_{k}\}$가 $x^{\ast}$로 superlinearly converge 한다.

마지막 search direction 조건은 quasi-Newton method에서

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

와 동등하다. 즉 $B_{k}$가 $p_{k}$를 따라서만 $\nabla^{2} f(x^{\ast})$를 approximation하면 성립한다. 이 조건은 필요충분조건이다.

Theorem 3.7

$f$가 twice continuously differentiable이라 가정하자. $x_{k+1}=x_{k}+p_{k}$를 통해서 업데이트하는데, 이 때, $p_{k}=-B^{-1}_{k}\nabla f_{k}$라고 하자. 만약 $\{ x_{k} \}$가 $\nabla f(x^{\ast})=0$이고 $\nabla^{2}f(x^{\ast})$가 positive definite인 점 $x^{\ast}$로 수렴한다 가정하자. 그러면, $\{ x_{k}\}$이 superlinearly converge한다는 아래의 조건과 동치이다.

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

• 증명
  먼저 search direction 조건이
  $p_{k}-p^{N}_{k}=o(\|p_{k}\|)$
  과 동치임을 증명한다.
  $p_{k}-p^{N}_{k}=\nabla^{2} f^{-1}_{k}(\nabla^{2}f_{k}p_{k}+\nabla f_{k})\\= \nabla^{2}f^{-1}_{k}(\nabla^{2} f_{k}-B_{k})p_{k} \\ = O(\| (\nabla^{2}f_{k}-B_{k})p_{k}\|) \\ =o(\|p_{k}\|)$
  $O$가 들어간 등호는 $x^{\ast}$에 충분히 가까운 $x_{k}$에 대해서 $\|\nabla^{2}f^{-1}_{k}\|$가 위로 bound 되어 있다는 점에서 성립한다 ($\nabla^{2}f(x^{\ast})$이 positive definite해서. Theorem 3.5 증명의 링크 참조). 마지막 $o$가 들어간 등호는 search direction 조건이 만족한다는 조건하에 성립한다. 거꾸로 $p_{k}-p^{N}_{k}=o(\|p_{k}\|)$이면 search direction 조건이 만족된다는 증명은
  $\nabla^{2}f_{k}o(\|p_{k}\|)=o(\|p_{k}\|)\\=\nabla^{2}f_{k}(p_{k}-p^{N}_{k})\\=(\nabla^{2}f_{k}-B_{k})p_{k}$
  이다.
  $\| x_{k}+p_{k}-x^{\ast}\| \leq \| x_{k}+p^{N}_{k}-x^{\ast}\|+\|p_{k}-p^{N}_{k}\|\\=O(\|x_{k}-x^{\ast}\|^{2})+o(\|p_{k}\|)\\ \leq o(\|x_{k}-x^{\ast}\|)$
  $O$ 항은 Theorem 3.5의 증명에서 왔다(Newton method에 대한 정리). 마지막 inequality는 $\|p_{k}\|=O(\|x_{k}-x^{\ast}\|)$ ($\|p_{k}\|\leq \|x_{k}-x^{\ast}\|+\|x_{k}+p_{k}-x^{\ast}\|$)에서 왔다. 결론적으로 superlinearly converge 한다.
  
• $o$, $O$, $\Omega$ 정의

  1. $\eta_{k}=O(v_{k})$

     충분히 큰 모든 $k$에 대해 $|\eta_{k}|\leq C|v_{k}|$를 만족하는 상수 $C>0$이 존재
     

  2. $\eta_{k}=o(v_{k})$

     $\lim_{k\rarr \infty} \frac{\eta_{k}}{v_{k}}=0$

  3. $\eta_{k}=\Omega(v_{k})$

     $C_{0}|v_{k}|\leq |\eta_{k}|\leq C_{1} |v_{k}|$을 만족하는 상수 $0<C_{0}\leq C_{1}<\infty$가 존재

Newton’s method with Hessian modification

Hessian matrix가 positive definite 하지 않으면 Newton direction이 descent direction이 아닐 수 있다. Hessian을 살짝 수정해서 $p^{N}_{k}$과 크게 차이나지 않는 $p_{k}$를 구하는 일련의 알고리즘들에 대해 얘기하자. 제너럴하게 알고리즘을 적어보자면 아래와 같다. 이 때 $E_{k}$가 modification matrix이다. (일부 알고리즘은 $E_{k}$를 explicit하게 구하지 않기도 한다.)

Convergence of line search method에서 언급했듯 $\{B_{k}\}$가 bounded condition number을 가지도록 $E_{k}$를 설정하면 ($\kappa(B_{k})=\|B_{k}\|\|B^{-1}_{k}\|\leq C$. 이 때, $C>0$, $k=0,1,\dots$) global convergence를 만족할 것이다.

Theorem 3.8

$f$가 open set $\mathcal{D}$에서 twice continuously differentiable하다 가정하고, level set $\mathcal{L}=\{x\in\mathcal{D}:f(x)\leq f(x_{0})\}$이 compact하도록 Algorithm 3.2의 시작점 $x_{0}$을 잡자. $\{B_{k}\}$가 bounded condition number을 가지면

$\lim_{k \rarr\infty}\nabla f(x_{k})=0$

$\nabla^{2} f(x^{\ast})$가 충분히 positive definite 하다면 iteration이 충분히 진행되면 $k>k_{0}$에 대해 $E_{k}=0$이 되며 pure Newton method와 마찬가지로 quadratic하게 수렴한다. $\nabla^{2}f(x^{\ast})$가 singular의 가까운 경우 $E_{k}$가 vanish 할 것이라 보장할 수 없고 convergence rate도 linear 할 수 있다. $E_{k}$는 condition number 조건을 만족하는 동시에 modification을 최소화 하여야 하며, 현실적인 문제로 계산이 용이해야한다.

EVD 후 negative eigenvalue인 부분을 numerical analysis 측면에서 가장 작은 양수$\delta$로 바꾼다. 그런데 이렇게 바꿀 경우 $p_{k}=-B^{-1}_{k}\nabla f_{k}$의 방향이 eigenvalue가 $\delta$인 eigenvector로 치우치게 된다. 이를 해결하기 위한 방법에는 여러가지가 있고, 어떤게 최선인지는 합의된 바 없다. (생략) 그래도 이게 어떤 측면에서는 최선인 부분이, $A=Q\Lambda Q^{T}$가 symmetric matrix라면, 모든 eigenvalue가 $\delta$보다 크도록 만들고 minimum Frobenius norm을 가지는 $\Delta A$는

$\Delta A$는 일반적으로 non-diagonal이다. 조건을 바꿔 minimum Euclidean norm을 달성하도록 만들면 diagonal한 $\Delta A$를 얻을 수 있다.

$\nabla^{2}f(x_{k})+\tau I$가 충분히 positive definite 하도록 만드는 $\tau$는 다음 같은 알고리즘을 통해 찾을 수 있다.

다른 접근법으로는 Cholesky factorization을 하면서 diagnoal element의 값을 수정하는 방법이다. 이 방법은 modified Cholesky factor가 존재하고, 그 factor가 actual Hessian의 norm에 relative하게 bound 되고, Hessian이 충분히 positive definite 한 경우에는 modify하지 않는 것을 보장한다. 일반적인 Cholesky factorization은 $A=MM^{T}$의 형태를 띄지만 여기서는 $A=LDL^{T}$인 방식을 다루자. $A$가 indefinite하면 factorization이 존재하지 않거나, Cholesky factorization이 numerical하게 unstable해서 특정 element의 값이 지나치게 커질 수 있다. 따라서 분해하고 modify하는 것이 아니라 분해 과정 자체를 수정할 필요가 있다.

modify하는 경우 여기서 3번째의 $d_{j}$를 구하는 식만

로 바꾸면 된다. 이렇게 구한 $B_{k}$는 bounded condition number 조건을 만족한다.

마지막으로 symmetric indefinite factorization을 이용하는 방법을 소개하자. Symmetric matrix $A$는 다음과 같이 쓸 수 있다.

이 때, $L$은 unit lower triangular, $B$는 1(or 2)-dimensional block diagonal, $P$는 permutation matrix이다. Block diagonal matrix $B$를 사용함으로써 factorization이 numerically stable해진다. 또 $B$의 2x2 block은 항상 1개의 positive eigenvalue와 1개의 negative eigenvalue를 가지므로 분해하고나면 positive eigenvalue, negative eigenvalue 세기가 용이하다. symmetric indefinite factorization을 이용한 modification 방법은 먼저 $LBL^{T}$로 분해한 다음 다시 $B=Q\Lambda Q^{T}$로 EVD한다 ($B$의 구조때문에 계산복잡도가 낮다). 그 후 modification matrix $F$를 $L(B+F)L^{T}$가 충분히 positive definite 하도록

을 통해 구한다. Cholesky와 다르게 nondiagonal하다.

Step-length selection algorithms

의 minimum을 찾는 문제를 생각해보자. $p_{k}$는 descent direction ($\phi '(0)<0$)이어서 $\alpha>0$만 탐색하면 된다. 만약에 $f$가 convex quadratic ($f(x)=\frac{1}{2}x^{T}Qx-b^{T}x$)이면

이다. $f$가 일반적인 nonlinear function이면 iterative하게 탐색해야한다. Line search 알고리즘은 사용하는 derivative 정보에 따라 분류된다. 함수 값 자체만 사용하는 방식은 효율이 낮고, first derivative를 사용한다면 Wolfe condition이나 Goldstein condition을 성립하는지 확인할 수 있다. 일반적으로 $x_{k}$가 $x^{\ast}$에 충분히 가까울 때는 처음 고른 $\alpha$가 condition들을 만족할 때가 많고 line sarch를 할 필요가 없다.

일반적으로 line search는 1) bracketing phase: interval $[\bar{a},\bar{b}]$를 구하는 과정, 2) selection phase: 최종 $\alpha_{k}$를 구하는 과정으로 나뉜다. $\alpha_{k}$로 적으면 각 iteration에서 정해진 step length, $\alpha_{i}$로 적으면 한 iteration에서 line search 과정 중에 trial 해보는 step length라고 하자.

Interpolation

line search의 목적은 sufficient decrease 하는 $\alpha_{i}$ 중에 너무 작지 않은 값을 찾는 것이기 때문에 $\alpha_{i}$는 $\alpha_{i-1}$에 비해 너무 작지 않게 만든다. Sufficient decrease 조건은

알고리즘이 derivative를 적게 계산할수록 효율적이라고 정의한다. 만약 $\alpha_{0}$가 sufficient decrease하면 search를 종료한다. 그렇지 않다면, interval $[0,\alpha_{0}]$을 얻을 것이다. $\phi(0)$, $\phi '(0)$, $\phi(\alpha_{0})$을 이용해서 quadratic하게 interpolation 한다.

다음 trial value $\alpha_{1}$은 interpolation 된 함수의 minimzer로 정한다.

만약 $\alpha_{1}$이 sufficient decrease 조건을 만족하면 search는 종료, 그렇지 않으면 이번에는 $\phi(0)$, $\phi'(0)$, $\phi(\alpha_{0})$, $\phi(\alpha_{1})$ 네 정보를 가지고 cubic하게 interpolation 한다.

다시 minimizer를 통해 다음 trial value를 얻는다.

원하는 $\alpha_{i}$를 얻을 때 까지 가장 최근 두 $\phi(\alpha_{i})$ 값을 이용해서 interpolation 한다. 값이 너무 크거나 작으면 $\alpha_{i}=\alpha_{i-1}/2$로 reset한다.

만약에 derivative를 구하는 것이 계산적으로 복잡하지 않은 경우라면 $\phi(\alpha_{i-1})$, $\phi'(\alpha_{i-1})$, $\phi(\alpha_{i})$ ,$\phi'(\alpha_{i})$를 이용해서 interpolation 하는것이 좋다. 이 경우 다음 trial은

일반적으로 cubic interpolation을 이용하면 $\alpha_{i}$가 quadratic하게 converge한다.

Initial step length

Newton, quasi-Newton method에서는 항상 $\alpha_{0}=1$을 사용하는 것이 좋다. Steepest descent나 conjugate gradient 같은 경우(scale sensitive한 알고리즘)에는 알고있는 정보를 활용해야하는데, 가장 보편적인 전략은 first-order 변화가 저번 step과 이번 step에서 동일할 것이라 가정하는 것이다. 즉, $\alpha_{0}\nabla f^{T}_{k}p_{k}=\alpha_{k-1}\nabla f^{T}_{k-1}p_{k-1}$이므로

다른 방법은 $f(x_{k-1})$, $f(x_{k})$, $\nabla f^{T}_{k-1}p_{k-1}$을 이용해서 interpolation 하는 방법이고, 이 경우

가 된다. $x_{k}\rarr x^{\ast}$ superlinearly converge 할 때, 위 식의 값은 1로 수렴한다.

Line search algorithm for the Wolfe condition

알고리즘은 2단계로 구성되어있다. 먼저 initial trial $\alpha_{1}$로 시작해서 acceptable한 step length를 찾거나, desired step length가 있을 interval을 찾을 때까지 값을 키운다. 만약에 interval을 구했다면, zoom 과정을 통해 acceptable한 step length를 찾을때까지 값을 줄여나간다.

Algorithm 3.5는 아래의 3 조건 중 하나를 만족하면 interval $(\alpha_{i-1}, \alpha_{i})$에 strong Wolfe condition을 만족하는 step length가 포함되어 있다는 사실을 이용한다.

1. $\alpha_{i}$가 sufficient decrease 조건을 위배한다.
2. $\phi(\alpha_{i})\geq \phi(\alpha_{i-1})$
3. $\phi'(\alpha_{i})\geq 0$

다음 trial value $\phi(\alpha_{i+1})$을 찾기 위해서는 interval $(\alpha_{i}, \alpha_{max})$ 사이의 값 하나를 찾는다(여러 방법을 생각해볼 수 있다.).