7.110 능동집합법과 내점법
1. 두 가지 패러다임의 개요
제약 최적화, 특히 이차 계획법(QP)의 수치적 해법은 크게 능동집합법(active set method)과 내점법(interior point method)의 두 패러다임으로 나뉜다. 이 ��� 방법은 제약을 처리하는 근본적으로 다른 전략을 채택하며, 각각 고유한 장단점을 갖는다.
2. 능동집합법
2.1 핵심 전략
능동집합법은 최적점에서의 능동 제약 집합을 반복적으로 추정하고, 추정된 능동 집합하에서의 등식 제약 하위 문제를 풀어 다음 반복점을 결정한다. 반복열은 허용 영역의 경계(꼭짓점, 변, 면)를 따라 이동하며, 각 반복에서 하나의 제약이 추가되거나 제거된다.
2.2 알고리즘의 특성
허용 가능성 유지: 모든 반복에서 원초 허용 가능성이 유지된다. 초기 허용점이 필요하며, 이를 얻기 위해 1단계 보조 문제(Phase I problem)를 풀 수 있다.
조합적 탐색: m개의 제약 중 능동 집합은 2^m개의 가능한 조합을 가지며, 이론적으로 최악의 경우 지수적 반복이 필요하다. 그러나 실용적으로는 대부분의 문제에서 반복 횟수가 문제 규모에 비례하는 수준이다.
웜 스타트: 이전 해의 능동 집합을 초기 추정으로 사용할 수 있어, 매개변수가 약간 변한 QP를 매우 효율적으로 풀 수 있다. 로봇 MPC에서 연속적인 QP 사이의 능동 집합 변화가 소수에 그치므로, 1~5회의 반복으로 수렴하는 경우가 일반적이다.
반복당 비용: O(n^2) 또는 O(n^3) (KKT 시스템의 인수 분해 갱신에 의존). 능동 집합의 변화가 계수 1 갱신(rank-1 update)으로 처리되면 반복당 비용이 O(n^2)로 유지된다.
3. 내점법
3.1 핵심 전략
내점법은 허용 영역의 내부(interior)를 통과하는 경로를 따라 최적점에 접근한다. 부등식 ��약을 로그 장벽 함수로 처리하여, 장벽 매개변수를 영으로 감소시키면서 중심 경로(central path)를 추적한다.
3.2 원시-쌍대 내점법의 구조
각 반복에서 섭동된 KKT 시스템을 뉴턴법으로 풀어 원시 변수 (\mathbf{x}, \mathbf{s})와 쌍대 변수 (\boldsymbol{\mu}, \boldsymbol{\nu})를 동시에 갱신한다.
\begin{bmatrix} \mathbf{H} & \mathbf{0} & \mathbf{A}_{eq}^T & \mathbf{A}^T \\ \mathbf{0} & \boldsymbol{\mu}\text{diag}(\mathbf{s})^{-1} & \mathbf{0} & \mathbf{I} \\ \mathbf{A}_{eq} & \mathbf{0} & \mathbf{0} & \mathbf{0} \\ \mathbf{A} & \mathbf{I} & \mathbf{0} & \mathbf{0} \end{bmatrix} \begin{bmatrix} \Delta\mathbf{x} \\ \Delta\mathbf{s} \\ \Delta\boldsymbol{\nu} \\ \Delta\boldsymbol{\mu} \end{bmatrix} = -\begin{bmatrix} \text{정류 잔차} \\ \text{상보성 잔차} \\ \text{등식 잔차} \\ \text{부등식 잔차} \end{bmatrix}
축소(condensing)를 통해 여유 변수를 소거하면, (n + p) \times (n + p) 시스템으로 환원된다.
3.3 알고리즘의 특성
다항 시간 수렴: O(\sqrt{m}\log(1/\epsilon)) 반복 내에 \epsilon-정확도 달성이 ��장된다.
반복 횟수의 규모 무관성: 실용적으로 반복 횟수가 15~50회로 문제 규모에 거의 무관하다.
반복당 비용: O(n^3) 또는 희소 분해의 비용. 대규모 희소 문제에서는 희소 촐레스키/LDL 분해에 의해 반복당 비용이 현저히 감소한다.
웜 스타트의 제한: 내점법은 허용 영역의 내부에서 출발해야 하므로, 이전 해(경계점)를 직접 초기점으로 사용하기 어렵다. 내점법을 위한 웜 스타트 기법이 연구되고 있으나, 능동집합법만큼 효과적이지 않다.
4. 두 방법의 비교
| 특성 | 능동집합법 | 내점법 |
|---|---|---|
| 경로 | 허용 영역 경계 | 허용 영역 내부 |
| 반복 횟수 | ���제 의존(웜 스타트 시 소수) | 거의 규모 무관(\sim 20~50) |
| 반복당 비용 | O(n^2) (갱신) | O(n^3) (분해) |
| 웜 스타트 | 매우 효과적 | 제한적 |
| 최악 경우 | 지수적 | 다항적 |
| 적합 규모 | 소~중규모, 반복적 | 중~대규모 |
| 대표 해법기 | qpOASES | MOSEK, Gurobi(내점) |
5. 로봇 공학 응용에서의 선택
실시간 모델 예측 제어: 제어 주기 내에서 QP를 풀어야 하는 실시간 MPC에서는 능동집합법의 웜 스타트가 결정적 이점이다. 연속적인 QP 사이의 능동 집합 변화가 적으므로, 소수의 반복(1~5회)으로 수렴한다. qpOASES가 이 용도의 표준 해법기이다.
대규모 궤적 최적화: 수천 이상의 변수를 갖는 궤적 최적화에서는 내점법 또는 ADMM 기반 방법이 더 적합하다. 문제의 희소 구조를 활용한 효율적 행렬 분해가 핵심이다.
혼합 전략: 일부 해법기는 내점법으로 초기 근사 해를 구한 후, 능동집합법으로 마무리하여 정확한 능동 집합과 정밀한 해를 얻는 혼합 전략을 채택한다.
6. 참고 문헌
- Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
- Ferreau, H. J., Kirches, C., Potschka, A., Bock, H. G., & Diehl, M. (2014). “qpOASES: A Parametric Active-Set Algorithm for Quadratic Programming.” Mathematical Programming Computation, 6(4), 327–363.
- Wright, S. J. (1997). Primal-Dual Interior-Point Methods. SIAM.
- Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
version: 1.0