[인공지능] 6. Karush-Kuhn-Tucker(KKT) Approach

KKT Approach

 

저번 게시물에서 다루었던 'Continuous State Problem'에 대해 떠올려봅시다. f(x) 를 최소화하는데 이때 g(x) = 0 이고 h(x) <= 0 을 만족시켜야 하는 걸 'constrained optimization problem' 라고 하였죠. 하지만 이를 어기고 페널티를 받아서 함수를 unconstrained optimization problem 으로 바뀔 수 있었습니다. 페널티 함수인 'Generalized Lagrange Function(라그랑)' (= generalized Lagrangian)을 사용하면 됩니다.  이 함수는 아래 그림과 같습니다. 

라그랑 함수 

보면 새로운 변수, 람다와 알파를 추가해서 새로운 함수를 만든 것을 볼 수 있죠. 이 둘을 Lagrange multipliers(or KKT multipliers) 라고 합니다. 

 

즉 generalized Lagrangian 은 당연히 x 에 대해서 최소화가 되어야하고 알파와 람다에 대해서는 최소화를 해야합니다. 그게 Constraint 를 지키는 즉, 제한 조건을 어겼을 때 페널티를 최대한 많이 줄려고 하기 때문이죠. 아래 식이 기존에 문제를 재정의 한 것입니다. 식이 어려워 보이지만 별거 없습니다. 저희가 위에서 이야기 했던 것과 동일하죠.

 

'x 는 최소화, 람다와 알파는 최대화' 입니다.

 

여기서 F 는 feasible region 입니다. Constraint 가 없는 거처럼 여겨지기 때문이죠.

여기서 left side와 right side 이 두 개의 문제가 같은 optimal points , x* 를 가지게 됩니다. 어떻게 이렇게 될까요? 

 

 이를 만족하면 1,2 번이 성립이 되겠죠. 이렇게 되면 L 함수는 다 떨어져나가고 f(x*) 만이 남게 될 것입니다. 반대로 제한을 어겼을 때는 무한대 값으로 주어지고 이러면 어떠한 infeasible point 도 최적화의 답이 될 수 없습니다. 이렇게 랑그랑 함수를 최적화 시키는 것이 같은 해를 구하는 것임을 알 수 있습니다. 또 랑그랑 함수에서 min, max 하는 순서를 변경할 수 있습니다. 아래를 보면 즉 min x 하는 랑그랑 함수를 dual function 이라고 불리는 Ld 

이렇게 하면 기존의 constrained optimization problem에 대해 해결을 할 수가 있습니다. 즉 x 를 찾는 대신 람다와 알파를 만족시키는 겁니다. 

 

 

x*가 optimal solution 일때 hj(x) = 0 때에는 active 이야기할 수 있습니다.

해는 당연히 inequality 에 바운더리 안에 존재를 할 것 입니다. 또 알파는 양수일 겁니다. 

 

 

 

Generalized Lagrange Function 예시

 

 

간단한 예를 확인해봅시다. 다음 문제를 풀어봅시다. 

매우 직관적인 그래프가 나올 겁니다. 

직관적으로도 확인할 수 있짐나 랑그랑 함수를 정의해봅시다. 

그리고 x 에 관해서 minimize 해야합니다. 

일단 x1에 대해 미분을 해보면 다음과 같이 나옵니다. x1 이 람다라는 것을 알 수 있겠죠.

동일하게 x2에 대해서도 미분을 하면 x2 = 람다 + 알파 라는 것을 알 수 있습니다. 결론적으로는 아래와 같은 dual function 이 나오게 됩니다. 

이제 이 함수에 대해서 람다와 알파를 maximize 하면 되는겁니다. 

그러기 위해서는 람다에 관해서, 알파에 관해서 미분을 해줍니다.

결과적으로 x가 다 람다로 표현되는 것을 볼 수 있으니 x값들을 구할 수가 있겠죠. 

x1 = 람다 = 1/4

x2 = 알파 + 람다 = 3/4

입니다.