6.131 이차 형식과 최적화 문제의 행렬 표현

1. 개요

이차 형식(quadratic form)은 벡터의 성분에 대한 2차 다항식을 행렬로 표현한 것으로, 로봇공학의 다양한 최적화 문제에서 핵심적인 역할을 한다. 운동 에너지의 표현, 최소 자승 문제, 최적 경로 계획, 역기구학의 여유 자유도 활용 등에서 이차 형식이 나타난다. 본 절에서는 이차 형식의 수학적 정의와 성질을 서술하고, 로봇공학 최적화 문제에의 행렬 표현을 다룬다.

2. 이차 형식의 정의

2.1 스칼라 이차 형식

벡터 \mathbf{x} = (x_1, x_2, \ldots, x_n)^T \in \mathbb{R}^n와 대칭 행렬 A \in \mathbb{R}^{n \times n}에 대해, 이차 형식은 다음과 같이 정의된다.

Q(\mathbf{x}) = \mathbf{x}^T A \mathbf{x} = \sum_{i=1}^{n} \sum_{j=1}^{n} a_{ij} x_i x_j

아인슈타인 합산 규약으로 쓰면 다음과 같다.

Q(\mathbf{x}) = a_{ij} x^i x^j

2.2 대칭 행렬의 역할

임의의 정방행렬 B에 대해 \mathbf{x}^T B \mathbf{x} = \mathbf{x}^T \left(\frac{B + B^T}{2}\right) \mathbf{x}가 성립한다. 따라서 이차 형식의 행렬은 항상 대칭으로 가정할 수 있다.

A = \frac{B + B^T}{2}

2.3 이차 형식의 기하학적 의미

이차 형식 Q(\mathbf{x}) = c (상수)가 정의하는 등위면(level surface)의 형태는 행렬 A의 고유값에 의해 결정된다.

• A가 양의 정부호(positive definite): 타원체(ellipsoid)
• A가 양의 준정부호(positive semi-definite): 퇴화 타원체
• A가 부정부호(indefinite): 쌍곡면(hyperboloid)

3. 정부호성과 분류

3.1 정부호성의 정의

대칭 행렬 A의 정부호성은 다음과 같이 분류된다.

3.2 실비스터 판정법

n \times n 대칭 행렬 A가 양의 정부호이기 위한 필요충분조건은 모든 선행 주소행렬식(leading principal minor)이 양수인 것이다.

\Delta_1 = a_{11} > 0, \quad \Delta_2 = \begin{vmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{vmatrix} > 0, \quad \ldots, \quad \Delta_n = \det(A) > 0

3.3 촐레스키 분해

양의 정부호 행렬 A는 하삼각 행렬 L을 이용하여 다음과 같이 분해할 수 있다.

A = L L^T

이 분해를 촐레스키 분해(Cholesky decomposition)라 하며, 이차 형식의 최적화 문제를 효율적으로 푸는 데 활용된다.

4. 이차 형식의 미분

4.1 그래디언트

이차 형식 Q(\mathbf{x}) = \mathbf{x}^T A \mathbf{x}의 그래디언트는 다음과 같다.

\nabla_{\mathbf{x}} Q = \frac{\partial Q}{\partial \mathbf{x}} = (A + A^T)\mathbf{x} = 2A\mathbf{x}

마지막 등호는 A가 대칭일 때 성립한다.

4.2 헤시안

이차 형식의 헤시안(Hessian) 행렬은 상수이다.

H = \frac{\partial^2 Q}{\partial \mathbf{x} \partial \mathbf{x}^T} = A + A^T = 2A

이차 형식의 임계점이 극솟값인지 여부는 헤시안, 즉 A의 정부호성으로 판단한다.

4.3 일반적인 이차 함수

선형 항과 상수항을 포함하는 일반적인 이차 함수는 다음과 같다.

f(\mathbf{x}) = \frac{1}{2}\mathbf{x}^T A \mathbf{x} + \mathbf{b}^T \mathbf{x} + c

그래디언트:

\nabla f = A\mathbf{x} + \mathbf{b}

A가 양의 정부호일 때, \nabla f = \mathbf{0}의 해가 유일한 최솟값이다.

\mathbf{x}^* = -A^{-1}\mathbf{b}

5. 로봇공학에서의 이차 최적화 문제

5.1 최소 자승 문제

과결정(overdetermined) 연립방정식 A\mathbf{x} \approx \mathbf{b}의 최소 자승 해는 다음의 이차 형식을 최소화한다.

\min_{\mathbf{x}} \lVert A\mathbf{x} - \mathbf{b} \rVert^2 = \min_{\mathbf{x}} (\mathbf{x}^T A^T A \mathbf{x} - 2\mathbf{b}^T A \mathbf{x} + \mathbf{b}^T \mathbf{b})

정규 방정식(normal equation)을 통해 해를 구한다.

A^T A \mathbf{x} = A^T \mathbf{b}

\mathbf{x}^* = (A^T A)^{-1} A^T \mathbf{b} = A^{\dagger} \mathbf{b}

여기서 A^{\dagger}는 무어-펜로즈 의사역행렬(Moore-Penrose pseudoinverse)이다.

5.2 가중 최소 자승 문제

가중 행렬 W(양의 정부호 대칭 행렬)를 포함하는 가중 최소 자승 문제:

\min_{\mathbf{x}} (A\mathbf{x} - \mathbf{b})^T W (A\mathbf{x} - \mathbf{b})

해:

\mathbf{x}^* = (A^T W A)^{-1} A^T W \mathbf{b}

로봇공학에서 가중 행렬 W는 각 구속 조건의 상대적 중요도를 반영한다.

5.3 역기구학의 여유 자유도 활용

여유 자유도(redundant) 로봇(n > 6)의 역기구학에서, 원하는 말단 속도 \mathcal{V}_d를 만족하면서 부가 목적 함수를 최적화하는 문제는 다음과 같이 정식화된다.

\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

여기서 J는 야코비안, W는 양의 정부호 가중 행렬이다. 이 문제의 해는 가중 의사역행렬을 사용하여 구한다.

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

5.4 관절 토크 최소화

정적 평형 조건 J^T \mathbf{f} = \boldsymbol{\tau}에서, 원하는 말단 힘 \mathbf{f}_d를 발생시키면서 관절 토크의 2-노름을 최소화하는 문제:

\min_{\boldsymbol{\tau}} \frac{1}{2} \boldsymbol{\tau}^T \boldsymbol{\tau}

\text{subject to} \quad J^T \mathbf{f}_d = \boldsymbol{\tau}

5.5 경로 최적화

로봇의 경로 \mathbf{q}(t)를 최적화하는 문제에서, 경로의 매끄러움(smoothness)은 다음의 이차 형식으로 측정된다.

J_{\text{smooth}} = \int_0^T \ddot{\mathbf{q}}(t)^T W \ddot{\mathbf{q}}(t) \, dt

이산화하면 다음과 같은 유한 차원 이차 형식이 된다.

J_{\text{smooth}} = \mathbf{Q}^T H \mathbf{Q}

여기서 \mathbf{Q}는 이산화된 경유점 벡터이고, H는 양의 준정부호 행렬이다.

6. 이차 계획법

6.1 문제 정식화

이차 계획법(quadratic programming, QP)은 이차 목적 함수와 선형 구속 조건을 가진 최적화 문제이다.

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

\text{subject to} \quad A_{eq} \mathbf{x} = \mathbf{b}_{eq}, \quad A_{ineq} \mathbf{x} \leq \mathbf{b}_{ineq}

Q가 양의 준정부호이면 이 문제는 볼록(convex) 이차 계획 문제이며, 전역 최적해가 존재한다.

6.2 KKT 조건

이차 계획 문제의 최적성 조건은 카루시-쿤-터커(Karush-Kuhn-Tucker, KKT) 조건이다.

Q\mathbf{x} + \mathbf{c} + A_{eq}^T \boldsymbol{\lambda} + A_{ineq}^T \boldsymbol{\mu} = \mathbf{0}

A_{eq} \mathbf{x} = \mathbf{b}_{eq}

\boldsymbol{\mu} \geq \mathbf{0}, \quad A_{ineq} \mathbf{x} \leq \mathbf{b}_{ineq}, \quad \mu_i (A_{ineq,i} \mathbf{x} - b_{ineq,i}) = 0

6.3 로봇공학에서의 QP 응용

실시간 로봇 제어에서 QP는 다음과 같은 문제에 활용된다.

7. 레일리 지수

7.1 정의

대칭 행렬 A에 대한 레일리 지수(Rayleigh quotient)는 다음과 같다.

R(\mathbf{x}) = \frac{\mathbf{x}^T A \mathbf{x}}{\mathbf{x}^T \mathbf{x}}

7.2 성질

레일리 지수는 A의 최소 고유값 \lambda_{\min}과 최대 고유값 \lambda_{\max} 사이의 값을 가진다.

\lambda_{\min} \leq R(\mathbf{x}) \leq \lambda_{\max}

등호는 \mathbf{x}가 대응하는 고유벡터일 때 성립한다.

7.3 로봇공학에서의 의미

질량 행렬 M(\mathbf{q})에 대한 레일리 지수는 단위 관절 속도당 운동 에너지의 상하한을 제공한다. 이는 로봇의 조종성(manipulability) 분석에서 활용된다.

8. 참고 문헌

1. Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
2. Nocedal, J., & Wright, S. J. (2006). Numerical Optimization. 2nd ed., Springer.
3. Strang, G. (2016). Introduction to Linear Algebra. 5th ed., Wellesley-Cambridge Press.
4. Siciliano, B., Sciavicco, L., Villani, L., & Oriolo, G. (2009). Robotics: Modelling, Planning and Control. Springer.
5. Nakamura, Y. (1991). Advanced Robotics: Redundancy and Optimization. Addison-Wesley.

v 0.1