라그랑주 승수법이란?
라그랑주 승수법은 제약이 있는 최적화 문제를 푸는 방법 중 하나로, 모든 제약식에 라그랑주 승수(Lagrange Multiplier) λ를 곱하고 등식 제약이 있는 문제를 제약이 없는 문제로 바꾸어 문제를 해결하는 방법입니다. 만약, 등식이 아니라 부등식의 제약이 있는 문제라면, KKT(Karush-Kuhn-Tucker) 조건을 만족하는 문제일 때 라그랑주 승수법으로 문제를 해결할 수 있습니다. 예를 들어 f(x)=x2+1 을 최소화 하는 문제에서 g(x)≤3 이라는 제약조건이 있다면, 제약조건의 형태를 g(x)−3≤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로 표현할 수 있습니다. λ는 라그랑주 상수로 임의의 상수입니다.
이때 f와 g를 통해 Eqn. 3과 같은 라그랑주 함수(Lagrange Function)을 정의할 수 있습니다.
라그랑주 함수 L의 구배 벡터가 영벡터가 되는 조건은 다음과 같습니다.
라그랑주 함수 L의 구배 벡터가 영벡터가 되는 점을 찾는 것은, Eqn. 2의 해를 찾는 것과 같기 때문에 라그랑주 함수의 구배 벡터가 영벡터인 지점을 찾음으로서 두 함수 f, g가 접하는 점을 찾을 수 있습니다. 즉, 라그랑주 함수 L을 각 변수들 x,y,λ로 편미분한 결과인 Gradient가 0이 되는 수식을 정리하면 세 가지 식을 구할 수 있고(∵ 변수가 2개이고, 제약조건이 하나이므로) 해당 식을 연립하여 제약식을 풀게되면 최적화된 해를 구할 수 있게 됩니다. 또한, 제약조건이 한 개가 아닌 여러개라면, Eqn. 4와 같이 일반화 할 수 있습니다.
KKT(Karush-Kuhn-Tucker) 조건
라그랑주 승수법을 소개하면서 부등식의 제약조건을 가지는 문제는 KKT 조건을 만족해야 라그랑주 승수법을 적용할 수 있다고 언급하였습니다. (단, 부등식 제약조건은 모두 ≥ 형태로 변환) KKT 조건은 다음 3개의 조건으로 이루어 집니다.
첫 번째 조건은 라그랑주 승수의 조건에도 포함되어 있습니다. 최소점을 찾기 위해 미분 값이 0인 지점을 찾기 때문입니다. 다만 변수 x에 대한 미분값만 0이면 됩니다.
두 번째 조건은 라그랑주 함수를 라그랑주 승수 λ로 미분한 값은 반드시 0이 될 필요는 없다는 점을 시사합니다. 등식 제약조건의 경우 처럼 gj가 0이 되거나, 혹은 라그랑주 승수 값 자체가 0이 되어야 함을 의미합니다.
마지막 조건은 KKT 조건이 실제로 부등식 제약조건이 있는 최적화 문제와 동일한 문제임을 보장하는 조건입니다.
Example
라그랑주 승수법의 간단한 예제를 들어보겠습니다.
'[Calculus]' 카테고리의 다른 글
| [Calculus] Taylor Series (테일러 급수) (0) | 2021.09.21 |
|---|
