Wolfe condition이 존재한다는 증명

Let $f: \mathbb{R}^n \to \mathbb{R}$ be continously differentiable and let $p_k$ be the descent direction at $x_k$. Assuming $f$ is bounded below along the ray $\{x_k + \alpha p_k | \alpha >0 \}$. Then, if $0 < c_1 < c_2 < 1$, there exists a step length $\alpha$ that satisfies wolfe conditions and strong wolfe conditions.

증명은 비교적 간단하다. $\phi(\alpha) = f(x_k + \alpha p_k)$, $\alpha >0$ 는 당연히 bounded below이다. 추가로 $0 < c_1 < 1$ 이기 때문에 $l(\alpha) = f(x_k) + c_1 \alpha \nabla f_k^T p_k$ 와 $\phi$ 는 교차점이 생긴다. $\alpha ‘$ 를 가장 작은 교차점이라 가정했을때 다음의 식을 만족한다.
$$f(x_k + \alpha ‘ p_k) = f(x_k) + \alpha ‘ c_1 \nabla f_k^T p_k$$
따라서, sufficient decrease condition은 $\alpha ‘$ 보다 작을때 만족한다.

Mean Value Theorem (MVT)에 따라 다음 식을 만족하는 $\alpha ” \in (0, \alpha ‘)$ 이 존재한다.
$$f(x_k + \alpha ‘ p_k) – f(x_k) = \alpha’ \nabla f(x_k + \alpha ” p_k)^T p_k$$
위 두식을 합쳤을 때 다음 식을 얻을수있다.
$$\nabla f(x_k + \alpha ” p_k)^T p_k = c_1 \nabla f_k^T p_k > c_2 \nabla f_k^T p_k$$
따라서 smoothness condition을 이용하여 $\alpha ”$ 근처에 식을 만족하는 $\alpha$ 가 존재함을 알 수 있다. Strong wolfe condition도 위 식을 modify하여 얻을수있다.

댓글 남기기

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

Site Footer

Sliding Sidebar

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