라그랑지 승수법(Lagrange multiplier) : 어떤 함수(F)가 주어진 제약식(h)을 만족시키면서, 그 함수가 갖는 최대값 혹은 최소값을 찾고자할 때 사용한다.


L(x,λ) = F(x) + λ*h(x) 으로 표기하며, (x,λ)변수들로 각각 편미분 한 식이 0이 되는 값으로 해를 구한다. 

이러한 계산의 원리는, 사실 두 함수의 기울기가 같아지는 공통접선을 구하는 것이다.


위 수식이 성립하는 이유는, F(x) = F(X) 에서 양변에 0에해당하는 제약식( 0=h(x) )을 더해서 F(x) + λ*0 = F(x) + λ*h(x) 으로 놓고 문제를 푼것이라 생각하면 된다.


http://blog.naver.com/mindo1103/90154212128

이글에 원리가 아주 잘 설명되어 있음.


부연 설명 : 라그랑지 승수법의 원리는 사실, 두가지 조건을 동시에 만족시키는 공통접선을 찾는 과정이다. 공통 접선이란 함수 F(x)와 제약식 h(x)을 미분해서 구한 접선의 기울기 벡터가 서로 평행한 점에서의 접선을 의미한다. 

--> 즉, F(x)와 h(x)를 각각 미분하여 구한 기울기가 서로 평행하다는 것을 이용해, 이를 등식 "="으로 놓은 뒤 미지수 λ를 곱하여 길이가 서로 같다고 놓고 등식을 세운 것이다.


ex) GMM의 EM에서는 P(hidden | observation) + λ(sum(π)-1) = 0 으로 놓고 이 식을 편미분해서 최적화 식을 구해낸다.


이때 위의 예시처럼 제약식이 등호로 이루어진 경우, equality constraint problem 이라 부르며 이는 편미분만 하면 되서, 푸는 방법이 간단하다.

하지만 제약식이 등호가 아닌 부등호인 경우를 inequality constraint problem 이라 부르고 KKT condition 이라는 라그랑지 승수법에서 추가된 조건을 써야 한다.

만약 제약식의 람다가 0인 경우는 unconstraint problem이라 하며, 그냥 단순히 F(X)를 1번 미분한 것이 0, 2번 미분한 것이 양수인 경우를 풀면 극소점이 된다.(참고로 행렬을 벡터로 1번 미분한 걸 자코비안, 2번 미분한걸 헤시안이라고 부른다.)


KKT condition : 등식의 제약식이 있는 최적화 문제를 푸는 것을 라그랑지 승수법이라 하고, 부등식의 제한 조건에서도 쓸 수 있게 확장시킨 것을 KKT condition이라 한다.


http://blog.naver.com/sdland85/90162606149

http://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions

http://blog.naver.com/piccoro77/100109694027

http://blog.naver.com/ghessy2413/120201486715

by 곽동현 이스텔리앙 2014.07.18 16:55
  • SH 2016.08.31 21:05 ADDR EDIT/DEL REPLY

    라그랑지배수를 공부하려 찾은 자료 중 제일이네요
    쉽고 직관적인 설명이네요
    잘 배우고 갑니다~ 감사합니다