7장. 쌍대성

모든 최소화 문제에는 짝이 되는 최대화 문제가 있습니다. 이 짝을 쌍대 문제라 하고, 그 최댓값은 언제나 원래 최솟값의 하한이 됩니다. 볼록 문제에서는 둘이 정확히 같아서, 어려운 원래 문제 대신 쉬운 쌍대 문제를 풀 수 있습니다. SVM이 커널 함수로 무한 차원 특성을 다룰 수 있는 것, 최적 수송의 계산, 게임 이론의 미니맥스 정리가 모두 쌍대성 덕분입니다.

7.1 쌍대 함수

6장의 문제(원문제, primal problem)와 라그랑주 함수 $\mathcal L(\mathbf x, \boldsymbol\lambda, \boldsymbol\nu)$에 대해

정의 7.1. 라그랑주 쌍대 함수(Lagrange dual function)는

($\inf$는 하한 중 가장 큰 값으로, 최솟값이 있으면 최솟값과 같습니다.)

$d$는 $(\boldsymbol\lambda, \boldsymbol\nu)$에 대한 일차함수들의 하한이므로, 원문제가 볼록이 아니어도 항상 오목합니다.

7.2 약한 쌍대성

정리 7.2 (약한 쌍대성). $\boldsymbol\lambda \ge \mathbf 0$이면 $d(\boldsymbol\lambda, \boldsymbol\nu) \le p^*$입니다. 여기서 $p^*$는 원문제의 최솟값입니다.

증명. 실행 가능한 $\tilde{\mathbf x}$에서 $g_i(\tilde{\mathbf x}) \le 0$, $\lambda_i \ge 0$, $h_j(\tilde{\mathbf x}) = 0$이므로 $\mathcal L(\tilde{\mathbf x}, \boldsymbol\lambda, \boldsymbol\nu) \le f(\tilde{\mathbf x})$. 그러므로 $d \le \mathcal L(\tilde{\mathbf x}, \cdot) \le f(\tilde{\mathbf x})$이고, 모든 실행 가능한 $\tilde{\mathbf x}$에 대해 성립하므로 $d \le p^*$. □

가장 좋은 하한을 찾는 문제

를 쌍대 문제(dual problem)라 합니다. 언제나 $d^* \le p^*$이고, 차이 $p^* - d^*$를 쌍대 간격(duality gap)이라 합니다.

쓸모. 어떤 실행 가능한 $\mathbf x$와 쌍대 실행 가능한 $\boldsymbol\lambda$를 갖고 있으면 $f(\mathbf x) - d(\boldsymbol\lambda)$가 현재 해의 최적성 간격의 상한입니다. 알고리즘의 멈춤 조건으로 씁니다.

7.3 강한 쌍대성

정리 7.3 (슬레이터 조건). 원문제가 볼록이고, 모든 부등식 제약을 엄격하게 만족하는 점($g_i(\mathbf x) < 0$)이 하나라도 있으면 $d^* = p^*$(강한 쌍대성)입니다.

강한 쌍대성이 성립하면 원문제의 해 $\mathbf x^*$와 쌍대 문제의 해 $(\boldsymbol\lambda^*, \boldsymbol\nu^*)$는 정확히 KKT 조건을 만족하는 짝입니다. 그래서 쌍대 문제를 풀고 KKT 정상성으로 $\mathbf x^*$를 되찾을 수 있습니다.

예제 7.4. $\min x^2$ s.t. $x \ge 1$, 곧 $g(x) = 1 - x \le 0$. $p^* = 1$.

• $\mathcal L = x^2 + \lambda(1 - x)$를 $x$로 최소화: $x = \lambda/2$, $d(\lambda) = \lambda - \lambda^2/4$.
• $\max_{\lambda \ge 0}d(\lambda)$: $\lambda^* = 2$, $d^* = 1 = p^*$. 강한 쌍대성.
• 되찾기: $x^* = \lambda^*/2 = 1$.

7.4 최소 노름 문제

예제 7.5. $\min\frac12\|\mathbf x\|^2$ s.t. $A\mathbf x = \mathbf b$(방정식이 미지수보다 적은 경우, 해가 무수히 많을 때 가장 짧은 해).

• $\mathcal L = \frac12\|\mathbf x\|^2 + \boldsymbol\nu^\top(A\mathbf x - \mathbf b)$, $\nabla_{\mathbf x}\mathcal L = \mathbf x + A^\top\boldsymbol\nu = \mathbf 0$에서 $\mathbf x = -A^\top\boldsymbol\nu$.
• $d(\boldsymbol\nu) = -\frac12\boldsymbol\nu^\top AA^\top\boldsymbol\nu - \mathbf b^\top\boldsymbol\nu$, 최대화하면 $\boldsymbol\nu^* = -(AA^\top)^{-1}\mathbf b$.
• $\mathbf x^* = A^\top(AA^\top)^{-1}\mathbf b$. 선형대수의 유사역행렬 해입니다.

7.5 SVM과 커널

선형 분리 가능한 데이터 $(\mathbf x_i, y_i)$, $y_i \in \{\pm1\}$에 대해, 두 클래스 사이 여백(margin)이 가장 큰 초평면을 찾는 서포트 벡터 머신(SVM)은

(여백의 폭이 $2/\|\mathbf w\|$이므로 $\|\mathbf w\|$를 최소로 합니다.) 쌍대 문제는

이고 $\mathbf w^* = \sum_i\alpha_i^*y_i\mathbf x_i$입니다.

두 가지가 중요합니다.

1. 서포트 벡터. 상보 여유성에 따라 여백 경계에 있지 않은 점은 $\alpha_i = 0$입니다. 해는 경계 위의 몇 점(서포트 벡터)만으로 정해집니다.
2. 커널 기법. 쌍대 문제에는 데이터가 내적 $\mathbf x_i^\top\mathbf x_j$로만 나옵니다. 이것을 $k(\mathbf x_i, \mathbf x_j) = \phi(\mathbf x_i)^\top\phi(\mathbf x_j)$로 바꾸면, 특성 변환 $\phi$를 계산하지 않고도 고차원(가우스 커널이면 무한 차원) 공간에서 선형 분리를 하는 것과 같습니다.

7.6 이 장의 요약

• 쌍대 함수 $d = \inf_{\mathbf x}\mathcal L$은 항상 오목. 약한 쌍대성 $d^* \le p^*$.
• 볼록 + 슬레이터 조건이면 강한 쌍대성 $d^* = p^*$, 해의 짝은 KKT 조건.
• 최소 노름 해 $A^\top(AA^\top)^{-1}\mathbf b$. SVM의 쌍대 문제 → 서포트 벡터와 커널.

쓰이는 곳. SVM과 커널 방법, 가우시안 과정, 최적 수송과 바서슈타인 거리(WGAN의 판별자는 쌍대 문제의 해), 강화학습의 제약 정책 최적화(라그랑주 승수를 학습), 분산 최적화(ADMM), 게임 이론의 미니맥스 정리와 GAN, 전력망 운영의 가격 결정(쌍대 변수 = 전기 가격)이 쌍대성을 씁니다.

문제

6
9

5

1
1

0.4