7.140 종료 기준의 설계와 실용적 고려 사항

1. 종료 기준의 필요성

반복적 최적화 알고리즘은 이론적으로 무한 반복에서 최적해에 수렴하지만, 실용적으로는 유한 반복에서 종료해야 한다. 종료 기준(termination criterion, stopping criterion)은 현재 반복점이 최적해에 충분히 가까운지를 판정하여 알고리즘을 중단하는 조건이다. 부적절한 종료 기준은 과도한 반복(계산 낭비)이나 조기 종료(부정확한 해)를 초래한다.

2. 주요 종료 기준

2.1 그래디언트 노름 기준

$\lVert \nabla f(\mathbf{x}_k) \rVert \leq \epsilon_g$

1차 최적 조건(정류 조건)의 만족도를 직접 측정한다. 비제약 문제에서 가장 기본적인 기준이며, 제약 문제에서는 KKT 잔차의 노름으로 확장된다.

절대 기준: $\lVert \nabla f(\mathbf{x}_k) \rVert \leq \epsilon_g$

상대 기준: $\lVert \nabla f(\mathbf{x}_k) \rVert \leq \epsilon_g (1 + \lvert f(\mathbf{x}_k) \rvert)$

상대 기준은 목적 함수의 스케일에 무관하게 적용 가능하다. 통상 $\epsilon_g = 10^{-6}$ ~ $10^{-8}$ 이 사용된다.

2.2 스텝 크기 기준

$\lVert \mathbf{x}_{k+1} - \mathbf{x}_k \rVert \leq \epsilon_s (1 + \lVert \mathbf{x}_k \rVert)$

변수의 변화가 무시할 수 있을 정도로 작으면 수렴으로 판정한다. 목적 함수의 평탄한 영역에서 그래디언트가 작지만 최적이 아닌 경우에도 스텝이 작아질 수 있으므로, 단독 사용보다 다른 기준과 병행한다.

2.3 목적 함수 변화 기준

$\lvert f(\mathbf{x}_{k+1}) - f(\mathbf{x}_k) \rvert \leq \epsilon_f (1 + \lvert f(\mathbf{x}_k) \rvert)$

목적 함수의 개선이 미미하면 수렴으로 판정한다. 이 기준은 목적 함수값의 수렴을 측정하지만, 변수 공간에서의 수렴을 보장하지 않는다.

2.4 최대 반복 횟수

$k \geq k_{\max}$

계산 시간의 상한을 설정하기 위한 안전 기준이다. 수렴에 실패한 경우를 검출하는 역할도 한다. $k_{\max}$ 는 문제의 규모와 알고리즘의 수렴 속도에 따라 설정한다.

2.5 최대 계산 시간

$t_{elapsed} \geq t_{\max}$

실시간 시스템에서 절대적 시간 제한을 부과한다.

3. 제약 최적화에서의 종료 기준

3.1 KKT 잔차 기준

제약 문제에서는 KKT 조건의 잔차를 종합적으로 평가한다.

$\max\left(\lVert \nabla_{\mathbf{x}}\mathcal{L} \rVert_\infty, \; \lVert \mathbf{h}(\mathbf{x}_k) \rVert_\infty, \; \max_i[\mu_i g_i(\mathbf{x}_k)]^+, \; \max_i[g_i(\mathbf{x}_k)]^+\right) \leq \epsilon$

정류 조건, 등식 제약 위반, 상보성 잔차, 부등식 제약 위반을 동시에 검사한다.

3.2 제약 위반 기준

$\lVert \mathbf{h}(\mathbf{x}_k) \rVert \leq \epsilon_h, \quad \max_i g_i(\mathbf{x}_k) \leq \epsilon_g$

허용 가능성(feasibility)의 달성을 판정한다.

4. 복합 종료 기준의 설계

실용적 구현에서는 다수의 기준을 논리적으로 결합한다.

성공 종료: 그래디언트 노름 기준 AND 제약 위반 기준이 만족되면 “수렴 달성“으로 종료.

경고 종료: 스텝 크기 기준 또는 목적 함수 변화 기준이 만족되지만 그래디언트 노름이 아직 크면 “느린 진행“으로 경고.

실패 종료: 최대 반복 횟수 초과, 또는 목적 함수가 발산하면 “수렴 실패“로 종료.

5. 허용 오차의 선택

5.1 절대 허용 오차와 상대 허용 오차

문제의 스케일에 민감하지 않으려면 상대 허용 오차가 바람직하다. 그러나 최적값이 영에 가까운 경우 상대 기준이 과도하게 엄격해지므로, 절대 기준과의 결합이 필요하다.

$\lvert f_{k+1} - f_k \rvert \leq \epsilon_{rel}\lvert f_k \rvert + \epsilon_{abs}$

5.2 기계 정밀도와의 관계

허용 오차를 기계 엡실론 $\epsilon_{mach} \approx 10^{-16}$ 이하로 설정하면, 반올림 오차에 의해 기준이 만족되지 않아 알고리즘이 영원히 종료되지 않을 수 있다. 실용적 하한은 $\sqrt{\epsilon_{mach}} \approx 10^{-8}$ (수치 미분 사용 시) 또는 $\epsilon_{mach}^{2/3} \approx 10^{-11}$ (해석적/자동 미분 사용 시)이다.

6. 로봇 공학에서의 실용적 고려

6.1 실시간 시스템

모델 예측 제어, 전신 운동 제어 등의 실시간 응용에서는 시간 기반 종료가 주된 기준이다. 제어 주기(1~10ms) 내에 가용한 반복 횟수가 제한되며, 불완전한 해라도 시간 내에 산출하는 것이 우선이다. 이 경우 “가능한 만큼 반복하고 현재 해를 사용“하는 전략이 채택된다.

6.2 웜 스타트와 종료 기준의 완화

웜 스타트에 의해 초기점이 이미 양호하면, 1~3회의 반복만으로 원하는 정밀도에 도달할 수 있다. 연속적인 제어 주기에서 해의 변화가 미미하므로, 종료 기준을 완화하여 소수의 반복으로 종료해도 실용적으로 충분하다.

6.3 수렴 실패의 처리

최적화가 수렴에 실패한 경우, 로봇 시스템은 안전한 대안 행동(이전 해의 유지, 비상 정지, 보수적 제어)으로 전환해야 한다. 종료 상태 코드(성공/경고/실패)를 반환하여 상위 시스템이 적절히 대응할 수 있도록 설계한다.

7. 참고 문헌

Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
Gill, P. E., Murray, W., & Wright, M. H. (1981). Practical Optimization. Academic Press.
Conn, A. R., Gould, N. I. M., & Toint, P. L. (2000). Trust-Region Methods. SIAM.

version: 1.0