[최적화]Karush-Kuhn-Tucker(KKT)의 개념

업데이트:

Karush-Kuhn-Tucker(KKT)의 개념

참고링크

컨벡스 문제(convex problem)에서의 KKT condition

프리멀 문제(primal problem)가 컨벡스(convex)일때, KKT 조건은 프리멀(primal), 듀얼(dual) 최적화 포인트임을 보이는데 충분하다. 즉, 만약 $f_i$가 컨벡스이고, $h_i$가 아핀(affine)일 때, 어떠한 지점(any point) $\tilde{x}, \tilde{\lambda}, \tilde{v}$에 대해서 아래와 같이 KKT 조건을 만족한다면, $\tilde{x}, (\tilde{\lambda}, \tilde{v})$는 프리멀, 듀얼 최적값(primal and dual optimal)이며, zero duality gap 입니다.

\[f_i(\tilde{x}) \leq 0, \, i=1,\dots,m\] \[h_i(\tilde{x}) = 0, \, i=1,\dots,p\] \[\tilde{\lambda}_i \geq 0, \, i=1,\dots,m\] \[\tilde{\lambda}_i f_i(\tilde{x}) = 0, \, i=1,\dots,m\] \[\bigtriangledown f_0(\tilde{x}) + \sum_{i=1}^{m}\tilde{\lambda}_i \bigtriangledown f_i(\tilde{x}) + \sum_{i=1}^{p}\tilde{v}_i \bigtriangledown h_i(\tilde{x}) = 0\]

처음 두가지 조건은 $\tilde{x}$가 primal feasible임을 보여줍니다. $\tilde{\lambda}_i \geq 0$ 이므로, $L(x, \tilde{\lambda}, \tilde{v})$ 는 $x$에 대해 컨벡스입니다. KKT에서 마지막 조건이 의미하는 바는, $x$에 대한 그래디언트(gradient)는 $x = \tilde{x}$에서 사라집니다. 즉, $\tilde{x}$는 $L(x, \tilde{\lambda}, \tilde{v})$를 $x$에 대해 최소화시킵니다.

\[\begin{align} g(\tilde{\lambda}) &= L(x, \tilde{\lambda}, \tilde{v}) \\ &= f_0(\tilde{x}) + \sum_{i=1}^{m}\tilde{\lambda}_i f_i(\tilde{x}) + \sum_{i=1}^{p}\tilde{v}_i h_i(\tilde{x}) \\ &= f_0(\tilde{x}) \\ \end{align}\]

마지막 부분에서는 $h_i(\tilde{x}) = 0$, $\tilde{\lambda}_i f_i(\tilde{x}) = 0$ 조건을 사용했습니다. 이는 $\tilde{x}, (\tilde{\lambda}, \tilde{v})$ 는 zero duality gap을 가진다는 것을 보여주고, 그러므로 primal and dual optimal 이 되겠습니다.

정리하면, 컨벡스 최적화 문제에서 목적함수와 제약함수가 미분가능할때, KKT 조건을 만족하는 지점은 primal and dual 최적값이며, zero duality gap을 가집니다.