7.122 국소 최적해와 전역 최적해

1. 정의

전역 최소점: \mathbf{x}^* \in \mathcal{F}가 허용 영역의 모든 점에 대해 f(\mathbf{x}^*) \leq f(\mathbf{x})를 만족하면 전역 최소점(global minimizer)이라 한다.

국소 최소점: \mathbf{x}^*의 어떤 근방 \mathcal{N}(\mathbf{x}^*, \epsilon) 내의 모든 허용 점에 대해 f(\mathbf{x}^*) \leq f(\mathbf{x})를 만족하면 국소 최소점(local minimizer)이라 한다.

엄밀 국소 최소점: \mathbf{x} \neq \mathbf{x}^*인 모든 근방 내 허용 점에 대해 f(\mathbf{x}^*) < f(\mathbf{x})이면 엄밀 국소 최소점(strict local minimizer)이라 한다.

모든 전역 최소점은 국소 최소점이지만, 비볼록 문제에서 그 역은 일반적으로 성립하지 않는다.

2. 국소 해와 전역 해의 관계

볼록 최적화에서는 모든 국소 최소점이 전역 최소점이므로, 국소 해법으로 전역 해를 보장할 수 있다. 비볼록 문제에서는 다수의 국소 최소점이 존재하며, 각 국소 해의 목적 함수값이 상이하다. 전역 최소점은 이들 중 목적 함수값이 가장 작은 것이다.

국소 최소점의 수와 분포는 목적 함수의 비볼록성의 정도에 의존한다. 로봇 역기구학에서 기구학적 구조에 따라 2개, 4개, 8개 또는 16개의 역기구학 해가 존재할 수 있으며, 각각이 국소 최적점에 해당한다.

3. 전역 최적화 방법

3.1 결정론적 방법

분기 한정법(Branch and Bound): 허용 영역을 재귀적으로 분할하고, 각 부분 영역의 하한(볼록 이완에 의해 계산)과 상한(국소 해)을 비교하여 비유망한 영역을 가지치기한다. 전역 최적성이 보장되지만, 최악의 경우 지수적 계산량을 요구한다.

구간 산술(Interval Arithmetic): 구간 확장(interval extension)을 이용하여 함수값의 범위를 보수적으로 추정하고, 전역 최소점을 포함할 수 없는 구간을 제거한다.

3.2 확률론적 방법

시뮬레이티드 어닐링(Simulated Annealing): 온도 매개변수에 의해 확률적 상향 이동(uphill move)을 허용하여 국소 최소점에서의 탈출을 가능하게 한다.

유전 알고리즘(Genetic Algorithm): 모집단(population) 기반의 진화적 탐색으로, 교차(crossover)와 돌연변이(mutation) 연산에 의해 해 공간을 탐색한다.

입자 군집 최적화(Particle Swarm Optimization): 다수의 입자가 개인 최적과 전역 최적 정보를 공유하면서 탐색한다.

이러한 방법들은 전역 최적에의 수렴이 이론적으로 보장될 수 있으나(충분한 시간이 주어질 때), 실용적으로는 유한 시간 내에 전역 최적을 보장하지 못한다.

3.3 다중 시작점 전략(Multistart)

가장 단순하고 실용적인 전역 탐색 전략으로, 무작위 또는 체계적으로 선택된 다수의 초기점에서 국소 최적화를 반복 수행하고, 얻어진 국소 해 중 최선의 것을 선택한다. 초기점의 수를 증가시킬수록 전역 해에 가까운 해를 찾을 확률이 증가하며, 국소 최적화가 효율적인 경우 전체 계산 비용이 관리 가능하다.

4. 국소 해의 품질 평가

국소 해 \mathbf{x}^*가 전역 해에 얼마나 가까운지를 직접적으로 평가하기 어렵다. 다음의 간접적 지표가 사용된다.

쌍대 간극: 볼록 이완의 쌍대 최적값 d^*는 전역 최적값의 하한이다. 국소 해의 목적 함수값 f(\mathbf{x}^*)와 하한 d^*의 차이 f(\mathbf{x}^*) - d^*가 최적성 간극의 상한을 제공한다.

다중 시작점 일관성: 다수의 초기점에서 동일한 국소 해에 수렴하면, 해당 해가 전역 해일 가능성이 높다.

감도 분석: 국소 해 주위의 목적 함수 곡률이 클수록(깊은 골), 해당 국소 해가 양호할 가능성이 높다.

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

로봇 공학 응용에서 전역 최적해의 필요성은 문제에 따라 다르다.

전역 해가 중요한 경우: 최소 시간 궤적, 에너지 효율 극대화 등 성능이 비용에 직접 연동되는 문제에서 전역 해의 탐색이 가치 있다.

국소 해로 충분한 경우: 실시간 제어에서는 제어 주기 내에 양호한 국소 해를 구하는 것이 전역 해를 구하는 것보다 중요하다. 연속적인 궤적 추종에서 이전 해의 근방에서 국소 최적화를 수행하면, 시간적 연속성에 의해 양호한 해가 보장된다.

전역 탐색과 국소 정밀화의 결합: RRT*, PRM 등의 샘플링 기반 경로 계획으로 전역적으로 양호한 초기 궤적을 구하고, 경사 기반 궤적 최적화로 국소적으로 정밀화하는 2단계 전략이 널리 채택된다.

6. 참고 문헌

• Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
• Horst, R., & Tuy, H. (1996). Global Optimization: Deterministic Approaches (3rd ed.). Springer.
• Floudas, C. A. (2000). Deterministic Global Optimization. Springer.
• Bertsekas, D. P. (2016). Nonlinear Programming (3rd ed.). Athena Scientific.

version: 1.0