논문

하루에도 수만개의 글자를 읽고 있습니다. 하루에도 수백장의 종이를 들춰 읽습니다.
이것은 그 읽기에 대한 일기입니다.

Steepest descent with line search

http://www.matf.bg.ac.rs/tempus/wp-content/uploads/2011/08/lecturenotes.pdf

Optimization, Lecture notes, 2011 summer, Greg von Winckel, 2011/08/15, Institute for Mathematics and Scientific Computing Karl-Franzens-Universität Graz

4.1 Steepest descent with line search

어떤 함수 $ f(x) $ 가 부드럽게 변하는 함수이지만 quadratic 다항식은 아니라고 가정해보자. 시작 지점 $ x_0 $에서 함수가 변하는 방향인 그래디언트 $ p_0 = \nabla f(x_0) $를 계산하면 이를 우리가 찾고자 하는 최저점의 위치로 향하는 방향으로 사용할 수 있을 것이다. 이 그래디언트의 값이 0이 아닌 한, $ x_0 $ 주변에는 $ f(x) \lt f(x_0) $인 지점이 존재한다는 것이다. 단, 함수가 quadratic이 아니기 때문에 이 그래디언트는 지점에서 변화하는 방향만을 제시해줄 뿐 정확한 위치를 가리키는 것이 아니기 때문에 최저점으로 향하는 다음 지점은 $ x_1 = x_0 + \alpha_0 p_0 $ 과 같이 그래디언트 방향으로 길이 $ \alpha_0 $만큼 이동한 위치로 사용해보도록 하자. 그렇다면 원하는 a는 아래와 같이 나타낼 수 있다.

$$min_{a} \phi(\alpha) = f(x_0 + \alpha p_0), \alpha \gt 0 $$

또한 $ a $에 대하여 $ f(x) $의 변화율은 아래와 같다.

$$\phi'(\alpha) = p_0^T \nabla f(x_0 + \alpha p_0)$$

적당한 a를 찾기 위해서는 위의 두 식의 계산이 많이 이루어지는데 이것의 계산량은 부담이 된다. 따라서 효율적으로 $ \alpha $를 찾는 방법을 고려하여야 한다. 바로 Line searches 방법이다. 그래디언트 방향을 따라 $a$를 변경해가며 주어진 조건에 맞는지를 확인하여 $ \alpha $를 결정할 것이다.

4.1.1 The Wolfe Conditions

일반적으로 자주 사용되는 조건 중 하나인 이 방법은 함수 f를 충분히 감소시키도록 $\alpha$를 결정한다. 아래 조건에 따라 $ \alpha $를 찾고자 한다.

  • Armijo condition:

$$f(x_k + \alpha p_k) \leq f(x_k) + c_1 \alpha p_k ^T \nabla f_k$$

c1은 0과 1 사이의 상수로 문제에 따라 다르게 지정하면 되는데 보통 $ 10^{-4} $ 정도의 값이 사용된다.

  • Curvature condition:

$$p_k^T \nabla f(x_k + \alpha p_k) \geq c_2 p_k^T f_k$$

c2는 c1과 1 사이의 값으로 conjugate gradient 방법에서는 0.1을, (quasi)-Newton 방법에서는 0.9를 보통 사용한다.

이 두 조건을 묶어 Wolfe conditions이라고 한다.

변형된 버전으로 strong Wolfe conditions가 있다.

$$f(x_k + \alpha p_k) \leq f(x_k) + c_1 \alpha p_k ^T \nabla f_k$$

$$|p_k^T \nabla f(x_k + \alpha p_k) | \leq c_2 |p_k^Tf_k|$$

4.1.2 Sufficient decrease and backtracking

위의 조건만으로는 적절한 $ \alpha $를 찾기가 힘들고, 값을 어떻게 찾아가야 하는지에 대한 방법이 필요하다. 가장 간단한 방법으로 backtracking line search를 알아보자. 이 방법은 한 $ \alpha $에 대해 시도해보고 조건에 맞는 값인지 알아보고 조건에 맞지 않으면 $ \alpha $를 줄인 뒤 다시 시도해보는 방법이다.

Input: $ \alpha_{max} $, $ \rho \in (0, 1) $

Output: $ \alpha_k $

while $ f(x_k + \alpha p_k) \gt f(x_k) + c \alpha p_k^T \nabla f_k $ do
| $ \alpha \leftarrow \rho \alpha $
end

$ \alpha_k \leftarrow \alpha $

일반적으로 (qusai)-Newton 방법에서는 $ \alpha_{max} = 1 $ 를 사용한다. $ \rho $ 는 매 반복마다 다른 값을 사용할 수 있으며 이러한 경우에는 0과 1 사이의 값으로 제한하도록 한다.

이 방법은 많은 반복을 수행하여 $ \alpha_k $를 찾기 때문에 Newton 방법에 적절하나 quasi-Newton나 conjugate gradient같은 방법들에는 다른 적절한 방법이 필요하다.

4.1.3 Convergence of line search methods

Line search 방법은 $ p_k \neq \nabla f_k $ 이라면 두 벡터 사이의 각도, 즉 함수가 낮아지는 방향과 현재 지점의 그래디언트와의 각도 $ \theta_k $$ \pm \pi / 2 $이내로 $p_k$를 제한하면 해당 지역에서의 최소지점으로 수렴하는 것이 증명되어있다고 한다.


Add a Comment Trackback