[최적화] (7) Lagrangian Multiplier Method

여지껏 우리는 convex problem을 풀기 위한 방법인 gradient method와 newton method를 살펴봤다.

사실 좌측 그림과 같이 2차함수의 경우 미분한 도함수가 0이 되는 지점을 찾으면 convex problem이 해결된다. 그러나 우측 그림과 같은 고차함수의 경우 이를 미분하는 연산 자체가 복잡할 뿐더러 미분이 불가한 함수일 수도 있다. 따라서 우리는 gradient method, newton method와 같이 initial point만 주어진다면 바로 인근의 local minimum을 찾을 수 있는 방법론들을 살펴봤다. 

 

"도함수가 0이다"라는 조건은 해당지점이 local minimum이기 위한 필요조건이다. 실제로 해당지점이 local max, saddle point일 수도 있지만 적어도 local min이기 위해선 도함수가 0이 되어야하니 이에 집중해왔던 것이다. 

 

이제부턴 constraints(제약조건)을 가진 convex problem을 해결할 방법을 살펴보자. 

가령 h(x)=0이란 equality constarint가 존재한다고 가정하자. 우측의 그림 상에선 h(x)=0이 목적함수 f(x)와 두 지점에서 교차하는데, 좌측의 x1*이 이 문제에선 optimal solution이 된다. 그러나 이 지점은 일전에 살펴본 예시와는 달리 미분값이 0이 아니다. 즉, constraints가 주어진 상황에선 미분값=0이 더이상 주된 관심사가 아니게 되는 것이다. 

 

따라서 우리의 새로운 필요조건은 Lagrangian function L(x, λ)=f(x)+λh(x) 의 x편도함수 aL/ax가 0이 되어야하고, 동시에 given constraint가 만족되어야만 한다. 이를 풀어쓰면 위 그림의 필요조건 명제와 같다. 

 

이 필요조건을 기하적으로 이해하기 위해서 다음과 같이 생각해볼 수 있다. 

필요조건1은 del f = -λ(del h)로 재정의될 수 있으며, 이 식에 의하면 del f 와 del h는 서로 평행해야한다. 적어도 서로 평행해야지 이후 λ가 곱해져서라도 이둘을 똑같이 만들 수 있기 때문이다. 그렇다면 우린 given constraint가 만족되는 특정 지점 중 이 둘이 평행해지는 지점을 찾아야만 한다. 둘이 평행하다는 사실 자체가 local min을 위한 필요조건이 되는 것이다.

del f를 생각해보면 이는 gradient로서 특정 지점(optimal sol)에 대해선 항상 고정된 벡터값을 지닌다. 그 del f에 대응되는 특정 유닛방향벡터 u가 존재할텐데 만약 u가 del f와 이루는 각이 둔각으로 형성될 경우 이 둘의 내적인 방향도함수값은 음수가 된다. 둘을 내적하면 |del f| * |u| * cosθ가 도출되는데 |u|=1이고 |del f|는 값이 고정되기 때문에 cosθ가 값을 결정짓기 때문이다. 그런데 u와 del f가 둔각을 이루는 경우 -1<cosθ<0 사이에서 cosθ값이 형성되고 방향도함수값이 음수가 되기 때문에 u방향으로 진행하면 f값은 더 감소한다는 뜻이 된다. 이는 아직 덜 minimized되었음을 뜻한다. 그런데 정말로 local min에 도달하게 되면 방향도함수값은 0이 되는데, u와 del f 벡터가 서로 직교할때 cosθ=0이 되며 u는 위 그림에서 빨간선과 같이 형성된다. 이 경우 더 이상 어떠한 방향으로 나아가도 f는 줄어들지 않으며(방향도함수가 0이기 때문에), 그리고 equality constraint 또한 충족이 된다. 즉, local minimum인 상황이다.

 

가령 위 그림처럼 equality constraints를 만족하면서, 즉 optimal solution x*이면서 del f와 del h, 방향벡터 u가 다음과 같이 형성된 경우가 있다고 생각해보자. 이 지점은 local min인가? 

우선 del f와 u가 둔각을 형성하기 때문에 해당 방향으로 나아가면 f가 더욱 작아진다. 그런데 이 경우 움직이면 constraints가 깨질 수 있다. 그러나 del h와 u가 서로 수직이기 때문에 해당 지점으로 나아가도 h값에는 전혀 변화가 없다. 즉 u 방향으로 움직여도 equality constraint는 유지되는 것이다. 이 경우 이 지점은 local minimum이 아니다. u 방향으로 계속 나아가다보면 del h와 del f가 평행인 local min인 optimal sol을 만나게 된다.

 

따라서 우린 이러한 Lagrangian fn의 필요조건을 활용하여 given constraint의 convex problem을 풀 수 있다. 

첫째, del_x L = 0 & h(x) = 0을 연립한다.

둘째, del_x L = 0 & del_λ L = 0을 연립한다. (사실 첫번째 방법과 똑같다)

셋째, del_x L = 0로 argmin x L를 찾고, 구한 x를 L에 대입한다. 그리고 del_λ minL =0 를 통해 λ를 찾는다. 

 

간단한 예시를 통해 상술한 기하학적 이해를 더욱 탄탄히 해보자.

위 그림처럼 빨간색 타원이 equality constraint로 주어졌을 때 이 constraint를 만족하는 원의 최대/최소는 무엇일까? 이를 기하학적으로 단순히 풀어낸다면 위 그림과 같이 그릴 수 있을 것이다. 잘 살피면 최소인 지점에서 타원과 원은 공통접선을 가지고, 최대인점도 마찬가지다. 즉, primal fn과 equality constraint가 공통접선을 가지는 지점 중 optimal solution이 존재한다. 해당 지점에서 두 접선은 평행하다.

equlaity constraint의 경우 위 그림과 같이 등위곡선으로 표현가능한데, del h(x)는 optimal solution에서 접선과 수직인 벡터, 즉 gradient다. 마찬가지로 primal fn은 특정지점에서 접선을 갖고 이 접선에 수직인 벡터인 del f가 존재한다. 따라서 이 둘은 lambda만큼 차이나되 서로 평행하니 그 둘을 합한 값은 0이다. 

 

그럼 예시를 통해 풀이과정을 살펴보자. Z=AX를 만족하는, X의 norm2 제곱을 minimize해주는 convex problem이 있다. 

 

풀이방법은 이전에 살펴본 세가지 방법 중 1번을 택했다. Lagrangian을 x에 대해 편미분하면 lambda가 인수로 포함된 x식을 얻게 된다. 이를 Z=AX에 대입하면 두번째 줄과 같이 lambda에 대한 수식을 얻게 되는데, 이를 처음 얻은 x식에 대입하면 optimal solution을 구할 수 있다.