7.118 반정치 계획법(SDP)의 기초

1. 반정치 계획의 정의

반정치 계획법(Semidefinite Programming, SDP)은 대칭 행렬 변수에 대한 선형 목적 함수를 선형 행렬 부등식(Linear Matrix Inequality, LMI) 제약하에서 최소화하는 볼록 최적화 문제이다. 표준형은 다음과 같다.

$\min_{\mathbf{X} \in \mathbb{S}^n} \quad \text{tr}(\mathbf{C}\mathbf{X})$

$\text{s.t.} \quad \text{tr}(\mathbf{A}_i\mathbf{X}) = b_i, \quad i = 1, \ldots, m$

$\mathbf{X} \succeq 0$

여기서 $\mathbf{X} \in \mathbb{S}^n$ 은 $n \times n$ 대칭 행렬 결정 변수, $\mathbf{C}, \mathbf{A}_i \in \mathbb{S}^n$ 은 데이터 행렬, $\mathbf{X} \succeq 0$ 은 양의 반정치 제약이다. 목적 함수와 제약이 모두 $\mathbf{X}$ 에 대해 선형이며, 양의 반정치 원추 $\mathbb{S}_+^n$ 위에서의 최적화 문제이다.

2. LP와 QP의 일반화

SDP는 LP와 QP를 특수한 경우로 포함하는 더 일반적인 문제이다.

LP를 SDP로: 벡터 변수 $\mathbf{x}$ 를 대각 행렬 $\mathbf{X} = \text{diag}(\mathbf{x})$ 로 치환하면, $\mathbf{x} \geq 0$ 은 $\mathbf{X} \succeq 0$ 이 된다.

QP를 SDP로: $\min \mathbf{x}^T\mathbf{H}\mathbf{x} + \mathbf{c}^T\mathbf{x}$ 는 슈어 보수를 이용하여 SDP로 재정식화할 수 있다.

3. 선형 행렬 부등식(LMI)

LMI는 다음의 형태를 갖는다.

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

여기서 $\mathbf{F}_i \in \mathbb{S}^m$ 은 대칭 행렬이다. LMI의 허용 집합은 볼록이며, 다수의 제어 공학 문제가 LMI로 정식화된다.

4. 해법

SDP는 내점법에 의해 다항 시간 내에 풀 수 있다. 각 반복에서 자기 쌍대 장벽(self-concordant barrier)에 기반한 뉴턴 스텝을 계산하며, 반복 횟수는 $O(\sqrt{n}\log(1/\epsilon))$ 이다. 대표적 해법기로 SeDuMi, SDPT3, MOSEK 등이 있다.

SDP의 주요 계산 병목은 행렬 변수의 크기에 있다. $n \times n$ 행렬의 독립 변수 수가 $n(n+1)/2$ 이므로, $n$ 이 커지면 계산 비용이 급증한다. 실용적으로 $n$ 이 수백 이하인 문제가 다루어진다.

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

강건 제어 설계: 리아프노프 안정성 분석과 제어기 합성에서 안정성 조건이 LMI로 표현된다. 상태 피드백 이득 $\mathbf{K}$ 의 결정이 SDP로 정식화된다.

센서 배치 최적화: 피셔 정보 행렬(Fisher information matrix)의 최소 고유값을 최대화하는 센서 배치 문제가 SDP로 정식화된다.

위치 추정의 이완: 거리 기반 위치 추정(range-based localization)에서 비볼록 이차 제약을 반정치 이완(SDP relaxation)으로 처리하여 전역 최적해의 근사를 구한다.

자세 추정: 점 대응(point correspondence)에 기반한 자세 추정 문제의 반정치 이완이 인증 가능한 전역 최적해를 제공하는 것으로 알려져 있다.

6. 참고 문헌

Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
Vandenberghe, L., & Boyd, S. (1996). “Semidefinite Programming.” SIAM Review, 38(1), 49–95.
Ben-Tal, A., & Nemirovski, A. (2001). Lectures on Modern Convex Optimization. SIAM.
Todd, M. J. (2001). “Semidefinite Optimization.” Acta Numerica, 10, 515–560.

version: 1.0