[Math] Karush-Kuhn-Tucker Conditions (KKT Conditions)

KKT Conditions

KKT조건은

inequality constraints을 가지는 constrained optimization problem의

optimal solution이 만족해야하는 necessary condition들의 집합(4개의 necessary conditions)임.

Lagransian multiplier (or dual variable)를 도입하여
equality constraints를 가지는 contrained optimization problem을
unconstrained optimization으로 바꾸어 푸는 방식 (=Lagrange Method) 에서의
necessary condition을
inequality contraints를 가지는 경우로 확장 한 것임.

 

necessary condition 이기 때문에, KKT 조건을 만족한다고 반드시 optimal solution이 되는 것은 아니다.

• 최소한, KKT 조건을 만족하지 않는 경우는 절대로 optimal solution이 아님.
• 하지만, Strong duality의 경우 sufficient and necessary condition이 되기 때문에,
• 실제로 optimal solution을 구할 때 많이 사용된다.

KKT conditions은 LP보다 QP (=non-linear object function, Convex Optimization의 한 종류)에서 optimal solution을 구하는데 주로 사용됨.

또한 KKT conditions를 적용하려면 해당 $\textbf{x}$가 regular point여야 한다.
만얀 regular point가 아닌 경우, 즉 문제가 regularity condition을 만족 못 시키는 경우, solution으로 구해지는 Lagrange Muliplier들이 유일하게 결정되지 않는다.

때문에 KKT conditions를 만족하지 않는 regular point $\textbf{x}$는 local minimum solution이 아니지만,
만약 irregular point라면 이를 보장하지 못하게 된다 (irregular point에서는 KKT 를 만족하지않더라도 최솟값을 가질수 있음). 

---

Regular points란 :2023.07.07 - [.../Math] - [Math] A regular point of the feasible set.

[Math] A regular point of the feasible set.

---

necessary condition과 sufficient condition : 2022.05.19 - [.../Math] - [Math] 필요조건, 충분조건, 필요충분조건

[Math] 필요조건, 충분조건, 필요충분조건

---

KKT conditions : 4개의 필요조건들

KKT condition은 4가지 조건으로 구성된다. 수식으로 살펴보면 다음과 같음.

 

다음과 같은 optimization problem이 있다고 하자.

 

$$\begin{aligned}&p=\text{min }f(\textbf{x})\\
& \text{s.t.}\\ & g_i(\textbf{x}) \le 0, i=1,\dots,m \\ & h_j(\textbf{x})=0,j=1,\dots,k\end{aligned}$$

 

위 문제에 대한 Karush-Kuhn-Tucker Condition은 다음과 같음.

1. Stationarity Condition

solution $\textbf{x}^*$는 다음을 만족함.

• $\textbf{x}^*$ 에서의 Lagrangian의 gradient가 $\textbf{0}$이어야 함
  • (=$\textbf{x}^*$는 stationary point여야함).
• 달리 애기하면 다음과 같음.

$$\nabla f(\textbf{x}^*)+\sum_{i=1}^m\alpha_i\nabla g_i(\textbf{x}^*)+\sum_{j=1}^k \mu_j \nabla  h_j (\textbf{x}^*)=\textbf{0}$$

---

2. Primal Feasibility Condition

Optimal Solution 은 primal 문제의 모든 constraint를 만족하는 the feasible region에 있어야 함.

간단히 말하면, $\textbf{x}^*$는 feasible이어야 함.

• $g_i(\textbf{x}^*) \le 0, i=1,\dots,m \\ h_j(\textbf{x}^*)=0,j=1,\dots,k$

equality와 inequality를 따로따로 condition으로 취하는 경우 KKT는 5가지조건으로 표기됨. 5가지로 표기하는 경우도 종종 있음.

---

3. Dual Feasibility Condition

inequality conditions에 대한 dual variable (=Lagrangian Multiplier)들이 0 이상 (non-negative) 이어야 함.

• $\alpha_{(i)} \ge 0 \quad \text{ for } \forall i $

참고로 Dual variable은 constraint에 대한 sensitivity에 해당함.

Dual feasibility와 Stationarity 에 의해
$\sum_{i=1}^m \nabla g(\textbf{x}^*)$와 $\nabla f(\textbf}(\textbf{x})$는
평행하면서 서로 반대방향이어야 함을 의미함.
같은 방향이면, inequality를 보다 작게하면서 objective function을 작게할 수 있기 때문임.

---

4. Complementary Slackness Condition

각 inequality constraints와 해당하는 dual variable(or lagrangian multiplier)의 곱이 모두 0이 되어야 한다는 조건.

• $ \alpha_i \cdot g_j(\textbf{x}^*)=0 \quad \text{ for }\forall i$

The constraint is not active ( active = binding 용어 기억),
its dual variable must be zero.
The dual variable is positive, the corresponding constraint must be active.

inequality constraint 가 0이 되는 경우를 active 또는 binding이라고 부름.
not active인 경우엔 대응하는 dual variable이 0이어야 함.

 

Strong duality에서 KKT condition 를 만족하는 경우, primal과 dual의 각 optimal solution이 같아지게 되어 primal problem을 dual로 풀 수 있게 됨. (dual의 최대값이 primal의 최소값과 같아지고 이들에 해당하는 solution이 일치하게 됨.)

---

KKT Necessary Optimality Conditions

$\textbf{x}^*$가 local minimum 일 경우,

다음을 만족하는 Lagrangian mulitplier $\alpha_i \ge 0 \forall i$ 와 $\mu_j \forall j$가 존재한다.

$$\nabla f(\textbf{x}^*)+\sum_{i=1}^m\alpha_i\nabla g_i(\textbf{x}^*)+\sum_{j=1}^k \mu_j \nabla  h_j (\textbf{x}^*)=\textbf{0}$$

 

이는, 앞서 애기한대로 KKT conditions는 necessary condition임을 말해준다. 

위에서 optimal solution이라고 했지만, 사실은 local minimum임 (convex 인 경우엔 global minimum 즉 optimal solution이 되지만, convex등이 아닌 경우엔 엄밀히 애기해서 local minimum이라고 해야함.)

 

때문에 다음과 같이 말할 수 있음.

 

KKT Condition은
non-linear constrained optimization problem (비선형 제약 최적화 문제)에서
local optimal solution(국소 최적해)를 찾기 위한 necessary condition임.

---

KKT Sufficient Optimality Conditions

$f(\textbf{x})$가 convex이고,
모든 inequality constraints $g_i(\textbf{x})$ 들이 continuously differentiable convex이고
모든 equality constraints $h_j$가 affine function (= linear function에 constant term을 더한 것)인 경우,

feasible KKT point는 optimal solution이 됨.

 

이를 통해 Linear programming과 Quadratic programming에서는 KKT조건이 필요충분조건이 된다. 

참고로, LP와 QP에서는 KKT를 만족시 optimal solution임.