6.133 볼록 최적화와 반정치 계획법

1. 볼록 집합과 볼록 함수의 정의

볼록 최적화(convex optimization)는 최적화 문제의 한 부류로서, 목적 함수가 볼록 함수이고 가능 영역(feasible region)이 볼록 집합인 경우를 다룬다. 볼록 최적화의 핵심적 장점은 모든 국소 최솟값(local minimum)이 전역 최솟값(global minimum)과 일치한다는 것이다.

집합 \mathcal{C} \subseteq \mathbb{R}^n이 볼록 집합이라 함은, 임의의 \mathbf{x}_1, \mathbf{x}_2 \in \mathcal{C}와 0 \leq \theta \leq 1에 대하여

\theta \mathbf{x}_1 + (1 - \theta) \mathbf{x}_2 \in \mathcal{C}

가 성립하는 것이다. 함수 f: \mathbb{R}^n \to \mathbb{R}이 볼록 함수라 함은, 정의역이 볼록 집합이고 임의의 \mathbf{x}_1, \mathbf{x}_2와 0 \leq \theta \leq 1에 대하여

f\bigl(\theta \mathbf{x}_1 + (1-\theta)\mathbf{x}_2\bigr) \leq \theta f(\mathbf{x}_1) + (1-\theta) f(\mathbf{x}_2)

를 만족하는 것이다. 이차 미분 가능한 함수의 경우, 볼록성의 필요충분조건은 헤시안 행렬 \nabla^2 f(\mathbf{x})가 모든 점에서 양의 반정치(positive semidefinite)인 것이다.

\nabla^2 f(\mathbf{x}) \succeq 0 \quad \forall \mathbf{x} \in \text{dom}(f)

2. 볼록 최적화 문제의 표준형

일반적인 볼록 최적화 문제는 다음과 같은 표준형으로 표현한다.

\begin{aligned} \min_{\mathbf{x}} \quad & f_0(\mathbf{x}) \\ \text{subject to} \quad & f_i(\mathbf{x}) \leq 0, \quad i = 1, \dots, m \\ & \mathbf{A}\mathbf{x} = \mathbf{b} \end{aligned}

여기서 f_0, f_1, \dots, f_m은 볼록 함수이고, 등식 제약 조건은 아핀(affine)이다. 이 문제의 라그랑지안(Lagrangian)은 다음과 같다.

L(\mathbf{x}, \boldsymbol{\lambda}, \boldsymbol{\nu}) = f_0(\mathbf{x}) + \sum_{i=1}^{m} \lambda_i f_i(\mathbf{x}) + \boldsymbol{\nu}^T (\mathbf{A}\mathbf{x} - \mathbf{b})

여기서 \lambda_i \geq 0은 부등식 제약에 대한 라그랑지 승수이고, \boldsymbol{\nu}는 등식 제약에 대한 라그랑지 승수이다. 강한 쌍대성(strong duality)이 성립하면 원초 문제(primal problem)와 쌍대 문제(dual problem)의 최적값이 동일하며, 이는 슬레이터 조건(Slater’s condition)에 의하여 보장된다.

3. 반정치 계획법(Semidefinite Programming, SDP)

3.1 기본 정의

반정치 계획법은 볼록 최적화의 한 부류로서, 결정 변수가 양의 반정치 행렬인 최적화 문제를 다룬다. SDP의 표준형은 다음과 같다.

\begin{aligned} \min_{\mathbf{X}} \quad & \text{tr}(\mathbf{C}\mathbf{X}) \\ \text{subject to} \quad & \text{tr}(\mathbf{A}_i \mathbf{X}) = b_i, \quad i = 1, \dots, m \\ & \mathbf{X} \succeq 0 \end{aligned}

여기서 \mathbf{X} \in \mathbb{S}^n은 n \times n 대칭 행렬이고, \mathbf{C}, \mathbf{A}_1, \dots, \mathbf{A}_m \in \mathbb{S}^n은 주어진 대칭 행렬이며, b_1, \dots, b_m \in \mathbb{R}은 상수이다. 표기 \mathbf{X} \succeq 0은 행렬 \mathbf{X}가 양의 반정치임을 나타낸다.

3.2 SDP의 쌍대 문제

SDP의 쌍대 문제는 다음과 같다.

\begin{aligned} \max_{\mathbf{y}} \quad & \mathbf{b}^T \mathbf{y} \\ \text{subject to} \quad & \sum_{i=1}^{m} y_i \mathbf{A}_i + \mathbf{S} = \mathbf{C} \\ & \mathbf{S} \succeq 0 \end{aligned}

여기서 \mathbf{y} \in \mathbb{R}^m이 쌍대 변수이고, \mathbf{S}는 슬랙 행렬(slack matrix)이다. 원초-쌍대 최적해 (\mathbf{X}^*, \mathbf{y}^*, \mathbf{S}^*)에서 상보성 조건(complementarity condition)은 다음과 같다.

\mathbf{X}^* \mathbf{S}^* = \mathbf{0}

3.3 선형 계획법 및 이차 계획법과의 관계

SDP는 선형 계획법(LP)과 이차 원추 계획법(SOCP)을 특수 경우로 포함하는 일반적인 프레임워크이다.

4. 선형 행렬 부등식(Linear Matrix Inequality, LMI)

SDP의 제약 조건은 선형 행렬 부등식으로 표현할 수 있다. LMI는 다음과 같은 형태를 가진다.

\mathbf{F}(\mathbf{x}) = \mathbf{F}_0 + \sum_{i=1}^{n} x_i \mathbf{F}_i \succeq 0

여기서 \mathbf{F}_0, \mathbf{F}_1, \dots, \mathbf{F}_n \in \mathbb{S}^m은 주어진 대칭 행렬이고, \mathbf{x} = (x_1, \dots, x_n)^T가 결정 변수이다. \mathbf{F}(\mathbf{x}) \succeq 0이라 함은 \mathbf{F}(\mathbf{x})의 모든 고유값이 비음수인 것을 의미한다. LMI의 가능 영역 \{\mathbf{x} \mid \mathbf{F}(\mathbf{x}) \succeq 0\}은 볼록 집합이다. 이를 스펙트라헤드론(spectrahedron)이라 한다.

5. 로봇공학에서의 SDP 적용

5.1 자세 추정 문제

로봇의 3차원 자세(pose)를 추정하는 문제에서, 회전 행렬 \mathbf{R} \in SO(3)을 결정해야 한다. 직접적인 비볼록 제약 \mathbf{R}^T \mathbf{R} = \mathbf{I}, \det(\mathbf{R}) = 1 대신, SDP 완화(relaxation)를 통하여 볼록 문제로 변환할 수 있다.

\begin{aligned} \min_{\mathbf{Z}} \quad & \text{tr}(\mathbf{Q}\mathbf{Z}) \\ \text{subject to} \quad & \mathbf{Z} \succeq 0 \\ & \text{tr}(\mathbf{Z}) = 1 \\ & \text{rank}(\mathbf{Z}) = 1 \quad (\text{완화 시 제거}) \end{aligned}

랭크-1 제약을 제거하면 SDP가 되며, 이를 세마이 완화(Shor relaxation)라 한다. 완화된 해의 랭크가 1이면 원래 문제의 전역 최적해를 복원할 수 있다.

5.2 경로 계획에서의 장애물 회피

로봇 경로 계획에서 장애물 회피 조건을 타원체(ellipsoid)로 모델링할 때, 두 타원체의 분리 조건을 LMI로 표현할 수 있다. 타원체 \mathcal{E}_i = \{\mathbf{x} \mid (\mathbf{x} - \mathbf{c}_i)^T \mathbf{P}_i^{-1} (\mathbf{x} - \mathbf{c}_i) \leq 1\}에 대하여, \mathcal{E}_1 \cap \mathcal{E}_2 = \emptyset인 조건을 S-procedure를 이용하여 다음과 같이 나타낸다.

\exists \tau \geq 0 : \quad \begin{bmatrix} \mathbf{P}_1^{-1} - \tau \mathbf{P}_2^{-1} & -\mathbf{P}_1^{-1}\mathbf{c}_1 + \tau \mathbf{P}_2^{-1}\mathbf{c}_2 \\ (-\mathbf{P}_1^{-1}\mathbf{c}_1 + \tau \mathbf{P}_2^{-1}\mathbf{c}_2)^T & \mathbf{c}_1^T \mathbf{P}_1^{-1}\mathbf{c}_1 - \tau \mathbf{c}_2^T \mathbf{P}_2^{-1}\mathbf{c}_2 - 1 + \tau \end{bmatrix} \succeq 0

5.3 힘/토크 제약 하의 파지 계획

로봇 그리퍼(gripper)가 물체를 안정적으로 파지(grasp)하기 위한 접촉력을 결정하는 문제도 SDP로 정식화할 수 있다. 각 접촉점 i에서의 접촉력 \mathbf{f}_i가 마찰 원추(friction cone) 내에 있어야 하는 조건은 이차 원추 제약으로 표현한다.

\lVert \mathbf{f}_{i,t} \rVert_2 \leq \mu_i f_{i,n}

여기서 \mathbf{f}_{i,t}는 접선 방향 힘, f_{i,n}은 법선 방향 힘, \mu_i는 마찰 계수이다. 이 SOCP 제약을 LMI로 변환하면 다음과 같다.

\begin{bmatrix} \mu_i f_{i,n} \mathbf{I} & \mathbf{f}_{i,t} \\ \mathbf{f}_{i,t}^T & \mu_i f_{i,n} \end{bmatrix} \succeq 0

6. SDP의 수치 해법

6.1 내점법(Interior-Point Method)

SDP를 풀기 위한 가장 널리 사용되는 방법은 원초-쌍대 내점법이다. 장벽 함수(barrier function)로서 로그-행렬식 장벽을 사용한다.

\phi(\mathbf{X}) = -\log \det(\mathbf{X})

이 함수는 \mathbf{X} \succ 0일 때 정의되며, \mathbf{X}가 경계(\mathbf{X}의 최소 고유값이 0에 접근)에 가까워지면 무한대로 발산한다. 뉴턴 스텝을 계산하기 위하여 다음의 선형 시스템을 풀어야 한다.

$$
\begin{bmatrix}
\mathbf{H} & \mathbf{A}^T \
\mathbf{A} & \mathbf{0}
\end{bmatrix}
\begin{bmatrix}
\Delta \mathbf{x} \
\Delta \boldsymbol{\nu}
\end

\begin{bmatrix}
-\mathbf{g} \
\mathbf{h}
\end{bmatrix}
$$

여기서 \mathbf{H}는 헤시안, \mathbf{g}는 그래디언트, \mathbf{A}는 등식 제약의 행렬이다. 내점법의 반복 복잡도는 O(\sqrt{n} \log(1/\epsilon))이며, 각 반복에서의 계산 복잡도는 O(n^3 m + n^2 m^2)이다.

6.2 교대 방향 승수법(ADMM)

대규모 SDP 문제에 대하여 교대 방향 승수법(Alternating Direction Method of Multipliers)을 적용할 수 있다. ADMM은 원래 문제를 분리 가능한 부분 문제들로 분할하여 반복적으로 풀며, 각 부분 문제는 양의 반정치 원추에 대한 사영(projection)을 포함한다. 행렬 \mathbf{M}을 양의 반정치 원추에 사영하려면 고유값 분해를 수행한다.

\mathbf{M} = \mathbf{U} \boldsymbol{\Lambda} \mathbf{U}^T \quad \Rightarrow \quad \Pi_{\mathbb{S}_+^n}(\mathbf{M}) = \mathbf{U} \max(\boldsymbol{\Lambda}, 0) \mathbf{U}^T

여기서 \max(\boldsymbol{\Lambda}, 0)은 각 고유값을 0과의 최댓값으로 대체한 대각 행렬이다.

7. 볼록 완화 기법의 품질 평가

SDP 완화의 품질은 쌍대 간극(duality gap)으로 평가한다. 원초 최적값 p^*와 쌍대 최적값 d^*에 대하여

p^* - d^* \geq 0

이 간극이 0이면 완화가 정확(tight)하다고 한다. 로봇공학의 여러 문제에서, 특히 자세 추정이나 센서 네트워크 위치 결정 문제에서 SDP 완화가 정확하게 되는 충분조건을 분석하는 것이 활발한 연구 주제이다.

8. 참고 문헌

• Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
• Wolkowicz, H., Saigal, R., & Vandenberghe, L. (2000). Handbook of Semidefinite Programming. Springer.
• Rosen, D. M., Carlone, L., Bandeira, A. S., & Leonard, J. J. (2019). SE-Sync: A certifiably correct algorithm for synchronization over the special Euclidean group. International Journal of Robotics Research, 38(2-3), 95–125.
• Ben-Tal, A., & Nemirovski, A. (2001). Lectures on Modern Convex Optimization. SIAM.
• Siciliano, B., Sciavicco, L., Villani, L., & Oriolo, G. (2009). Robotics: Modelling, Planning and Control. Springer.

v 0.1