[KKT 조건 - 1] 등식과 부등식 제약조건이 있는 최적화 문제

제약조건이 없는 일반적인 최적화 문제는 다음과 같다.

 

$$p^{\star }=\underset{\mathbf{x}}{min}f(\mathbf{x})$$

 

여기서 $\mathbf{x}$는 최적화 변수이고, $f(\mathbf{x})$는 목적함수(objective function)이다. ${\mathbf{x}}^{\star }$가 로컬(local) 최소점이 되기 위한 필요조건(necessary condition)은 $\mathbf{x}={\mathbf{x}}^{\star }$에서 $f$의 그래디언트(gradient)가 $0$이 되는 것이다.

 

$${\mathrm{\nabla }}_{\mathbf{x}}f({\mathbf{x}}^{\star })=0$$

 

 

 

등식 제약조건이 있는 일반적인 최적화 문제는 다음과 같다.

 

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

 

여기서 $h_j(\mathbf{x})$는 등식 제약함수(equality constraint function)이다. 제약함수는 편의상 다음과 같이 벡터 형태로 표현하기도 한다.

 

$$\mathbf{h}(\mathbf{x})=\left[\begin{array}{c}{h}_1(\mathbf{x})\\ ⋮\\ h_k(\mathbf{x})\end{array}\right]=0$$

 

여기서 부등식과 등식은 벡터 함수 $\mathbf{h}(\mathbf{x})$의 성분별로 적용된다.

라그랑지 곱수법을 이용하면 등식 제약조건이 있는 최적화 문제를 다음과같이 제약조건이 없는 최적화 문제로 바꿀 수 있다.

 

$$\begin{array}{rl}{p}^{\star }& =\underset{\mathbf{x},{\lambda }_1,...,{\lambda }_k}{min}L(\mathbf{x},{\lambda }_1,{\lambda }_2,...,{\lambda }_k)\\ \\ & =\underset{\mathbf{x},\lambda }{min}L(\mathbf{x},\lambda )\end{array}$$

 

여기서 $\lambda ={\left[\begin{array}{ccc}{\lambda }_1& ...& {\lambda }_k\end{array}\right]}^T$를 라그랑지 곱수(Lagrange multiplier)라고 한다. $L$은 라그랑지안(Lagrangian)이라고 하며 다음과 같이 정의한다.

 

$$\begin{array}{rl}L(\mathbf{x},\lambda )& =f(\mathbf{x})+\sum _{j=1}^k{\lambda }_j{h}_j(\mathbf{x})\\ \\ & =f(\mathbf{x})+{\lambda }^T\mathbf{h}(\mathbf{x})\end{array}$$

 

함수 $f(\mathbf{x})$가 ${\mathbf{x}}^{\star }$에서 로컬 최소값이 되기 위한 필요조건은 $\mathbf{x}={\mathbf{x}}^{\star }$와 $\lambda ={\lambda }^{\star }$에서 $L$의 그래디언트(gradient)가 $0$이 되는 것이다.

 

$$\begin{array}{rl}& {\mathrm{\nabla }}_{\mathbf{x}}L({\mathbf{x}}^{\star },{\lambda }^{\star })=0\\ \\ & {\mathrm{\nabla }}_{\lambda }L({\mathbf{x}}^{\star },{\lambda }^{\star })=0\text{(or }{h}_j({\mathbf{x}}^{\star })=0,j=1,...,k\text{)}\end{array}$$

 

 

 

등식과 부등식 제약조건이 있는 일반적인 최적화 문제는 다음과 같다.

 

$$\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}$$

 

여기서 $g_i(\mathbf{x})$를 부등식 제약함수(inequality constraint function), $h_j(\mathbf{x})$를 등식 제약함수라고 한다. 부등식, 등식 제약함수는 편의상 다음과 같이 벡터 형태로 표현하기도 한다.

 

$$\begin{array}{rl}& \mathbf{g}(\mathbf{x})=\left[\begin{array}{c}{g}_1(\mathbf{x})\\ ⋮\\ g_m(\mathbf{x})\end{array}\right]\le 0\\ \\ & \mathbf{h}(\mathbf{x})=\left[\begin{array}{c}{h}_1(\mathbf{x})\\ ⋮\\ h_k(\mathbf{x})\end{array}\right]=0\end{array}$$

 

여기서 부등식과 등식은 벡터 함수 $\mathbf{g}(\mathbf{x}),\mathbf{h}(\mathbf{x})$의 성분별로 적용된다.

 

 

만약 제약조건을 만족하는 $\mathbf{x}$값이 존재하지 않는다면 최적화 문제는 실행 불가능(infeasible)이라고 하는데, 그 때의 최소값은 $p^{\star }=\mathrm{\infty }$가 된다.

부등식 제약조건이 있는 경우 등식 제약조건만 있을 때와 비슷한 방법으로 라그랑지 곱수를 도입하여 다음과 같이 라그랑지안 함수를 만들 수 있다.

 

$$\begin{array}{rl}L(\mathbf{x},\mu ,\lambda )& =f(\mathbf{x})+\sum _{j=1}^m{\mu }_j{g}_j(\mathbf{x})+\sum _{j=1}^k{\lambda }_j{h}_j(\mathbf{x})\\ \\ & =f(\mathbf{x})+{\mu }^T\mathbf{g}(\mathbf{x})+{\lambda }^T\mathbf{h}(\mathbf{x})\end{array}$$

 

등식 제약조건만 있을 때는 최적화 변수 $\mathbf{x}$와 라그랑지 곱수에 대해서 라그랑지안의 그래디언트를 계산했지만 부등식 제약조건이 포함되면 이를 고려한 추가적인 수식이 더 필요한데, 이를 KKT(Karush-Kuhn-Tucker) 조건이라고 한다.

KKT 조건은 선형 및 비선형 최적화 문제에서 최적해를 구하기 위한 핵심적인 조건이다.

KKT 조건은

          1. 선형 프로그래밍(LP, linear programming)문제에서는 최적화의 필요충분조건이다.

          2. 컨벡스(볼록, convex) 최적화 문제에서는 최적화의 필요충분조건이다.

          3. 비컨벡스(non-convex) 최적화 문제에서는 최적화의 필요조건이다.

여기서 비컨벡스 최적화 문제는 딥러닝 모델의 학습에서 일반적으로 나타나는 최적화 문제다.