Lagrange Multiplier Method

find min(max) with constraint

본 포스팅 출처 : Link

Lagrange Multiplier Method

• 언제? :
  multi-variate function을 optimize할 때
  constraint가 존재할 경우
  최적점의 필요조건을 찾기 위해
  Lagrange Multiplier Method 사용

• 핵심 아이디어 :
  주어진 function \(f\) 와 constraint \(g_{i}\) 에 대해
  \(f\) 와 \(g_{i}\) 의 접점 (경계)에 \(f\) 의 최댓(솟)값이 존재할 수도 있다!
  그리고 접점에서는 \(\nabla f\) 를 \(\nabla g_{i}\) 들의 linear comb.로 표현할 수 있다!
  (다만, 접점은 극점이므로 반드시 최댓값 또는 최솟값이 존재하는 건 아니다)

Equality Constraint

• \(g_{i}\) 가 등식일 경우 (e.g. \(g_{i} = 1 - \phi_{i}^T\phi_{i} = 0\)) :
  접점에서 gradient가 평행하므로 (이에 대한 수식 증명은 참고한 포스팅 Link 에 있음)
  \(\nabla f = \sum_{i=1}^N \lambda_{i} \nabla g_{i}\) 로부터
  아래처럼 풀면 된다
  (단, \(\lambda \neq 0\))
  (단, \(\nabla f\) 과 \(\nabla g_{i}\) 은 평행할 뿐 방향은 반대여도 됨)
  • 방법 1)
    \(\nabla f + \sum_{i=1}^N \lambda_{i} \nabla g_{i} = 0\) 와 \(g_{i} = 0\) 을 연립하여 풀면 된다
  • 방법 2)
    Equivalently,
    \(L = f + \sum_{i=1}^N \lambda_{i} g_{i}\) 에 대해
    \(L\) 의 극소(대)점을 찾으면 된다
    즉, \(f, g_{i}\) 가 \(x_{j}\) 에 대한 함수일 경우
    \(\frac{\partial L}{\partial x_{j}} = 0\) 과 \(\frac{\partial L}{\partial \lambda_{i}} = 0\) 을 연립하여 풀면 된다

Inequality Constraint

등식 constraint일 때의 Lagrange Multiplier Method는 완전히 이해했는데,
부등식 constraint일 때의 Lagrange Multiplier Method는 아직 이해 못함.
추후에 고칠(이해할) 필요 있음. TBD

• 부등식 constraint일 경우 KKT (Karush-Kuhn-Tucker) 조건을 만족해야 한다
  • 1) \(f\) 는 모든 variable (e.g. \(x, y\))에 대해 differentiable
  • 2) \(\lambda_{i} \nabla g_{i} = 0\)
  • 3) \(\lambda{i} \geq 0\)
    (만약 \(\lambda_{i} \lt 0\) 일 경우 \(\nabla f\) 와 \(\nabla g_{i}\) 가 평행하지만 방향이 반대라는 의미이므로 두 함수의 최적점이 서로 반대 방향에 위치하여 constraint를 만족할 수 없다)
    (따라서 \(\lambda_{i} \geq 0\) 이어야만 (\(\nabla f\) 방향과 \(\nabla g_{i}\) 방향이 일치해야만) \(\nabla f\) 를 \(\nabla g_{i}\) 들의 linear comb.로 표현 가능한지 아닌지를 판정할 수 있다)
• \(g_{i}\) 가 부등식일 경우 (e.g. \(g_{i} = 1 - \phi_{i}^T\phi_{i} \leq 0\)) :
  \(\lambda_{i} \nabla g_{i} = 0\)
  • \(\nabla g_{i} = 0\) 일 경우 :
    constraint \(g_{i} \leq 0\) 을 항상 만족하므로
    \(\nabla f \geq 0\) 을 푸는 문제로 바꿔 쓸 수 있다
    (constraint 없이 \(f\) 만 최적화하면 됨!)
  • \(\lambda_{i} = 0\) 일 경우 :
    \(\nabla f\) 를 \(\nabla g_{i}\) 들의 linear comb.로 표현 불가능하다는 의미이므로
    비교하는 두 gradient가 평행하지 않다
    따라서 gradient 방향에 따라 constraint 만족하는 지 여부가 달라지므로
    \(\nabla g_{i} \gt 0\) 인 경우와 \(\nabla g_{i} \lt 0\) 인 경우를 모두 따져봐서
    어떤 경우(방향)가 constraint를 만족하는지 확인해야 한다