Constraint Optimization와 같이 정리하는 KKT condition

제약 최적화 문제를 푸는 방법을 알아본다.

Convex 함수를 가정한다.

Constraint Optimization 문제는 세 가지로 나뉠 수 있다.

 

1) No Constraint

minimize $f(x)$

 

2) Equality Constraint

minimize $f(\bar{x})$
subject to $g(\bar{x}) = 0$

 

3) Inequality Constraint

minimize $f(\bar{x})$
subject to $g(\bar{x}) \leq 0$

 

---

No Constraint

이 경우에서는 함수를 미분해서 0되는 지점을 따져서 최솟값을 구하면 되겠다.

 

Equality Constraint

minimize $f(x_1, x_2) = x_1^2 + x_2^2 - 1$
subject to $g(x_1, x_2) = x_1 + x_2 - 1$ = 0

 

f 함수는 빗살무늬토기 모양이고, g=0에서의 함수는 위에서 보면(2차원 상에서는) 직선이겠다.

 

 

그 중에서 $g(x) = 0$인 부분만 취하면 함수값을 최소화하는 최적점 $(x_1^*, x_2^*)$은 위와 같겠다.

이때 gradient는 함숫값이 증가하는 방향인데 f와 g의 gradient가 평행하다(같은방향이거나 아예 반대 방향).

$$\Rightarrow \bigtriangledown f(x) + \lambda \bigtriangledown g(x) = 0$$

 

 

이는 라그랑즈로 표현할 수 있다.

$$L(x, \lambda) = f(x) + \lambda g(x)$$

 

$\bigtriangledown_x f(x) + \lambda \bigtriangledown_x g(x) = 0$  $\Leftrightarrow$   $\bigtriangledown_x L(x, \lambda) = 0$
                    $g(x) = 0 $                    $\Leftrightarrow$   $\bigtriangledown_\lambda L(x, \lambda) = 0$

 

위 문제를 라그랑즈로 표현하면 

$$L(x, \lambda) = f(x) + \lambda g(x) = x_1^2 + x_2^2 - 1 + \lambda(x_1 + x_2 -1)$$

 

• $\bigtriangledown_{x}L(x, \lambda) = 0$

$\left\{\begin{matrix} {\bigtriangledown_{x1}L(x, \lambda) = 2x_1 + \lambda = 0}\\{\bigtriangledown_{x2}L(x, \lambda) = 2x_2 + \lambda = 0}\end{matrix}\right.$

• $\bigtriangledown_\lambda L(x, \lambda) = x_1 + x_2 - 1 = 0$

 

$(x_1^*, x_2^*) = (0.5, 0.5)$

 

 

 

Inequality Constraint

minimize $f(x_1, x_2) = x_1^2 + x_2^2 - 1$
subject to $g(x_1, x_2) = x_1 + x_2 - 1 \leq 0$

$g(x)$를 면적스럽게 고려해야한다.

 

우선 $g(x)\leq 0$이 아래처럼 그려졌다고 하고 이에 따른 gradient 방향을 살펴보자.

핑크 면쪽으로 갈수록 함숫값이 작아지는 것이다. 즉 경계에서 함숫값이 maximum하겠다.

gradient 방향은 함숫값이 커지는 방향이므로 너무 당연하게 작아지는 방향의 반대 방향을 가리키겠다.

 

그 다음 제약조건문장을 다시 살펴보자.

어떤 convex f 함수를 minimize하는데, 제약조건이 $g(x)\leq0$이다.

그렇다면 우리는 두 가지로 나누어 살펴볼 수 있겠다.

 

1) Global minimum이 내부에 있는 경우 $g(x) <0$와,

2) 외부 내지 경계에 있는 경우 $g(x)\geq  0$로 살펴볼 수 있겠다. 

이때 후자의 경우 global minimum이 경계에 있으면 좋겠지만 이는 희박한 확률이겠다.

그러므로 $g(x)=0$을 위쪽으로 들어올릴 때 접하는 지점이 최적점이 되겠다.

 

 

 

 

1) Constraint is Inactive

최적점이 제약조건 안쪽에 있을 것이다

(global minimum이 제약조건 안쪽으로!!)

 

 

이는 Unconstraint optimization($\lambda = 0$)처럼 제약조건이 없는 것 마냥 풀면 된다.

 

$$L(x, \lambda) = f(x) + \lambda g(x)$$

$\bigtriangledown_{x}L(x, \lambda) = 0$에서 $\lambda = 0$이 적용되어

$$\bigtriangledown_x f(x) = 0$$

just minimize 빗살무늬토기

(미분하여 0되는 지점을 찾으면 되겠다)

 

2) Constraint is Active

최적점이 제약조건 $g(x)=0$ 경계에 있을 것이다

(global minimum이 제약조건 경계와 바깥 쪽으로!!) 

 

 

Equality의 경우에서는 최적점이 경계에 있을 시 f와 g의 gradient 방향이 아주 같거나, 아주 반대였다(합쳐서 parallel).

 

그러나 이 경우에서는 방향이 무조건 반대이다.

왜냐? $g(x)$의 gradient 방향이 면적 바깥쪽을 무조건적으로 향하고,

$f(x)$의 gradient 방향이 면적 안쪽을 무조건적으로 향하기 때문이다.

 

Active인 경우를 어떻게 가정하고 시작했는지를 생각하면 쉽게 이해 가능하다.

 

 

$$L(x, \lambda) = f(x) + \lambda g(x)$$

$\bigtriangledown_{x}L(x, \lambda) = 0$이 적용되는데 $\lambda > 0$이 적용되어

 

For some $\lambda > 0$

$$\bigtriangledown_x f(x) + \lambda\bigtriangledown_x g(x) = 0$$ 

 

 

 

---

Karush-Kuhn-Tucker(KKT) Condition

 

이제야 좀 KKT Condition에 대해서 논할 수 있겠다.

 

어떠한 제약조건 상황에서 힘숫값을 최소화하는 값을 찾는 것이다.

 

모두 공통적으로 라그랑즈 식을 다음처럼 세울 수 있고

$$L(x, \lambda) = f(x) + \lambda g(x)$$

 

또한 공통적으로 그라디언트 방향을 가지고 논하였다.

이를 한꺼번에 쓴 것 뿐이다.

 

$L(x, \lambda) = f(x) + \lambda g(x)$

$\bigtriangledown_x L(x, \lambda) = 0$

• $g(x^*)\leq 0$
• $\lambda \geq 0$
• $\lambda g(x^*) = 0$

 

위 세 개에 대하여 더 명료하게 표현하자면,

• ​$\lambda > 0 \Rightarrow​ g(x^*) = 0 \Rightarrow \bigtriangledown_\lambda L(x, \lambda) = 0$ (active)
• $g(x^*) < 0 \Rightarrow \lambda = 0$ (inactive) 

제약최적화문제	제약조건		풀이법
Unconstraint	NONE		$\bigtriangledown_x f(x) = 0$
equality	$g(x) = 0$		$\bigtriangledown_x L(x, \lambda) = 0$, $\bigtriangledown_\lambda L(x, \lambda) = 0$
inequality의 active	$g(x) \leq 0$	$g(x) = 0$	$\bigtriangledown_x L(x, \lambda) = 0$, $\lambda > 0$
inequality의 inactive		$g(x) < 0$	$\bigtriangledown_x L(x, \lambda) = 0$, $\lambda = 0$ $\Rightarrow\bigtriangledown_x f(x) = 0$

 

 

 

이 KKT Condition은 향후 SVM과 관련있다.