등식 제약조건에서의 뉴턴방법 (Newton’s Method)

뉴턴방법(Newton's method)은 제약조건이 없는 최적화 문제에서 최적해를 이터레이션(iteration)으로 구하는 방법이었다. 하지만 뉴턴방법은 등식 제약조건을 갖는 최적화 문제로도 확장 적용될 수 있다.

 

 

등식 제약조건(equality constraints)을 갖는 컨벡스 최적화 문제(convex optimization problem)는 다음과 같다.

 

$$\begin{array}{r}\text{(1)}& & \underset{\mathbf{x}}{min}f(\mathbf{x})\\ & \text{subject to : }A\mathbf{x}=\mathbf{b}\end{array}$$

 

여기서 $\mathbf{x}\in {\mathbb{R}}^n$ 은 최적화 변수이고, $f(\mathbf{x})$ 는 컨벡스 함수로서 두번 미분가능하다고 가정한다. 그리고 $A\in {\mathbb{R}}^{p\times n}$ 이며, $rank(A)=p<n$ 이라고 가정한다. 이 가정은 제약조건의 개수가 최적화 변수의 개수보다 적어야 한다는 것을 의미한다.

 

 

위 최적화 문제의 KKT(Karush-Kuhn-Tucker) 식은 다음과 같다.

 

$$\begin{array}{r}\text{(2)}& & {\mathrm{\nabla }}_{\mathbf{x}}f(\mathbf{x})+A^T\lambda =0\\ & A\mathbf{x}-\mathbf{b}=0\end{array}$$

 

여기서 $\lambda \in {\mathbb{R}}^p$ 는 라그랑지 곱수이다. 식 (2)는 식 (1)의 필요충분조건으로서 식 (1)의 최적해를 구하는 것은 식 (2)의 해를 구하는 것과 같다.

뉴턴방법의 기본 개념대로 최적화 변수의 시작값(starting point) $\mathbf{x}$ 에서 식 (1)의 목적함수 $f(\mathbf{x})$ 를 2차 함수로 근사화하고 이 2차 근사 함수를 최소화해 보자.

 

$$\begin{array}{r}\text{(3)}& & \underset{\mathrm{\Delta }\mathbf{x}}{min}f(\mathbf{x}+\mathrm{\Delta }\mathbf{x})\approx f(\mathbf{x})+{\mathrm{\nabla }}_{\mathbf{x}}^{T}f(\mathbf{x})\mathrm{\Delta }\mathbf{x}+\frac{1}{2}\mathrm{\Delta }{\mathbf{x}}^T{\mathrm{\nabla }}_{\mathbf{x}}^{2}f(\mathbf{x})\mathrm{\Delta }\mathbf{x}\\ & \text{subject to : }A(\mathbf{x}+\mathrm{\Delta }\mathbf{x})=\mathbf{b}\end{array}$$

 

여기서 $\mathrm{\Delta }\mathbf{x}$ 를 뉴턴스텝(Newton step) 이라고 한다. 만약 시작값 $\mathbf{x}$ 가 등식 제약조건을 만족한다면, 또는 실현가능(feasible)하다면, $A\mathbf{x}-\mathbf{b}=0$ 가 되므로 식 (2)의 KKT 식은 다음과 같이 된다.

 

$$\begin{array}{r}\text{(4)}& & {\mathrm{\nabla }}_{\mathbf{x}}f(\mathbf{x})+{\mathrm{\nabla }}_{\mathbf{x}}^{2}f(\mathbf{x})\mathrm{\Delta }\mathbf{x}+A^T\lambda =0\\ & A\mathrm{\Delta }\mathbf{x}=0\end{array}$$

 

식 (4)의 두번째 식인 $A\mathrm{\Delta }\mathbf{x}=0$ 을 만족하는 $\mathrm{\Delta }\mathbf{x}$ 를 실현가능한 방향(feasible direction)을 갖는 뉴턴스텝이라고 한다. 식 (4)를 행렬과 벡터 형식으로 쓰면 다음과 같다.

 

$$\begin{array}{}\text{(5)}& \left[\begin{array}{cc}{\mathrm{\nabla }}_{\mathbf{x}}^{2}f(\mathbf{x})& A^T\\ A& 0\end{array}\right]\left[\begin{array}{c}\mathrm{\Delta }\mathbf{x}\\ \lambda \end{array}\right]=\left[\begin{array}{c}-{\mathrm{\nabla }}_{\mathbf{x}}f(\mathbf{x})\\ 0\end{array}\right]\end{array}$$

 

식 (5)를 KKT 시스템이라고 한다. 식 (5)의 해를 구하는 방법은 다음에 설명하기로 한다.

뉴턴감소량(Newton decrement)은 제약조건이 없는 뉴턴방법과 동일하게 주어지며

 

$$\begin{array}{}\text{(6)}& q(\mathbf{x})={(\mathrm{\Delta }{\mathbf{x}}^T{\mathrm{\nabla }}_{\mathbf{x}}^{2}f(\mathbf{x})\mathrm{\Delta }\mathbf{x})}^{\frac{1}{2}}\end{array}$$

 

최적해에 어느 정도 근접했는지 확인하는 척도로 사용할 수 있다.

등식 제약조건을 갖는 뉴턴방법을 정리하면 다음과 같다.

   0. $A\mathbf{x}-\mathbf{b}=0$ 을 만족하는 시작값 $\mathbf{x}$ 와 종료조건 값 $ϵ>0$ 을 설정한다.
   1. 다음을 반복한다.

      [1] 뉴턴스텝과 뉴턴감소량을 계산한다.
      [2] 뉴턴감소량이 종료조건 값 $ϵ$ 보다 작으면 이터레이션을 중지한다.
      [3] 스텝사이즈 $\eta$ 를 계산한다.
      [4] $\mathbf{x}$ 를 업데이트 한다.
               $\mathbf{x}\leftarrow \mathbf{x}+\eta \mathrm{\Delta }\mathbf{x}$

 

 

위 알고리즘의 단점은 시작값을 등식 제약조건을 만족하는 값으로 정해야 한다는 것이다. 이제 뉴턴방법을 더욱 확장시켜서 이러한 등식 제약조건을 만족시키지 않아도 되는 시작값에서 출발해도 되게 해보자. 이러한 방법을 실현가능하지 않은 시작값을 갖는(infeasible start) 뉴턴방법이라고 한다.

$A\mathbf{x}-\mathbf{b}\ne 0$ 이라면 식 (4)를 다음과 같이 수정하면 된다.

 

$$\begin{array}{r}\text{(7)}& & {\mathrm{\nabla }}_{\mathbf{x}}f(\mathbf{x})+{\mathrm{\nabla }}_{\mathbf{x}}^{2}f(\mathbf{x})\mathrm{\Delta }\mathbf{x}+A^T\lambda =0\\ & A\mathrm{\Delta }\mathbf{x}=\mathbf{b}-A\mathbf{x}\end{array}$$

 

이 경우에도 뉴턴스텝 $\mathrm{\Delta }\mathbf{x}$ 이 목적함수의 하강 방향(descent direction)을 가리키는지 확인해 보자. 즉 $\mathrm{\Delta }\mathbf{x}$ 이 $f(\mathbf{x}+\eta \mathrm{\Delta }\mathbf{x})<f(\mathbf{x})$ 가 되도록 만드는 어떤 스칼라 값 $\eta >0$ 이 존재하는지 알아보자. 그러기 위해서 $\varphi (\eta )=f(\mathbf{x}+\eta \mathrm{\Delta }\mathbf{x})$ 로 놓고 $\varphi$ 를 $\eta$ 로 미분한다.

 

$$\begin{array}{}\text{(8)}& {\varphi }^{\prime }(\eta )={\mathrm{\nabla }}_{\mathbf{x}}^{T}f(\mathbf{x})\mathrm{\Delta }\mathbf{x}+\eta \mathrm{\Delta }{\mathbf{x}}^T{\mathrm{\nabla }}_{\mathbf{x}}^{2}f(\mathbf{x})\mathrm{\Delta }\mathbf{x}+\cdots \end{array}$$

 

$\eta =0$ 에서 위 미분을 계산하면 식 (7)에 의해서 다음과 같이 된다.

 

$$\begin{array}{r}\text{(9)}& {\varphi }^{\prime }(0)& ={\mathrm{\nabla }}_{\mathbf{x}}^{T}f(\mathbf{x})\mathrm{\Delta }\mathbf{x}\\ & =-\mathrm{\Delta }{\mathbf{x}}^T({\mathrm{\nabla }}_{\mathbf{x}}^{2}f(\mathbf{x})\mathrm{\Delta }\mathbf{x}+A^T\lambda )\\ \\ & =-\mathrm{\Delta }{\mathbf{x}}^T{\mathrm{\nabla }}_{\mathbf{x}}^{2}f(\mathbf{x})\mathrm{\Delta }\mathbf{x}-(A\mathrm{\Delta }\mathbf{x}{)}^T\lambda \\ \\ & =-\mathrm{\Delta }{\mathbf{x}}^T{\mathrm{\nabla }}_{\mathbf{x}}^{2}f(\mathbf{x})\mathrm{\Delta }\mathbf{x}+(A\mathbf{x}-\mathbf{b}{)}^T\lambda \end{array}$$

 

식 (9)에 의하면 $A\mathbf{x}=\mathbf{b}$ 가 만족하지 않는 이상, 또는 $\mathbf{x}$ 가 실행가능(feasible)하지 않는 이상, ${\varphi }^{\prime }(0)<0$ 임을 보장하지 않는다. 따라서 뉴턴스텝 $\mathrm{\Delta }\mathbf{x}$ 이 목적함수의 하강 방향(descent direction)을 가리킨다고 말할 수 없다.

 

 

이제 관점을 바꾸어서 최적화 변수 $\mathbf{x}$ 와 라그랑지 곱수 $\lambda$ 를 모두 업데이트하는 방법을 생각해 보자. 식 (7)에서 $\lambda$ 를 $\lambda +\mathrm{\Delta }\lambda$ 로 치환하면 다음과 같이 된다.

 

$$\begin{array}{r}\text{(10)}& & {\mathrm{\nabla }}_{\mathbf{x}}f(\mathbf{x})+{\mathrm{\nabla }}_{\mathbf{x}}^{2}f(\mathbf{x})\mathrm{\Delta }\mathbf{x}+A^T(\lambda +\mathrm{\Delta }\lambda )=0\\ & A\mathrm{\Delta }\mathbf{x}=\mathbf{b}-A\mathbf{x}\end{array}$$

 

여기서 $\mathrm{\Delta }\lambda$ 를 듀얼스텝(dual step)이라고 한다. 이 경우 KKT 시스템은 다음과 같이 수정된다.

 

$$\begin{array}{}\text{(11)}& \left[\begin{array}{cc}{\mathrm{\nabla }}_{\mathbf{x}}^{2}f(\mathbf{x})& A^T\\ A& 0\end{array}\right]\left[\begin{array}{c}\mathrm{\Delta }\mathbf{x}\\ \mathrm{\Delta }\lambda \end{array}\right]=-\left[\begin{array}{c}{\mathrm{\nabla }}_{\mathbf{x}}f(\mathbf{x})+A^T\lambda \\ A\mathbf{x}-\mathbf{b}\end{array}\right]\end{array}$$

 

위 식의 오른쪽 항 벡터의 성분을 각각 듀얼 잔차(dual residual) ${\mathbf{r}}_{dual}$, 프라이멀 잔차(primal residual) ${\mathbf{r}}_{prim}$ 라고 한다.

 

$$\begin{array}{r}\text{(12)}& & {\mathbf{r}}_{dual}(\mathbf{x},\lambda )={\mathrm{\nabla }}_{\mathbf{x}}f(\mathbf{x})+A^T\lambda \\ & {\mathbf{r}}_{prim}(\mathbf{x},\lambda )=A\mathbf{x}-\mathbf{b}\end{array}$$

 

식 (2)에 의하면 잔차 벡터가 모두 $0$ 일 때 최적해를 얻을 수 있다.

이제 식 (11)로 계산한 뉴턴스텝 $\mathrm{\Delta }\mathbf{x}$ 와 듀얼스텝 $\mathrm{\Delta }\lambda$ 가 잔차 벡터의 크기가 $0$ 으로 작아지는 방향으로 업데이트가 되는지 확인해 보자. 여기서 잠시 표기를 간단하게 하기 위해서 $\mathbf{y}=\left[\begin{array}{c}\mathbf{x}\\ \lambda \end{array}\right]$, $\mathrm{\Delta }\mathbf{y}=\left[\begin{array}{c}\mathrm{\Delta }\mathbf{x}\\ \mathrm{\Delta }\lambda \end{array}\right]$, $\mathbf{r}(\mathbf{y})=\left[\begin{array}{c}{\mathbf{r}}_{dual}(\mathbf{y})\\ {\mathbf{r}}_{prim}(\mathbf{y})\end{array}\right]$ 로 쓴다. 잔차의 크기로서 2-놈(norm)을 사용한다. 그러면 이 문제는 뉴턴-듀얼스텝 $\mathrm{\Delta }\mathbf{y}$ 가 $\parallel \mathbf{r}(\mathbf{y}+\eta \mathrm{\Delta }\mathbf{y}){\parallel }_2<\parallel \mathbf{r}(\mathbf{y}){\parallel }_2$ 이 되도록 만드는 어떤 스칼라 값 $\eta >0$ 가 존재하는지 증명하는 문제와 동일하다.

먼저 $\mathbf{r}(\mathbf{y}+\mathrm{\Delta }\mathbf{y})$ 를 1차 테일러 시리즈로 전개하면 다음과 같다.

 

$$\begin{array}{}\text{(13)}& \mathbf{r}(\mathbf{y}+\mathrm{\Delta }\mathbf{y})\approx \mathbf{r}(\mathbf{y})+{\mathrm{\nabla }}_{\mathbf{y}}^T\mathbf{r}(\mathbf{y})\mathrm{\Delta }\mathbf{y}\end{array}$$

 

여기서 $\mathbf{r}(\mathbf{y}+\mathrm{\Delta }\mathbf{y})=0$ 으로 놓으면 식 (13)은 식 (11)과 동일한 식이다. 따라서 식 (14)로 계산되는 뉴턴-듀얼스텝 $\mathrm{\Delta }\mathbf{y}$ 는 식 (11)로 계산되는 뉴턴-듀얼스텝과 동일하다.

 

$$\begin{array}{}\text{(14)}& {\mathrm{\nabla }}_{\mathbf{y}}^T\mathbf{r}(\mathbf{y})\mathrm{\Delta }\mathbf{y}=-\mathbf{r}(\mathbf{y})\end{array}$$

 

이제 $\varphi (\eta )=\parallel \mathbf{r}(\mathbf{y}+\eta \mathrm{\Delta }\mathbf{y}){\parallel }_2^2$ 로 놓고 $\varphi$ 를 $\eta$ 로 미분한다.

 

$$\begin{array}{r}\text{(15)}& {\varphi }^{\prime }(\eta )& =2{\mathbf{r}}^T(\mathbf{y}){\mathrm{\nabla }}_{\mathbf{y}}^T\mathbf{r}(\mathbf{y})\mathrm{\Delta }\mathbf{y}+\eta {\mathbf{r}}^T(\mathbf{y})\mathrm{\Delta }{\mathbf{y}}^T{\mathrm{\nabla }}_{\mathbf{y}}^2\mathbf{r}(\mathbf{y})\mathrm{\Delta }\mathbf{y}\\ & +2\eta \mathrm{\Delta }{\mathbf{y}}^T{\mathrm{\nabla }}_{\mathbf{y}}\mathbf{r}(\mathbf{y}){\mathrm{\nabla }}_{\mathbf{y}}^T\mathbf{r}(\mathbf{y})\mathrm{\Delta }\mathbf{y}+\cdots \end{array}$$

 

$\eta =0$ 에서 위 미분을 계산하면 식 (14)에 의해서 다음과 같이 된다.

 

$$\begin{array}{r}\text{(16)}& {\varphi }^{\prime }(0)& =2{\mathbf{r}}^T(\mathbf{y}){\mathrm{\nabla }}_{\mathbf{y}}^T\mathbf{r}(\mathbf{y})\mathrm{\Delta }\mathbf{y}\\ & =-2{\mathbf{r}}^T(\mathbf{y})\mathbf{r}(\mathbf{y})<0\end{array}$$

 

식 (16)에 의하면 결국 $\varphi (\eta )<\varphi (0)$ 이 되는 $\eta$ 가 존재한다는 것이며 이는 어떤 $\eta >0$ 에 대해서 다음 부등식이 성립함을 의미한다.

 

$$\begin{array}{}\text{(17)}& \parallel \mathbf{r}(\mathbf{y}+\eta \mathrm{\Delta }\mathbf{y}){\parallel }_2<\parallel \mathbf{r}(\mathbf{y}){\parallel }_2\end{array}$$

 

지금까지의 논의를 종합하여 실현가능하지 않은 시작값을 갖는(infeasible start) 뉴턴방법을 정리하면 다음과 같다.

   0. 시작값 $\mathbf{x}$ 와 종료조건 값 $ϵ>0$ 을 설정한다.
   1. $A\mathbf{x}=\mathbf{b}$ 와 $\parallel \mathbf{r}(\mathbf{x},\lambda ){\parallel }_2\le ϵ$ 가 성립할 때까지 다음을 반복한다

      [1] 뉴턴스텝 $\mathrm{\Delta }\mathbf{x}$ 와 듀얼스텝 $\mathrm{\Delta }\lambda$ 를 계산한다.
      [2] 스텝사이즈 $\eta$ 를 계산한다.
      [3] $\mathbf{x}$ 와 $\lambda$ 를 업데이트 한다.
               $\mathbf{x}\leftarrow \mathbf{x}+\eta \mathrm{\Delta }\mathbf{x}$,    $\lambda \leftarrow \lambda +\eta \mathrm{\Delta }\lambda$

 

 

한가지 재미있는 사실은 스텝사이즈 $\eta =1$ 이라면 식 (7)에 의해서 $A(\mathbf{x}+\mathrm{\Delta }\mathbf{x})=\mathbf{b}$ 가 성립하여 그 다음 이터레이션에서는 $\mathbf{x}$ 가 실현가능한 영역에 진입한다는 것이다. 그리고 그 이후부터는 스텝사이즈에 관계없이 $\mathbf{x}$ 가 계속 실현가능한 영역에 머문다. 그러면 위 알고리즘 대신에 앞서 논의했던 등식 제약조건을 만족하는 뉴턴방법을 사용해도 된다.

스텝사이즈 $\eta$ 는 백트래킹 라인 서치(backtracking line search) 알고리즘을 사용하여 계산한다. 이에 대한 자세한 내용은 다음에 설명하기로 한다.

   0. $\alpha \in (0,1/2),\beta \in (0,1)$ 을 설정한다.
   1. $\eta =1$
   2. 다음을 반복한다.

      [1] $\parallel \mathbf{r}(\mathbf{x}+\eta \mathrm{\Delta }\mathbf{x},\lambda +\eta \mathrm{\Delta }\lambda ){\parallel }_2\le (1-\alpha \eta )\parallel \mathbf{r}(\mathbf{x},\lambda ){\parallel }_2$ 이면 이터레이션을 종료한다.
      [2] $\eta \leftarrow \beta \eta$