Armijo Backtracking Line Search (Unconstrained Optimization)

Unconstrained Optimization

Armijo Backtracking Line Search

많은 Line search method중 가장 성공적인것은 Armijo backtracking line search이다.

먼저 basic backtracking line search를 알아보자. 가능한 큰 \(\alpha_{init}\) 에서 시작하여 \(f(x_k+\alpha_k p_k)<f(x_k)\) 를 만족할때 까지 \(\alpha_k\) 를 감소 시킨다. 하지만 이 방법은 \(\alpha\) 가 너무 커지는것을 막을 수 없다.

Algorithm: Backtracking line search

1. $x=x_0$, $k=0$
2. while (not converged)
3.    Given $\alpha_{init}>0 (e.g., \alpha_{init}=1)$
4.    let $\alpha=\alpha_{init}$ and $l=0$
5.    while $f(x_k+\alpha p_k)<f(x_k)$
6.       $\alpha=\tau\alpha$, where $\tau \in (0,1) (e.g., \tau=\frac{1}{2})$
7.    end
8. end

Armijo condition 은 함수값이 감소하는 \(\alpha\) 값을 좀 더 간단하게 준다.

\[ f(x_k+\alpha_k p_k)\leq f(x_k) + \alpha_k \beta p_k^T \nabla f(x_k), \]

여기서 \(\beta \in (0,1)\) (e.g., \(\beta=0.1\) or \(\beta = 0.0001\)). 또한 \(p_k^T \nabla f(x_k)<0\) 이므로 함수는 감소한다.

Algorithm: Armijo backtracking line search

1. $x=x_0$, $k=0$
2. while
3.    Given $\alpha_{init}>0 (e.g., \alpha_{init}=1)$
4.    let $\alpha=\alpha_{init}$ and $l=0$
5.    while $f(x_k+\alpha_k p_k)\leq f(x_k) + \alpha_k \beta p_k^T \nabla f(x_k),$
6.       $\alpha=\tau\alpha$, where $\tau \in (0,1) (e.g., \tau=\frac{1}{2})$
7.    end
8. end

Armijo backtracking line search 는 \(\alpha\) 값이 너무 크거나, 너무 작거나 하는것을 방지해준다.

Theorem Let \(f:\mathbb{R}^n \rightarrow \mathbb{R}\) continuously diffenentiable, and let \(\nabla f\) be locally Lipschitz continuous at \(x_k\) with Lipschitz constant \(L(x_k)\),

\[ \left\| \nabla f(x_k+x) - \nabla f(x_k) \right\|_2 \leq L(x_k) \| x \|_2. \]

If \(\beta \in (0,1)\) and \(p_k\) is a descent direction of \(f\) at \(x_k\), then Armijo condition

\[ f(x_k+\alpha p_k) \leq f(x_k) + \alpha \beta p_k^T \nabla f(x_k) \]

is satisfied for all \(\alpha \in [0, \alpha_{\max} (x_k, p_k)]\), where

\[ \alpha_{max} (x_k,p_k) = \frac{2(\beta-1)p_k^T \nabla f(x_k)}{L(x_k)\|p_k\|^2_2}. \]

Proof

Corollary Under the condition of the previous theorem, the backtracking Armijo line search therminates with

\[ \alpha_k \geq \min \left( \alpha_{init}, \cfrac{2 \tau(\beta-1)p_k^{T} \nabla f(x_k)}{L(x_k)\| p_k \|^2_2} \right). \]

Proof

Theorem Let \(f: \mathbb{R}^n \rightarrow \mathbb{R}\) be \(\nabla f\) be locally Lipschitz at \(x_k\) with Lipschitz constant \(L(x_k)\). Then the generic minimization algorithm with backtracking Armijo line search leads to one of the following results:

1. \(\nabla f(x_k)=0\) for some \(k\geq 0\).

2. \(\lim_{k\rightarrow \infty} f(x_k)=-\infty\).

3. \(\lim_{k\rightarrow \infty} \min \left( |p_k^T \nabla f(x_k)|, \cfrac{|p^T_k \nabla f(x_k)|}{\| p_k \|_2} \right)=0\)

Proof

성공적인 알고리즘을 위해서 descent direction 조건이 추가 되어야 한다.