Untitled

라그랑주 승수법 (Lagrange Multiplier Method) 본문

지능형시스템/최적화

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

CHML 2016. 9. 1. 11:33

라그랑주 승수법 (Lagrange multiplier method)은 프랑스의 수학자 조세프루이 라그랑주 (Joseph-Louis Lagrange)가 제약 조건이 있는 최적화 문제를 풀기 위해 고안한 방법이다. 라그랑주 승수법은 어떠한 문제의 최적점을 찾는 것이 아니라, 최적점이 되기 위한 조건을 찾는 방법이다. 즉, 최적해의 필요조건을 찾는 방법이다.


1. 기하학적 해석

라그랑주 승수법의 기본 가정은 "제약 조건 $g$를 만족하는 $f$의 최솟값 또는 최댓값은 $f$와 $g$가 접하는 지점에 존재할 수도 있다."는 것이다. 아래의 [그림 1]은 제약 조건 $g(x, y) = c$를 만족하는 $f(x, y)$의 최댓값을 구하는 문제를 나타낸다. 만약, $f(x, y)$의 최댓값을 $k$라고 하면, $k$는 기하학적으로 $xy$평면에서 직선의 y축 절편 (y-intercept)을 나타낸다. 따라서, 제약 조건 $g(x, y) = c$와 $f(x, y)$가 접할 때 $f(x, y)$는 최대가 된다 (제 3사분면에서 접하는 경우는 최소가 된다).


[그릠 1] 제약 조건 $g(x, y) = c$를 만족하는 $f(x, y)$의 최댓값 문제에 대한 기하학적 표현


라그랑주 승수법에서는 두 함수 $f$와 $g$가 접하는 지점을 찾기 위해 구배 벡터 (gradient vector)를 이용한다. [식 1]은 $f(x, y)$에 대한 구배 벡터를 나타낸다.



어떠한 지점에서의 접선 벡터와 구배 벡터의 내적 (dot product)은 0이므로, 구배 벡터는 접선 벡터와 수직을 이룬다. 따라서, 두 함수 $f$와 $g$가 접한다는 것은 두 함수의 구배 벡터가 서로 상수배인 관계에 있다는 것이다. 이러한 관계를 [식 2]와 같이 나타낼 수 있으며, 이를 만족하는 $(x, y)$를 구하면 $g$와 $f$가 접하는 점을 찾을 수 있다. [식 2]에서 $\lambda$는 임의의 상수이다.



라그랑주 승수법에서는 [식 3]과 같은 보조 함수를 정의한다.



[식 3]의 함수 $L$의 구배 벡터가 영벡터가 되는 점을 찾는 것은 [식 2]를 푸는 것과 같기 때문에 함수 $L$의 구배 벡터가 영벡터가 되는 점을 찾으면 두 함수 $f$와 $g$가 접하는 점을 찾을 수 있다. 함수 $L$을 $x$와 $y$에 대해 편미분하면 총 2개의 식을 얻을 수 있으며, 여기에 제약 조건인 $g(x, y) = c$를 이용하면 미지수가 3개인 문제의 해 (solution)를 구할 수 있다. 여기에서 구한 $x$와 $y$는 제약 조건 $g$를 만족하는 함수 $f$의 최적점이 될 가능성이 있는 점이다.

만약, 제약 조건 $g$가 $n$개인 경우에는 [식 3]을 아래의 [식 4]와 같이 일반화할 수 있다.



2. 전미분 (total differential)을 이용한 해석

기하학적 해석은 직관적으로 이해하기에는 용이할 수 있지만, 라그랑주 승수법이 어떻게 계산되는지를 명확하게 나타내지는 못 한다. 따라서, 전미분 (total differential)을 이용하여 라그랑주 승수법의 정의를 더욱 수치적으로 해석한다.

어떠한 함수 $f(x, y, z)$의 최솟값 또는 최댓값은 극점에 존재할 수도 있으며, 다변수 함수의 극점은 전미분 $df = 0$인 지점 중에 존재한다. 함수 $f(x, y, z)$의 전미분은 [식 5]와 같이 정의된다.



변수 $dx, dy, dz$가 각각 독립적이라면, 함수 $df = 0$이 되는 조건은 아래의 [식 6]과 같다.



제약 조건 $g(x, y, z) = 0$에 대해서 전미분을 하면, 아래의 [식 7]을 얻을 수 있다.



[식 7]을 $dz$에 대해서 정리하면 [식 8]과 같다.



[식 8]에서 계산한 $dz$를 [식 5]에 대입하면 아래의 [식 9]를 얻을 수 있다.



함수 $f$의 전미분이 0이 되는 지점을 찾는 것이 목적이므로, [식 9]는 [식 10]과 같이 변형된다.



[식 10]을 정리하면, 아래의 [식 11]과 같다.



또한, $\lambda$를 아래의 [식 12]와 같이 정의한다.



앞의 [식 12]에서 정의한 $\lambda$를 [식 11]에 대입하여 식을 정리하면 [식 13, 14]의 과정을 통해 [식 15]를 얻을 수 있다.





서로 독립적인 $dx$와 $dy$를 포함하는 [식 15]를 만족하기 위해서는 아래의 [식 16, 17]과 같은 식이 성립해야 한다.




[식 16]과 [식 17]의 내용을 정리하면, 아래의 [식 18]과 같다. 이는 기하학적 해석에서 함수 $f$의 구배 벡터와 제약 조건 $g$의 구배 벡터가 상수배의 관계에 있어야 한다는 [식 2]와 같다.



3. 예제

[그림 2]는 같이 제약 조건 $g(x, y) = $${x}^{2}$$ + 4{y}^{2}$$ = 4$를 만족하면서, 사각형의 네 변의 합을 최대화하는 문제를 나타낸다.


[그릠 2] 제약 조건이 존재하는 최적화 문제 예시


이 문제에서 최적화해야 하는 목적 함수 (objective function)는 $f(x, y) = 4|x| + 4|y|$이다. 이 문제에 라그랑주 승수법을 적용하면, 아래와 같은 [식 19-21]을 얻을 수 있다.





[식 21]을 제약 조건 $g$에 대입하면, $x$와 $y$의 값을 계산할 수 있다.



따라서, 목적 함수 $f$를 최대화하는 $x$와 $y$의 값은 다음과 같다.





7 Comments
  • 프로필사진 noeffserv 2016.11.23 08:02 안녕하세요? 질문 하나 드려도 될까요? 혹시 부등식에 관련된 라그랑주 승수법에 대해서 아시나요? 잘 아신다면 아래 문제에 답변해주실수 있나요? 문제는 f(x,y) = x*x + y*y 가 있고 조건이 x+2y <= 20, 4x + 3y <= 17 일때, f(x,y)를 최대화 하는 것입니다. 그런데 저는 이것도 당연히 라그랑주 승수로 풀릴줄 알았습니다. 그러나 이 문제는 라그랑주 문제가 아니었습니다. 왜 라그랑주 승수로 풀수 없는지 궁금하네요. 감사합니다.
  • 프로필사진 CHML 2016.11.23 23:10 신고 라그랑주 승수법은 목적 함수와 제약 조건이 접하는 지점을 찾는 방식입니다. 따라서, 부등식으로 표현된 제약 조건에 대해서는 적용이 불가능합니다.
    이러한 문제를 해결하기 위해 라그랑주 승수법과 KKT 조건 (Karush-Kuhn-Tucker conditions)을 결합한 방법을 이용합니다. 댓글로 설명하기에는 KKT 조건에 대한 내용이 너무 많기 때문에 따로 찾아보시는 게 좋을듯합니다.
  • 프로필사진 noeffserv 2016.11.25 16:21 KKT 조건을 사용해서 풀어봤었습니다. 하지만 최적의 해를 주질 않았습니다. 위 문제에서의 최적의 해는 x = 0, y = 17/3 인것으로 알고 있습니다. 하지만 이 값은 KKT조건을 만족시키지 않습니다. 왜 그런 결과가 나오는 걸까요?
  • 프로필사진 noeffserv 2016.11.25 16:26 제가 KKT 조건을 이용해 파이썬으로 얻었던 해는 2.72 와 2.04 였습니다. 모든 연립방정식을 만족했습니다. 하지만 이 값은 x = 0, y = 17/3 일때보다 x*x + y*y 를 최대화 시키지는 않습니다. 그래서 라그랑주 승수법에 대한 개념을 잘못 이해하고 있나 싶습니다. 이에 대한 답을 알고 계신지 궁금합니다....
  • 프로필사진 ㅇㄴㅁ 2021.03.17 22:33 애초에 저 문제는 최대값이 존재안하는데 문제를 풀려고 하는게 잘못된거 아닌가요
  • 프로필사진 CHML 2016.11.25 17:06 신고 noeffserv// 코드를 볼 수 없어서 프로그래밍 하신 결과가 왜 그렇게 나오는지는 저도 잘 모르겠습니다... "B553 Lecture 7: Constrained Optimization, Lagrange Multipliers, and KKT Conditions"으로 검색하시면 나오는 문서의 4페이지를 읽어보시면 라그랑주 승수법에 대해 더 자세히 아실 수 있을 것입니다.
  • 프로필사진 김경호 2019.10.29 03:22 좋은 글 잘 읽고 갑니다!~
댓글쓰기 폼