7.98 시컨트 조건과 곡률 근사
1. 시컨트 조건의 유래
시컨트 조건(secant condition)은 1변수 함수의 시컨트 근사(secant approximation)로부터 유래한다. 스칼라 함수 g(x)에 대해 x_k와 x_{k+1} 두 점에서의 함수값으로 도함수를 근사하면 다음을 얻는다.
g'(x_{k+1}) \approx \frac{g(x_{k+1}) - g(x_k)}{x_{k+1} - x_k}
이를 다변수 함수로 확장하면, 헤시안 근사 \mathbf{B}_{k+1}이 가장 최근의 그래디언트 변화를 정확히 반영해야 한다는 요구로 귀결된다.
\mathbf{B}_{k+1}(\mathbf{x}_{k+1} - \mathbf{x}_k) = \nabla f(\mathbf{x}_{k+1}) - \nabla f(\mathbf{x}_k)
표준 표기로 \mathbf{s}_k = \mathbf{x}_{k+1} - \mathbf{x}_k, \mathbf{y}_k = \nabla f(\mathbf{x}_{k+1}) - \nabla f(\mathbf{x}_k)를 사용하면 다음과 같다.
\mathbf{B}_{k+1}\mathbf{s}_k = \mathbf{y}_k
이것이 시컨트 조건이다. 역헤시안 근사 \mathbf{H}_{k+1} \approx [\nabla^2 f(\mathbf{x}_{k+1})]^{-1}에 대해서는 다음의 역 시컨트 조건이 된다.
\mathbf{H}_{k+1}\mathbf{y}_k = \mathbf{s}_k
2. 시컨트 조건의 정당성
시컨트 조건은 평균값 정리의 다변수 확장으로 정당화된다. 직선 \mathbf{x}(\tau) = \mathbf{x}_k + \tau \mathbf{s}_k (\tau \in [0, 1])를 따라 그래디언트를 적분하면 다음을 얻는다.
\mathbf{y}_k = \nabla f(\mathbf{x}_{k+1}) - \nabla f(\mathbf{x}_k) = \left[\int_0^1 \nabla^2 f(\mathbf{x}_k + \tau \mathbf{s}_k) \, d\tau\right] \mathbf{s}_k = \bar{\mathbf{A}}_k \mathbf{s}_k
여기서 \bar{\mathbf{A}}_k는 \mathbf{x}_k에서 \mathbf{x}_{k+1}까지의 경로를 따른 헤시안의 평균이다. 따라서 시컨트 조건 \mathbf{B}_{k+1}\mathbf{s}_k = \mathbf{y}_k는 근사 헤시안이 최근 이동 방향에서의 평균 곡률을 정확히 반영할 것을 요구한다.
3. 곡률 조건
시컨트 조건이 의미있으려면 \mathbf{s}_k와 \mathbf{y}_k 사이의 다음 관계가 성립해야 한다.
\mathbf{s}_k^T \mathbf{y}_k > 0
이를 곡률 조건(curvature condition)이라 한다. 이 조건은 이동 방향 \mathbf{s}_k를 따른 평균 곡률이 양수임을 의미한다.
\mathbf{s}_k^T \mathbf{y}_k = \mathbf{s}_k^T \bar{\mathbf{A}}_k \mathbf{s}_k > 0
f가 강볼록이면 \bar{\mathbf{A}}_k \succ 0이므로 곡률 조건은 자동으로 만족된다. 비볼록 함수에서는 울프 조건을 만족하는 직선 탐색이 곡률 조건을 보장한다.
곡률 조건이 위반되면(\mathbf{s}_k^T \mathbf{y}_k \leq 0), BFGS 갱신이 양정치성을 잃을 수 있으므로 해당 갱신을 건너뛰거나 댐핑(damping) 기법을 적용해야 한다.
4. 시컨트 조건의 부정성(underdeterminacy)
n차원에서 시컨트 조건 \mathbf{B}_{k+1}\mathbf{s}_k = \mathbf{y}_k는 n개의 등식을 부과한다. 대칭 행렬 \mathbf{B}_{k+1}의 독립 원소 수는 n(n+1)/2이므로, n > 1일 때 시컨트 조건만으로는 \mathbf{B}_{k+1}을 유일하게 결정할 수 없다. 이 부정성을 해결하기 위해 추가 조건이 필요하며, 대표적인 접근법은 다음과 같다.
최소 변화 원리: 시컨트 조건을 만족하면서 이전 근사 \mathbf{B}_k로부터의 변화를 최소화한다.
\min_{\mathbf{B}} \lVert \mathbf{B} - \mathbf{B}_k \rVert_W \quad \text{subject to} \quad \mathbf{B} = \mathbf{B}^T, \; \mathbf{B}\mathbf{s}_k = \mathbf{y}_k
가중 프로베니우스 노름 \lVert \cdot \rVert_W의 선택에 따라 BFGS 또는 DFP 갱신이 도출된다. BFGS 갱신은 W가 평균 헤시안의 역에 해당할 때 최적 해이다.
5. 다중 시컨트 조건
가장 최근의 m개 벡터 쌍에 대해 시컨트 조건을 동시에 만족하도록 요구할 수 있다.
\mathbf{B}_{k+1}\mathbf{s}_j = \mathbf{y}_j, \quad j = k-m+1, \ldots, k
이는 L-BFGS의 이론적 기반을 제공한다. m이 증가하면 근사의 정확도가 향상되지만, m > n이면 조건이 과결정(overdetermined)이 될 수 있다.
6. 곡률 근사의 품질
시컨트 조건에 기반한 곡률 근사의 품질은 이동 방향의 다양성에 의존한다. 모든 이동 \mathbf{s}_j가 유사한 방향이면 특정 방향에서의 곡률만 정확히 추정되고, 직교 방향에서의 곡률 정보는 부족하다. BFGS의 자기 보정 성질은 반복이 진행됨에 따라 다양한 방향에서의 곡률 정보가 점진적으로 축적되어 근사가 개선됨을 의미한다.
데니스-모레 조건은 시컨트 기반 곡률 근사의 점근적 정확성을 다음과 같이 표현한다.
\lim_{k \to \infty} \frac{\lVert (\mathbf{B}_k - \nabla^2 f(\mathbf{x}^*))\mathbf{d}_k \rVert}{\lVert \mathbf{d}_k \rVert} = 0
이는 근사 헤시안이 탐색 방향에서 실제 헤시안에 수렴함을 의미하며, 초선형 수렴의 이론적 기반을 형성한다.
7. 댐핑된 BFGS 갱신
비볼록 문제에서 곡률 조건 \mathbf{s}_k^T\mathbf{y}_k > 0이 위반될 수 있다. 이를 처리하기 위해 포웰(Powell)은 댐핑된 BFGS 갱신을 제안하였다.
\hat{\mathbf{y}}_k = \theta_k \mathbf{y}_k + (1 - \theta_k)\mathbf{B}_k\mathbf{s}_k
\theta_k = \begin{cases} 1 & \text{if } \mathbf{s}_k^T\mathbf{y}_k \geq 0.2 \, \mathbf{s}_k^T\mathbf{B}_k\mathbf{s}_k \\ \frac{0.8 \, \mathbf{s}_k^T\mathbf{B}_k\mathbf{s}_k}{\mathbf{s}_k^T\mathbf{B}_k\mathbf{s}_k - \mathbf{s}_k^T\mathbf{y}_k} & \text{otherwise} \end{cases}
수정된 \hat{\mathbf{y}}_k는 \mathbf{s}_k^T\hat{\mathbf{y}}_k \geq 0.2 \, \mathbf{s}_k^T\mathbf{B}_k\mathbf{s}_k > 0을 만족하므로, 양정치성이 보존된다. 이 기법은 순차적 이차 계획법(SQP)의 BFGS 갱신에서 특히 중요하다.
8. 참고 문헌
- Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
- Dennis, J. E., & Moré, J. J. (1977). “Quasi-Newton Methods, Motivation and Theory.” SIAM Review, 19(1), 46–89.
- Powell, M. J. D. (1978). “A Fast Algorithm for Nonlinearly Constrained Optimization Calculations.” Lecture Notes in Mathematics, 630, 144–157.
- Fletcher, R. (1987). Practical Methods of Optimization (2nd ed.). Wiley.
version: 1.0