Lagrange multiplier

Lagrange multiplier.

(출처: https://en.wikipedia.org/wiki/Lagrange_multiplier)

PLICP를 공부하다 알게 되었다. (Point to Line Iterative Closest/Corresponding Point)

간단하게 얘기하자면, 

함수 f(x,y), g(x,y)가 존재한다고 하자. 이때, g(x,y) = c 를 만족하는 x,y로 만들 수 있는 f(x,y) 값중 가장 큰 값이나 가장 작은 값을 구하는 방법이다.

---

결론부터 적자면

$$ L(x,y,\lambda) = f(x,y) - \lambda * (g(x,y) - C) $$  

-----  (1) 번 식.

를 한뒤. L의 gradient 값이 0을 만족하는 x, y점이 가장 크거나 가장 작은 값의 후보군이 될 수 있다.

$$ \nabla L(x,y,\lambda) = 0 $$

이는 결국 편미분한 값이므로 

$$ \nabla L = ( \frac{\partial L}{\partial x} ,\frac{\partial L}{\partial y}, \frac{\partial L}{\partial \lambda} ) = 0 $$

이고 이에 (1)번식을 대입하면,

$$ \nabla f = \lambda \nabla $$와$$g(x,y) = C $$ 

으로 나타 낼 수있다. 위 두식을 만족하는 x, y 중 가장 작은값과 가장 큰값등 원하는 값을 찾으면된다. 

(물론 g(x,y)=C 의 시작 & 끝점을 항상 고려해줘야한다.)

이때의 lambda를 lagrange multiplier 라고한다.

---

이해

위의 이론에 가장 중요한 식은 

$$ \nabla f = \lambda \nabla g $$

이 식이라고 할 수 있다. 왜 이것을 만족하는 점이 가장 작은값 혹은 가장 큰값의 후보군이 될 수 있는 것인가?

이를 3차원 그래프로 이해하면 굉장히 편하다. 

( 출처 : wikipedia )

위와같은 그래프에서 우리가 제한시킨 부분 =>  g(x,y)=c 를 선으로 나타 낼 수 있다.

이때 gradient f 가 의미하는 것은 값이 가장 많이 변하는 방향이다.

gradient g가 의미하는것도 값이 가장 많이 변하는 방향이다.  

이때 g(x,y) 값은 변하지 않으므로 가장 많이 변하는 부분은 선의 진행방향(접선)의 수직인 방향이 될 것이고, 

grad f(x,y)값이 가장 많이 변하는 부분과 평행 하게 된다.

이는 결국, g(x,y)=c 인 선을 따라 움직일때, f(x,y)가 변하지 않는 부분을 만나게되면 ( grad 값의 수직인 부분은 정적인 변화를 가지고 있다. )

$$ \nabla f = \lambda \nabla g $$

를 만족하게 된다는 것이다. (평행 이므로)

그리고 이값이 최대, 최소의 후보군이 될 수 있는 이유는,  우리가 일반적인 함수에서 최대 최소를 찾기위해 미분값을 0인 부분을 찾는 것과 같이 생각 할 수 있다.

g(x,y) = c를 따라가다 보니, f(x,y)값이 변하지 않는 것을 보았고, 이부분은 최소나 최대가 될 수 있는 후보군이 된다.

---

사실 처음 이해할때 가장 어려웠던 부분이 gradient의 의미를 이해하는 것이었다.

왜  gradient는 값이 가장 많이 변하는 방향을 가리킬까, 또 왜 gradient의 수직한 방향은 왜 일정한 값을 갖는 것일까.

gradient f를 생각해보자,

$$ \nabla f(x,y) = ( \frac{\partial f}{\partial x} ,\frac{\partial f}{\partial y})$$ 이고 ,

$$ f(x+dx,y+dy) \approx f(x,y) + \frac{\partial f}{\partial x} dx + \frac{\partial f}{\partial y} dy$$

이 때, $$ dx^2 + dy^2 = 1 $$ 을 만족시키는 최대값은 $$ <\frac{\partial f}{\partial x}, \frac{\partial f}{\partial y} > $$ 

와 같은 방향을 갖는 것이다. (이 부분은 혼자 증명해보는게 좋을듯 ㅎㅎ)

그렇기 때문에 gradient는 변화량이 가장 많은 방향이라고 생각하면 된다. 

그렇다면 외 수직한 방향은 일정한 값을 갖는가 ? 수직한 방향은 $$ <\frac{\partial f}{\partial x}, \frac{\partial f}{\partial y} > $$  

와 수직한 방향이 되고, f(x+dx,y+dy) - f(x,y)값은 $$ \frac{\partial f}{\partial x} dx + \frac{\partial f}{\partial y} dy$$

이므로, <dx,dy>벡터와 $$ <\frac{\partial f}{\partial x}, \frac{\partial f}{\partial y} > $$  의 dot product라고 볼 수있다. 

그렇기 때문에  수직한 벡터의 dot product는 0이므로 변화량이 0이 되는 방향인 것이다.