---
# System prepended metadata

title: Line search

---

# Line search

\begin{equation}
\underset{x}{\text{minimize}} f(x)
\end{equation}

위의 식과 같이 constraint가 없는 최적화 문제에 problem domain이 모든 영역에서 differentiable하면 (미분가능, 이건 연속이랑 다른 개념이라는 걸 고딩 때 배우지) 해당 함수의 gradient, $\nabla f = 0$ 지점이 함수의 극 값, 즉 maximum이나 minimum이 된다.
그래서 최적화 문제 풀 때 $\nabla f(x) = 0$ 의 방정식을 푸는데 (이 방정식을 만족시키는 x를 구한다) 이 과정에서 line search가 나온다.

수치해석적으로 $x$를 적절히 이동시키면서 위의 방정식이 어떤 tolerance $\epsilon$ 내에서 만족되면 연산을 정지한다. 


---
$k=0$
**while** || $\nabla f ||_{\infty} \geq \epsilon$ **do**
>search direction $p_k$ 결정
    step length $\alpha_k$ 결정
    $x_{k+1} = x_k+\alpha_k p_k$
    $k=k+1$

**end while**

---

근데 그러면 $p_k$ 랑 $\alpha_k$ 는 어떻게 결정하면 될까?
일단 subproblem으로 다른 변수들은 다 fix한 상태에서 $\alpha$를 구하는 것을 먼저 생각해 보자. $k+1$ 번째 $x$는 $x_{k+1} = x_k + \alpha p_k$ 이므로 이를 함수 $f$에 대입하면 
$f(x_{k+1}) = f(x_k + \alpha p_k) = \phi(\alpha)$
이고, 함수 $\phi$를 step length $\alpha$에 의한 함수로 정의하자.
이 함수 값은 $\alpha = 0$ 일때 $\phi(0) = f(x_k)$ 이므로 (현재 우리가 알고 있는 값) 여기서 $\phi'(0)$ 보다 좀 더 flat한 직선을 그었을 때 $\phi(\alpha)$ 값들이 이 직선보다 작아야 한다. (여기서 $\phi'(0) < 0$)

\begin{equation}
\phi(\alpha) \leq \phi(0)+\mu_1 \alpha \phi'(0) = f(x_k)+ \mu_1 \alpha \nabla f(x_k)p_k
\end{equation}

$\phi'(\alpha) = \nabla f(x_k+ \alpha p_k)p_k$
$\phi'(0) = \nabla f(x_k)p_k$

![](https://i.imgur.com/FodgTJ0.png)

이런 $\alpha$를 찾기 위해서 아래의 알고리즘 절차를 거친다.

---
**set** $\alpha_{init} > 0$, $0<\mu_1 <1$, $0<\rho <1$

$\alpha = \alpha_{init}$
**while** $\phi(\alpha) \geq \phi(0)+\mu_1 \alpha \phi'(0)$ **do**
> $\alpha = \rho \alpha$

**end while**

---

근데 거의 몇번의 iteration만 거치면 적당한 $\alpha$를 빨리 찾는다. 
$\phi'(\alpha)$가 너무 steep하면 조건을 만족하는 alpha를 찾기가 힘들다. 이때 **strong Wolfe conditions** 이라는 것을 적용하여 vertical line처럼 아예 가파르게 되는 지점을 제외시킨다.

\begin{equation}
|\phi'(\alpha)| \leq \mu_2 |\phi'(0)| 
\end{equation}