반정부호 계획법

최적설계 수치해석 통계 마지막 수정: 2026-07-28 05:09:24

1. 개요[편집]

반정부호 계획법(Semidefinite Programming, SDP)은 결정변수가 대칭 반정부호 행렬인 볼록 최적화 문제다. 목적함수와 제약은 그 행렬에 대해 여전히 선형이지만, 변수가 놓이는 공간이 “실수 비음수 축”에서 “반정부호 행렬 원뿔”로 넓어졌다. 선형계획법에서 $x \ge 0$ 이라 쓰던 자리에 $X \succeq 0$ 이 들어간다고 보면 된다.

이 한 글자 차이로 표현력이 폭발한다. 고유값 제약, 스펙트럼 노름, 이차형식의 부호, 다항식의 비음수성, 심지어 조합 최적화 문제의 완화까지 전부 SDP 한 틀에 들어온다. 그러면서도 볼록 최적화이므로 국소해가 곧 전역해고, 내점법으로 다항시간에 풀린다. “볼록성을 잃지 않고 갈 수 있는 가장 먼 곳” 정도의 위치를 차지한다.¹

2. 표준형과 선형행렬부등식[편집]

$\mathbb{S}^n$ 을 $n \times n$ 대칭행렬 공간, $\langle A, B \rangle = \mathrm{tr}(A^\top B)$ 를 내적이라 하면 표준형은

\min_{X \in \mathbb{S}^n} \; \langle C, X \rangle \quad \text{s.t.} \quad \langle A_i, X \rangle = b_i \; (i = 1,\dots,m), \quad X \succeq 0

여기서 $X \succeq 0$ 은 $X$ 가 대칭 반정부호, 즉 모든 고유값이 0 이상이라는 뜻이다. 이 조건은 무한히 많은 부등식 $v^\top X v \ge 0 \;(\forall v)$ 과 동치라서, 유한 개의 선형 제약으로는 절대 표현할 수 없다.

쌍대 형태로 쓰면 더 익숙한 얼굴이 나온다. 변수 $x \in \mathbb{R}^m$ 에 대해

F(x) = F_0 + \sum_{i=1}^{m} x_i F_i \succeq 0

를 선형행렬부등식(Linear Matrix Inequality, LMI)이라 한다. 제어 이론 문헌은 거의 전부 이 표기를 쓴다. LMI로 표현된 집합은 항상 볼록이고, 여러 LMI는 블록 대각으로 쌓아 하나로 합칠 수 있다. 그리고 슈어 보수 보조정리가 있어서

\begin{bmatrix} P & S \\ S^{\top} & R \end{bmatrix} \succeq 0 \iff R \succ 0, \; P - S R^{-1} S^{\top} \succeq 0

덕분에 겉보기에 비선형(이차 분수식, 노름 제약)인 조건들이 줄줄이 LMI로 변신한다. SDP 모델링의 절반은 슈어 보수를 어디에 쓸지 찾는 일이다.

3. 원뿔 계획의 위계[편집]

SDP는 더 큰 그림인 원뿔 계획(conic programming)의 한 사례다. 문제를 $\min c^\top x$ s.t. $Ax = b$ , $x \in \mathcal{K}$ 로 쓰고 원뿔 $\mathcal{K}$ 만 갈아 끼우면 다음 위계가 된다.

문제	원뿔	대표 제약
LP	비음수 상한 $\mathbb{R}^n_+$	성분이 0 이상
SOCP	2차 원뿔(아이스크림콘)	노름이 선형식 이하
SDP	반정부호 원뿔 $\mathbb{S}^n_+$	행렬의 고유값이 0 이상

그리고 $\text{LP} \subset \text{SOCP} \subset \text{SDP}$ 의 포함 관계가 성립한다. LP는 대각행렬만 허용한 SDP고, 2차 원뿔 제약은 슈어 보수로 $2 \times 2$ 블록 LMI가 된다. 표현력이 올라가는 만큼 계산 비용도 올라가므로, SOCP로 표현 가능한 문제를 굳이 SDP로 던지는 것은 손해다. 이 위계 감각이 실무 모델링의 기본기다.²

4. 쌍대성과 슬레이터 조건[편집]

쌍대문제는 다음과 같다.

\max_{y \in \mathbb{R}^m} \; b^{\top} y \quad \text{s.t.} \quad S = C - \sum_{i=1}^{m} y_i A_i \succeq 0

약쌍대성 $\langle C, X\rangle - b^\top y = \langle X, S \rangle \ge 0$ 은 LP와 똑같이 공짜로 성립한다(반정부호 행렬 두 개의 내적은 항상 0 이상이다). 그런데 강쌍대성은 공짜가 아니다. LP는 아무 조건 없이 쌍대 간극이 0이었지만, SDP에서는 슬레이터 조건(엄격 실행가능점 $X \succ 0$ 의 존재) 같은 제약자격이 필요하다. 이게 깨지면

최적값은 유한한데 쌍대 간극이 양수로 남거나,
최적값에 임의로 가까이 갈 수 있는데 달성하는 해가 없거나

하는 일이 실제로 벌어진다. 반정부호 원뿔이 다면체가 아니라 곡면 경계를 가지기 때문에 생기는 현상이다. 상보성 조건도 $x_j s_j = 0$ 대신 행렬식 $XS = 0$ 으로 바뀌고, 최적에서 $\mathrm{rank}(X) + \mathrm{rank}(S) \le n$ 이라는 랭크 관계가 따라온다. 엄격 상보성이 성립하면 등호가 되고, 이게 깨진 문제는 수치적으로도 아주 고약해진다.

5. 해법과 계산 비용[편집]

주력은 원-쌍대 내점법이다. 로그 배리어로 $-\log\det X$ 를 쓰는데, 이 함수가 반정부호 원뿔의 자기일치 배리어이고 파라미터가 $n$ 이라 반복 수는 $O(\sqrt{n}\log(1/\epsilon))$ 으로 이론 보증이 붙는다. 실제로도 20~50회 반복이면 끝나는 편이라 반복 수는 걱정거리가 아니다. 문제는 반복당 비용이다.

한 반복마다 $m \times m$ 슈어 보수 행렬을 만들어 촐레스키로 푸는데, 밀집 문제에서 조립에 대략 $O(m n^3 + m^2 n^2)$ , 풀이에 $O(m^3)$ 이 든다. 메모리도 $m^2$ 이다. 그래서 제약 개수 $m$ 이 수천을 넘어가면 급격히 힘들어지고, 이 벽을 넘으려는 시도가 여럿 있다.

저랭크 인수분해(Burer-Monteiro): $X = RR^\top$ 로 두고 $R \in \mathbb{R}^{n \times r}$ 을 비볼록 최적화한다. $r(r+1)/2 > m$ 이면 가짜 국소해가 없다는 결과가 있어서, 최적해의 랭크가 낮은 문제에 잘 먹힌다.
일차 방법: ADMM 계열이 큰 문제에 쓰인다. 정확도는 떨어지지만 규모가 다르다. 다만 매 반복 고유분해가 필요해 고유값 문제 비용을 피할 수는 없다.
구조 활용: 사슬형 희소성이 있으면 큰 LMI를 작은 블록들의 합으로 쪼개는 사슬형 분해(chordal decomposition)로 비용을 크게 줄인다.

6. 응용[편집]

제어의 LMI 설계. 선형 시스템 $\dot{x} = Ax$ 의 안정성은 $A^\top P + PA \prec 0$ , $P \succ 0$ 인 $P$ 의 존재와 동치다(리아푸노프 정리). 이건 $P$ 에 대한 LMI 실행가능성 문제, 즉 SDP다. 여기서 출발해 상태 궤환 이득 설계, $H_\infty$ 성능 보장, 다중 모델에 대한 강건 안정성까지 전부 LMI 묶음으로 표현된다. 1990년대 초 이 관점이 제어 이론을 통째로 재편했고, 대응하는 리카티 방정식 해법과 이론적으로 등가인 경우가 많다 — 다만 LMI 쪽은 여러 제약을 동시에 얹기가 쉽다는 강점이 있다.

MaxCut과 0.878 근사. 그래프의 정점을 두 집합으로 나눠 가로지르는 간선 가중치 합을 최대화하는 MaxCut은 NP-난해다. $x_i \in \{-1, 1\}$ 을 단위벡터 $v_i$ 로 완화하고 $X_{ij} = v_i^\top v_j$ 로 두면 $X \succeq 0$ , $X_{ii} = 1$ 인 SDP가 된다. 이 해를 촐레스키로 분해해 나온 벡터들을 무작위 초평면으로 자르면, 기대 절단값이 SDP 최적값의 $0.87856\dots$ 배 이상임을 보일 수 있다(괴만스-윌리엄슨, 1995). 유일 게임 추측이 참이라면 이 상수를 개선하는 다항시간 알고리즘은 없다.³

행렬 완성과 통계. 관측된 일부 성분만으로 저랭크 행렬을 복원하는 문제에서, 랭크 최소화는 비볼록이지만 그 볼록 완화인 핵노름(특이값의 합) 최소화는 SDP로 표현된다. 특이값 분해와 주성분 분석의 강건 변형(robust PCA)도 같은 틀이다. 실험 설계에서 정보행렬의 행렬식·최소고유값을 최적화하는 D-/E-최적 설계 역시 SDP다.

다항식 최적화. 다항식이 비음수라는 조건은 일반적으로 다루기 어렵지만, 제곱합(sum of squares)으로 표현 가능하다는 더 강한 조건은 계수의 그램 행렬이 반정부호라는 SDP 제약이 된다. 이 완화를 차수별로 쌓아 올린 것이 라세르 위계이며, 비볼록 다항식 문제의 전역 하계를 준다.

구조 최적화. 트러스 위상 설계에서 컴플라이언스 최소화 문제는 SDP로 정확히 정식화된다(강성행렬의 반정부호성이 그대로 제약이 된다). 좌굴 하중이나 최소 고유진동수 제약도 고유값 부등식이라 LMI로 들어가고, 응력 제약의 일부 완화 역시 같은 방식으로 처리된다. 위상 최적화의 밀도법이 실무를 지배하지만, 전역 최적성이 증명되는 유일한 경로는 대개 이쪽이다.

7. 관련 문서[편집]

물론 “가장 먼 곳”은 계속 갱신된다. 초다항 원뿔, 상대 엔트로피 원뿔, 완전정부호 원뿔 등이 더 밖에 있다. 다만 완전정부호 원뿔은 위에서 최적화하는 것 자체가 NP-난해라, 볼록이라고 다 풀리는 건 아니라는 교훈을 준다. ↩
모델링 언어에 $\lVert Ax - b \rVert_2 \le t$ 를 던지면 알아서 SOCP로 잡아 준다. 그걸 손으로 슈어 보수 때려서 $n{+}1$ 차 LMI로 만들어 SDP 솔버에 넣으면, 정확히 같은 답을 몇십 배 느리게 얻는다. 해본 사람이 하는 말이다. ↩
0.87856은 $\min_{\theta} \frac{2}{\pi} \frac{\theta}{1 - \cos\theta}$ 에서 나온다. 무작위로 초평면 하나 그었을 뿐인데 최적값의 87.8%를 보장한다는 게 이 결과의 충격 포인트. 조합 최적화 강의에서 학생들 표정이 바뀌는 지점이기도 하다. ↩