라인서치 (Line Search) 방법

제약조건이 없는 최적화 문제

 

$$\begin{array}{}\text{(1)}& \underset{\mathbf{x}}{min}f(\mathbf{x})\end{array}$$

 

는 보통 초기 추측값 ${\mathbf{x}}^{(0)}$ 에서 시작하여 이터레이션(iteration)을 통하여 일련의 중간 단계의 해 ${\mathbf{x}}^{(k)}$ 를 구하며 점진적으로 최적해에 접근하는 방법을 취한다.

 

 

이터레이션의 다음 단계의 해 ${\mathbf{x}}^{(k+1)}$ 는 현 단계 해 ${\mathbf{x}}^{(k)}$ 에서 일정 스텝(step) $\mathrm{\Delta }{\mathbf{x}}^{(k)}$ 으로 일정한 스텝사이즈 ${\eta }^{(k)}$ 만큼 이동시켜 구하게 된다.

 

$$\begin{array}{}\text{(2)}& {\mathbf{x}}^{(k+1)}={\mathbf{x}}^{(k)}+{\eta }^{(k)}\mathrm{\Delta }{\mathbf{x}}^{(k)}\end{array}$$

 

$\mathrm{\Delta }{\mathbf{x}}^{(k)}$ 를 탐색 방향(search direction)이라고도 하는데, 경사하강법(gradient descent)에서는 목적함수 $f(\mathbf{x})$ 의 그래디언트의 반대 방향인 $\mathrm{\Delta }{\mathbf{x}}^{(k)}=-\mathrm{\nabla }f({\mathbf{x}}^{(k)})$ 를, 뉴턴방법(Newton's method)에서는 목적함수의 헤시안(Hessian)이 포함된 $\mathrm{\Delta }{\mathbf{x}}^{(k)}=-{({\mathrm{\nabla }}^{2}f({\mathbf{x}}^{(k)}))}^{-1}\mathrm{\nabla }f({\mathbf{x}}^{(k)})$ 를 사용한다.

스텝사이즈 ${\eta }^{(k)}$ 는 크지고 작지도 않은 적당한 값으로 정해야 한다. 너무 크면 발산할 수 있고 너무 작으면 수렴 속도가 매우 느릴 수 있기 때문이다.

라인서치(line search)는 스텝사이즈 $\eta$ 를 정하는 방법이다. 최적의 스텝사이즈는 다음과 같은 최적화 문제를 풀면 된다.

 

$$\begin{array}{r}\text{(3)}& & \underset{\eta }{min}f({\mathbf{x}}^{(k)}+\eta \mathrm{\Delta }{\mathbf{x}}^{(k)})\\ & \text{subject to : }\eta \ge 0\end{array}$$

 

매 이터레이션 마다 또 다른 최적화 문제를 풀어야 하는 위 방법 대신에 실제로 많이 사용되는 방법은 백트래킹 라인서치(backtracking line search) 방법이다.

기본 개념은 스텝사이즈가 너무 작지 않도록 일단 탐색 방향으로 일정 사이즈만큼 이동한 후 점차 사이즈를 줄여가면서 목적함수의 값이 전 단계 이터레이션 값보다 작아지는지 확인하는 것이다.

    0. $\eta >1$ (보통 $\eta =1$), $\beta \in (0,1)$ 을 설정한다.

    1. 다음을 반복한다.

        [1] $f({\mathbf{x}}^{(k)}+\eta \mathrm{\Delta }{\mathbf{x}}^{(k)})<f({\mathbf{x}}^{(k)})$ 이면 이터레이션을 중지한다.

        [2] $\eta \leftarrow \beta \eta$

위와 같은 백트래킹 라인서치 기본 알고리즘은 스텝사이즈가 너무 작아지는 것은 방지했지만, 너무 큰 크기의 스텝이 발생할 수 있는 단점이 있다. 이것을 보완하고자 다음과 같이 이터레이션 종료조건을 수정한 알고리즘이 많이 사용된다.

    0. $\eta >1$ (보통 $\eta =1$), $\beta \in (0,1)$, $\alpha \in (0,0.5)$ 를 설정한다.

    1. 다음을 반복한다.

        [1] $f({\mathbf{x}}^{(k)}+\eta \mathrm{\Delta }{\mathbf{x}}^{(k)})<f({\mathbf{x}}^{(k)})+\alpha \eta {\mathrm{\nabla }}^{T}f({\mathbf{x}}^{(k)})\mathrm{\Delta }{\mathbf{x}}^{(k)}$ 이면 이터레이션을 중지한다.

        [2] $\eta \leftarrow \beta \eta$

 

알고리즘 [1]의 이터레이션 종료조건에 의하면, $f({\mathbf{x}}^{(k)}+\eta \mathrm{\Delta }{\mathbf{x}}^{(k)})$ 의 값이 $f({\mathbf{x}}^{(k)})$ 에서의 1차 테일러 근사화에 의해 계산되는 감소량 $\eta {\mathrm{\nabla }}^{T}f({\mathbf{x}}^{(k)})\mathrm{\Delta }{\mathbf{x}}^{(k)}$ 의 일정 비율 $\alpha$ 배 이상이라면 함수의 값이 충분히 감소했다고 간주한다.

 

 

위 그림에서 보듯 기본 알고리즘에 의한 종료조건 (${\eta }_2\mathrm{\Delta }\mathbf{x}$) 보다 수정 알고리즘의 종료조건 (${\eta }_1\mathrm{\Delta }\mathbf{x}$)이 스텝의 크기가 작다는 것을 알 수 있다.