[Calculus] Lagrange Multiplier Method (라그랑주 승수법)

라그랑주 승수법이란?

라그랑주 승수법은 제약이 있는 최적화 문제를 푸는 방법 중 하나로, 모든 제약식에 라그랑주 승수(Lagrange Multiplier) $\lambda$를 곱하고 등식 제약이 있는 문제를 제약이 없는 문제로 바꾸어 문제를 해결하는 방법입니다. 만약, 등식이 아니라 부등식의 제약이 있는 문제라면, KKT(Karush-Kuhn-Tucker) 조건을 만족하는 문제일 때 라그랑주 승수법으로 문제를 해결할 수 있습니다. 예를 들어 $\mathit{f}(x) = x^2 +1$ 을 최소화 하는 문제에서 $g(x) \leq 3$ 이라는 제약조건이 있다면, 제약조건의 형태를 $g(x)-3 \leq 0$ 과 같이 바꿔준 후 라그랑주 승수법(Lagrange Multiplier Method)을 적용하고 KKT 조건 만족을 판정하여 문제 해결 유무를 알아볼 수 있습니다. 주어진 제약조건 하에서 목적함수를 최대화 또는 최소화할 때 사용하는 방법인 라그랑주 승수법은 목적함수와 제약조건은 각각 1차 미분이 가능해야만 합니다.

라그랑주 승수법의 기하학적 해석

라그랑주 승수법의 기본 아이디어는 어떤 조건 $g$를 만족하는 함수 $f$의 최대값 또는 최소값을 찾는 문제에서 찾고자 하는 값이 $f$와 $g$의 접점에 존재할 수도 있다는 가능성에서 출발합니다. 아래의 Fig. 1은 제약조건 $g(x,y) = l$ 를 만족하는 $f(x,y) = x + y$의 최대값을 구하는 문제입니다. $f(x,y)$의 값을 $k$라고 하면, $k$는 기하학적으로 제 1사분면에서 제약조건 $g(x,y) = l$과 $f(x,y)$이 접할 때, $k$가 최대임을 알 수 있습니다.

라그랑주 승수법에서는 두 함수가 접하는 지점을 찾기 위해 구배 벡터(Gradient Vector)를 이용합니다.

Eqn. 1은 $f(x,y)$에 대한 구배 벡터입니다. 어떠한 지점에서의 접선 벡터와 구배 벡터는 수직임으로 두 함수 $f$와 $g$가 접한다면, 두 함수의 구배 벡터가 서로 상수배의 관계를 가지게 됩니다. 이러한 관계를 Eqn. 2로 표현할 수 있습니다. $\lambda$는 라그랑주 상수로 임의의 상수입니다.

이때 $f$와 $g$를 통해 Eqn. 3과 같은 라그랑주 함수(Lagrange Function)을 정의할 수 있습니다.

라그랑주 함수 $\mathit{L}$의 구배 벡터가 영벡터가 되는 조건은 다음과 같습니다.

라그랑주 함수 $\mathit{L}$의 구배 벡터가 영벡터가 되는 점을 찾는 것은, Eqn. 2의 해를 찾는 것과 같기 때문에 라그랑주 함수의 구배 벡터가 영벡터인 지점을 찾음으로서 두 함수 $f$, $g$가 접하는 점을 찾을 수 있습니다. 즉, 라그랑주 함수 $\mathit{L}$을 각 변수들 $x, y, \lambda$로 편미분한 결과인 Gradient가 0이 되는 수식을 정리하면 세 가지 식을 구할 수 있고($\because$ 변수가 2개이고, 제약조건이 하나이므로) 해당 식을 연립하여 제약식을 풀게되면 최적화된 해를 구할 수 있게 됩니다. 또한, 제약조건이 한 개가 아닌 여러개라면, Eqn. 4와 같이 일반화 할 수 있습니다.