프라이멀-듀얼 내부점 방법 (Primal-Dual Interior-Point Method)

제약조건이 있는 컨벡스(convex) 최적화 문제에 대해서

 

$$\begin{array}{r}\text{(1)}& & \underset{\mathbf{x}}{min}f(\mathbf{x})\\ & \text{subject to : }{g}_i(\mathbf{x})\le 0,i=1,...,m\\ \\ & A\mathbf{x}=\mathbf{b}\end{array}$$

 

KKT(Karush-Kuhn-Tucker) 수정식은 다음과 같다.

 

$$\begin{array}{r}\text{(2)}& & {\mathrm{\nabla }}_{\mathbf{x}}f(\mathbf{x})+\sum _{i=1}^m{\mu }_i{\mathrm{\nabla }}_{\mathbf{x}}{g}_i(\mathbf{x})+A^T\lambda =0\\ \text{(3)}& & g_i(\mathbf{x})\le 0,i=1,...,m\\ \text{(4)}& & A\mathbf{x}=\mathbf{b}\\ \text{(5)}& & {\mu }_i\ge 0,i=1,...,m\\ \text{(6)}& & {\mu }_i{g}_i(\mathbf{x})=-\frac{1}{t},t>0,i=1,...,m\end{array}$$

 

여기서 $t$ 는 KKT 식을 수정식으로 바꾸기 위한 파라미터이다.

 

 

장벽 내부점 방법(barrier interior-point method)에서는 식 (6)을 (2)에 대입하였다. 그러면 식 (3)과 (5)가 자동으로 만족되는 로그 장벽함수가 되었다.

반면에 프라이얼-듀얼 내부점 방법(primal-dual interior-point method)에서는 식 (2), (4), (6)을 뉴턴방법(Newton's method)을 이용하여 직접 푸는 방식을 택한다.

 

 

우선 다음과 같은 잔차(residual) 벡터 ${\mathbf{r}}_t(\mathbf{x},\mu ,\lambda )$ 를 정의한다.

 

$$\begin{array}{}\text{(7)}& {\mathbf{r}}_t(\mathbf{x},\mu ,\lambda )=\left[\begin{array}{c}{\mathrm{\nabla }}_{\mathbf{x}}f(\mathbf{x})+{\mathrm{\nabla }}_{\mathbf{x}}^T\mathbf{g}(\mathbf{x})\mu +A^T\lambda \\ -\mathbf{diag}(\mu )\mathbf{g}(\mathbf{x})-\frac{1}{t}\mathbf{1}\\ A\mathbf{x}-\mathbf{b}\end{array}\right]\end{array}$$

 

여기서

 

$$\mathbf{g}(\mathbf{x})=\left[\begin{array}{c}{g}_1(\mathbf{x})\\ ⋮\\ g_m(\mathbf{x})\end{array}\right],\mu =\left[\begin{array}{c}{\mu }_1\\ ⋮\\ {\mu }_m\end{array}\right],\mathbf{diag}(\mu )=\left[\begin{array}{ccc}{\mu }_1& & 0\\ & \ddots & \\ 0& & {\mu }_m\end{array}\right]$$

 

이다. 그러면 잔차 벡터가 모두 $0$ 일 때 식 (2), (4), (6)이 만족된다. 식 (7)의 첫번째 벡터 성분을 듀얼 잔차(dual residual) ${\mathbf{r}}_{dual}$, 두번째 벡터 성분을 중심성 잔차(centrality residual) ${\mathbf{r}}_{cent}$, 세번째 벡터 성분을 프라이멀 잔차(primal residual) ${\mathbf{r}}_{prim}$ 라고 한다.

이제 ${\mathbf{r}}_t(\mathbf{x},\mu ,\lambda )=0$ 을 뉴턴방법을 이용하여 풀어보자. 이 때 주의할 점은 뉴턴방법의 매 이터레이션 단계에서 $g(\mathbf{x})<0$, $\mu >0$ 이 만족되도록 해야 한다는 것이다.

여기서 잠시 표기를 간단하게 하기 위해서 $\mathbf{y}=\left[\begin{array}{c}\mathbf{x}\\ \mu \\ \lambda \end{array}\right]$, $\mathrm{\Delta }\mathbf{y}=\left[\begin{array}{c}\mathrm{\Delta }\mathbf{x}\\ \mathrm{\Delta }\mu \\ \mathrm{\Delta }\lambda \end{array}\right]$, ${\mathbf{r}}_t(\mathbf{y})=\left[\begin{array}{c}{\mathbf{r}}_{dual}(\mathbf{y})\\ {\mathbf{r}}_{cent}(\mathbf{y})\\ {\mathbf{r}}_{prim}(\mathbf{y})\end{array}\right]$ 로 쓴다. 그리고 ${\mathbf{r}}_t(\mathbf{y}+\mathrm{\Delta }\mathbf{y})$ 를 1차 테일러 시리즈로 전개하면 다음과 같다.

 

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

 

뉴턴방법에 의하면 $\mathbf{r}(\mathbf{y}+\mathrm{\Delta }\mathbf{y})=0$ 으로 만드는 $\mathrm{\Delta }\mathbf{y}$ 값을 구해야 한다.

 

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

 

위 식을 다시 풀어 쓰면 다음과 같다.

 

$$\begin{array}{r}\text{(10)}& & \left[\begin{array}{ccc}{\mathrm{\nabla }}_{\mathbf{x}}^{2}f(\mathbf{x})+\sum _{i=1}^m{\mu }_i{\mathrm{\nabla }}_{\mathbf{x}}^2{g}_i(\mathbf{x})& {\mathrm{\nabla }}_{\mathbf{x}}^T\mathbf{g}(\mathbf{x})& A^T\\ -\mathbf{diag}(\mu ){\mathrm{\nabla }}_{\mathbf{x}}\mathbf{g}(\mathbf{x})& -\mathbf{diag}(\mathbf{g}(\mathbf{x}))& 0\\ A& 0& 0\end{array}\right]\left[\begin{array}{c}\mathrm{\Delta }\mathbf{x}\\ \mathrm{\Delta }\mu \\ \mathrm{\Delta }\lambda \end{array}\right]\\ & =\left[\begin{array}{c}{\mathrm{\nabla }}_{\mathbf{x}}f(\mathbf{x})+{\mathrm{\nabla }}_{\mathbf{x}}^T\mathbf{g}(\mathbf{x})\mu +A^T\lambda \\ -\mathbf{diag}(\mu )\mathbf{g}(\mathbf{x})-\frac{1}{t}\mathbf{1}\\ A\mathbf{x}-\mathbf{b}\end{array}\right]\end{array}$$

 

프라이멀-듀얼 내부점 방법에서는 식 (10)을 사용하여 뉴턴스텝 $\mathrm{\Delta }\mathbf{x}$ 와 중심성스텝 $\mathrm{\Delta }\mu$, 듀얼스텝 $\mathrm{\Delta }\lambda$ 를 잔차 벡터가 $0$ 이 될 때까지 업데이트 한다.

그렇다면 특정 $t$ 에서 구한 최적값 $f({\mathbf{x}}^{\star }(t))$ 와 식 (1)의 최적값 $p^{\star }$ 의 차이는 어떻게 계산할 수 있을까. 이터레이션을 어딘가에서 멈추려면 이 값을 아는 것이 중요하다. 장벽방법에서는 이 값이 듀얼리티 갭(duality gap) $\frac{m}{t}$ 이었다. 하지만 장벽방법과는 다르게 프라이멀-듀얼 방법에서는 이터레이션 단계에서 $\mathbf{x},\mu ,\lambda$ 값이 실현가능(feasible)하다는 보장이 없으므로 듀얼리티 갭을 계산하기가 쉽지 않다. 대신 아래 식으로 표현되는 대체(surrogate) 듀얼리티 갭을 사용한다.

 

$$\begin{array}{}\text{(11)}& \hat{\kappa }(\mathbf{x},\mu )=-\mathbf{g}(\mathbf{x}{)}^T\mu \end{array}$$

 

여기서 $\mathbf{x}$ 는 $\mathbf{g}(\mathbf{x})<0$ 과 $\mu >0$ 의 조건을 만족해야 한다. 만약 $A\mathbf{x}=\mathbf{b}$ 이고 ${\mu }_i=-\frac{1}{t{g}_i(\mathbf{x})}$ 이라면 식 (11)은 듀얼리티 갭 $\frac{m}{t}$ 과 일치한다. 이를 이용하면 대체 듀얼리티 갭 $\hat{\kappa }$ 가 듀얼리티 갭인 $\frac{m}{t}$ 과 일치하도록 파라미터 $t$ 를 계산할 수 있다.

 

$$\begin{array}{}\text{(12)}& t=\frac{m}{\hat{\kappa }}\end{array}$$

 

이처럼 $t$ 를 계산하면 $t$ 에 대한 이터레이션 루프가 필요 없어지고 뉴턴방법에 의한 이터레이션만 남게 된다. 프라이멀-듀얼 내부점 방법을 정리하면 다음과 같다.

 

 

     0. $\mathbf{g}(\mathbf{x})<0$ 인 시작값 $\mathbf{x}$ 와 $\mu >0$, 파라미터 종료조건 값 $ϵ>0$, ${ϵ}_{feas}>0$, $t$ 의 증가팩터 $\gamma >1$ 을 설정한다.

     1. 다음을 반복한다.

         [1] $t$ 를 계산한다.

                     $t\leftarrow \gamma t=\gamma \frac{m}{\hat{\kappa }}$

         [2] $\mathrm{\Delta }\mathbf{y}$ 를 계산한다.

         [3] 스텝사이즈 $\eta$ 를 계산한다.

         [4] $\mathbf{y}$ 를 업데이트 한다.

                     $\mathbf{y}\leftarrow \mathbf{y}+\eta \mathrm{\Delta }\mathbf{y}$

         [5] 다음 종료조건을 모두 만족하면 이터레이션을 중지한다.

                     $\parallel {\mathbf{r}}_{prim}{\parallel }_2\le {ϵ}_{feas}$,   $\parallel {\mathbf{r}}_{dual}{\parallel }_2\le {ϵ}_{feas}$,   $\hat{\kappa }\le ϵ$

프라이멀-듀얼 내부점 알고리즘에서 [1]은 파라미터 $t$ 를 증가시키기 위한 것으로 장벽방법에서도 사용되는 업데이트 방식이다. 알고리즘 [5]의 종료조건은 프라이멀과 듀얼 잔차 벡터의 크기가 모두 $0$ 에 근접하고 대체 듀얼리티 갭이 미리 설정한 값 이하로 작아질 때이다.

알고리즘 [3]의 스텝사이즈 계산은 $\mathbf{g}(\mathbf{x})<0$ 과 $\mu >0$ 이 성립할 수 있도록 표준 백트래킹 라인서치(backtracking line search) 방법을 수정해서 사용한다. 먼저 $\mu +\eta \mathrm{\Delta }\mu >0$ 이 되도록 크기가 $1$ 이내인 범위에서 $\eta$ 의 최대값을 구한다.

 

$$\begin{array}{}\text{(13)}& {\eta }_{max}=max\{\eta \in [0,1]|\mu +\eta \mathrm{\Delta }\mu >0\}\end{array}$$

 

그런 후 $\eta =0.99{\eta }_{max}$ 에서부터 시작하여 $\mathbf{g}(\mathbf{x})<0$ 이 얻어질 때까지 $\beta \in (0,1)$ 를 $\eta$ 에 곱한다. 그리고 나서 다음과 같은 표준 백트래킹 라인서치 방법을 사용한다.

     0. $\alpha \in (0.01,0.1),\beta \in (0,1)$ 을 설정한다.

     1. 다음을 반복한다.

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

         [2] $\eta \leftarrow \beta \eta$

프라이멀-듀얼 내부점 방법의 장점은 이터레이션 루프가 1개라는 것이다. 뿐만 아니라 LP, QP, SOCP(second-order cone programming), SDP(semidefinite programming) 문제에서는 장벽방법의 성능을 훨씬 능가한다고 한다.