7.121 비선형 최적화 문제의 특성과 어려움

7.121 비선형 최적화 문제의 특성과 어려움

1. 비선형 최적화의 정의

비선형 최적화(nonlinear optimization) 또는 비선형 계획법(nonlinear programming, NLP)은 목적 함수 또는 제약 함수 중 하나 이상이 비선형인 최적화 문제를 지칭한다.

\min_{\mathbf{x}} \quad f(\mathbf{x}) \quad \text{s.t.} \quad \mathbf{g}(\mathbf{x}) \leq \mathbf{0}, \; \mathbf{h}(\mathbf{x}) = \mathbf{0}

로봇 공학에서 발생하는 대부분의 최적화 문제(역기구학, 궤적 최적화, 파라미터 추정, 경로 계획 등)가 비선형 최적화에 해당한다.

2. 비볼록성과 다중 극값

비선형 문제의 가장 근본적인 어려움은 비볼록성(non-convexity)이다. 비볼록 목적 함수는 다수의 국소 최소점(local minima)을 가질 수 있으며, 대부분의 수치적 알고리즘은 초기점에 따라 서로 다른 국소 최소점에 수렴한다. 전역 최소점(global minimum)의 발견은 일반적으로 NP-어려운 문제이다.

로봇 역기구학에서 다수의 관절 자세가 동일한 말단 장치 위치를 달성할 수 있으며, 궤적 최적화에서 장애물의 좌우 통과에 해당하는 서로 다른 위상적(topological) 클래스의 궤적이 각각 국소 최적해를 형성한다.

3. 안장점과 고원

비볼록 함수에서는 극소점 외에 안장점(saddle point)이 존재한다. 안장점에서 그래디언트는 영이지만 헤시안이 부정치(indefinite)이다. 고차원 문제에서 안장점의 수는 극소점보다 지수적으로 많을 수 있으며, 경사 하강법이 안장점 근방에서 정체하는 현상이 발생한다.

고원(plateau)은 그래디언트가 거의 영에 가까운 넓은 영역으로, 경사 기반 알고리즘의 수렴을 극도로 느리게 만든다.

4. 비매끄러움과 불연속성

일부 로봇 최적화 문제에서는 목적 함수 또는 제약 함수가 미분 불가능하거나 불연속적이다.

접촉 전환: 로봇의 접촉 상태 변화(접촉/비접촉)에 의한 동역학의 불연속은 목적 함수의 미분 불가능성을 야기한다.

최대값/최소값 함수: \max, \min 연산을 포함하는 목적 함수는 꼭짓점에서 미분 불가능하다.

정수 변수: 접촉 순서나 이산적 선택이 관여하면 혼합 정수 비선형 계획(MINLP)이 되어 조합적 복잡성이 추가된다.

5. 제약의 비선형성

비선형 등식 제약 \mathbf{h}(\mathbf{x}) = \mathbf{0}은 매끄러운 매니폴드를 정의하며, 비선형 부등식 제약 \mathbf{g}(\mathbf{x}) \leq \mathbf{0}의 허용 영역은 비볼록일 수 있다. 제약 자격의 위반, 제약의 퇴화, 허용 영역의 비연결성 등이 추가적인 어려움을 야기한다.

장애물 회피 제약의 허용 영역은 전형적으로 비볼록이며, 다수의 연결 성분(connected component)으로 구성될 수 있다. 이 경우 국소 최적화 알고리즘은 초기점이 속한 연결 성분 내의 해만을 탐색한다.

6. 스케일링과 조건수

비선형 문제에서 변수와 제약의 스케일이 크게 다르면 수치적 어려움이 발생한다. 로봇 시스템에서 위치(m), 각도(rad), 질량(kg), 관성(kg·m²) 등의 물리량이 수십 자릿수의 차이를 보일 수 있다. 부적절한 스케일링은 헤시안의 조건수를 악화시키고, 수치적 반올림 오차의 영향을 증폭시킨다.

7. 계산 복잡도

비선형 최적화의 계산 복잡도는 문제의 크기와 구조에 강하게 의존한다. 일반적인 비볼록 NLP에서 전역 최적해를 보장하는 것은 NP-어려우므로, 실용적으로는 국소 최적해를 효율적으로 구하는 데 집중한다.

국소 해법의 비용: SQP, 내점법 등의 국소 최적화 알고리즘은 반복 횟수가 문제 규모의 다항 함수인 경우가 많으며, 희소 구조의 활용으로 대규모 문제에도 적용 가능하다.

전역 해법의 비용: 분기 한정법, 시뮬레이티드 어닐링, 유전 알고리즘 등의 전역 최적화 방법은 계산 비용이 현저히 높으며, 대규모 문제에서는 실용적 시간 내에 전역 해를 보장하기 어렵다.

8. 실용적 대응 전략

다중 초기점 전략: 다양한 초기점에서 국소 최적화를 반복하여 최선의 국소 해를 선택한다.

볼록 근사: 비볼록 문제를 순차적 볼록 근사(SCP)로 풀어 국소 해를 효율적으로 구한다.

전역-국소 혼합: 전역 탐색(샘플링 기반 경로 계획 등)으로 양호한 초기점을 설정하고, 국소 최적화로 정밀화한다.

문제 구조의 활용: 희소성, 대칭성, 분리 가능성 등 문제의 구조적 특성을 활용하여 계산 효율을 향상시킨다.

9. 참고 문헌

  • Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
  • Bertsekas, D. P. (2016). Nonlinear Programming (3rd ed.). Athena Scientific.
  • Betts, J. T. (2010). Practical Methods for Optimal Control and Estimation Using Nonlinear Programming (2nd ed.). SIAM.
  • Conn, A. R., Gould, N. I. M., & Toint, P. L. (2000). Trust-Region Methods. SIAM.

version: 1.0