라그랑지 승수법, KKT condition

라그랑지 승수법(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