KKT Condition

최적화 문제에서 최적 해를 찾는 필요,충분 조건 KKT 조건에 대해 알아보자

참고 1 : Karush-Kuhn-Tucker Conditions
참고 2 : 모두를 위한 컨벡스 최적화, KKT Conditions
참고 3 : CMU-convex optimiazation, KKT Conditions

KKT condition은 어떠한 선형 또는 비선형 최적화 문제에서 최적해를 찾는 필요, 충분 조건이다. 여기에 primal 문제가 convex 일 경우엔 KKT condition은 strong duality에 대한 충분조건도 된다.

반대로 primal 문제의 목적함수와 제약들이 미분 가능하면서 strong duality를 만족한다면, primal & dual 양쪽의 optimal point에서 KKT condition을 만족하게 된다.

KKT Condition

다음 최적화 문제가 있다 :

\[\begin{align} \min_x & \quad f(x) \nonumber \\ \text{s.t. } & \quad h_i(x) \leq 0, i = 1 ... m \nonumber \\ & \quad l_j(x) = 0, j = 1 ... r \end{align}\]

이때, KKT(Karush-Kuhn-Tucker)-Condition은 다음과 같은 조건들로 이루어져 있다.

Stationarity Condition :

\[\begin{align} \nabla f(x^*) + \sum_{i=1}^{m} \lambda_i \nabla h_i(x^*) + \sum_{j=1}^{r} \nu_j \nabla l_j(x^*) = 0 \label{kkt-stationarity} \end{align}\]

이는 라그랑지안의 gradient가 0이 되는 조건과 동일하다. 처음부터 이걸 의도하고 만들어진게 라그랑지안 함수니까.

Primal Feasibility :

\[\begin{align} h_i(x^*) & \leq 0, i = 1 ... m \nonumber \\ l_j(x^*) & = 0, j = 1 ... r \label{kkt-primal} \end{align}\]

Primal 문제의 제약 조건들이다. 당연히 만족해야 한다.

Dual Feasibility :

\[\begin{align} \lambda_i \geq 0, i = 1 ... m \label{kko-dual} \end{align}\]

Dual 문제가 가능하기 위한 조건이다. 자세한 내용은 Duality-Linear Program에서 lagrangian dual function의 부등식이 성립하는 조건을 살펴보자.

Complementary Slackness :

\[\begin{align} \lambda_i h_i(x^*) = 0, i = 1 ... m \label{kkt-complementary} \end{align}\]

부등식 제약 조건 또는 해당 lagrangian multiplier들 중 적어도 하나는 0이 되어야 한다는 조건이다.
원래 lagrange multiplier 방법은 등식 제약 조건에만 사용된다. 부등식 제약 조건, $h_i(x) \leq 0$는 부등식의 경계인 $h_i(x) = 0$에서는 등식 제약 조건으로써 작용한다. 하지만 $h_i(x) < 0$ 의 영역이라면 더 이상 등식 조건이 아니므로, 해당하는 lagrange multiplier를 0으로 만들어서 영향을 없애는 것이다.

이 말을 다르게 표현하면, $h_i(x)$ 또는 $\lambda_i$ 중 적어도 하나는 0이 되어야 한다는 것이며, 수식으로 합치면 $\lambda_i h_x(x)=0$이 된다. 그래서 상보적인(Complementary) 라는 말이 붙었다.

관련 성질 증명

KKT Condition을 만족하는 $x,\lambda, \nu$ 를 각각 $x^* ,\lambda^* , \nu^* $ 라 하자

Convex Primal Problem에서 KKT Condition을 만족하면, Strong Duality를 보인다.

Convex Primal Solution 이므로, $f(x), l_i(x)$는 convex function이다. 이떄, $\mathcal{L}(x,\lambda^* , \nu^* )$도 convex function 이다.

\[\begin{align} \mathcal{L}(x,\lambda^* , v^* ) &= f(x) + \sum_{i=1}^m \lambda_i^* h_i(x) + \sum_{j=1}^r \nu_j^* l_j(x) \nonumber \\ &= f(x) + \sum_{j=1}^r \nu_j^* l_j(x) + 0, \text{by } (\ref{kkt-complementary}) \nonumber \\ & \text{ : convex function (sum of convex functions)} \end{align}\]

또한, stationary condition ($\ref{kkt-stationarity}$) 에 의해 $ \nabla \mathcal{L}(x^* , \lambda^* , \nu^* ) = 0$ 이므로, convex 함수에 대해 극점이면 그곳이 바로 global minimum point가 된다. 즉 $x^* $는 $\mathcal{L}(x,\lambda^* , \nu^* )$의 최소점이다.
거기다가 primal feasibility에 의해 $l_j(x^* ) = 0$이므로, $\mathcal{L}(x^* ,\lambda^* , \nu^* ) = f(x^* )$ 이다. 그러므로 $x^* $는 primal 문제의 최적해이다.

\[\begin{align} \mathcal{L}(x^* ,\lambda^* , \nu^* ) &= \min_x \mathcal{L}(x, \lambda^* , \nu^* ) \nonumber \\ &= f(x^* ) + \sum_{j=1}^r \nu_j^* l_j(x^* ) \nonumber \\ &= f(x^* ) \end{align}\]

따라서, $g^* = f^* $임이 보장되므로, strong duality를 만족한다.

Strong Duality를 보이면, KKT Condition을 만족한다.

Strong duality에 의해, 다음이 성립한다

\[\begin{align} f(x^* ) &= g(\lambda^* , \nu^* ) \nonumber \\ &= \min_x \left( f(x) +\sum_{i=1}^m \lambda^* h_i(x) + \sum_{j=1}^r \nu_j^* l_j(x) \right) \nonumber \\ &= \min_x f(x) = f^* \label{kkt-1} \end{align}\]

zero duality gap에 의해 $f^* = g(\lambda^* , \nu^* )$이 된다.
$\ref{kkt-1}$ 이 성립하게 만드는 조건이 complementary slackness와 primal feasibility 이다.

요약하면 KKT 조건은 :

• Zero duality gap을 가진 primal, dual solution의 충분조건.
• Strong duality를 가졌다면 primal, dual solution의 필요조건.

KKT Matrix

특정 optimization 문제에 대한 KKT 조건은 행렬 형태로 나타낼 수 있다.

예를 들어 다음의 Quadratic Programming 문제를 생각해보자. $Q \succ 0$ 이고, 이 문제는 convex 하며, Slater’s condition을 만족한다 하자.

\[\begin{align} \min_x & \quad \frac{1}{2} x^T Q x + p^T x + r \nonumber \\ \text{s.t. } & \quad Ax \leq b \nonumber \end{align}\]

위 문제의 라그랑지안은 다음과 같다 :

\[\begin{align} \mathcal{L}(x,\nu) &= \frac{1}{2} x^T Q x + p^T x + r + \nu^T (Ax - b) \nonumber \end{align}\]

이때, stationary condition은 다음과 같다 :

\[\begin{align} \nabla_x \mathcal{L}(x,\nu) &= Qx + p + A^T \nu = 0 \nonumber \\ \Rightarrow & Qx^* + A^T \nu^* = -p \end{align}\]

primal feability condition은 다음과 같다 :

\[\begin{align} Ax^* & = b \end{align}\]

이때, 위의 2개의 조건을 행렬의 형태로 합치면, 다음과 같은 형태가 나오는데. 이를 KKT Matrix 라 한다 :

\[\begin{align} \begin{bmatrix} Q & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} x^* \\ \nu^* \end{bmatrix} = \begin{bmatrix} -p \\ b \end{bmatrix} \end{align}\]

이렇게 KKT Matrix를 구하면, primal 문제의 최적해와 dual 문제의 최적해를 동시에 구할 수 있으며, 역행렬을 사용해 한번에 closed form solution으로 나온다.

여기에서, 위의 quadratic programming 함수를 2차 테일러 전개로 바꾸면, constrainted newton step과도 동일해진다.
$Q = \nabla^2 f(x_k), p = \nabla f(x_k), r = f(x_k)$ 로 바꾸면 된다.

\[\begin{align} \begin{bmatrix} \nabla^2 f(x_k) & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} x_{k+1} \\ \nu_k \end{bmatrix} = \begin{bmatrix} -\nabla f(x_k) \\ b \end{bmatrix} \end{align}\]