7.108 등식 제약 이차 계획의 해석해

1. 문제의 정의

등식 제약만을 갖는 이차 계획 문제는 다음과 같다.

\min_{\mathbf{x} \in \mathbb{R}^n} \quad \frac{1}{2}\mathbf{x}^T\mathbf{H}\mathbf{x} + \mathbf{c}^T\mathbf{x}

\text{subject to} \quad \mathbf{A}\mathbf{x} = \mathbf{b}

여기서 \mathbf{H} \in \mathbb{R}^{n \times n}은 대칭 양정치 행렬, \mathbf{A} \in \mathbb{R}^{p \times n} (p \leq n)은 행 완전 계수(full row rank)인 제약 행렬이다.

2. KKT 시스템에 의한 해석해

라그랑주 함수 \mathcal{L}(\mathbf{x}, \boldsymbol{\nu}) = \frac{1}{2}\mathbf{x}^T\mathbf{H}\mathbf{x} + \mathbf{c}^T\mathbf{x} + \boldsymbol{\nu}^T(\mathbf{A}\mathbf{x} - \mathbf{b})의 정류 조건은 다음의 KKT 선형 시스템을 산출한다.

\begin{bmatrix} \mathbf{H} & \mathbf{A}^T \\ \mathbf{A} & \mathbf{0} \end{bmatrix} \begin{bmatrix} \mathbf{x}^* \\ \boldsymbol{\nu}^* \end{bmatrix} = \begin{bmatrix} -\mathbf{c} \\ \mathbf{b} \end{bmatrix}

이 (n+p) \times (n+p) 대칭 시스템을 KKT 시스템 또는 안장점 시스템(saddle-point system)이라 한다. \mathbf{H} \succ 0이고 \mathbf{A}가 행 완전 계수이면, 이 시스템은 유일한 해를 갖는다.

3. 축소(Schur 보수)에 의한 해

KKT 시스템의 첫 번째 행으로부터 \mathbf{x}^*를 \boldsymbol{\nu}^*의 함수로 표현할 수 있다.

\mathbf{x}^* = -\mathbf{H}^{-1}(\mathbf{c} + \mathbf{A}^T\boldsymbol{\nu}^*)

이를 두 번째 행 \mathbf{A}\mathbf{x}^* = \mathbf{b}에 대입하면 다음을 얻는다.

-\mathbf{A}\mathbf{H}^{-1}(\mathbf{c} + \mathbf{A}^T\boldsymbol{\nu}^*) = \mathbf{b}

\mathbf{A}\mathbf{H}^{-1}\mathbf{A}^T\boldsymbol{\nu}^* = -\mathbf{b} - \mathbf{A}\mathbf{H}^{-1}\mathbf{c}

\mathbf{S} = \mathbf{A}\mathbf{H}^{-1}\mathbf{A}^T \in \mathbb{R}^{p \times p}은 슈어 보수(Schur complement)로, \mathbf{H} \succ 0이고 \mathbf{A}가 행 완전 계수이면 \mathbf{S} \succ 0이다. 따라서 승수는 다음과 같이 유일하게 결정된다.

\boldsymbol{\nu}^* = -\mathbf{S}^{-1}(\mathbf{b} + \mathbf{A}\mathbf{H}^{-1}\mathbf{c})

이를 \mathbf{x}^*의 표현에 대입하면 최적해가 완전히 결정된다.

\mathbf{x}^* = \mathbf{H}^{-1}\mathbf{A}^T\mathbf{S}^{-1}(\mathbf{b} + \mathbf{A}\mathbf{H}^{-1}\mathbf{c}) - \mathbf{H}^{-1}\mathbf{c}

4. 영공간 방법(Null-Space Method)

\mathbf{A}의 영공간 기저 \mathbf{Z} \in \mathbb{R}^{n \times (n-p)} (\mathbf{A}\mathbf{Z} = \mathbf{0})와 특수해 \hat{\mathbf{x}} (\mathbf{A}\hat{\mathbf{x}} = \mathbf{b})를 이용하면, 허용 해는 \mathbf{x} = \hat{\mathbf{x}} + \mathbf{Z}\mathbf{w}로 매개변수화된다. 이를 목적 함수에 대입하면 비제약 문제로 환원된다.

\min_{\mathbf{w}} \quad \frac{1}{2}\mathbf{w}^T\mathbf{Z}^T\mathbf{H}\mathbf{Z}\mathbf{w} + (\mathbf{H}\hat{\mathbf{x}} + \mathbf{c})^T\mathbf{Z}\mathbf{w}

축소 헤시안 \mathbf{Z}^T\mathbf{H}\mathbf{Z} \in \mathbb{R}^{(n-p) \times (n-p)}이 양정치이면, 최적 \mathbf{w}^*는 다음과 같다.

\mathbf{w}^* = -(\mathbf{Z}^T\mathbf{H}\mathbf{Z})^{-1}\mathbf{Z}^T(\mathbf{H}\hat{\mathbf{x}} + \mathbf{c})

이 방법은 제약 공간의 차원이 작을 때(n - p가 작을 때) 효율적이다.

5. 범위 공간 방법(Range-Space Method)

p가 작을 때(즉, 등식 제약의 수가 적을 때), 슈어 보수 \mathbf{S} = \mathbf{A}\mathbf{H}^{-1}\mathbf{A}^T를 직접 형성하고 p \times p 시스템을 풀어 승수를 결정하는 것이 효율적이다. 이 방법은 \mathbf{H}의 분해(촐레스키 등)를 한 번 수행한 후, 전방/후방 대입으로 \mathbf{H}^{-1}\mathbf{A}^T와 \mathbf{H}^{-1}\mathbf{c}를 계산한다.

6. 수치적 해법의 선택

희소 시스템에서는 각 방법의 실제 비용이 채움(fill-in) 패턴에 크게 의존하므로, 문제의 희소 구조에 맞는 방법을 선택해야 한다.

7. 특수한 경우: \mathbf{H} = \mathbf{I}

\mathbf{H} = \mathbf{I}이면 최소 노름 문제로 환원된다.

\min_{\mathbf{x}} \quad \frac{1}{2}\lVert \mathbf{x} \rVert^2 + \mathbf{c}^T\mathbf{x} \quad \text{s.t.} \quad \mathbf{A}\mathbf{x} = \mathbf{b}

\mathbf{c} = \mathbf{0}이면 최소 노름 해 \mathbf{x}^* = \mathbf{A}^T(\mathbf{A}\mathbf{A}^T)^{-1}\mathbf{b} = \mathbf{A}^\dagger\mathbf{b}로, 의사 역행렬(pseudoinverse)에 의한 해와 일치한다. 이 결과는 로봇 역기구학에서 여유 자유도 시스템의 최소 노름 관절 속도 해로 직접 활용된다.

8. 로봇 공학에서의 응용

역동역학 해법: 관절 가속도가 주어졌을 때, 동역학 제약 \mathbf{M}\ddot{\mathbf{q}} + \mathbf{h} = \boldsymbol{\tau} + \mathbf{J}_c^T\mathbf{f}_c를 만족하면서 접촉력의 노름을 최소화하는 문제가 등식 제약 QP로 정식화된다.

여유 자유도 역기구학: 과업 공간 제약 \mathbf{J}\dot{\mathbf{q}} = \dot{\mathbf{x}}_d를 등식 제약으로 갖는 관절 속도의 이차 최적화 문제이다.

9. 참고 문헌

• Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
• Golub, G. H., & Van Loan, C. F. (2013). Matrix Computations (4th ed.). Johns Hopkins University Press.
• Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.

version: 1.0