6.132 라그랑주 승수법의 행렬 형식

1. 개요

라그랑주 승수법(method of Lagrange multipliers)은 등식 구속 조건이 있는 최적화 문제를 풀기 위한 고전적 방법이다. 이 방법을 행렬 형식으로 표현하면, 로봇공학에서 자주 등장하는 구속 최적화 문제를 체계적으로 정식화하고 해석할 수 있다. 본 절에서는 라그랑주 승수법의 행렬 형식을 유도하고, 로봇공학에서의 응용을 다룬다.

2. 등식 구속 최적화 문제

2.1 일반적 형식

등식 구속 조건이 있는 최적화 문제는 다음과 같이 정의된다.

\min_{\mathbf{x}} f(\mathbf{x})

\text{subject to} \quad \mathbf{h}(\mathbf{x}) = \mathbf{0}

여기서 \mathbf{x} \in \mathbb{R}^n은 결정 변수, f: \mathbb{R}^n \to \mathbb{R}은 목적 함수, \mathbf{h}: \mathbb{R}^n \to \mathbb{R}^m은 m개의 등식 구속 조건 (m < n)이다.

2.2 라그랑주 함수

라그랑주 승수 벡터 \boldsymbol{\lambda} \in \mathbb{R}^m을 도입하여 라그랑주 함수(Lagrangian)를 정의한다.

\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \boldsymbol{\lambda}^T \mathbf{h}(\mathbf{x})

2.3 정류 조건(Stationarity Conditions)

라그랑주 함수의 정류 조건은 다음과 같다.

\frac{\partial \mathcal{L}}{\partial \mathbf{x}} = \nabla f(\mathbf{x}) + \left(\frac{\partial \mathbf{h}}{\partial \mathbf{x}}\right)^T \boldsymbol{\lambda} = \mathbf{0}

\frac{\partial \mathcal{L}}{\partial \boldsymbol{\lambda}} = \mathbf{h}(\mathbf{x}) = \mathbf{0}

여기서 \frac{\partial \mathbf{h}}{\partial \mathbf{x}} \in \mathbb{R}^{m \times n}은 구속 조건의 야코비안 행렬이다.

3. 이차 목적 함수와 선형 구속의 행렬 형식

3.1 문제 정의

이차 목적 함수와 선형 등식 구속 조건을 가진 문제:

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

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

여기서 Q \in \mathbb{R}^{n \times n}은 양의 정부호 대칭 행렬, \mathbf{c} \in \mathbb{R}^n, A \in \mathbb{R}^{m \times n}, \mathbf{b} \in \mathbb{R}^m이다.

3.2 라그랑주 함수

\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) = \frac{1}{2} \mathbf{x}^T Q \mathbf{x} + \mathbf{c}^T \mathbf{x} + \boldsymbol{\lambda}^T (A \mathbf{x} - \mathbf{b})

3.3 정류 조건의 행렬 형식

정류 조건을 연립하면 다음의 KKT 시스템(Karush-Kuhn-Tucker system)을 얻는다.

\begin{bmatrix} Q & A^T \\ A & \mathbf{0} \end{bmatrix} \begin{bmatrix} \mathbf{x} \\ \boldsymbol{\lambda} \end{bmatrix} = \begin{bmatrix} -\mathbf{c} \\ \mathbf{b} \end{bmatrix}

이 (n + m) \times (n + m) 연립방정식을 KKT 행렬 방정식이라 한다.

3.4 KKT 행렬의 성질

KKT 행렬 K의 주요 성질은 다음과 같다.

K = \begin{bmatrix} Q & A^T \\ A & \mathbf{0} \end{bmatrix}

1. 대칭성: K = K^T
2. 부정부호성: Q가 양의 정부호이더라도 K는 부정부호(indefinite)이다
3. 비특이성: Q가 양의 정부호이고 A가 행 최대 계수(full row rank)이면 K는 비특이(nonsingular)이다
4. 관성: K의 양의 고유값 수는 n개, 음의 고유값 수는 m개이다

3.5 해의 명시적 표현

KKT 시스템을 블록 소거법으로 풀면 다음을 얻는다.

첫 번째 행에서:

\mathbf{x} = Q^{-1}(-\mathbf{c} - A^T \boldsymbol{\lambda})

이를 두 번째 행에 대입하면:

A Q^{-1} A^T \boldsymbol{\lambda} = -A Q^{-1} \mathbf{c} - \mathbf{b}

\boldsymbol{\lambda} = -(A Q^{-1} A^T)^{-1}(A Q^{-1} \mathbf{c} + \mathbf{b})

최적해:

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

4. 라그랑주 승수의 물리적 의미

4.1 감도 해석

라그랑주 승수 \lambda_i는 i번째 구속 조건이 최적값에 미치는 영향을 나타낸다. 구속 조건의 우변 \mathbf{b}가 \delta \mathbf{b}만큼 변할 때, 최적 목적 함수값의 변화는 다음과 같다.

\delta f^* \approx -\boldsymbol{\lambda}^T \delta \mathbf{b}

따라서 \lambda_i의 크기가 큰 구속 조건이 최적값에 큰 영향을 미친다.

4.2 구속력으로서의 해석

로봇 동역학에서 라그랑주 승수는 구속 조건을 유지하기 위해 필요한 **구속력(constraint force)**에 대응한다. 이는 닫힌 사슬(closed-chain) 기구학 또는 접촉 역학에서 중요한 물리적 의미를 가진다.

5. 로봇공학에서의 응용

5.1 구속 역기구학

말단 장치 속도를 추종하면서 관절 속도의 노름을 최소화하는 문제:

\min_{\dot{\mathbf{q}}} \frac{1}{2} \dot{\mathbf{q}}^T \dot{\mathbf{q}}

\text{subject to} \quad J \dot{\mathbf{q}} = \mathcal{V}_d

라그랑주 함수:

\mathcal{L} = \frac{1}{2} \dot{\mathbf{q}}^T \dot{\mathbf{q}} + \boldsymbol{\lambda}^T (J \dot{\mathbf{q}} - \mathcal{V}_d)

정류 조건:

\dot{\mathbf{q}} + J^T \boldsymbol{\lambda} = \mathbf{0}, \quad J \dot{\mathbf{q}} = \mathcal{V}_d

해:

\dot{\mathbf{q}}^* = J^T (J J^T)^{-1} \mathcal{V}_d = J^{\dagger} \mathcal{V}_d

여기서 J^{\dagger} = J^T(JJ^T)^{-1}는 우(right) 의사역행렬이다. 라그랑주 승수는 다음과 같다.

\boldsymbol{\lambda} = -(JJ^T)^{-1} \mathcal{V}_d

5.2 가중 최소 노름 문제

가중 행렬 W(양의 정부호)를 포함하면:

\min_{\dot{\mathbf{q}}} \frac{1}{2} \dot{\mathbf{q}}^T W \dot{\mathbf{q}}

\text{subject to} \quad J \dot{\mathbf{q}} = \mathcal{V}_d

KKT 시스템:

\begin{bmatrix} W & J^T \\ J & \mathbf{0} \end{bmatrix} \begin{bmatrix} \dot{\mathbf{q}} \\ \boldsymbol{\lambda} \end{bmatrix} = \begin{bmatrix} \mathbf{0} \\ \mathcal{V}_d \end{bmatrix}

해:

\dot{\mathbf{q}}^* = W^{-1} J^T (J W^{-1} J^T)^{-1} \mathcal{V}_d

5.3 닫힌 사슬 동역학

닫힌 사슬 기구(closed-chain mechanism)의 동역학은 홀로노믹 구속(holonomic constraint) \mathbf{h}(\mathbf{q}) = \mathbf{0}을 포함한다. 라그랑주 방정식은 다음과 같다.

M(\mathbf{q})\ddot{\mathbf{q}} + C(\mathbf{q}, \dot{\mathbf{q}})\dot{\mathbf{q}} + \mathbf{g}(\mathbf{q}) = \boldsymbol{\tau} + A^T(\mathbf{q}) \boldsymbol{\lambda}

여기서 A(\mathbf{q}) = \frac{\partial \mathbf{h}}{\partial \mathbf{q}}는 구속 야코비안이고, A^T \boldsymbol{\lambda}는 구속력의 일반화 힘이다.

구속 조건을 시간에 대해 두 번 미분하면 가속도 수준의 구속을 얻는다.

A \ddot{\mathbf{q}} + \dot{A} \dot{\mathbf{q}} = \mathbf{0}

이를 동역학 방정식과 결합하면 확장 KKT 시스템이 된다.

\begin{bmatrix} M & -A^T \\ A & \mathbf{0} \end{bmatrix} \begin{bmatrix} \ddot{\mathbf{q}} \\ \boldsymbol{\lambda} \end{bmatrix} = \begin{bmatrix} \boldsymbol{\tau} - C\dot{\mathbf{q}} - \mathbf{g} \\ -\dot{A}\dot{\mathbf{q}} \end{bmatrix}

5.4 접촉 역학

로봇과 환경의 접촉에서, 접촉 구속은 다음과 같이 모델링된다.

J_c \dot{\mathbf{q}} = \mathbf{0} \quad \text{(비활주 접촉)}

이때 라그랑주 승수 \boldsymbol{\lambda}는 접촉력에 대응한다. 접촉력이 물리적으로 유효하려면 마찰 원뿔(friction cone) 내에 있어야 한다는 부등식 구속이 추가된다.

6. 차 충분 조건

6.1 사영 헤시안

라그랑주 승수법에서 극솟값의 충분 조건은 구속 조건의 접평면 위에서 라그랑주 함수의 헤시안이 양의 정부호인 것이다.

구속 야코비안 A의 영공간(null space)의 기저를 열로 가진 행렬을 Z라 하면 (AZ = \mathbf{0}),

Z^T \nabla^2_{\mathbf{x}\mathbf{x}} \mathcal{L} \, Z \succ 0

이 조건은 구속 조건을 만족하는 방향으로의 이동에 대해 목적 함수가 증가함을 보장한다.

6.2 이차 목적 함수의 경우

f(\mathbf{x}) = \frac{1}{2}\mathbf{x}^T Q \mathbf{x} + \mathbf{c}^T \mathbf{x}이고 구속이 A\mathbf{x} = \mathbf{b}인 경우, 사영 헤시안 조건은 다음과 같다.

Z^T Q Z \succ 0

Q가 양의 정부호이면 이 조건은 자동으로 만족된다.

7. 수치 해법

7.1 직접 해법

KKT 시스템의 직접 해법으로는 다음의 방법이 있다.

1. 블록 LDL 분해: KKT 행렬의 대칭 부정부호 성질을 이용하는 분해법
2. 슈르 보완(Schur complement): AQ^{-1}A^T를 형성하여 축소된 시스템을 풀기
3. 범위-영공간 분해(range-null space decomposition): 구속 조건을 먼저 만족시킨 후 최적화

7.2 반복 해법

대규모 문제에서는 반복 해법이 효율적이다.

• 켤레 그래디언트법(Conjugate Gradient): 사전 조건자(preconditioner)와 결합
• 교대 방향 승수법(ADMM, Alternating Direction Method of Multipliers): 분산 최적화에 적합

8. 참고 문헌

1. Nocedal, J., & Wright, S. J. (2006). Numerical Optimization. 2nd ed., Springer.
2. Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
3. Nakamura, Y. (1991). Advanced Robotics: Redundancy and Optimization. Addison-Wesley.
4. Featherstone, R. (2008). Rigid Body Dynamics Algorithms. Springer.
5. Murray, R. M., Li, Z., & Sastry, S. S. (1994). A Mathematical Introduction to Robotic Manipulation. CRC Press.
6. Golub, G. H., & Van Loan, C. F. (2013). Matrix Computations. 4th ed., Johns Hopkins University Press.

v 0.1