카루시-쿤-터커 조건

3. KKT 조건 (필요 조건)

카루시-쿤-터커(KKT) 조건은 최적화 문제에서 국소 최적해(최소화 또는 최대화 문제)가 만족해야 하는 필요 조건이다. 라그랑주 승수법을 일반화하여 부등식 제약 조건을 다룰 수 있도록 확장한 것이다.

만약 $x^*$가 국소 최적해이고, 최적화 문제가 특정 정규성 조건을 만족한다면, 다음과 같은 네 가지 조건을 만족하는 KKT 승수 $\backslash mu\_i\backslash \; (i\; =\; 1,\backslash ldots,m)$ 및 $\backslash lambda\_j\backslash \; (j\; =\; 1,\backslash ldots,\backslash ell)$가 존재한다.^[8]

• 정류성(Stationarity):
• $f(x)$를 최소화하는 경우: $\backslash partial\; f(x^*)\; +\; \backslash sum\_\{j=1\}^\backslash ell\; \backslash lambda\_j\; \backslash partial\; h\_j(x^*)\; +\; \backslash sum\_\{i=1\}^m\; \backslash mu\_i\; \backslash partial\; g\_i(x^*)\; \backslash ni\; \backslash mathbf\; 0$
• $f(x)$를 최대화하는 경우: $-\backslash partial\; f(x^*)\; +\; \backslash sum\_\{j=1\}^\backslash ell\; \backslash lambda\_j\; \backslash partial\; h\_j(x^*)\; +\; \backslash sum\_\{i=1\}^m\; \backslash mu\_i\; \backslash partial\; g\_i(x^*)\; \backslash ni\; \backslash mathbf\; 0$

• 주 문제의 실행 가능 조건(Primal feasibility):
• $h\_j(x^*)\; =\; 0,\; \backslash text\{\; for\; \}\; j\; =\; 1,\; \backslash ldots,\; \backslash ell\; \backslash ,\backslash !$
• $g\_i(x^*)\; \backslash le\; 0,\; \backslash text\{\; for\; \}\; i\; =\; 1,\; \backslash ldots,\; m$

• 쌍대 문제의 실행 가능 조건(Dual feasibility):
• $\backslash mu\_i\; \backslash ge\; 0,\; \backslash text\{\; for\; \}\; i\; =\; 1,\; \backslash ldots,\; m$

• 상보적 완화 조건(Complementary slackness):
• $\backslash sum\_\{i=1\}^m\; \backslash mu\_i\; g\_i\; (x^*)\; =\; 0.$

• $m=0$인 경우(부등식 제약 조건이 없는 경우), KKT 조건은 라그랑주 조건과 동일하며, KKT 승수는 라그랑주 승수라고 불린다.
• 제약 조건이 특정 조건을 만족하지 않는 경우, KKT 조건을 만족하는 해가 반드시 최적해가 아닐 수 있다.

3. 1. 행렬 표현

• '''정류성(Stationarity)'''
• $f(x)$를 최대화하는 경우: $\backslash partial\; f(x^*)\; -\; D\; \backslash mathbf\; g(x^*)^\{\backslash top\}\; \backslash boldsymbol\{\backslash mu\}\; -\; D\; \backslash mathbf\; h(x^*)^\{\backslash top\}\; \backslash boldsymbol\{\backslash lambda\}\; =\; \backslash mathbf\; 0$
• $f(x)$를 최소화하는 경우: $\backslash partial\; f(x^*)\; +\; D\; \backslash mathbf\; g(x^*)^\{\backslash top\}\; \backslash boldsymbol\{\backslash mu\}\; +\; D\; \backslash mathbf\; h(x^*)^\{\backslash top\}\; \backslash boldsymbol\{\backslash lambda\}\; =\; \backslash mathbf\; 0$

• '''주 문제의 실행 가능 조건(Primal feasibility)'''
• $\backslash mathbf\; g(x^*)\; \backslash le\; \backslash mathbf\; 0$
• $\backslash mathbf\; h(x^*)\; =\; \backslash mathbf\; 0$

• '''쌍대 문제의 실행 가능 조건(Dual feasibility)'''
• $\backslash boldsymbol\; \backslash mu\; \backslash ge\; \backslash mathbf\; 0$

• '''상보적 완비성(Complementary slackness)'''
• $\backslash boldsymbol\; \backslash mu^\{\backslash top\}\; \backslash mathbf\; g\; (x^*)\; =\; 0.$

4. 정규성 조건 (제약 조건)

KKT 조건이 국소 최적해의 필요조건이 되기 위해서는 몇 가지 정규성 조건(constraint qualification)을 만족해야 한다. 이러한 조건들은 최적화 문제의 제약 조건이 특정 성질을 만족하도록 보장한다. 주요 정규성 조건은 다음과 같다.

위 조건들 간의 관계는 다음과 같다.

• LICQ ⇒ MFCQ ⇒ CPLD ⇒ QNCQ
• LICQ ⇒ CRCQ ⇒ CPLD ⇒ QNCQ

5. 충분 조건

Karush–Kuhn–Tucker^영어 조건 (KKT 조건)이 최적해에 대한 충분 조건이 되는 경우는 다음과 같다.

목적 함수 $f$와 부등식 제약 조건 $g\_j$가 볼록 함수이고, 등식 제약 조건 $h\_i$가 아핀 함수이며, 슬레이터 조건이 성립하는 최대화 문제의 경우, KKT 조건 (필요 조건)은 최적성에 대한 충분 조건이 된다.^[11] 최소화 문제의 경우, 목적 함수 $f$가 볼록 함수이면 KKT 조건은 최적성에 대한 충분 조건이 된다.

일반적으로 KKT 조건은 최적성에 대한 충분 조건이 아니며, 이차 충분 조건 (SOSC)과 같은 추가 정보가 필요하다. 매끄러운 함수의 경우 SOSC에는 2차 도함수가 포함되며, 이 때문에 이름이 붙여졌다.

KKT 조건이 전역적 최적성을 보장하는 더 넓은 함수 집합은 1985년 Martin에 의해 Type 1 '''인벡스 함수'''로 밝혀졌다.^[12][13]

매끄러운 비선형 최적화 문제에 대한 2차 충분 조건은 다음과 같다.

다음 라그랑지안

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

에 대해, 다음이 성립하면 위 절에서 찾은 해 $x^*,\; \backslash lambda^*,\; \backslash mu^*$는 제약 조건이 있는 국소 최소값이다.

:$s^T\backslash nabla\; ^2\_\{xx\}L(x^*,\backslash lambda^*,\backslash mu^*)s\; \backslash ge\; 0$

여기서 $s\; \backslash ne\; 0$는 다음을 만족하는 벡터이다.

:$\backslash left[\; \backslash nabla\_x\; g\_i(x^*),\; \backslash nabla\_x\; h\_j(x^*)\; \backslash right]^T\; s\; =\; 0\_\{\backslash mathbb\{R\}^\{2\}\}$

여기서 엄격한 상보성(즉, $\backslash mu\_i\; >\; 0$)에 해당하는 활성 부등식 제약 $g\_i(x)$만 적용된다. 부등식이 엄격한 경우 해는 엄격한 제약 조건이 있는 국소 최소값이다.

6. 경제학에서의 응용

수리 경제학에서 카루시-쿤-터커(KKT) 접근 방식은 질적 결과를 얻기 위해 이론적 모델에 자주 사용된다.^[14] 예를 들어, 최소 이윤 제약 조건 하에 매출을 극대화하는 기업을 생각해 보자.

• `Q`: 생산량 (선택 대상)
• `R(Q)`: 매출 (양의 1차 도함수를 가지며, 생산량이 0일 때 매출도 0)
• `C(Q)`: 생산 비용 (양의 1차 도함수를 가지며, 생산량이 0일 때 비용은 0 이상)
• `G_{\min}`: 이윤의 최소 허용 수준 (양수)
• 수익 함수가 결국 비용 함수보다 덜 가파르게 증가

7. 일반화

프리츠 존 조건은 KKT 조건의 일반화된 형태이다. 이 조건은 추가 곱셈자 $\backslash mu\_0\backslash geq0$를 사용하여 $\backslash nabla\; f(x^*)$ 앞에 위치시키며, KKT 정류성 조건을 다음과 같이 변경한다.

:$$

\begin{align}

& \mu_0 \,\nabla f(x^*) + \sum_{i=1}^m \mu_i \,\nabla g_i(x^*) + \sum_{j=1}^\ell \lambda_j \,\nabla h_j(x^*) = 0, \\[4pt]

& \mu_ig_i(x^*)=0, \quad i=1,\dots,m,

\end{align}



이때 $(\backslash mu\_0,\backslash mu,\backslash lambda)\backslash neq0$이다. 이 최적성 조건은 제약 조건 없이 유지되며, "KKT 또는 (not-MFCQ)"와 동등하다.

또한, KKT 조건은 서브미분을 사용하여 비-매끄러운 함수를 허용하는 더 넓은 클래스의 1차 필요 조건(FONC)에 속한다.^[8]

참조

_[1] 서적 Optimal Control by Mathematical Programming Prentice-Hall
_[2] 간행물 Nonlinear programming http://projecteuclid[...] University of California Press
_[3] 학위논문 Minima of Functions of Several Variables with Inequalities as Side Constraints http://pi.lib.uchica[...] Dept. of Mathematics, Univ. of Chicago, Chicago, Illinois
_[4] 논문 A contextualized historical analysis of the Kuhn-Tucker theorem in nonlinear programming: the impact of World War II
_[5] 서적 Methods of Optimization John Wiley & Sons
_[6] 서적 Introduction to Mathematical Economics https://archive.org/[...] Springer
_[7] 서적 Convex Optimization Cambridge University Press
_[8] 서적 Nonlinear Optimization Princeton University Press
_[9] 웹사이트 Karush-Kuhn-Tucker conditions, Optimization 10-725 / 36-725 http://www.cs.cmu.ed[...] 2022-06-17
_[10] 서적 Nonlinear Programming Athena Scientific
_[11] 서적 Convex Optimization Cambridge University Press
_[12] 논문 The Essence of Invexity
_[13] 논문 Invexity and the Kuhn-Tucker Theorem
_[14] 서적 Fundamental Methods of Mathematical Economics