Line Search Methods for Unconstrained Optimisation
Line Search Methods for Unconstrained Optimisation
https://people.maths.ox.ac.uk/hauser/hauser_lecture2.pdf
The Generic Framework
풀고자 하는 문제, unconstrained minimisation problem는
$$min_{x \in R^n} f(x)$$
을 만족하는 x를 찾는 것이다. 수식을 정확히 알고 있지 않는 이상, 알고리즘들은 일반적으로 특정 초기 위치 $ x^0 $ 에서 시작하여 x를 갱신 $ x^k \rightarrow x^0 $시켜가며 해답을 찾는 과정을 거치게 된다. 당연하겠지만 매 반복마다 선택되는 $ x^{k+1} $는 $ f(x^{k+1}) \lt f(x^k) $ 이어야 할 것이다.
Generic Line Search Method
이를 정리해보면 아래와 같다.
- 초기 값 $x^0$을 선택, $k=0$
- $x^k$가 수렴할 때 까지 반복한다.
- x를 이동할 방향 $p^k$을 정한다.
이는 $[g^k]^Tp^k \lt 0, \text{if }g^k \neq 0$ 이어야 한다. - 얼마나 이동할지, 그 길이 $ \alpha^k \gt 0 $를 정한다.
이 값은 $ f(x^k + \alpha^k p^k) \lt f^k $가 되어야 한다. - $ x^{k+1} = x^k + \alpha^k p^k $
- x를 이동할 방향 $p^k$을 정한다.
거의 모든 알고리즘들은 2.1, 2.2부분을 어떻게 하느냐에 따라 달라진다.
Computing a Step Length $\alpha^k$
중요한 부분 중 하나는 적절한 $ \alpha^k $를 찾는 것이다. 이 값은 너무 커서도 안되고 너무 작아도 안될 것이다.
Backtracking Line Search
단순한 방법으로 $\alpha$를 일정한 비율로 줄여가면서 탐색하는 backtracking line search를 생각해 볼 수 있다.
- 0보다 큰 값 $ \alpha_{init}$를 초기값으로 사용하여 $alpha^{(0)}, l=0$에서부터 시작한다.
- $ f(x^k + \alpha^{(l)}p^k) \lt f^k $ 이 될때까지 다음을 반복한다.
- $ f(x^k + \alpha^{(l)}) $ where $\tau \in (0, 1)$
- l을 1 증가시킨다.
- $ \alpha^k = \alpha^{(l)} $
이 방법은 $\alpha$가 지나치게 길게 설정되는 것을 막을 수는 없다.
Backtracking-Armijo Line Search
위의 backtracking 방법에서 2번의 조건을 조금 강화보자.
- 0보다 큰 값 $ \alpha_{init}$를 초기값으로 사용하여 $alpha^{(0)}, l=0$에서부터 시작한다.
- $ f(x^k + \alpha^{(l)}p^k) \leq f(x^k) + \alpha^{(l)} \beta \dot [g^k]^T p^k $ 이 될때까지 다음을 반복한다.
- $ f(x^k + \alpha^{(l)}) $ where $\tau \in (0, 1)$
- l을 1 증가시킨다.
- $ \alpha^k = \alpha^{(l)} $
수정된 조건을 Armijo condition이라고 하며, 이는 Taylor 1차 근사값의 $ \beta $를 곱한 값보다 $\alpha$만큼 이동한 곳의 값이 더 낮아야 함을 의미한다.
Computing a Search Direction $ p^k $
또 다른 중요한 부분은 x를 이동할 방향 $p^k$를 어떻게 결정한 것인가에 관한 방법이다.
Method of Steepest Descent
단순한 접근법으로 이동할 방향으로 그래디언트를 이용하는 방법이다.
$$p^k = -g^k$$
이를 steepest-descent 방법이라고 한다. 이 방법의 특징은,
- 어떤 지점에서 시작해도 어느 한 점으로는 수렴한다.
- 많은 다른 방법들도 그 과정이 실패하면 이 방법으로 전환한다.
- 함수의 스케일에 영향을 받는다.
- 수렴 속도가 매우 느리다.
- 그 값은 꼭 수렴하지 않을 때도 있다.
More General Descent Methods
만약 한 행렬 $ B^k $가 symmetric하고 Positive definite matrix (PDM)이라면 다음 식을 통해 $p^k$를 정의할 수 있다.
$$B^k p^k = -g^k$$
이는 positive definite matrix의 성질에 따라,
$$[g^k]^T p^k = - [g^k]^T [B^k]^{-1} g^k \lt 0$$
이기 때문에 $p^k$는 값이 낮아지는 방향이 된다.
이 B 행렬로써 Hessian matrix를 사용하면 Newton method라고 부른다. 또한, 이 B 행렬을 매 반복마다 업데이트하면서 방향을 계산하는 방법은 통틀어 variable metric method라고 한다.
Modified Newton Methods
x점을 이동하며 그 지점에서 Hessian을 구한 뒤 이를 B로 사용하는 것은, 매 지점의 Hessian이 PDM이어야만 통하는 방법이다. 하지만 실상은 그렇지 않을 때가 많다. 따라서 그 자체가 PDM이면서도 $ H^k + M^k $가 최대한 PDM이 되도록 하는 행렬 $ M^k $를 선택하여 $ B^k = H^k + M^k $로 사용한다. 이렇게 만든 행렬 B는 $ M^k = 0 $일 경우 위의 Newton method와 완벽히 동일하게 된다.