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

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

 

\[ p^\star= \min_{\mathbf{x}}⁡ f(\mathbf{x}) \]

 

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

 

\[ \nabla_{\mathbf{x}} f(\mathbf{x}^\star )=0 \]

 

 

 

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

 

\[ \begin{align} & p^\star = \min_{\mathbf{x}}⁡ f(\mathbf{x}) \\ \\ \mbox{subject to } \ \ & h_j (\mathbf{x}) = 0, \ \ j=1, ... ,k \end{align} \]

 

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

 

\[ \mathbf{h}(\mathbf{x}) = \begin{bmatrix} h_1 (\mathbf{x}) \\ \vdots \\ h_k (\mathbf{x}) \end{bmatrix} = 0 \]

 

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

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

 

\[ \begin{align} p^\star &= \min_{\mathbf{x}, \lambda_1, ..., \lambda_k} ⁡L(\mathbf{x}, \lambda_1, \lambda_2, ..., \lambda_k ) \\ \\ &= \min_{\mathbf{x}, \mathbf{\lambda}} ⁡L(\mathbf{x}, \mathbf{\lambda}) \end{align} \]

 

여기서 \(\mathbf{\lambda} = \begin{bmatrix} \lambda_1 & ... & \lambda_k \end{bmatrix}^T\)를 라그랑지 곱수(Lagrange multiplier)라고 한다. \(L\)은 라그랑지안(Lagrangian)이라고 하며 다음과 같이 정의한다.

 

\[ \begin{align} L(\mathbf{x}, \mathbf{\lambda}) &= f(\mathbf{x}) + \sum_{j=1}^k \lambda_j h_j (\mathbf{x}) \\ \\ &= f(\mathbf{x}) + \mathbf{\lambda}^T \mathbf{h}(\mathbf{x}) \end{align} \]

 

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

 

\[ \begin{align} & \nabla_\mathbf{x} L(\mathbf{x}^\star, \mathbf{\lambda}^\star )=0 \\ \\ & \nabla_\mathbf{\lambda} L(\mathbf{x}^\star, \mathbf{\lambda}^\star )=0 \ \mbox{(or } h_j (\mathbf{x}^\star) =0, \ j=1,...,k \mbox{)}\end{align} \]

 

 

 

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

 

\[ \begin{align} & p^\star = \min_{\mathbf{x}}⁡ f(\mathbf{x}) \\ \\ \mbox{subject to } \ \ & g_i (\mathbf{x}) \le 0, \ \ i=1, ... ,m \\ \\ \ \ & h_j (\mathbf{x}) = 0, \ \ j=1, ... ,k \\ \\ \end{align} \]

 

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

 

\[ \begin{align} & \mathbf{g}(\mathbf{x}) = \begin{bmatrix} g_1 (\mathbf{x}) \\ \vdots \\ g_m (\mathbf{x}) \end{bmatrix} \le 0 \\ \\ & \mathbf{h}(\mathbf{x}) = \begin{bmatrix} h_1 (\mathbf{x}) \\ \vdots \\ h_k (\mathbf{x}) \end{bmatrix} = 0 \end{align} \]

 

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

 

 

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

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

 

\[ \begin{align} L(\mathbf{x}, \mathbf{\mu}, \mathbf{\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}) + \mathbf{\mu}^T \mathbf{g}(\mathbf{x}) + \mathbf{\lambda}^T \mathbf{h}(\mathbf{x}) \end{align} \]

 

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

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

KKT 조건은

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

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

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

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