7.100 등식 제약 조건과 라그랑주 승수법

1. 등식 제약 최적화 문제

등식 제약 최적화(equality-constrained optimization)는 다음과 같이 정식화된다.

$\min_{\mathbf{x} \in \mathbb{R}^n} \quad f(\mathbf{x})$

$\text{subject to} \quad h_j(\mathbf{x}) = 0, \quad j = 1, 2, \ldots, p$

여기서 $f: \mathbb{R}^n \to \mathbb{R}$ 은 목적 함수, $h_j: \mathbb{R}^n \to \mathbb{R}$ 은 등식 제약 함수이다. 허용 영역은 $p$ 개의 등식 제약이 정의하는 $(n-p)$ 차원 매니폴드이다.

2. 라그랑주 함수의 구성

라그랑주 승수(Lagrange multiplier) $\nu_j \in \mathbb{R}$ 을 도입하여 라그랑지안(Lagrangian)을 다음과 같이 정의한다.

$\mathcal{L}(\mathbf{x}, \boldsymbol{\nu}) = f(\mathbf{x}) + \sum_{j=1}^{p} \nu_j h_j(\mathbf{x}) = f(\mathbf{x}) + \boldsymbol{\nu}^T\mathbf{h}(\mathbf{x})$

여기서 $\boldsymbol{\nu} = [\nu_1, \ldots, \nu_p]^T$ 는 라그랑주 승수 벡터, $\mathbf{h}(\mathbf{x}) = [h_1(\mathbf{x}), \ldots, h_p(\mathbf{x})]^T$ 는 제약 함수 벡터이다.

3. 차 필요 조건

$\mathbf{x}^*$ 가 등식 제약 최적화 문제의 국소 최소점이고 LICQ(선형 독립 제약 자격)이 성립하면, 라그랑주 승수 $\boldsymbol{\nu}^*$ 가 유일하게 존재하여 다음이 성립한다.

정류 조건:

$\nabla_{\mathbf{x}} \mathcal{L}(\mathbf{x}^*, \boldsymbol{\nu}^*) = \nabla f(\mathbf{x}^*) + \sum_{j=1}^{p} \nu_j^* \nabla h_j(\mathbf{x}^*) = \mathbf{0}$

제약 만족 조건:

$\mathbf{h}(\mathbf{x}^*) = \mathbf{0}$

이 두 조건은 총 $n + p$ 개의 방정식으로 $n + p$ 개의 미지수 $(\mathbf{x}^*, \boldsymbol{\nu}^*)$ 를 결정한다.

4. 기하학적 해석

정류 조건 $\nabla f(\mathbf{x}^*) = -\sum_{j=1}^{p} \nu_j^* \nabla h_j(\mathbf{x}^*)$ 는 최적점에서 목적 함수의 그래디언트가 제약 함수 그래디언트들의 선형 결합으로 표현됨을 의미한다. 기하학적으로, 제약 곡면에 대한 접선 공간 $\mathcal{T} = \{\mathbf{d} : \nabla h_j(\mathbf{x}^*)^T\mathbf{d} = 0, \forall j\}$ 위에서 $\nabla f(\mathbf{x}^*)$ 의 투영이 영이 된다. 즉, 제약 곡면을 따라 이동할 때 목적 함수의 1차 변화가 없으므로, 제약 곡면 위에서의 정류점에 해당한다.

5. 차 충분 조건

1차 필요 조건 $(\mathbf{x}^*, \boldsymbol{\nu}^*)$ 가 만족되고, 접선 공간에 제한한 라그랑지안의 헤시안이 양정치이면, $\mathbf{x}^*$ 는 엄밀한 국소 최소점이다.

$\mathbf{d}^T \nabla^2_{\mathbf{x}\mathbf{x}}\mathcal{L}(\mathbf{x}^*, \boldsymbol{\nu}^*)\mathbf{d} > 0, \quad \forall \mathbf{d} \in \mathcal{T} \setminus \{\mathbf{0}\}$

여기서 $\nabla^2_{\mathbf{x}\mathbf{x}}\mathcal{L} = \nabla^2 f + \sum_j \nu_j \nabla^2 h_j$ 는 라그랑지안의 $\mathbf{x}$ 에 대한 헤시안이다. 이 조건은 제약 곡면 위에서의 곡률이 양수임을 요구한다.

6. 라그랑주 승수의 해석

라그랑주 승수 $\nu_j^*$ 는 $j$ 번째 제약 조건의 한계 가치(marginal value)를 나타낸다. 제약 $h_j(\mathbf{x}) = 0$ 을 $h_j(\mathbf{x}) = \epsilon_j$ 로 완화할 때, 최적 목적 함수값의 변화는 다음과 같다.

$\frac{\partial f^*}{\partial \epsilon_j} = -\nu_j^*$

따라서 $\lvert \nu_j^* \rvert$ 가 큰 제약은 목적 함수에 대한 영향이 크며, 해당 제약의 완화가 큰 성능 개선으로 이어질 수 있음을 의미한다.

7. KKT 시스템의 해법

라그랑주 필요 조건을 뉴턴법으로 풀기 위해, 다음의 KKT 시스템(또는 라그랑주 시스템)을 구성한다.

$\begin{bmatrix} \nabla^2_{\mathbf{x}\mathbf{x}}\mathcal{L} & \mathbf{A}^T \\ \mathbf{A} & \mathbf{0} \end{bmatrix} \begin{bmatrix} \Delta\mathbf{x} \\ \boldsymbol{\nu}_{k+1} \end{bmatrix} = -\begin{bmatrix} \nabla f(\mathbf{x}_k) + \mathbf{A}^T\boldsymbol{\nu}_k \\ \mathbf{h}(\mathbf{x}_k) \end{bmatrix}$

여기서 $\mathbf{A} = \nabla \mathbf{h}(\mathbf{x}_k)^T \in \mathbb{R}^{p \times n}$ 은 제약 야코비안이다. 이 $(n+p) \times (n+p)$ 연립 방정식은 부정치(indefinite) 대칭 시스템으로, LDL 분해 또는 범위-영공간(range-null space) 분해로 효율적으로 풀 수 있다.

8. 축소 공간 방법(Reduced-Space Method)

제약 야코비안 $\mathbf{A}$ 의 영공간 기저 $\mathbf{Z} \in \mathbb{R}^{n \times (n-p)}$ ( $\mathbf{A}\mathbf{Z} = \mathbf{0}$ )를 이용하여, 문제를 제약 곡면의 접선 공간상의 비제약 문제로 환원한다. 갱신 벡터를 $\Delta\mathbf{x} = \mathbf{Z}\mathbf{p}$ 로 매개변수화하면, 축소된 헤시안 $\mathbf{Z}^T\nabla^2_{\mathbf{x}\mathbf{x}}\mathcal{L}\mathbf{Z}$ 에 대한 $(n-p)$ 차원 시스템을 풀게 된다.

9. 등식 제약의 로봇 공학 응용

폐쇄 체인 기구학: 폐루프 메커니즘이나 병렬 로봇에서 관절 변수 사이의 기구학적 구속은 등식 제약으로 표현된다. 이 제약하에서의 운동 계획이나 역기구학 문제에 라그랑주 승수법이 적용된다.

궤적 최적화의 동역학 제약: 직접 전사법으로 이산화된 궤적 최적화에서 시간 단계 간의 동역학 관계는 등식 제약으로 부과된다. 연속적인 상태가 운동 방정식을 만족해야 하는 조건이 $\mathbf{x}_{k+1} = \mathbf{f}(\mathbf{x}_k, \mathbf{u}_k)$ 의 형태로 등식 제약을 구성한다.

말단 장치 과업 제약: 매니퓰레이터가 특정 자세를 유지하면서 다른 자유도를 최적화하는 문제에서, 과업 공간의 위치/자세 제약이 등식 제약으로 작용한다.

10. 참고 문헌

Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
Bertsekas, D. P. (2016). Nonlinear Programming (3rd ed.). Athena Scientific.
Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
Luenberger, D. G., & Ye, Y. (2016). Linear and Nonlinear Programming (4th ed.). Springer.

version: 1.0