Line Search Methods
Step-Size Conditions and Global Convergence
References: Jorge Nocedal and Stephen J. Wright, Numerical Optimization, 2nd ed., Springer, 2006, Ch. 3.
이 장에서는 결정론적 무제약 최적화에서 이동 방향이 주어졌을 때 step size를 선택하는 line search를 다룬다. 핵심은 특정 구현을 암기하는 것이 아니라, 어떤 조건이 충분한 감소를 만들고, 그 조건을 만족하는 step size가 실제로 존재하며, 결과적으로 반복점이 stationary point에 접근한다는 사실을 증명하는 것이다. 목적함수는 아래로 유계이고, 별도의 언급이 없으면 $f:\mathbb{R}^n\rightarrow\mathbb{R}$는 연속 미분 가능하다고 가정한다.
Line Search Framework
다음 무제약 최적화 문제를 생각한다.
\[\min_{x\in\mathbb{R}^n}f(x).\]Line-search method는
\[x_{k+1}=x_k+\alpha_k p_k\]의 형태로 반복점을 생성한다. 여기서 $p_k$는 search direction이고 $\alpha_k>0$는 step size이다. $g_k=\nabla f(x_k)$라 쓸 때
\[g_k^Tp_k<0\]이면 $p_k$는 descent direction이다. 한 iteration에서의 문제를 일변수 함수
\[\phi_k(\alpha)=f(x_k+\alpha p_k)\]로 제한하면
\[\phi_k'(\alpha)=\nabla f(x_k+\alpha p_k)^Tp_k, \qquad \phi_k'(0)=g_k^Tp_k<0\]이다. 따라서 충분히 작은 $\alpha>0$에서는 $\phi_k(\alpha)<\phi_k(0)$가 성립한다.
Exact line search는
\[\alpha_k\in\underset{\alpha>0}{\operatorname{argmin}}\ \phi_k(\alpha)\]를 계산한다. 그러나 이 일차원 최적화 문제를 정확히 푸는 비용이 원래 iteration보다 커질 수 있고, 전역 수렴에는 정확한 최소점까지 필요하지 않다. Inexact line search는 계산 가능한 부등식으로 충분한 감소와 적절한 step size를 동시에 보장한다.
Armijo Sufficient Decrease
$c_1\in(0,1)$를 고정한다. Step size $\alpha>0$가
\[f(x_k+\alpha p_k) \leq f(x_k)+c_1\alpha g_k^Tp_k\]를 만족하면 Armijo condition 또는 sufficient-decrease condition을 만족한다고 한다. $g_k^Tp_k<0$이므로 우변은 $f(x_k)$보다 작다.
Theorem: 작은 step size에서 Armijo condition의 성립
$f$가 $x_k$에서 미분 가능하고 $p_k$가 descent direction이면, 어떤 $\bar{\alpha}_k>0$가 존재하여 모든 $\alpha\in(0,\bar{\alpha}_k]$가 Armijo condition을 만족한다.
Proof
미분 가능성에 의해
\[f(x_k+\alpha p_k) = f(x_k)+\alpha g_k^Tp_k+o(\alpha)\]이다. 따라서
\[f(x_k+\alpha p_k)-f(x_k)-c_1\alpha g_k^Tp_k = (1-c_1)\alpha g_k^Tp_k+o(\alpha).\]$1-c_1>0$이고 $g_k^Tp_k<0$이므로 우변은 충분히 작은 $\alpha>0$에서 음수이다. 따라서 Armijo condition이 성립한다. $\square$
이 정리는 Armijo step이 존재한다는 사실만 보장한다. Gradient가 Lipschitz continuous하면 허용 가능한 step size의 크기를 정량적으로 구할 수 있다.
Lemma: $L$-smooth 함수의 Armijo step bound
$\nabla f$가 $L$-Lipschitz continuous라고 하자. 그러면
\[0<\alpha \leq \frac{2(1-c_1)(-g_k^Tp_k)}{L\lVert p_k\rVert^2}\]인 모든 $\alpha$는 Armijo condition을 만족한다.
Proof
Descent Lemma에 의해
\[f(x_k+\alpha p_k) \leq f(x_k)+\alpha g_k^Tp_k +\frac{L\alpha^2}{2}\lVert p_k\rVert^2.\]마지막 두 항이 $c_1\alpha g_k^Tp_k$ 이하(아미조 조건)가 되기 위한 충분조건은
\[(1-c_1)g_k^Tp_k +\frac{L\alpha}{2}\lVert p_k\rVert^2 \leq 0\]이며, 이를 $\alpha$에 대해 정리하면 주장한 bound를 얻는다. $\square$
Backtracking Line Search
$\bar{\alpha}>0$, $\beta\in(0,1)$를 정한다. Backtracking line search는
\[\alpha=\bar{\alpha},\ \bar{\alpha}\beta,\ \bar{\alpha}\beta^2,\ldots\]를 순서대로 검사하여 Armijo condition을 처음 만족하는 값을 $\alpha_k$로 선택한다.
방향의 크기가 iteration마다 지나치게 변하지 않도록 어떤 $m,M>0$에 대해
\[g_k^Tp_k\leq-m\lVert g_k\rVert^2, \qquad \lVert p_k\rVert\leq M\lVert g_k\rVert\]가 모든 $k$에서 성립한다고 하자. 이러한 조건은 search direction이 gradient와 충분한 각도를 유지하고 적절한 크기를 갖는다는 뜻이다.
Theorem: backtracking의 유한 종료와 step-size lower bound
$\nabla f$가 $L$-Lipschitz continuous이고 위의 방향 조건이 성립한다고 하자. 그러면 backtracking은 매 iteration에서 유한 번 안에 종료하고,
\[\alpha_k\geq \min\left\{ \bar{\alpha}, \frac{2\beta(1-c_1)m}{LM^2} \right\} =:\alpha_{\min}>0\]을 만족한다.
Proof
앞의 lemma와 방향 조건으로부터
\[\frac{2(1-c_1)(-g_k^Tp_k)}{L\lVert p_k\rVert^2} \geq \frac{2(1-c_1)m}{LM^2} =:\widehat{\alpha}\]를 얻는다. 따라서 $0<\alpha\leq\widehat{\alpha}$이면 Armijo condition이 반드시 성립한다. $\bar{\alpha}\beta^j\rightarrow0$이므로 backtracking은 유한한 $j$에서 종료한다.
$\bar{\alpha}\leq\widehat{\alpha}$이면 첫 후보가 선택되어 $\alpha_k=\bar{\alpha}$이다. 그렇지 않고 감소된 후보가 선택되었다면 바로 이전 후보 $\alpha_k/\beta$는 거절되었으므로 $\alpha_k/\beta>\widehat{\alpha}$이고, 따라서 $\alpha_k>\beta\widehat{\alpha}$이다. 두 경우를 합치면 주장한 lower bound를 얻는다. $\square$
Steepest-descent direction $p_k=-g_k$에서는 $m=M=1$이므로
\[\alpha_k\geq \min\left\{ \bar{\alpha}, \frac{2\beta(1-c_1)}{L} \right\}.\]Wolfe Conditions
Armijo condition은 step size가 충분히 작으면 항상 성립한다. 따라서 Armijo condition만 요구하고 임의의 허용값을 선택하면 $\alpha_k$가 불필요하게 작아질 수 있다. 이를 방지하기 위해 $0<c_1<c_2<1$에 대해 curvature condition
\[\nabla f(x_k+\alpha p_k)^Tp_k \geq c_2g_k^Tp_k\]을 함께 사용한다. Armijo condition과 curvature condition을 합쳐 weak Wolfe conditions라고 한다.
Curvature condition의 더 강한 형태는
\[\left|\nabla f(x_k+\alpha p_k)^Tp_k\right| \leq c_2\left|g_k^Tp_k\right|\]이며, Armijo condition과 이 부등식을 합쳐 strong Wolfe conditions라고 한다. Strong Wolfe conditions는 새 점에서의 directional derivative가 양 또는 음의 어느 방향으로도 지나치게 크지 않도록 제한한다.
Theorem: Wolfe step의 존재성
$p_k$가 descent direction이고 $\phi_k$가 연속 미분 가능하며 $\alpha\geq0$에서 아래로 유계라고 하자. 그러면 $0<c_1<c_2<1$에 대해 strong Wolfe conditions를 만족하는 $\alpha>0$가 존재한다. 따라서 weak Wolfe conditions를 만족하는 step도 존재한다.
Proof
표기를 단순화하여 $\phi=\phi_k$라 하고
\[\ell(\alpha)=\phi(0)+c_1\alpha\phi'(0)\]라 두자. $\phi’(0)<0$이고 $c_1<1$이므로 충분히 작은 $\alpha>0$에서는
\[\phi(\alpha)<\ell(\alpha)\]가 성립한다. 반면 $\ell(\alpha)\rightarrow-\infty$이고 $\phi$는 아래로 유계이므로 충분히 큰 $\alpha$에서는 $\phi(\alpha)>\ell(\alpha)$이다. 연속성에 의해 처음으로 두 함수가 만나는 점 $\bar{\alpha}>0$를 잡을 수 있고,
\[\phi(\alpha)<\ell(\alpha) \quad(0<\alpha<\bar{\alpha}), \qquad \phi(\bar{\alpha})=\ell(\bar{\alpha})\]이다. 평균값정리에 의해 어떤 $\widetilde{\alpha}\in(0,\bar{\alpha})$가 존재하여
\[\phi'(\widetilde{\alpha}) = \frac{\phi(\bar{\alpha})-\phi(0)}{\bar{\alpha}} =c_1\phi'(0)\]을 만족한다. $\phi’(0)<0$이고 $c_1<c_2$이므로
\[\phi'(0)<c_2\phi'(0)<c_1\phi'(0) =\phi'(\widetilde{\alpha}).\]$\phi’$의 연속성에 의해 어떤 $\alpha_W\in(0,\widetilde{\alpha})$가 존재하여
\[\phi'(\alpha_W)=c_2\phi'(0)\]이다. $\alpha_W<\bar{\alpha}$이므로 Armijo condition이 성립하고,
\[|\phi'(\alpha_W)| =c_2|\phi'(0)|\]이므로 strong curvature condition도 성립한다. $\square$
실제 Wolfe line search는 먼저 허용 구간을 bracket하고, 그 안에서 interpolation과 zoom을 반복하여 Armijo condition과 curvature condition을 동시에 만족하는 점을 찾는다. 위 정리는 이러한 탐색이 목표로 하는 step이 공집합이 아님을 보장한다.
Zoutendijk Theorem
Wolfe conditions의 핵심 결과는 한 번의 감소량이 search direction과 gradient 사이의 각도로 제어된다는 것이다. 다음과 같이 각도 $\theta_k$를 정의한다.
\[\cos\theta_k = \frac{-g_k^Tp_k}{\lVert g_k\rVert\lVert p_k\rVert}.\]$p_k$가 descent direction이면 $\cos\theta_k>0$이다.
Theorem: Zoutendijk condition
$f$가 초기 level set
\[\mathcal{L}_0=\{x:f(x)\leq f(x_0)\}\]에서 아래로 유계이고, $\mathcal{L}_0$를 포함하는 열린 집합에서 $\nabla f$가 $L$-Lipschitz continuous라고 하자. 각 $p_k$가 descent direction이고 $\alpha_k$가 weak Wolfe conditions를 만족하면
\[\sum_{k=0}^{\infty} \cos^2\theta_k\lVert g_k\rVert^2 <\infty\]이다.
Proof
Wolfe curvature condition에 의해
\[g_{k+1}^Tp_k\geq c_2g_k^Tp_k\]이므로
\[(g_{k+1}-g_k)^Tp_k \geq (1-c_2)(-g_k^Tp_k).\]한편 gradient의 Lipschitz continuity와 $x_{k+1}-x_k=\alpha_kp_k$를 사용하면
\[(g_{k+1}-g_k)^Tp_k \leq \lVert g_{k+1}-g_k\rVert\lVert p_k\rVert \leq L\alpha_k\lVert p_k\rVert^2.\]따라서
\[\alpha_k \geq \frac{(1-c_2)(-g_k^Tp_k)}{L\lVert p_k\rVert^2}.\]Armijo condition으로부터
\[f(x_k)-f(x_{k+1}) \geq c_1\alpha_k(-g_k^Tp_k)\]이고, 위 lower bound를 대입하면
\[f(x_k)-f(x_{k+1}) \geq \frac{c_1(1-c_2)}{L} \frac{(g_k^Tp_k)^2}{\lVert p_k\rVert^2} = \frac{c_1(1-c_2)}{L} \cos^2\theta_k\lVert g_k\rVert^2.\]$k=0$부터 $N-1$까지 합하고 $f_{\inf}=\inf_{x\in\mathcal{L}_0}f(x)$라 하면
\[\frac{c_1(1-c_2)}{L} \sum_{k=0}^{N-1} \cos^2\theta_k\lVert g_k\rVert^2 \leq f(x_0)-f(x_N) \leq f(x_0)-f_{\inf}.\]$N\rightarrow\infty$로 보내면 주장한 급수의 수렴을 얻는다. $\square$
Global Convergence from the Angle Condition
Zoutendijk condition만으로는 항상 $\lVert g_k\rVert\rightarrow0$이라고 결론 내릴 수 없다. Search direction이 gradient에 점차 수직이 되어 $\cos\theta_k\rightarrow0$이면 weighted sum은 유한하면서 gradient norm은 감소하지 않을 수 있다.
Corollary: uniformly gradient-related direction의 전역 수렴
어떤 $\delta>0$에 대해 모든 $k$에서
\[\cos\theta_k\geq\delta\]라고 하자. Zoutendijk theorem의 가정이 성립하면
\[\lim_{k\rightarrow\infty}\lVert g_k\rVert=0.\]Proof
\[\delta^2\sum_{k=0}^{\infty}\lVert g_k\rVert^2 \leq \sum_{k=0}^{\infty}\cos^2\theta_k\lVert g_k\rVert^2 <\infty.\]음이 아닌 급수의 합이 유한하므로 $\lVert g_k\rVert^2\rightarrow0$이다. $\square$
Steepest descent에서는 $p_k=-g_k$이므로 $\cos\theta_k=1$이다. 따라서 Wolfe line search를 사용하는 steepest descent는 위 가정 아래에서
\[\lVert\nabla f(x_k)\rVert\rightarrow0\]을 만족한다.
보다 일반적으로 $B_k$가 symmetric positive definite이고
\[m_BI\preceq B_k\preceq M_BI\]를 만족하며 $p_k=-B_kg_k$라 하자. 그러면
\[-g_k^Tp_k=g_k^TB_kg_k\geq m_B\lVert g_k\rVert^2,\] \[\lVert p_k\rVert=\lVert B_kg_k\rVert\leq M_B\lVert g_k\rVert\]이므로
\[\cos\theta_k\geq\frac{m_B}{M_B}>0.\]따라서 uniformly bounded positive-definite scaling을 사용하는 방향도 Wolfe line search 아래에서 stationary point로 전역 수렴한다.
Convergence Rates with Backtracking
Wolfe conditions와 Zoutendijk theorem은 넓은 종류의 방향에 대해 정성적인 전역 수렴을 제공한다. 명시적인 iteration complexity를 얻으려면 accepted step에 대한 균일한 lower bound가 필요하다. 앞에서 사용한 방향 조건
\[g_k^Tp_k\leq-m\lVert g_k\rVert^2, \qquad \lVert p_k\rVert\leq M\lVert g_k\rVert\]과 backtracking을 다시 생각하자. 다음 상수를 둔다.
\[a=c_1m\alpha_{\min}>0.\]Armijo condition으로부터
\[f(x_k)-f(x_{k+1}) \geq c_1\alpha_k(-g_k^Tp_k) \geq a\lVert g_k\rVert^2\]를 얻는다.
Nonconvex stationarity complexity
$f$가 아래로 유계이면
\[a\sum_{k=0}^{K-1}\lVert g_k\rVert^2 \leq f(x_0)-f_{\inf}.\]따라서
\[\min_{0\leq k<K}\lVert g_k\rVert^2 \leq \frac{f(x_0)-f_{\inf}}{aK}.\]$\lVert g_k\rVert\leq\varepsilon$인 iteration을 얻기 위한 complexity는
\[K=\mathcal{O}\left(\frac{1}{\varepsilon^2}\right)\]이다.
Convex objective의 sublinear convergence
$f$가 convex이고 minimizer $x^\star$가 존재한다고 하자. 또한 level set에서
\[\lVert x_k-x^\star\rVert\leq R\]인 $R>0$가 존재한다고 하자. $\Delta_k=f(x_k)-f^\star$라 쓰면 convexity에 의해
\[\Delta_k \leq g_k^T(x_k-x^\star) \leq R\lVert g_k\rVert.\]따라서
\[\Delta_{k+1} \leq \Delta_k-\frac{a}{R^2}\Delta_k^2.\]$\Delta_{k+1}\leq\Delta_k$를 이용하면
\[\frac{1}{\Delta_{k+1}}-\frac{1}{\Delta_k} = \frac{\Delta_k-\Delta_{k+1}}{\Delta_k\Delta_{k+1}} \geq \frac{\Delta_k-\Delta_{k+1}}{\Delta_k^2} \geq \frac{a}{R^2}.\]이를 합하면
\[f(x_k)-f^\star \leq \frac{1}{\dfrac{1}{f(x_0)-f^\star}+\dfrac{ak}{R^2}} =\mathcal{O}\left(\frac{1}{k}\right).\]Strongly convex objective의 linear convergence
$f$가 $\mu$-strongly convex이면 Polyak–Łojasiewicz inequality
\[\lVert g_k\rVert^2\geq2\mu\bigl(f(x_k)-f^\star\bigr)\]가 성립한다. 따라서 $0<2\mu a<1$인 경우
\[f(x_{k+1})-f^\star \leq (1-2\mu a)\bigl(f(x_k)-f^\star\bigr),\]즉
\[f(x_k)-f^\star \leq (1-2\mu a)^k\bigl(f(x_0)-f^\star\bigr)\]의 linear convergence를 얻는다.
What the Conditions Guarantee
| Condition | Mathematical Role | Main Result |
|---|---|---|
| Descent direction | $\phi_k’(0)<0$ 보장 | 충분히 작은 감소 step의 존재 |
| Armijo condition | 목적함수의 충분 감소 | 단조 감소와 누적 감소량 제어 |
| Wolfe curvature condition | 지나치게 작은 step 배제 | Zoutendijk lower bound 유도 |
| Strong Wolfe condition | 새 점의 directional derivative 제어 | Conjugate-gradient 및 quasi-Newton 분석에 사용 |
| Uniform angle condition | 방향이 gradient와 수직으로 퇴화하는 현상 방지 | $\lVert\nabla f(x_k)\rVert\rightarrow0$ |
| Backtracking lower bound | accepted step의 정량적 크기 보장 | Complexity와 수렴속도 도출 |
Line search의 전역 수렴은 단순히 $f(x_{k+1})<f(x_k)$라는 사실에서 나오지 않는다. Armijo condition이 감소량을 제공하고, Wolfe curvature condition 또는 backtracking lower bound가 step size의 퇴화를 막으며, search direction의 angle condition이 그 감소량을 gradient norm과 연결한다. 비볼록 문제에서는 이 조건들로 stationary point 수렴까지만 보장되며, global minimum이나 iterate 자체의 유일한 극한을 얻으려면 convexity, strong convexity 또는 추가적인 regularity가 필요하다.