Newton method for equality constrained optimization(1)

뉴턴 메서드는 함수의 해를 근사적으로 찾는 수치해석 기법이며 변수의 시작점에서 Taylor Expansion을 통해 2차 함수를 근사하고 이후 근사한 2차 함수의 값이 감소(또는 증가)하는 방향으로 이동시키며 최소 값(또는 최대 값)을 만족시키는 최적 해를 찾습니다.

*일반적으로 극값이지만 편의를 위해 최소 값을 찾는 문제로 제한

*함수는 컨벡스하며 locally optimal solution = globally optimal solution 이다.

경사 하강법의 1차 근사와 달리 2차 함수로 근사하기 때문에 근사하는 지점 부근에서 상대적으로 더 자세히 모델링하므로 성능이 더 좋습니다.

이러한 수치적으로 해를 구하는 방법은 최적해(극점, 컨벡스 함수 제한)을 찾는데 사용될 수 있으며, 제약 조건을 만족시키기 위해 구속력으로서 도입된 라그랑지 승수를 포함시켜 제약 최적화를 달성하는데 사용될 수 있습니다.

다음과 같은 최적화 문제 예시를 보겠습니다.

$$min\ f(x) \\ such\ that \ Ax=b$$

위 문제는 함수가 최소값(극값)을 가지게 하는 최소점(극점)을 찾는 문제이며 이는 단순히 미분하여 해석적 해를 도출하여 해결될 수도 있지만 수치적으로 함수를 근사하며 해를 찾아가는 뉴턴 메서드를 활용합니다. 또한 최적 해는 stationarity, primal constraint라고 하는 조건을 만족해야하며 이를 확인하는 과정을 보겠습니다.

함수는 다음과 같이 테일러 급수를 이용해 근사되며

$f(x+\Delta x) \approx f(x) + \nabla f(x)\Delta x + {1\over2}\nabla^2 f(x)\Delta x^2 +H.O.T$

우리는 제약조건을 만족하는 최소점을 찾을 것이므로 뉴턴 메서드와 제약조건이 반영된 라그랑지안을 사용한다.

$L(x+\Delta x,\lambda) = f(x+\Delta x) +\lambda (A(x+\Delta x)-b)$

$$min \ L(x+\Delta x,\lambda) \\s.t \ A(x+\Delta x)=b$$

위 문제의 최적 해는 아래와 같은 조건들이 만족되어야합니다.

1. stationarity (최소점(극점)에서는 변화율이 0이므로 더 이상 움직일 움직일 필요가 없습니다. 따라서 라그랑지안의 변화율이 0이 되는 지점을 찾아야겠죠..)

   $\nabla_x L = \nabla f(x) + \nabla^2_x f(x) \Delta x + \lambda A= 0$

2. primal constraint (아래와 같은 제약을 만족하는 $A(x+\Delta x)$를 찾아야함을 의미합니다.)

   $A(x+\Delta x)-b =0$

   현재 $x$ 즉 시작점이 제약을 만족하는 feasible 영역, 제약에 위배되는 infeasible 영역에 있는지에 따라 방법이 조금 달라집니다.

feasible, infeasible 영역 두 가지에 대해 모두 다룰 것이고 feasible인 경우 먼저 확인할 것이고 해를 찾는 과정은 다음과 같습니다.

1. 함수의 감소 방향 구하기

2. 수렴율 확인

3. 스텝 크기 만큼 이동하여 함수 업데이트

현재 시작점이 feasible 영역에 있는 경우를 보면 $Ax-b=0$을 만족합니다. 따라서 증분에 대한 제약조건식은 $A\Delta x=0$이 됩니다. 이는 $\Delta x$ 증분이 제약 조건을 만족하는 방향으로 발생하도록 구속력을 가합니다. 위 와 같은 과정을 반복적으로 진행하면 증분이 발생하다 더 이상 일어나지 않는 지점에 이르고 최적 조건을 만족하는 것을 확인할 수 있습니다.

함수의 감소 방향 구하기

최소값을 찾기 위해 함수의 감소 방향을 구해야하므로 함수의 거동이 어느 방향으로 일어나는지 확인해봅니다.

우리는 앞서 제약조건에 대해 현 지점이 feasible하다 라고 했습니다. 그러므로 다음과 같이 정리될 수 있습니다.

$$\nabla f(x) + \nabla^2 f(x) \Delta x + \lambda A= 0 \\ \nabla f(x) = -\nabla^2 f(x) \Delta x - \lambda A$$

헤시안은 함수의 감소방향을 가리키며 $\lambda A$는 제약을 만족하도록 구속시켜주는 역할을 합니다.

$$\Delta x = -{ {\nabla f(x)} +\lambda A\over {\nabla^2 f(x)}}$$

여기서 함수와 조건이 모두 컨벡스하다면 뉴턴 메서드에서 이동하는 방향이 함수가 감소하는 방향임을 알 수 있습니다.

또한 감소하는 방향으로의 감소량을 조절하기 위해 스텝크기 $\eta$ 를 도입하는데 이를 다시 확인해보면

$$f(x+\eta \Delta x)=f(x) + \nabla f(x) \eta\Delta x + {1\over2}\nabla^2 f(x) \eta\Delta x^2 \\ \rightarrow \nabla L = \nabla f(x) + \nabla^2 f(x)\eta\Delta x +\lambda A= 0 \\ \rightarrow -\nabla^2 f(x) \Delta x - \lambda A + \nabla^2 f(x)\eta\Delta x +\lambda A =-(1-\eta)\nabla^2 f(x) \Delta x$$

위와 같은 식을 도출할 수 있고 이 때 스텝 크기는 $0<\eta <1$ 해야 감소하는 방향으로 제한할 수 있습니다. (에타의 범위는 수식적으로 다음과 같이 나오는데.. 실제 알고리즘을 돌려보면 1.xx 에서도 수렴하는 모습을 보여주네요.. 근사함수라 그럴까요.. 조금 더 커지면 발산하는 것을 확인할 수 있었습니다.)

수렴율 확인

여기까지 이동 방향과 그 양을 구했으니 이제 어느정도 수렴했는지 확인해야합니다.

감소 방향을 구하고 업데이트만 지속한다면 끝없이 알고리즘이 수행되겠죠..

제약이 반영되지 않은 함수를 가정하고 보면 현 상태 $x$ 에서 $\Delta x$ 만큼 증분 시켰을 때 차이 $f(x) - f(x+\Delta x)$ 를 이용해 계산할 수 있고 이동한 지점이 최적점이라면 $f(x) - f^* = 0$이 되겠죠

$$L(x,\lambda) - L(x+\Delta x , \lambda)= -\nabla f(x)\Delta x - {1\over2}\nabla^2f(x)\Delta x^2 -\lambda A \Delta x\\ =-(\nabla f(x)+\lambda A)\Delta x - {1\over2}{\nabla ^2f(x) \Delta x^2} \\={(\nabla f(x) + \lambda A)^2\over \nabla^2f(x)} -{1\over2}{(\nabla f(x) + \lambda A)^2\over \nabla^2f(x)} \\ ={1\over2}{(\nabla f(x) + \lambda A)^2\over \nabla^2 f(x)} \\ =e(x,\lambda)^2$$

이때 수렴율이 어느 정도의 크기가 되면 최적점 부근에 이르렀다고 보고 업데이트를 정지하면 됩니다. 그 크기를 수렴 조건이라고 하고 다음과 같이 작성할 수 있습니다. $10e-4>e(x,\lambda)$

업데이트

수렴이 되지 않았다면 $x_{next} = x +\eta \Delta x$ 로 업데이트를 해주시고 다시 감소량 구하는 과정을 반복하면 됩니다.