7.119 원뿔 계획법(SOCP)의 기초

1. 차 원뿔 계획의 정의

2차 원뿔 계획법(Second-Order Cone Programming, SOCP)은 선형 목적 함수를 2차 원뿔 제약(second-order cone constraint)하에서 최소화하는 볼록 최적화 문제이다. 표준형은 다음과 같다.

$\min_{\mathbf{x}} \quad \mathbf{c}^T\mathbf{x}$

$\text{s.t.} \quad \lVert \mathbf{A}_i\mathbf{x} + \mathbf{b}_i \rVert_2 \leq \mathbf{d}_i^T\mathbf{x} + e_i, \quad i = 1, \ldots, m$

$\mathbf{F}\mathbf{x} = \mathbf{g}$

여기서 $\mathbf{A}_i \in \mathbb{R}^{n_i \times n}$ , $\mathbf{b}_i \in \mathbb{R}^{n_i}$ , $\mathbf{d}_i \in \mathbb{R}^n$ , $e_i \in \mathbb{R}$ 이다. 각 제약 $\lVert \mathbf{A}_i\mathbf{x} + \mathbf{b}_i \rVert_2 \leq \mathbf{d}_i^T\mathbf{x} + e_i$ 는 2차 원뿔(second-order cone, Lorentz cone)에의 소속 조건이다.

2. 차 원뿔의 정의

$n$ 차원 2차 원뿔(또는 로렌츠 원뿔, ice-cream cone)은 다음과 같이 정의된다.

$\mathcal{K}^n = \left\{ (\mathbf{u}, t) \in \mathbb{R}^{n-1} \times \mathbb{R} : \lVert \mathbf{u} \rVert_2 \leq t \right\}$

이 집합은 볼록 원추(convex cone)이며, 자기 쌍대(self-dual)이다. $n = 1$ 이면 비음 실수의 집합 $\mathbb{R}_+$ 으로 환원되고, $n = 2$ 이면 평면의 원뿔이 된다.

3. LP, QP, SDP와의 관계

SOCP는 LP와 QP를 특수한 경우로 포함하며, SDP에 포함되는 중간 위치의 문제이다.

$\text{LP} \subset \text{QP} \subset \text{SOCP} \subset \text{SDP}$

LP를 SOCP로: 선형 부등식 $\mathbf{a}_i^T\mathbf{x} \leq b_i$ 는 $\lVert \mathbf{0} \rVert \leq b_i - \mathbf{a}_i^T\mathbf{x}$ 로 표현된다.

볼록 QP를 SOCP로: $\min \frac{1}{2}\mathbf{x}^T\mathbf{H}\mathbf{x} + \mathbf{c}^T\mathbf{x}$ ( $\mathbf{H} \succ 0$ )는 상위 그래프 변환(epigraph reformulation)과 촐레스키 분해를 통해 SOCP로 변환된다.

4. SOCP로 정식화 가능한 제약

4.1 유클리드 노름 제약

$\lVert \mathbf{A}\mathbf{x} - \mathbf{b} \rVert_2 \leq t$

로봇 공학에서 작업 공간 오차 노름의 한계 부과에 직접 대응한다.

4.2 이차 부등식

$\mathbf{x}^T\mathbf{P}\mathbf{x} + 2\mathbf{q}^T\mathbf{x} + r \leq 0, \quad \mathbf{P} \succeq 0$

$\mathbf{P} = \mathbf{L}\mathbf{L}^T$ (촐레스키 분해)를 이용하면 2차 원뿔 제약으로 변환된다.

4.3 회전된 2차 원뿔

$2uv \geq \lVert \mathbf{w} \rVert_2^2, \quad u, v \geq 0$

이 제약은 변수 변환에 의해 표준 2차 원뿔로 변환 가능하다.

4.4 마찰 원뿔 제약

로봇 접촉 역학에서 쿨롱 마찰 원뿔 제약은 자연스럽게 2차 원뿔 형태이다.

$\sqrt{f_x^2 + f_y^2} \leq \mu f_z$

이 제약은 선형 다면체 근사 없이 정확한 원뿔 형태로 SOCP에 포함된다.

5. 해법

SOCP는 내점법(interior point method)에 의해 다항 시간 내에 풀 수 있다. 2차 원뿔의 자기 쌍대 성질을 활용한 자기 쌍대 장벽(self-concordant barrier) 함수에 기반하며, 반복 횟수는 $O(\sqrt{m}\log(1/\epsilon))$ 이다. ECOS, MOSEK, SCS 등의 해법기가 SOCP를 지원한다.

SOCP의 반복당 비용은 SDP보다 현저히 작으므로, SDP로 정식화 가능하지만 SOCP로도 표현 가능한 문제는 SOCP로 푸는 것이 효율적이다.

6. 로봇 공학에서의 SOCP 응용

접촉력 최적화: 접촉 기반 로봇 제어에서 마찰 원뿔 제약을 정확히 포함하는 SOCP가 선형 근사 QP보다 물리적으로 정확한 접촉력 분배를 산출한다.

강건 궤적 최적화: 불확실성의 타원체적 모델 $\lVert \boldsymbol{\delta} \rVert \leq 1$ 하에서의 최악 경우 제약 만족 문제가 SOCP로 정식화된다.

안테나/센서 배치: 수신 신호 강도의 하한 제약이나 위치 추정 정밀도 제약이 SOCP 형태를 갖는 경우가 있다.

추력 제한 궤적 계획: 로켓이나 멀티로터의 추력 벡터 크기 제약 $\lVert \mathbf{T} \rVert \leq T_{\max}$ 가 2차 원뿔 제약으로 자연스럽게 표현된다. 추력 제한 하의 착륙 궤적 최적화(powered descent guidance)가 SOCP로 정식화되어 실시간으로 풀린다.

7. 참고 문헌

Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
Lobo, M. S., Vandenberghe, L., Boyd, S., & Lebret, H. (1998). “Applications of Second-Order Cone Programming.” Linear Algebra and Its Applications, 284(1-3), 193–228.
Alizadeh, F., & Goldfarb, D. (2003). “Second-Order Cone Programming.” Mathematical Programming, 95(1), 3–51.
Acikmese, B., & Ploen, S. R. (2007). “Convex Programming Approach to Powered Descent Guidance for Mars Landing.” Journal of Guidance, Control, and Dynamics, 30(5), 1353–1366.

version: 1.0