http://pages.cs.wisc.edu/~ferris/cs730/chap3.pdf

3.2 Convergence of Line Search Method

앞에서는 step length만을 주로 이야기 했지만 사실 제대로 최소지점을 찾으려면 이 뿐 아니라 이동하는 방향 $p_k$ 도 잘 골라야 한다. 이 방향 $p_k$의 한 속성으로 steepest descent direction $ -\nabla f_k$ 와의 각도를 생각해볼 수 있다.

$$\cos \theta_k = \frac{- \nabla f_k^T p_k}{|| \nabla f_k || || p_k ||}$$

Zoutendijk condition에 따르면,

Wolfe condition을 만족하고,

$$|| \nabla f(x) - \nabla f(\bar{x}) || \leq L || x - \bar{x} ||, \text{ for all } x, \bar{x}$$

인 L이 존재한다면,

$$\sum_{k\geq 0} \cos^2 \theta_k || \nabla f_k || ^2 \lt \infty$$

이라고 한다. 이는 곧, $ cos^2 \theta_k || \nabla f_k || ^2 \rightarrow 0 $을 의미하여, line search 방법을 반복하다보면 어느 한 점으로 수렴하게 된다는 성질(global convergence)이 나타나게 된다.

따라서 $p_k$를 선택할 때 $ \cos \theta_k \geq \delta \geq 0 $를 만족하는 양수 $ \delta $가 존재하도록, 즉 90도 이상으로 크게 되지 않도록 제한한다면 이는 $ \lim_{k \rightarrow \infty}||\nabla f_k || = 0 $가 되어 한 지점으로 수렴하게 될 것이다.

하지만 꼭 이 점이 최소점을 의미하지는 않는 점을 유의하자.

마찬가지로 Newton, quasi-Newton 방법 또한 $B_k $행렬이 condition number를 가지고 positive-definite라면 한 지점을 수렴하게 되어있다고 한다.

3.3 Rate of Convergence

3.4 Newton’s Method with Hessian Modification

Hessian 행렬을 그대로 사용하지 않고 특정 행렬을 더하는 방법으로 변형을 가한 방법들을 설명하고 있다.

3.5 Step-Length Selection Algorithms

이제 ste-length를 어떻게 구할 것인지에 대해서 생각해보자.

만약 함수가 quadratic 함수 $f(x) = \frac{1}{2}x^TQx + b^Tx + c$이라면 간단하게,

$$\alpha_k = \frac{\nabla f_k^T p_k}{p_k^T Q p_k}$$

으로 계산할 수 있으나 보통의 경우 함수는 quadratic이 아닐뿐더러 어떻게 생긴지 모르는데다가 비선형이기까지하다. 따라서 반복적 방법을 통해서 최대한 적절한 $ \alpha $를 계산하게 된다. 이 때 앞에서 언급했던 Wolfe condition이나 Goldstein condition을 사용하게 되는데, 그 자체로는 조건일 뿐인지라 다음 조사할 $\alpha$를 어떻게 정하는지가 과제로 남아있다.

모든 line search 방법은 초기값 $\alpha_0$가 필요하고 반복적으로 조사할 $\alpha_i$들을 필요로 한다. 그리고 조사한 $\alpha$에서 종료 조건을 만족시키면 반복을 종료하고 그 $\alpha$를 사용한다. 이러한 과정은 보통 2가지 단계로 진행되며, 탐색을 구간을 제한하는 bracketing phase와 그 안에서 $\alpha$를 선택하는 selection phase로 이루어진다.

앞에서는 단순히 특정 상수를 곱하여 $\alpha_i$를 변화시키는 예를 들었지만 interpolation을 통하여 계산시간을 줄이는 방법을 알아보자.

Interpolation

일단 초기값 $\alpha_0$에서 Wolfe condition을 만족한다면 그 값을 그대로 사용하여도 된다. 하지만 그렇지 않다면, [0, \alpha_0] 사이에 원하는 $\alpha$값이 존재한다고 생각되어진다. 따라서 세 값, $\phi(a_0), \phi(0), \phi'(0) $을 이용하여 quadratic approximation을 통하여 가장 낮은 지점을 추정할 수 있다.

$$\alpha_1 = \frac{\phi'(0) \alpha^2_0}{2[\phi(a_0) - \phi(0) - \phi'(0)\alpha_0]}$$

이 $\alpha_1$에서도 조건을 만족하지 않으면 이번에는, $\phi(0), \phi'(0), \phi(a_0), \phi(a_1) $을 이용하여 cubic interpolation을 이용하여 다음 지점을 추측할 수 있다. 뒤이어서 필요한 지점들은 $\phi(0), \phi'(0)$와 최근 계산했던 두 지점의 값을 이용하여 같은 방법으로 interpolation을 행하면 된다. 자세한 식은 논문에 나타나있다.

직전 지점과 현재 지점이 너무 가까워진다면 너무 나가버린 경우로 $\alpha_i = \alpha_{i-1} / 2 $로 초기화하여준다.

The Initial Step Length

Newton이나 quasi-Newton 방법은 보통 초기값으로 $\alpha_0 = 1$을 사용한다. 이들 방법은 hessian 행렬을 이용하기 때문에 초기값에 영향이 적은 편이기 때문에 오히려 1을 사용하는 편이 적당하다. 하지만 steepest descent나 conjugate gradient 방법의 경우 초기 $\alpha_0$ 값에 민감한 편이다.

주로 쓰이는 방법은 gradient 공간에서 직전에 사용하였던 step과 같은 길이를 사용하는 것이다.

$$a_0 = a_{k-1} \frac{\nabla f^T_{k-1} p_{k-1}}{\nabla f^T_k p_k}$$

또 다른 방법은 $f(x_{k-1}), f(x_k), \phi'(0)$에 quadratic interpolation을 사용하는 것이다.

$$a_0 = \frac{2 (f_k - f_{k-1})}{\phi'(0)}$$

A Line Search Algorithm for the Wolfe Conditions

위의 내용을 종합한 알고리즘 정리가 논문에 나타나있다.