함수 $f:\mathbb R^K\to \mathbb R$, $h_i:\mathbb R^K \to \mathbb R$ ($i=1,\cdots,m$), $l_j:\mathbb R^K\to \mathbb R$ ($j=1,\cdots,n$)가 주어질 때,
집합 $\mathcal C ={\mathbf x \in \mathbb R^K \mid h_i(\mathbf x) \le 0 (\forall i=1,\cdots,m), l_j(\mathbf x)=0 (\forall j=1,\cdots,n)}$에 속하는 $\mathbf x$에 대하여 $f(\mathbf x)$의 최솟값을 구하시오.
- $\mathcal C\neq \varnothing$일 때, $\mathcal C$를 실현가능한 원초집합(primal feasible set)이라 하고, $\mathcal C$에 속하는 $\mathbf x$를 실현가능한(feasible) $\mathbf x$라고 함
- 실현가능한 $\mathbf x$가 모든 $i=1,\cdots,m$에 대해 $h_i(\mathbf x)<0$를 만족시킬 때 엄밀하게 실현가능한 $\mathbf x$라고 함
\[\begin{aligned} & \text{min}_{\mathbf x}\ f(\mathbf x)\\ & {s.t}\ h_i(\mathbf x)\le 0,\quad i=1,\cdots,m\\ & l_j(\mathbf x)=0,\quad j=1,\cdots,n \end{aligned} \cdots\cdots (1)\]
이 원초문제에 대한 라그랑주 함수(Lagrangian function)를 다음과 같이 정의
\[L(\mathbf x, \mathbf u, \mathbf v)=\begin{cases}f(\mathbf x)+\sum_{i=1}^m u_i h_i(\mathbf x)+\sum_{j=1}^n v_j l_j(\mathbf x) &\ \text{if } \mathbf v=(v_1,\cdots,v_n)\in \mathbb R^n,\, \mathbf u\in \mathbb R^m, \, \mathbf u \succeq 0\\ -\infty & \ \text{else} \end{cases}\]벡터 $\mathbf u=(u_1,\cdots,u_m)\in \mathbb R^m$의 모든 성분에 대해 $u_i\ge 0$이 성립할 때 $u \succeq 0$로 나타낼 때,
모든 $\mathbf u\succeq 0$와 $\mathbf v$, 실현가능한 $\mathbf x$에 대해 $f(\mathbf x) \ge L(\mathbf x, \mathbf u,\mathbf v)$이 성립
원초문제의 최적값(primal optimal value)(이 경우 최솟값)을 $f^*$라 할 때, 임의의 $\mathbf u\succeq 0,\,\mathbf v$에 대해
\[f^* =\min_{\mathbf x\in \mathcal C}f(\mathbf x)\ge \min_{\mathbf x\in \mathcal C}L(\mathbf x,\mathbf u,\mathbf v) \ge \min_{\mathbf x\in \mathbb R^K}L(\mathbf x,\mathbf u,\mathbf v) \cdots \cdots (2)\]이 성립하고, $g(\mathbf u,\mathbf v):=\min_{\mathbf x\in \mathbb R^K}L(\mathbf x,\mathbf u,\mathbf v)$로 정의할 때 $g(\mathbf u,\mathbf v)$를 (원초문제에 대한) 라그랑주 쌍대함수(Lagrangian dual function)이라고 함.
모든 $\mathbf u\succeq 0$와 $\mathbf v$에 대해 $f^* \ge g(\mathbf u, \mathbf v)$
- 쌍대문제의 장점: 원초문제의 $f$가 (위로 또는 아래로) 볼록한지에 관계없이 항상 $g$는 위로 볼록한 함수가 되어 최댓값이 존재한다는 것
- $g(\mathbf u,\mathbf v)$가 위로 볼록한 함수가 되는 것은 각 $\mathbf x$에 대해 $L(\mathbf x,\mathbf u,\mathbf v)$가 $\mathbf u,\mathbf v$에 대한 아핀함수가 되므로 쉽게 확인 가능
쌍대문제의 최적값을 $g^* \text{라 하면} f^* \ge g^*$가 성립하고, 이를 약한 쌍대성(weak duality)라고 함
원초문제의 최적값 $f^* \text{와 쌍대문제의 최적값}$ $g^* \text{ 에 대해 }$ $f^*=g^*$가 성립할 때 강한 쌍대성(strong duality)이 만족된다고 함 (이 경우 원초문제의 최적값을 구하는 대신 쌍대문제의 최적값을 구하면 됨)
원초문제의 $f(\mathbf x)$와 쌍대문제의 $g(\mathbf u,\mathbf v)$에 대해 두 값의 차이 $f(\mathbf x)-g(\mathbf u,\mathbf v)$를 쌍대차이(duality gap)이라고 함
- 각 문제에 대해 실현가능한 $\mathbf x,\, \mathbf u,\, \mathbf v$와 각 문제의 최적값 $f^*, g^*$에 대해 다음 관계식이 항상 성립함 $0\le f(\mathbf x)-f^* \le f(\mathbf x)-g(\mathbf u,\mathbf v)$
- 즉, $f(\mathbf x)$와 $g(\mathbf u,\mathbf v)$에 대한 쌍대차이가 $0$이 되면 $\mathbf x$는 원초문제의 최적해 $\mathbf x^*$가 되고, $\mathbf u,\mathbf v$는 쌍대문제의 최적해 $\mathbf u^*,\,\mathbf v^*$가 됨 (이때, $f^*=f(\mathbf x^*)=g(\mathbf u^*,\mathbf v^*)= g^*$가 성립하여 강한 쌍대성이 성립) $\cdots\cdots (3)$
- 반복적으로 근사시키는 방식으로 최적해를 구하는 알고리즘에서는 쌍대차이에 대해 $f(\mathbf x)-g(\mathbf u,\mathbf v)<\epsilon$이 성립하는 것을 stopping 판별 조건으로 사용할 수 있음
(1)과 같은 최적화 문제에서 $f, h_1,\cdots,h_m$이 아래로 볼록한 함수이고, $l_1,\cdots,l_n$이 아핀(affine)함수(즉, $l(x_1,\cdots,x_K)=a_0+a_1x_1+\cdots+a_Kx_K$과 같이 선형사상과 평행이동이 결합된 함수)일 때, (1)을 컨벡스 최적화 문제(convex optimization problem)이라고 함
만약 원초문제가 컨벡스 최적화 문제이고 엄밀하게 실현가능한 $\mathbf x$가 적어도 하나 존재하면 강한 쌍대성이 성립한다.
원초문제의 쌍대문제:
\[\begin{aligned} &\text{[원초문제] }\\ & \text{min}_{\mathbf x}\ f(\mathbf x)\\ & {s.t}\ h_i(\mathbf x)\le 0, i=1,\cdots,m\\ & \ l_j(\mathbf x)=0, j=1,\cdots,n \end{aligned} \qquad \begin{aligned} & \text{[쌍대문제]}\\ & \max_{\mathbf u,\mathbf v}g(\mathbf u,\mathbf v)\\ & \text{ s.t } \mathbf u\succeq 0 \end{aligned}\]
- $\mathbf u=(u_1,\cdots,u_m)\succeq 0$일 때, $g(u,v)=\min_{\mathbf x}(f(\mathbf x)+\sum_{i=1}^m u_i h_i(\mathbf x)+\sum_{j=1}^n v_j l_j(\mathbf x))$
- (Stationary) $\mathbf u,\,\mathbf v$를 고정시키고 라그랑주 함수 $L(\mathbf x,\mathbf u,\mathbf v)$를 $\mathbf x$에 대한 함수로 생각할 때, $\mathbf x$에서의 서브그래디언트에 $\mathbf 0$이 포함됨
- (Complementary Slackness) 모든 $i=1,\cdots,m$에 대해 $u_i h_i(\mathbf x)=0$, 즉, $u_i$와 $h_i(\mathbf x)$ 중 적어도 하나는 $0$
- (Primal Feasibility) 모든 $1\le i \le m,\, 1\le j\le n)$에 대해 $h_i(\mathbf x) \le 0$ 이고 $l_j(\mathbf x)=0$
- (Dual Feasibility) 모든 $1\le i\le m$에 대해 $u_i\ge 0$
원초문제가 컨벡스 최적화 문제일 때 KKT 조건은 쌍대차이가 0이 될 충분조건
- 원초문제가 컨벡스 최적화 문제일 때,
$\mathbf x^*,\,\mathbf u^*,\,\mathbf v^*$가 원초문제에 대한 KKT 조건을 만족하면, 쌍대차이 $f(\mathbf x) -g(\mathbf u,\mathbf v)=0$을 만족시키는 해가 된다.
즉, $\mathbf x^*,\,\mathbf u^*,\,\mathbf v^*$가 원초문제에 대한 KKT 조건을 만족하면, $f(\mathbf x^*)$는 원초문제의 최적값 $f^*$가 되고, $g(\mathbf u^*,\mathbf v^*)$는 쌍대문제의 최적값 $g^*$가 되며 $f^*=g^*$가 성립한다.
증명 클릭!
$L(\mathbf x,\mathbf u^*,\mathbf v^*)$는 $\mathbf x$에 대해 아래로 볼록한 함수이므로 최솟 값을 가지고, $\mathbf x^*$에서의 서브그래디언트가 $\mathbf 0$을 포함하므로 $L(\mathbf x^*,\mathbf u^*,\mathbf v^*)$가 최솟값이다.(앞서 배운 ML2020-07-01(라쏘회귀 부분)의 서브그래디언트 설명 참고) 또, KKT 조건의 (Complementary slackness)와 (primal feasibility)를 이용하면 다음이 성립
\[\begin{aligned} g(\mathbf u^*,\mathbf v^*)=&\min_{\mathbf x}L(\mathbf x,\mathbf u^*,\mathbf v^*)\\ =& L(\mathbf x^*,\mathbf u^*,\mathbf v^*) \\ =& f(\mathbf x^*)+\sum_{i=1}^m u_i^* h_i(\mathbf x^*)+\sum_{j=1}^n v_j^* l_j(\mathbf x^*)\\ =& f(\mathbf x^*) \end{aligned}\]
- 에서 마지막 부등식에서 등호가 성립하려면 $\sum_{i=1}^m u_i^* h_i(\mathbf x^*)=0$이 되어야 하고, 모든 $1\le i\le i$에 대해 $h_i(\mathbf x^*)\le 0$이므로 $u_i^*h_i(\mathbf x^*)=0$이 성립해야 함 (KKT 조건의 Complementary slackness)
- 마지막으로 위 식의 첫 번째 부등식에서 등호가 성립하려면 $L(\mathbf x,\mathbf u^*,\mathbf v^*)$가 $\mathbf x^*$에서 최소가 되어야 하므로 $\mathbf x^*$에서의 서브그래디언트에 $\mathbf 0$이 포함됨 (KKT 조건의 Stationary)
- 종합하면,
원초문제와 쌍대문제 사이에 강한 쌍대성이 만족되면, $ \mathbf x^*$와 $\mathbf u^*,\,\mathbf v^*$가 각각 원초문제와 쌍대문제의 최적해 $\Longleftrightarrow$ $\mathbf x^*$와 $\mathbf u^*,\,\mathbf v^*$가 KKT 조건을 만족
원초문제가 컨벡스 최적화 문제일 때, 엄밀하게 실현가능한 $\mathbf x$가 존재하면,
$ \mathbf x^*$와 $\mathbf u^*,\,\mathbf v^*$가 각각 원초문제와 쌍대문제의 최적해
$\Longleftrightarrow$ $\mathbf x^*$와 $\mathbf u^*,\,\mathbf v^*$가 KKT 조건을 만족
- 주의할 점:
- 원초문제의 목적함수 $f$가 미분가능한 경우에도, KKT 조건의 Stationary 조건에서 $\mathbf x$에서의 서브그래디언트에 $\mathbf 0$이 포함된다는 것과 $\mathbf x$에서의 그래디언트 벡터가 $\mathbf 0$이 된다는 것은 일반적으로 동일한 조건이 아님
- 하지만, 목적함수 $f$가 미분가능하고 아래로 볼록한 경우에는 $\mathbf x$에서의 서브그래디언트는 그래디언트 벡터만으로 이루어짐
Reference:
Ryan Tibshirani의 컨벡스 최적화(Convex Optimization) 강의_카네기 멜런 대학교(Carnegie Mellon University) 통계학과를 참고해 구성된 강의 내용입니다. (강의 홈페이지 및 PPT 자료 링크)