Lagrange Multiplier method (라그랑주 승수법)

Intro

라그랑주 승수 법 (Lagrange multiplier method)은 프랑스의 수학자 조세프루이 라그랑주에 의해서 만들어진 방법입니다.

[1] Joseph-Louis Lagrange

최적화 문제에서 제약조건이 있을때를 고려하여 해결하기 위해서 제안한 방법이며, 최적점을 찾는 것이 아닌 최적점이 되기 위한 조건 (Condition)을 찾는 방법을 의미합니다. 즉 최적해의 필요조건을 찾는 방법입니다. 

 

Definition

연속미분가능한 함수 f(x)와 g(x)가 존재할 때 g(x) =0인 제약 아래서 f(x)를 최적화하는 문제를 생각해보겠습니다. 

이때 라그랑주 승수법은 이에 대한 하나의 해법으로서 라그랑즈 승수 λ (Lagrange multiplier)를 g(x)에 곱하여 f(x)에 더한 라그랑주 함수 L(x, λ)를 새로 만들어 해당 함수를 목적함수로 삼는 새로운 최적화 문제로 바꾸는 방법입니다. 

즉, 기존의 문제를 라그랑주 함수 L(x, λ)를 목적함수로 가지는 최적화 문제로 바꾸고 라그랑주 함수에 대해 최적화를 수행하면 되는 문제로 바꿀 수가 있습니다. 

제약조건이 없어졌으므로 목적함수 L에 대해서 최적화 기법을 사용할때 제약조건에 구속받지 않거나 덜 영향을 받는 방법들을 사용할 수 있게 됩니다. 

최적화하는 과정은 L함수를 λ에 대해 변화량이 0이 되는 지점을 찾으면 되므로 즉, 미분값이 0이 되는 값을 찾음으로써 최적화를 수행할 수 있습니다. 

변수가 2개일때도 마찬가지입니다. 

 

Geometrical interpretation

라그랑주 승수법의 기본 아이디어는 다음과 같습니다. 어떠한 조건 g를 만족하는 함수 f의 최대 또는 최솟값을 찾는 문제에서 찾고자 하는 값이 f와 g의 접점에 존재할 수도 있다는 가능성에서 출발하게 됩니다. 

gradient는 기울기라는 의미를 지니고 있습니다. f와 g라는 함수가 tangent일때 그들의 gradient vector는 평행이게 됩니다 (파란 화살표와 빨간 화살표). Tangent는 gradient vector의 크기를 말해주지는 않습니다. 그러나 방향에 대해서는 알려주고 있으며 f와 g의 gradient는 동일한 방향으로 향해있기 때문에 gradient 사이에 상수 곱으로 표현이 가능해지게 됩니다. 

예를 들어서 (x0, y0) 지점에서 f와 g가 tangent일때 아래와 같이 표현을 할 수 있습니다. 

즉, 라그랑즈 승수 λ (Lagrange multiplier)라는 상수를 이용하여 제약조건 g와 목적함수 f간의 관계를 표현할 수가 있으며 아래의 함수 L의 구배 벡터가 영 벡터가 되는 점을 찾는 것은 곧 위의 식을 푸는 것이 되는 것이 됩니다.

함수 L을 x, y각각에 대해 편미분을 수행하면 총 2개의 식을 얻을수 있으며 제약조건을 이용하면 총미지수가 3개인 문제의 해를 구할 수가 있게 됩니다. 이때 구한 x와 y값은 제약조건 g를 만족하는 함수 f의 최적점이 될 가능성이 있는 점입니다. 

Example

예제를 한가지 풀어보겠습니다. 문제는 다음과 같습니다. 제약조건 또는 타원 g(x, y)에서 f(x, y)가 최대, 최소를 구하는 게 목표입니다.

해당 식을 풀기 위해서 위에서 배웠던 방식 그대로 라그랑주 승수를 이용하여 라그랑주 목적함수 L로 바꿔주겠습니다. 

 

변수가 x, y이므로 각각에 대해 미분을 수행합니다. 그리고 얻어진 결과에 대해서 이항을 수행해줌으로서 연립방정식을 얻을 수가 있습니다.

이때 해를 구하게 되면 (x,y) = (0,0)이라는 임계점 후보와 λ= 2또는 -2라는 값을 얻을 수 있습니다. 

이제 λ = 2또는 -2에서 얻어지는 임계점도 확인해보겠습니다. 우선 L을 λ에 대해 편미분을 수행합니다. 

이때 λ = 2를 이용하여 y=x를 편미분 한 계산식에 넣어줍니다. 

마찬가지로 λ = -2 일때도 위와 동일한 결과가 나오게 되며 2개의 임계점을 아래와 같이 찾을 수가 있었습니다. 

이로서 임계점 후보가 3개가 되지만 위에서 찾아둔 임계점 (0,0)은 g(x,y)에 해당이 되지 않기에 제외합니다. 최종적으로  g(x, y)는 원의 방정식이므로 그림을 그렸을 때 f(x, y)는 g(x, y)에서 최대 2 값을 가질 수 있으며 좌표값은 위의 2개의 후보와 같습니다. 

 

Reference

[1]https://ko.wikipedia.org/wiki/%EC%A1%B0%EC%A0%9C%ED%94%84%EB%A3%A8%EC%9D%B4_%EB%9D%BC%EA%B7%B8%EB%9E%91%EC%A3%BC