Lagrangian Multiplier & Equality Constraint

Lagrangian Multiplier & Equality Constraint

제약조건이 없는 최적화의 경우, Gradient Descent / Newton’s Method / Quasi-Newton 등으로 풀 수 있다. 그리고 GD 경우, f(x)를 최소화 할 때, f’(x)가 0인 지점인 것은 극소이기 위한 필요조건이기 때문에 미분이 0인 지점을 찾았다.

min f(x)에서, s.t h(x)=0 이라는 equality 제약조건이 붙는 경우 필요조건은 어떻게 바뀌는가.

이럴 경우 필요조건은 라그랑지안 함수와 라그랑지안 승수를 도입해, 필요조건이 아래와 같이 바뀐다.

$\min f(\boldsymbol{x}) \\ s.t \ \ \ h(\boldsymbol{x})=0$

→ $L(\boldsymbol{x}, \boldsymbol{\lambda}) = f(\boldsymbol{x})+ \boldsymbol{\lambda}^{T}h(\boldsymbol{x})$

• local minimum의 필요조건
  1. $\nabla f(\boldsymbol{x}^{*}) + \boldsymbol{\lambda}^{T} \nabla h(\boldsymbol{x}^{*})= 0$
  2. $h(\boldsymbol{x}^{*}) = 0$

  을 만족하는 람다가 존재.

  • 참고 - boyd

    

  

하지만 이러한 필요조건이 되는 것도, Regularity Condition(Constraint Qualification)이 만족되는 경우에만 필요조건이 된다. 예를 들어, contstraint의 gradient끼리 선형독립(Linear Independent)여야 한다는 조건 등이 있다.

• 기하학적 의미 (11분 50초)

  첫 번째 필요 조건을 살펴보면, $\nabla f(x^{*}) = -\lambda \nabla h(x^{*})$으로, 극소인 지점에서의 gradient와 제약조건의 gradient가 평행하다는 것을 확인할 수 있다.

  만약 평행하지 않다면 두 번째 조건인 h(x)=0을 만족하면서 f(x)를 줄일 수 있는 다른 점이 존재한다.

• 푸는 방법 - Least Square Solution of Linear Equations - Stephen Boyd

  $\min f(x) \\ s.t \ \ \ h(x)=0 \\ \to L(x, \lambda) = f(x) + \lambda h(x)$

  • 위 제약 조건을 푸는 방법 3가지
    • 필요조건을 활용
      1. $\partial L(x,\lambda ) / \partial x = 0$ 과 $h(x)= 0$ 을 이용해 푼다.
      2. $\partial L(x,\lambda ) / \partial x = 0$ 과 $\partial L(x,\lambda ) / \partial \lambda = 0$ 을 연립해 푼다. (위 필요조건, Newton’s Method 이용, Infeasible start Newton method)
    • Duality problem으로 품 (Inequality 제약조건도 있을 때도 풀 수 있음)

      c. $\partial L(x,\lambda ) / \partial x = 0$ 을 이용해 $arg \min_{x}L$을 먼저 찾고(람다에 대한 함수) 이후에 찾은 L*에 대해 미분을 통해 람다가 최대가 되는 지점을 찾는 것

  • 예시문제 - Least-squares solution of linear equations

    

    z를 예를 들어 [3,2]^T라는 위와 같은 조건을 만족하는 해는 무수히 많으니, x의 l2 norm의 제곱이 가장 작고 z=Ax를 만족하는 x를 구해보자.

    $\min f(\boldsymbol{x}) = ||\boldsymbol{x}||^{2}_{2} \\ s.t \ \ \ \boldsymbol{z} = A\boldsymbol{x}$

    → $L(\boldsymbol{x}, \boldsymbol{\lambda}) = \boldsymbol{x}^{T}\boldsymbol{x} + \boldsymbol{\lambda}^{T}(\boldsymbol{z} - A \boldsymbol{x})$

  • a 방법

    → x벡터로 미분

    $\partial L(x,\lambda ) / \partial x = 2x^{T} - \lambda^{T}A = 0$ (벡터 미분의 결과는 행벡터로 표현)

    $x = {{1}\over{2}}A^{T}\lambda$

    → z=Ax에 구한 x값 대입

    $z = A({{1}\over{2}}A^{T}\lambda)$

    $\lambda = 2(AA^{T})^{-1}z$ (AA^T 가 역행렬이 존재하는 경우)

    → 구한 람다를 다시 x값에 대입

    $x = A^{T}(AA^{T})^{-1}z$

    z앞이 right pseudo inverse인 것을 볼 수 있다.

  • b 방법 - Infeasible start Newton’s method

    연립다항식이 많은 경우 미분해서 푸는 방법이 어려울 수 있어, 알고리즘으로 푼다.

    아래와 같이 x와 람다를 입력받는 함수 R을 놓고, $\partial L(x,\lambda ) / \partial x = 0$ 과 $\partial L(x,\lambda ) / \partial \lambda = 0$이되도록 구성하면 아래와 연립하여 쓸 수 있다.

    $\nabla_{x} L^{T}$는 원래 gradient는 행벡터이기 때문에 전치해준다. (cf. MML, 5장: 벡터함수의 gradient를 행렬로 표현할 수 있으며, 다변량 함수의 체인룰을 적용하기 쉽기 때문에 gradient는 행벡터로 표현)

    $R(\boldsymbol{w}) = R(\begin{bmatrix} \boldsymbol{x} \\ \boldsymbol{\lambda} \end{bmatrix}) = \begin{bmatrix} \nabla_{x} L \\ \boldsymbol{Z} - A\boldsymbol{x} \end{bmatrix} = \begin{bmatrix} (\partial f / \partial \boldsymbol{x}^{T})^{T} - A^{T}\boldsymbol{\lambda} \\ \boldsymbol{Z} - A\boldsymbol{x} \end{bmatrix} = \boldsymbol{0}$

    우리는 R이 0이되길 원하니 zero-finding하는 Newton’s method를 사용할 수 있다. 제약조건이 없었을 경우에는 x만 업데이트 하지만, 이 때는 x와 람다를 동시에 업데이트 한다.

    

    $R(w_{t+1}) = R(w_{t})- {{R(w_{t})}\over{R'(w_{t})}}$을 표현한 것이다.

    가운데 큰 역행렬, $R’(w_{t})^{-1}$은 아래와 같이 구성되어 있다.

    [[1행을 x로 미분, 1행을 람다로 미분],

    [2행을 x로 미분, 2행을 람다로 미분]

    Infeasible start Newton’s method라 불리는 이유는 제약조건을 만족하지 않더라도 시작할 수 있기 때문이며, 추가로 현재지점에서 다음 지점으로 움직일 때, 또 다른 상수를 넣어 보다 빠르게 zero finding 할 수 있게 하는 backtracking line search 알고리즘도 있다.

• References

  https://www.youtube.com/watch?v=NKB0XqMFuqA&list=PL_iJu012NOxeMJ5TPPW1JZKec7rhjKXUy&index=11