Line Search Method에서 Step Length 정하기

주로 line search 방법에서는 descent direction $p_k$ 가 정해졌을때 다음과 같은 update를 한다.
$$x_{k+1} = x_k + \alpha p_k$$
여기서 $a_k$ 는 양의 실수이며 step length라고 부른다. 이 글에서는 step length를 정하는 방법을 알아보겠다.

Step length를 정할때 보통 trade-off가 존재한다. 예를 들어, step length가 너무 작으면, optimum point를 도달하는데 시간이 너무 걸리고, step length가 크면 diverge할 가능성이 있다. 최선의 방법은 다음과 같은 univariate 함수에서 제일 작은 $\alpha$를 찾는 것이다:
$$\phi(\alpha) = f(x_k + \alpha p_k)$$
하지만 위에 식을 찾는데에는 시간이 오래걸리기 때문에, 보통 위 $\alpha^*$를 approximate 할 수 있는 수를 찾는다. 다른식으로 표현하지만 inexact solution을 찾는것이다. Step length를 찾는 알고리즘은 보통 두 stage로 나뉜다. 첫번째 bracketing stage는 대략적인 $\alpha$의 interval를 찾는다. 두번째 bisection stage는 이 interval안에 더 좋은 $\alpha$ 값을 찾는다.

제일 간단한 방법은 다음 식을 만족하는 $\alpha$를 고르는 것이다.
$$f(x_k + \alpha p_k) < f(x_k)$$
하지만 위 식으로 converge를 guarentee 하는것은 부족하고, 엄청 작은 $\alpha$를 고를 수도 있다. 따라서 아래에 소개하는 알고리즘들은 sufficient decrease condition이란 개념을 이용한다.

Wolf Condition

Wolfe condition은 우선 $\alpha$가 $f$라는 함수의 값을 많이 줄이는 sufficient decrease condition을 정의한다. 이는 다음과 같다.
$$f(x_k + \alpha p_k) \leq f(x_k) + c_1 \alpha \nabla f_k^T p_k$$
여기서, $c_1 \in (0, 1)$. 위 식은 Armijio condition이라고 불리기도 한다. 위 식을 분석해보자면, $c_1 \alpha \nabla f_k^T p_k$는 linear function이며 현재 tangent line을 보여준다. Sufficient decrease condition는 $\alpha$가 위에 있는 line보다 밑에 있어야 함을 보여준다. 이 condition은 algorithm이 reasonable progress를 하고 있을수 있게한다. 아래에 있는 그래프를 봤을때 $l(\alpha) = f(x_k) + c_1 \alpha \nabla f_k^T p_k$ 이며, 위 condition을 만족하는 $\alpha$는 acceptable이라 적혀있는 region이다.

위 식을 봤을때, sufficient decrease condition이 아주 작은 $\alpha$도 허용할수도 있음을 보여준다. 따라서 하나의 추가적은 condition을 부가한다. 두번째 condition은 curvature condition이라고 부르고 다음과 같이 정의한다.
$$\nabla f (x_k + \alpha p_k)^T p_k \geq c_2 \alpha \nabla f(x_k)^T p_k$$.
여기서 $c_2 \in (c_1, 1)$ 이다. 옆에 있는 항은 $\phi ‘ (\alpha)$ 와 동일하다. 따라서, 이 condition은 $\alpha$가 도달했을때 slope가 커야한다는 것을 보여준다. 만약에 slope가 비슷하면 조금 더 갔을때 더 많은 progress를 얻을수 있기 때문에 다음 condition은 존재한다. 두 condition을 모두 만족하는 $\alpha$값을 다음 그래프를 통해 볼수있다.

이 두 condition을 우리는 wolfe condition이라고 부른다. 추가적으로 strong wolfe condition은 다음을 만족한다:
$$\begin{align}
f(x_k + \alpha p_k) &\leq f(x_k) + c_1 \alpha \nabla f (x_k)^T p_k\\
|\nabla f(x_k + \alpha p_k)^T p_k| \leq c_2 |\nabla f_k^T p_k |
\end{align}$$
Strong wolfe condition은 $\phi ‘ (\alpha)$가 positive하는 것을 막아준다.

$f:\mathbb{R}^n \to \mathbb{R}$ 라는 함수가, continously differentiable 하고 bounded below할 때 wolfe condition을 만족하는 $\alpha$가 있는 것을 증명하는 것은 어렵지 않다.

Goldstein Condition

Wolfe condition과 비슷하게 goldstein condition은 $\alpha$ 가 너무 작은 것을 방지한다. 위에 식과 비교 했을 때 비교적 간단하며, condition은 다음과 같다:
$$f(x_k) + (1-c) \alpha \nabla f_k^T p_k \leq f(x_k + \alpha p_k) \leq f(x_k) + c \alpha \nabla f_k^T p_k$$
참고로 오른쪽 inequality는 sufficient decrease condition이며 $0 < c < 1/2$ 이다. $c$ 가 주어졌을 때 두 slope를 긋고 그 사이에 있는 $\alpha$ 를 선택하는거다. 그래프로 표현하면 다음과 같다.

한 단점은 minimum point을 제외할수있다는 점이다. 따라서 one iteration convergence는 불가능 할수 있다. 하지만 converge theory는 wolfe condition과 비슷하다.

Backtracking

위 식들에서 sufficient decrease condition 추가의 condition을 부여하였다. 하지만 알고리즘이 $\alpha$ 를 적절하게만 정하면 sufficient decrease condition만으로 좋은 $\alpha$를 찾을수있다. Backtracking 알고리즘은 다음과 같다.

Netwon method에서 $\bar{\alpha}$ 는 주로 1로 설정한다. Backtracking 알고리즘은 $\alpha_k$ 가 너무 크거나 작은 것을 방지한다.

출처:
[1] Nocedal, Jorge, and Stephen Wright. Numerical optimization. Springer Science & Business Media, 2006.

댓글 남기기

이 사이트는 스팸을 줄이는 아키스밋을 사용합니다. 댓글이 어떻게 처리되는지 알아보십시오.

Site Footer

Sliding Sidebar

%d 블로거가 이것을 좋아합니다: