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

1. 역사

라그랑주 승수법은 18세기 프랑스 수학자 조제프루이 라그랑주(Joseph-Louis Lagrange)가 처음 고안한 방법이다. 제약 조건이 있는 최적화 문제를 다룰 수 있어서 고전역학, 경제학, 기계학습 등 다양한 분야에서 사용되고 있다.

2. 수학적 정의와 유도

라그랑주 승수법은 다음과 같은 최적화 문제를 풀기 위해 사용된다.

"함수 $f(x, y, \dots)$ 를 최대 또는 최소화하되, 제약 조건 $g(x, y, \dots) = 0$ 을 만족해야 한다."

이를 위해 새로운 함수 $\mathcal{L}(x, y, \dots, \lambda)$ 를 정의한다.

여기서 $\lambda$ 는 라그랑주 승수라고 부른다. 이제 극값을 구하려면 다음 조건을 만족하는 지점을 찾아야 한다. 이를 연립 방정식으로 풀기 위해 라그랑주안 $\mathcal{L}$을 정의해서 푼다.

즉, 아래가 성립한다.

3. 기하학적 해석

기하학적으로 보면, 제약 조건 $g(x, y) = 0$ 이 표현하는 곡선이나 곡면 위에서 $f(x, y)$ 가 극값을 가지려면
함수 $f$ 의 등고선과 제약 조건의 곡선이 접해야 한다. 이 말은 두 벡터 $\nabla f$ 와 $\nabla g$ 가 같은 방향이라는 뜻이다. 즉,

두 그래디언트 벡터가 선형 종속일 때 극값이 발생한다. 이는 결국 등고선이 제약 조건에 "스칠 때" 최적화가 이루어진다는 의미다.

4. 전미분을 이용한 해석

조금 더 미분적인 관점에서 해석해보면 다음과 같다. 제약 조건 $g(x, y) = 0$ 을 만족하면서 $f(x, y)$ 를 극대화 또는 극소화한다고 할 때, $y$ 를 $x$ 의 함수로 보고 $f(x, y(x))$ 로 표현할 수 있다.

먼저 $g(x, y) = 0$ 을 전미분하면,

여기서 $dy$ 를 $dx$ 로 정리하면,

이를 $f$ 의 전미분에 대입하면,

극값을 위해서는 $df = 0$ 이어야 하므로,

이 조건은 결국 $\nabla f$ 와 $\nabla g$ 가 선형 종속이라는 것과 같고, 라그랑주 승수 $\lambda$ 가 존재함을 의미한다.

5. 라그랑주 승수법 보장 조건 (극값의 필요 조건)

라그랑주 승수법은 등식 제약 조건이 있는 최적화 문제에서 극값의 필요조건을 제공한다. 하지만 이 방법이 항상 성립하는 것은 아니며, 다음과 같은 수학적 조건이 충족되어야 한다.

1. 목적 함수와 제약 함수가 모두 연속 미분 가능일 것
   => $f(x)$ 와 모든 $g_i(x)$ 가 $\mathbb{R}^n$ 에서 $C^1$ 함수(한 번 이상 연속 미분 가능)이어야 한다.

2. 제약 조건의 그래디언트가 선형 독립일 것.
   => (Linear Independence Constraint Qualification, LICQ) 한 점 $x^*$에서, 아래 갑싱 선형 독립이어야 한다. 이는 해당 점에서 제약 조건이 "잘 정의된 곡면"을 이루고 있어야 한다는 의미다.

   $\{\nabla g_1(x^*), \nabla g_2(x^*), \dots, \nabla g_m(x^*)\}$

   위 두 조건이 충족된다면, 제약 조건을 만족하는 점 $x^*$에서 극값이 존재하려면 다음 조건을 만족하는 라그랑주 승수 $\lambda_1, \dots, \lambda_m$가 존재한다.

   $\nabla f(x^*) = \sum_{i=1}^m \lambda_i \nabla g_i(x^*), \quad g_i(x^*) = 0 \quad \text{for all } i$

   즉, 아래의 연립 조건이 극값의 필요조건으로 작용한다.

References

[\[Calculus\] Lagrange Multiplier Method (라그랑주 승수법)](https://decisionboundary.tistory.com/2)