7.109 부등식 제약 이차 계획의 해법

1. 문제의 구조

부등식 제약을 포함하는 이차 계획 문제는 다음과 같다.

\min_{\mathbf{x}} \quad \frac{1}{2}\mathbf{x}^T\mathbf{H}\mathbf{x} + \mathbf{c}^T\mathbf{x}

\text{s.t.} \quad \mathbf{A}_{eq}\mathbf{x} = \mathbf{b}_{eq}, \quad \mathbf{A}\mathbf{x} \leq \mathbf{b}

등식 제약 QP와 달리, 부등식 제약의 존재는 능동 집합의 식별이라는 조합적 문제를 내포한다. 최적해에서의 능동 집합 \mathcal{A}^*를 알고 있다면, 능동 제약을 등식 제약으로 취급하고 비능동 제약을 무시하여 등식 제약 QP로 환원할 수 있다. 부등식 제약 QP의 해법은 이 능동 집합을 효율적으로 식별하는 전략으로 분류된다.

2. 능동집합법(Active Set Method)

2.1 원시 능동집합법

능동집합법은 추정된 작업 집합(working set) \mathcal{W}_k를 반복적으로 갱신하면서 최적 능동 집합을 식별한다.

알고리즘:

1. 허용 초기점 \mathbf{x}_0와 초기 작업 집합 \mathcal{W}_0를 설정한다.
2. 작업 집합의 등식 제약 QP 하위 문제를 풀어 탐색 방향 \mathbf{d}_k를 구한다.

\min_{\mathbf{d}} \quad \frac{1}{2}\mathbf{d}^T\mathbf{H}\mathbf{d} + (\mathbf{H}\mathbf{x}_k + \mathbf{c})^T\mathbf{d} \quad \text{s.t.} \quad \mathbf{a}_i^T\mathbf{d} = 0, \; i \in \mathcal{W}_k

3. \mathbf{d}_k = \mathbf{0}이면 KKT 승수를 계산하여 최적성을 검사한다.
4. \mathbf{d}_k \neq \mathbf{0}이면 허용 가능한 스텝 크기를 결정하고 갱신한다.

2.2 장점과 한계

능동집합법은 소규모 문제에서 매우 효율적이며, 웜 스타트가 자연스럽게 지원된다. 이전 해의 능동 집합을 초기 작업 집합으로 사용하면, 매개변수 변화가 작을 때 소수의 반복으로 수렴한다. 이 특성은 로봇 MPC와 같이 유사한 QP를 반복적으로 풀어야 하는 응용에서 핵심적 이점이다. 최악의 경우 지수적 반복 횟수가 필요할 수 있으나, 실용적으로는 드문 경우이다.

3. 내점법(Interior Point Method)

3.1 원시-쌍대 내점법

부등식 제약에 여유 변수 \mathbf{s} \geq \mathbf{0}을 도입하고, 로그 장벽으로 비음 조건을 처리한다.

\min_{\mathbf{x}, \mathbf{s}} \quad \frac{1}{2}\mathbf{x}^T\mathbf{H}\mathbf{x} + \mathbf{c}^T\mathbf{x} - \tau\sum_{i} \ln s_i

\text{s.t.} \quad \mathbf{A}\mathbf{x} + \mathbf{s} = \mathbf{b}, \quad \mathbf{A}_{eq}\mathbf{x} = \mathbf{b}_{eq}

섭동된 KKT 시스템을 뉴턴법으로 풀고, 장벽 매개변수 \tau를 점진적으로 감소시킨다.

3.2 반복 횟수의 예측

내점법의 이론적 반복 횟수는 O(\sqrt{m}\log(1/\epsilon))로, 제약 수 m의 제곱근에 비례하여 증가한다. 실용적으로는 10~50회의 뉴턴 반복이 충분하며, 이 횟수는 문제 규모에 거의 무관하다. 그러나 각 뉴턴 반복에서 (n+m) \times (n+m) 선형 시스템을 풀어야 하므로, 반복당 비용은 능동집합법보다 크다.

3.3 장점과 한계

내점법은 대규모 QP에서 안정적인 성능을 보이며, 최악 경우 다항 시간 수렴이 보장된다. 그러나 웜 스타트가 능동집합법만큼 효과적이지 않으며, 소규모 문제에서는 능동집합법이 더 효율적인 경우가 많다.

4. ADMM 기반 방법

ADMM(Alternating Direction Method of Multipliers)은 QP를 연산자 분할(operator splitting)로 풀어, 대규모 희소 문제에서 효율적이다. OSQP 해법기가 이 접근법의 대표적 구현이다.

\min_{\mathbf{x}} \quad \frac{1}{2}\mathbf{x}^T\mathbf{H}\mathbf{x} + \mathbf{c}^T\mathbf{x} \quad \text{s.t.} \quad \mathbf{l} \leq \mathbf{A}\mathbf{x} \leq \mathbf{u}

ADMM의 각 반복은 선형 시스템 해법과 투영(projection) 연산으로 구성되며, 선형 시스템의 행렬은 반복에 걸쳐 변하지 않으므로 한 번의 행렬 분해로 전체 반복을 수행할 수 있다. 이는 실시간 로봇 제어에서 중요한 이점이다.

5. 매개변수적 QP

로봇 MPC에서는 동일한 구조의 QP를 매개변수(현재 상태 \mathbf{x}_0)만 변경하면서 반복적으로 풀어야 한다.

\min_{\mathbf{u}} \quad \frac{1}{2}\mathbf{u}^T\mathbf{H}\mathbf{u} + \mathbf{x}_0^T\mathbf{F}\mathbf{u} \quad \text{s.t.} \quad \mathbf{G}\mathbf{u} \leq \mathbf{w} + \mathbf{E}\mathbf{x}_0

매개변수적 QP(parametric QP)는 매개변수의 함수로서 최적해의 구조(능동 집합)가 구간적으로 일정한 성질을 갖는다. 이를 활용한 명시적 MPC(explicit MPC)에서는 상태 공간을 폴리토프 영역으로 분할하고, 각 영역에서의 최적 제어 법칙을 사전에 계산하여 온라인에서는 단순한 탐색(lookup)만으로 최적 제어를 결정한다.

6. 해법 선택 지침

7. 참고 문헌

• 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.
• Stellato, B., Banjac, G., Goulart, P., Bemporad, A., & Boyd, S. (2020). “OSQP: An Operator Splitting Solver for Quadratic Programs.” Mathematical Programming Computation, 12(4), 637–672.
• Bemporad, A., Morari, M., Dua, V., & Pistikopoulos, E. N. (2002). “The Explicit Linear Quadratic Regulator for Constrained Systems.” Automatica, 38(1), 3–20.

version: 1.0