[KKT 조건 - 2] KKT 조건과 적용 예제

등식과 부등식 제약조건이 있는 일반적인 최적화 문제에 대해서

 

$$\begin{array}{rl}& p^{\star }=\underset{\mathbf{x}}{min}f(\mathbf{x})\\ \\ \text{subject to : }& g_i(\mathbf{x})\le 0,i=1,...,m\\ \\ & h_j(\mathbf{x})=0,j=1,...,k\end{array}$$

 

 

 

KKT 조건(Karush-Kuhn-Tucker conditions)은 다음과 같다.

 

$$\begin{array}{rl}& \text{1. stationarity: }{\mathrm{\nabla }}_{\mathbf{x}}f(\mathbf{x})+\sum _{i=1}^m{\mu }_i{\mathrm{\nabla }}_{\mathbf{x}}{g}_i(\mathbf{x})+\sum _{j=1}^k{\lambda }_j{\mathrm{\nabla }}_{\mathbf{x}}{h}_j(\mathbf{x})=0\\ \\ & \text{2. primal constraints: }{g}_i(\mathbf{x})\le 0,i=1,...,m\\ \\ & h_j(\mathbf{x})=0,j=1,...,k\\ \\ & \text{3. dual constraints: }{\mu }_i\ge 0,i=1,...,m\\ \\ & \text{4. complementary slackness: }{\mu }_i{g}_i(\mathbf{x})=0,i=1,...,m\end{array}$$

 

여기서 1번과 2번항인 stationarity와 primal constraints 조건은 등식 제약조건만 있는 최적화문제의 경우와 동일한 것으로서, 최적화 변수 $\mathbf{x}$와 라그랑지 곱수 $\mu$, $\lambda$에 대해서 각각 계산한 라그랑지안,

 

$$L(\mathbf{x},\mu ,\lambda )=f(\mathbf{x})+\sum _{i=1}^m{\mu }_i{g}_i(\mathbf{x})+\sum _{j=1}^k{\lambda }_j{h}_j(\mathbf{x})$$

 

의 그래디언트가 $0$이 되는 정류점(stationary point)이 최적해가 됨을 나타낸다.

3번과 4번항은 부등식 제약조건에서 나타나는 추가적인 조건이다.
만약 최적해 ${\mathbf{x}}^{\star }$가 $g_i({\mathbf{x}}^{\star })<0$의 영역에 있다면 이 때의 부등식 제약조건을 슬랙 제약(slack constraints)이라고 하는데 이 경우는 최적해를 계산하는데 아무런 영향을 주지 않는다. 따라서 이에 대한 라그랑지 곱수는 ${\mu }_i=0$으로 주어진다. 만약 최적해 ${\mathbf{x}}^{\star }$가 부등식 제약조건의 경계선인 $g_i({\mathbf{x}}^{\star })=$0의 영역에 있다면 이 때의 제약조건을 바운딩 제약(bounding constraints)이라고 하는데 이 경우는 등식 제약조건과 다를 바 없게 된다. 이 두 경우를 합치면 4번항 complementary slackness(상호 보완적인 슬랙) 조건이 성립한다.

3번항은 부등식 제약조건에 관련된 라그랑지 곱수는 음수(마이너스)가 되면 안된다는 조건으로서 듀얼 제약조건이라고 한다. 프라이멀(primal)과 듀얼(dual)이라는 용어가 나왔는데 이에 대해서는 다음에 알아보기로 하고, 여기서는 KKT 조건을 최적화 예제에 적용해 보기로 하자.

다음과 같이 등식 및 부등식 제약조건을 갖는 최적화 문제가 있다.

 

$$\begin{array}{rl}& \underset{x,y}{min}{x}^2+y^2\\ \\ \text{subject to : }& x^2+y^2\le 5\\ \\ & x+2y=4\\ \\ & x,y\ge 0\end{array}$$

 

사실 이 문제는 그림을 그려 보면 해를 쉽게 구할 수 있다.

 

 

그림에서 검은색 동심원은 $x^2+y^2=c$ 를 그린 것이다. 녹색 원은 $x^2+y^2=5$ 를 그린 것이다. 그리고 1사분면에 있는 녹색 영역이 부등식 제약조건이다. 빨간색 직선은 등식 제약조건을 그린 것이다. 문제에 의하면 녹색 영역안에 있으면서 동시에 빨간색 직선과 접하는 동심원의 최대 반지름의 제곱이 최적해가 된다. 이 값은 $x^{\star }=0.8,y^{\star }=1.6$ 일 때, $f(x^{\star },y^{\star })=(x^{\star }{)}^2+(y^{\star }{)}^2=3.2$ 이다.

 

 

KKT 조건을 적용해 보는 것이 본 예제의 목적이므로 KKT 조건을 적용해서 동일한 최적해를 도출할 수 있는지 살펴보자. 먼저 문제를 표준형으로 바꾼다.

 

$$\begin{array}{rl}& \underset{x,y}{min}{x}^2+y^2\\ \\ \text{subject to : }& x^2+y^2-5\le 0\\ \\ & -x\le 0\\ \\ & -y\le 0\\ \\ & x+2y-4=0\end{array}$$

 

라그랑지안은 다음과 같다.

 

$$L(x,y,{\mu }_1,{\mu }_2,{\mu }_3,\lambda )=x^2+y^2+{\mu }_1(x^2+y^2-5)-{\mu }_{2}x-{\mu }_{3}y+\lambda (x+2y-4)$$

 

KKT 조건식은 다음과 같다.

 

$$\begin{array}{rl}& \text{1. stationarity: }\\ \\ & \frac{\partial L}{\partial x}=2x+2x{\mu }_1-{\mu }_2+\lambda =0\\ \\ & \frac{\partial L}{\partial y}=2y+2y{\mu }_1-{\mu }_3+2\lambda =0\\ \\ & \text{2. primal constraints: }\\ \\ & x^2+y^2-5\le 0\\ \\ & -x\le 0\\ \\ & -y\le 0\\ \\ & x+2y-4=0\\ \\ & \text{3. dual constraints: }{\mu }_1,{\mu }_2,{\mu }_3\ge 0\\ \\ & \text{4. complementary slackness: }\\ \\ & {\mu }_1(x^2+y^2-5)=0\\ \\ & {\mu }_{2}x=0\\ \\ & {\mu }_{3}y=0\end{array}$$

 

3개의 complementary slackness 조건이 있는데 ${\mu }_1,{\mu }_2,{\mu }_3$의 값에 따라 다음과 같이 8개의 경우의 수가 있다.

(1) ${\mu }_1={\mu }_2={\mu }_3=0\to x=\frac{4}{5},y=\frac{8}{5},\lambda =-\frac{8}{5}$
(2) ${\mu }_1={\mu }_2=0\to y=0,x=4\to \text{infeasible}$
(3) ${\mu }_1={\mu }_3=0\to x=0,y=2,\lambda =-2,{\mu }_2=-2$
(4) ${\mu }_2={\mu }_3=0\to x^2+y^2-5=0\to x=2.48,y=0.76$
(5) ${\mu }_1=0\to x=y=0\to \text{infeasible}$
(6) ${\mu }_2=0\to x^2+y^2-5=0,y=0\to x=\sqrt{5}\to \text{infeasible}$
(7) ${\mu }_3=0\to x^2+y^2-5=0,x=0\to y=\sqrt{5}\to \text{infeasible}$
(8) $x^2+y^2-5=0,x=0,y=0\to \text{infeasible}$

이 중에서 (1), (3), (4)번이 실행 가능한(feasible) 해이며 그 중에서 함수를 최소화하는 최적해는 (1)번으로서 $x^{\star }=\frac{4}{5},y^{\star }=\frac{8}{5}$ 이며 그 때의 함수 값은 $f(x^{\star },y^{\star })=3.2$ 이다.

이 최적해는 앞서 그림을 그려서 구한 해와 동일함을 알 수 있다.