Lagrange multiplier

참고:http://en.wikipedia.org/wiki/Lagrange_multiplier

등식 조건을 만족하는 조건부 최적화 문제를 풀기 위한 하나의 방법.

maximize f(x) subject to g1(x)=0, g2(x)=0, ..., g_m(x)=0을구하는 문제에서 f와 g가 연속인 1차 편도함수를 가지고 있다고 가정하자.

그러면, 원래의 조건부 최적화 문제의 해는 다음 함수의 stationary  point이다. (역은 성립 안함. 다시 말하면 필요 조건이지 충분 조건은 아니라는 뜻, 충분 조건을 만족하기 위해서는 Hessian에 관련된 어떤 성질을 만족하여야 하는데 이건 좀더 공부가 필요).

L(x,lamda1,lamda2,...,lamda_m)=f(x)-(다음을 각 i에 대해 더함: lamda_i*(g_i(x) )

함수 L의 stationary point는 다음의 조건을 모두 만족하는 점이다.

(1) x에 대한 편도함수가 0, 

(2) 각 i에 대해 lamda_i의 편도함수가 0

이 조건들은 다음을 의미한다.

(1) ->점 x에서 f의 gradient(벡터)가 각 g_i의 gradient(벡터)의 어떤 일차 결합과 서로 평행하다

      * 점 x에서 f의 값이 바뀌지 않는 방향 :f(x)의 gradient(벡터)에 수직인 벡터들

      * 각 g_i(x)=0을 모두 만족하는 방향 : 각 g_i(x)의 gradient(벡터)들의 어떤 일차결합'에'도' 수직인 벡터들

        (여기서 일차결합의 계수가 lamda_i임.)

     

      -> :f(x)의 gradient(벡터)에 수직인 벡터들은 g_i(x)의 gradient(벡터)들의 어떤 일차결합'에'도' 수직하다.

             다시 말하면,  점x에서 모든 g_i를 만족하는 어떤 방향으로 움직여도 f의 값이 바뀌지 않는다.  

             f의 값이 바뀌는 방향은 적어도 하나의 g_i를 만족하지 못하는 방향이다.

(2)  -> 최초 문제의 g1(x)=0, .., g_m(x)=0