라그랑주 승수법, KKT 조건 (Karush-Kuhn-Tucker)

제한조건이 있는 최적화 문제는 연립 방정식과 연립 부등식의 풀이 방법이 다르다.

연립 방정식은 라그랑주 승수법으로, 연립 부등식은 라그랑주 승수법에 KKT 조건을 만족하도록 푸는데 풀이가 거의 비슷하다.

 

라그랑주 승수법

원리는 두 가지 조건을 동시에 만족시키는 공통 접선을 찾는다. 즉, 제약 조건을 만족하며 최솟값, 최댓값을 찾는 것이다.

라그랑주 승수법은 목적함수 $f(x)$와 제약조건 $g(x)$가 있을 때, 하나의 식으로 만든다. 따라서, 제약조건이 달려있는 목적함수의 경우 라그랑주 승수법을 이용해 식을 간단하게 전개할 때도 사용한다.

 

공식

$h(x, \lambda) = f(x) + \sum_{j=1}^M\lambda_j g_j(x)$

예시

$f(x_1, x_2) = x_1^2 + x_2^2$를 최소화하며, 
$g(x_1, x_2) = x_1 + x_2 - 1 = 0$ 제약조건을 만족해야 할 때 $h(x_1, x_2, \lambda)  = f(x_1, x_2) + \lambda g(x_1, x_2)  = x_1^2 + x_2^2 + \lambda ( x_1 + x_2 - 1 )$로 식을 전개할 수 있다.

최저점을 구하기 위해선 위의 식에서 각 변수에 대해 편미분을 진행하면 된다.
$\dfrac{\partial h}{\partial x_1}  = 2{x_1} + \lambda = 0 \\ \dfrac{\partial h}{\partial x_2}  = 2{x_2} + \lambda = 0 \\ \dfrac{\partial h}{\partial \lambda}  = x_1 + x_2 - 1 = 0$

위의 해를 풀면
$x_1 = x_2 = \dfrac{1}{2}, \;\;\; \lambda = -1$
최소점을 찾을 수 있다.

최소점을 찾는 것이 목표기 때문에 라그랑주 승수값은 필요 없다.

KKT 조건

연립 부등식인 경우 라그랑주 승수법을 그대로 사용해주면 된다. 하지만, 연립 방정식과는 다르게 KKT 조건이 붙는다.

- 모든 변수 $x_1,...,x_n$에 대한 미분 값이 0이다.

- 모든 라그랑주 승수 값과 제한조건 부등식(라그랑주 승수 값에 대한 미분 값)의 곱이 0이다.

- 라그랑주 승수는 음수가 아니어야 한다.

 

맨 첫 번째 조건은 라그랑주 승수의 조건에도 포함되어있다. 최소점을 찾기 위해 미분 값이 0이 되는 지점을 찾기 때문이다. 

두 번째 조건은 라그랑주 승수에 대한 미분 값이 0이거나, 라그랑주 승수가 0이 되어도 된다.

 

세 가지의 조건이 모두 만족하지 않으면, 나온 값이 결국 정답이라고 할 수 없다.

즉, 최소점일 수는 있으나 제약조건에 만족하지 못한다는 문제가 생긴다. 이 문제에 대해서는 아래의 문제 풀이 링크를 참조하면 될 것이다.

 

 

라그랑주 승수 법과 KKT 조건의 문제 풀이는 다음 영상을 참고하라.