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

Karush-Kuhn-Tucker(KKT)의 개념

참고링크

머신러닝	딥러닝	선형대수	기초통계	최적화
k-means	신경망이란	고유값,고유벡터	확률변수	컨벡스 셋
k-최근접이웃	성능함수	행렬식	확률분포	컨벡스 함수
선형회귀	신경망 학습	내적	모집단과 표본	라그랑주 듀얼
로지스틱회귀	교차연결	기저	평균과 분산	KKT 조건
릿지,라쏘회귀	합성곱 신경망	랭크, 차원	공분산, 상관계수	ROC 커브
의사결정나무	배치, 에포크 차이	선형변환	최대가능도추정	크로스 밸리데이션
서포트벡터머신	텐서플로기초(1)	직교행렬	베르누이,이항분포	실루엣 스코어
원클래스 SVM	텐서플로기초(2)	고유값분해	기하,음이항분포
LDA	seq2seq	특이값분해	초기하분포
GMM	opencv기초		포아송분포
부스팅	resnet		정규분포
사이킷런 실습	다각형내부판별		감마분포
	엣지판별		지수분포
			카이제곱분포
			베타분포
			균일분포

컨벡스 문제(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을 가집니다.