7.82 직선 탐색 방법과 스텝 크기 선택

1. 직선 탐색의 기본 구조

반복적 최적화 알고리즘의 대부분은 현재 점 $\mathbf{x}_k$ 에서 탐색 방향 $\mathbf{d}_k$ 를 결정한 후, 해당 방향으로 적절한 스텝 크기(step size) $\alpha_k > 0$ 만큼 이동하여 다음 점을 생성하는 구조를 갖는다.

$\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{d}_k$

직선 탐색(line search)은 스텝 크기 $\alpha_k$ 를 결정하는 절차로, 1차원 최적화 문제를 구성한다. 스칼라 함수 $\phi(\alpha) = f(\mathbf{x}_k + \alpha \mathbf{d}_k)$ 를 정의하면, 직선 탐색은 $\alpha > 0$ 에서 $\phi(\alpha)$ 를 최소화하거나 충분히 감소시키는 $\alpha_k$ 를 찾는 문제로 환원된다.

2. 탐색 방향의 조건

직선 탐색이 유효하려면 탐색 방향 $\mathbf{d}_k$ 가 하강 방향(descent direction)이어야 한다. 즉, 다음의 조건이 만족되어야 한다.

$\nabla f(\mathbf{x}_k)^T \mathbf{d}_k < 0$

이 조건�� $\alpha$ 가 충분히 작은 양수일 때 $\phi(\alpha) < \phi(0) = f(\mathbf{x}_k)$ 가 성립함을 보장한다. 경사 하강법에서 $\mathbf{d}_k = -\nabla f(\mathbf{x}_k)$ 는 $\nabla f(\mathbf{x}_k)^T \mathbf{d}_k = -\lVert \nabla f(\mathbf{x}_k) \rVert^2 < 0$ 이므로 항상 하강 방향이다. 뉴턴 방향 $\mathbf{d}_k = -[\nabla^2 f(\mathbf{x}_k)]^{-1}\nabla f(\mathbf{x}_k)$ 는 헤시안이 양정치일 때 하강 방향이 된다.

3. 정밀 직선 탐색

정밀 직선 탐색(exact line search)은 $\phi(\alpha)$ 를 정확히 최소화하는 $\alpha_k$ 를 구한다.

$\alpha_k = \arg\min_{\alpha > 0} \phi(\alpha) = \arg\min_{\alpha > 0} f(\mathbf{x}_k + \alpha \mathbf{d}_k)$

정밀 직선 탐색의 최적성 조건은 다음과 같다.

$\phi'(\alpha_k) = \nabla f(\mathbf{x}_k + \alpha_k \mathbf{d}_k)^T \mathbf{d}_k = 0$

즉, 다음 점에서의 그래디언트가 현재 탐색 방향과 직교한다. 이차 목적 함수 $f(\mathbf{x}) = \frac{1}{2}\mathbf{x}^T\mathbf{A}\mathbf{x} - \mathbf{b}^T\mathbf{x}$ ( $\mathbf{A} \succ 0$ )에 대해 정밀 직선 탐색의 해는 다음과 같이 해석적으로 주어진다.

$\alpha_k = -\frac{\nabla f(\mathbf{x}_k)^T \mathbf{d}_k}{\mathbf{d}_k^T \mathbf{A} \mathbf{d}_k}$

일반적인 비선형 함수에 대해서는 정밀 직선 탐색이 과도한 계산 비용을 요구하므로, 실용적으로는 비정밀 직선 탐색(inexact line search)이 사용된다.

4. 비정밀 직선 탐색

비정밀 직선 탐색은 $\phi(\alpha)$ 의 정확한 최소점을 구하지 않고, 충분한 감소를 보장하는 조건을 만족하는 $\alpha_k$ 를 수용한다. 가장 널리 사용되는 조건은 아르미요 조건(Armijo condition)과 울프 조건(Wolfe conditions)이다.

4.1 아르미요 조��(Armijo Condition)

스텝 크기 $\alpha$ 가 다음을 만족하면 아르미요 조건이 충족된다.

$f(\mathbf{x}_k + \alpha \mathbf{d}_k) \leq f(\mathbf{x}_k) + c_1 \alpha \nabla f(\mathbf{x}_k)^T \mathbf{d}_k$

여기서 $c_1 \in (0, 1)$ 은 충분 감소 매개변수이며, 통상적으로 $c_1 = 10^{-4}$ 이 사용된다. 아르미요 조건은 목적 함수의 감소가 1차 근사에 의해 예측되는 감소의 $c_1$ 비율 이상이 되어야 함을 요구한다. 기하학적으로, $\phi(\alpha)$ 가 $\phi(0)$ 에서의 접선을 $c_1$ 배 축소한 직선 아래에 놓여야 한다.

아르미요 조건만으로는 $\alpha$ 가 지나치게 작은 값으로 수용될 수 있으므로, 일반적으로 역추적 직선 탐색(backtracking line search)과 결합하여 사용된다.

4.2 역추적 직선 탐색(Backtracking Line Search)

역추적 절차는 다음과 같다.

초기 스텝 크기 $\bar{\alpha} > 0$ 과 축소 인자 $\rho \in (0, 1)$ 을 설정한다.
$\alpha = \bar{\alpha}$ 로 시작한다.
아르미요 조건이 만족되면 $\alpha_k = \alpha$ 를 수용한다.
만족되지 않으면 $\alpha \leftarrow \rho \alpha$ �� 축소하고 3단계로 돌아간다.

통상적으로 $\bar{\alpha} = 1$ (뉴턴법이나 준뉴턴법의 경우), $\rho = 0.5$ 가 사용된다. 이 절차는 유한 횟수의 반복으로 종료됨이 보장된다.

4.3 울프 조건(Wolfe Conditions)

울프 조건은 아르미요 조건(충분 감소 조건)과 곡률 조건(curvature condition)의 결합이다.

충분 감소 조건:

$f(\mathbf{x}_k + \alpha \mathbf{d}_k) \leq f(\mathbf{x}_k) + c_1 \alpha \nabla f(\mathbf{x}_k)^T \mathbf{d}_k$

곡률 조건:

$\nabla f(\mathbf{x}_k + \alpha \mathbf{d}_k)^T \mathbf{d}_k \geq c_2 \nabla f(\mathbf{x}_k)^T \mathbf{d}_k$

여기서 $0 < c_1 < c_2 < 1$ 이다. 통상적인 값은 $c_1 = 10^{-4}$ , $c_2 = 0.9$ (준뉴턴법) 또는 $c_2 = 0.1$ (켤레 그래디언트법)이다.

곡률 조건은 스텝 크기가 지나치게 작아지는 것을 방지한다. $\phi'(\alpha) = \nabla f(\mathbf{x}_k + \alpha \mathbf{d}_k)^T \mathbf{d}_k$ 이므로, 곡률 조건은 $\phi'(\alpha_k)$ 의 절대값이 $\phi'(0)$ 의 절대값보다 충분히 작아야 함을 의미한다.

4.4 강 울프 조건(Strong Wolfe Conditions)

곡률 조건을 다음과 같이 강화한 것이다.

$\lvert \nabla f(\mathbf{x}_k + \alpha \mathbf{d}_k)^T \mathbf{d}_k \rvert \leq c_2 \lvert \nabla f(\mathbf{x}_k)^T \mathbf{d}_k \rvert$

강 울프 조건은 $\phi'(\alpha_k)$ 가 양수이든 음수이든 절대값이 충분히 작을 것을 요구하며, 켤레 그래디언트법과 준뉴턴법에서 탐색 방향�� 품질을 유지하는 데 중요하다.

5. 울프 조건을 만족하는 스텝 크기의 존재성

$f$ 가 하방 유계(bounded below)이고, $\nabla f$ 가 리프시츠 연속(Lipschitz continuous)이면, 울프 조건을 만족하는 스텝 크기가 항상 존재한다. 이 존재성은 중간값 정리에 기반한다. $\phi'(0) < 0$ (하강 방향)이고 $f$ 가 하방 유계이면, $\phi(\alpha)$ 는 결국 증가해야 하므로, $\phi'(\alpha) = 0$ 이 되는 점이 존재하며, 이 점은 반드시 울프 조건을 만족한다.

6. 구간 축소 기법

직선 탐색에서 최적 스텝 크기를 포함하는 ��간을 반복적으로 축소하는 방법이 사용된다.

6.1 황금 분할 탐색(Golden Section Search)

단봉(unimodal) 함수에 대해 최소점을 포함하는 구간을 황금비( $\tau = (\sqrt{5}-1)/2 \approx 0.618$ )의 비율로 축소하는 방법이다. 각 반복에서 하나의 함수 평가만이 필요하며, 수렴률은 선형이다.

6.2 이차 보간(Quadratic Interpolation)

기존의 함수값과 도함수값을 이용하여 $\phi(\alpha)$ 를 이차 다항식으로 보간하고, 그 최소점을 다음 시행 스텝 크기로 취하는 방법��다. 세 점 $(\alpha_0, \phi(\alpha_0))$ , $(\alpha_1, \phi(\alpha_1))$ , $(\alpha_2, \phi(\alpha_2))$ 가 주어지면 보간 다항식의 최소점은 해석적으로 계산된다. 초선형 수렴이 가능하지만, 보간이 실패하는 경우 안전 장치(safeguard)가 필요하다.

6.3 삼차 보간(Cubic Interpolation)

함수값과 도함수값의 정보를 모두 활용하여 삼차 다항식으로 보간하는 방법이다. 두 점에서의 함수값과 도함수값, 총 4개의 정보로 삼차 다항식을 결정하며, 이차 보간보다 높은 정확도를 제공한다. 실용적인 직선 탐색 구현에서 널리 사용된다.

7. 줌 절차(Zoom Procedure)

울프 조건을 만족하는 스텝 크기를 효율적으로 찾기 위한 2단계 절차이다.

1단계(괄호 설정): 울프 조건을 만족하는 스텝 크기를 포함하는 구간 $[\alpha_{lo}, \alpha_{hi}]$ 를 결정한다. 초기 스텝 크기를 점진적으로 증가시키면서 아르미요 조건이 위반되거나 $\phi(\alpha)$ 가 증가하기 시작하는 점을 탐지한다.

2단계(줌): 구간 $[\alpha_{lo}, \alpha_{hi}]$ 내에서 이차 또는 삼차 보간을 반복하여 울프 조건을 만족하는 $\alpha$ 를 정밀하게 결정한다.

이 절차는 Moré와 Thuente(1994)에 의해 정립된 것��로, 수치적으로 안정적이며 대부분의 실용적 구현에서 표준으로 채택되고 있다.

8. 수렴 보장과 조프 조건

직선 탐색 기반 최적화 알고리즘의 전역 수렴(global convergence, 임의의 초기점에서 정류점으로의 수렴)을 보장하기 위해서는 스텝 크기 선택에 추가 조건이 필요하다. 조프(Zoutendijk) 조건은 울프 조건을 만족하는 직선 탐색과 하강 방향을 결합하면, 다음이 성립함을 보장한다.

$\sum_{k=0}^{\infty} \cos^2 \theta_k \lVert \nabla f(\mathbf{x}_k) \rVert^2 < \infty$

여기서 $\theta_k$ 는 탐�� 방향 $\mathbf{d}_k$ 와 최급경사 방향 $-\nabla f(\mathbf{x}_k)$ 사이의 각도이다. 이 급수가 수렴하면 $\liminf_{k \to \infty} \lVert \nabla f(\mathbf{x}_k) \rVert = 0$ 이 보장되며, 이는 반복열의 어떤 부분열이 정류점에 수렴함을 의미한다. $\cos \theta_k$ 가 영으로 수��하지 않으면(즉, 탐색 방향이 그래디언트와 지나치게 직교하지 않으면) $\lVert \nabla f(\mathbf{x}_k) \rVert \to 0$ 이 성립한다.

9. 로봇 공학에서의 고려 사항

로봇 최적화 문제에서 직선 탐색의 적용 시 다음의 특수한 상황을 고려해야 한다.

목적 함수 평가의 비용: 로봇 동역학 시뮬레이션이나 궤적 비용의 평가는 상당한 계산 시간을 요구할 수 있다. 따라서 직선 탐색에서의 함수 평가 횟수를 최소화하는 것이 중요하며, 역추적법과 보간법의 결합이 효과적이다.

실시간 제약: 모델 예측 제어 등의 실시간 ��적화에서는 정밀한 직선 탐색에 할당할 수 있는 시간이 제한적이다. 이 경우 고정 스텝 크기 또는 단순 역추적법이 선호된다.

구조물의 특이성: 로봇 기구학의 야코비안 특이점 근방에서 목적 함수의 곡률이 급변할 수 있으며, 이러한 상황에서는 보수적인 스텝 크기 선택이 수치적 안정성을 확보하는 데 유리하다.

10. 참고 문헌

Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
Moré, J. J., & Thuente, D. J. (1994). “Line Search Algorithms with Guaranteed Sufficient Decrease.” ACM Transactions on Mathematical Software, 20(3), 286–307.
Dennis, J. E., & Schnabel, R. B. (1996). Numerical Methods for Unconstrained Optimization and Nonlinear Equations. SIAM.
Bertsekas, D. P. (2016). Nonlinear Programming (3rd ed.). Athena Scientific.

version: 1.0