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

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

 

\[ \begin{align} & \min_{\mathbf{x}}⁡ f(\mathbf{x}) \tag{1} \\ \\ & \mbox{subject to : } \ \ g_i (\mathbf{x}) \le 0, \ \ i=1, ...,m \\ \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ A \mathbf{x}=\mathbf{b} \end{align} \]

 

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

 

\[ \begin{align} & \nabla_{\mathbf{x}} f(\mathbf{x})+ \sum_{i=1}^m \mu_i \nabla_{\mathbf{x}} g_i (\mathbf{x}) +A^T \lambda=0 \tag{2} \\ \\ & g_i (\mathbf{x}) \le 0, \ \ i=1, ..., m \tag{3} \\ \\ & A \mathbf{x}=\mathbf{b} \tag{4} \\ \\ & \mu_i \ge 0, \ \ i=1, ..., m \tag{5} \\ \\ & \mu_i g_i (\mathbf{x})= - \frac{1}{t}, \ \ t \gt 0, \ \ i=1, ..., m \tag{6} \end{align} \]

 

여기서 \(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)\) 를 정의한다.

 

\[ \mathbf{r}_t (\mathbf{x}, \mu, \lambda) = \begin{bmatrix} \nabla_{\mathbf{x}} f(\mathbf{x})+ \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{bmatrix} \tag{7} \]

 

여기서

 

\[ \mathbf{g}(\mathbf{x})= \begin{bmatrix} g_1 (\mathbf{x}) \\ \vdots \\ g_m(\mathbf{x}) \end{bmatrix}, \ \ \mu= \begin{bmatrix} \mu_1 \\ \vdots \\ \mu_m \end{bmatrix}, \ \ \mathbf{diag} (\mu)= \begin{bmatrix} \mu_1 & & 0 \\ & \ddots & \\ 0 & & \mu_m \end{bmatrix} \]

 

이다. 그러면 잔차 벡터가 모두 \(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}) \lt 0\), \(\mu \gt 0\) 이 만족되도록 해야 한다는 것이다.

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

 

\[ \mathbf{ r}_t (\mathbf{y}+ \Delta \mathbf{y}) \approx \mathbf{r}_t (\mathbf{y})+ \nabla_{\mathbf{y}}^T \mathbf{r}_t (\mathbf{y}) \Delta \mathbf{y} \tag{8} \]

 

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

 

\[ \nabla_{\mathbf{y}}^T \mathbf{r}_t (\mathbf{y}) \Delta \mathbf{y} = - \mathbf{r}_t (\mathbf{y}) \tag{9} \]

 

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

 

\[ \begin{align} & \begin{bmatrix} \nabla_{\mathbf{x}}^2 f(\mathbf{x})+ \sum_{i=1}^m \mu_i \nabla_{\mathbf{x}}^2 g_i (\mathbf{x}) & \nabla_{\mathbf{x}}^T \mathbf{g}(\mathbf{x}) & A^T \\ -\mathbf{diag}(\mu) \nabla_{\mathbf{x}} \mathbf{g}(\mathbf{x}) & -\mathbf{diag}(\mathbf{g}(\mathbf{x})) & 0 \\ A & 0 & 0 \end{bmatrix} \begin{bmatrix} \Delta \mathbf{x} \\ \Delta \mu \\ \Delta \lambda \end{bmatrix} \tag{10} \\ \\ & \ \ \ \ \ \ \ \ \ \ = \begin{bmatrix} \nabla_{\mathbf{x}} f(\mathbf{x})+ \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{bmatrix} \end{align} \]

 

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

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

 

\[ \hat{\kappa}(\mathbf{x}, \mu)= - \mathbf{g}(\mathbf{x})^T \mu \tag{11} \]

 

여기서 \(\mathbf{x}\) 는 \( \mathbf{g}(\mathbf{x}) \lt 0\) 과 \(\mu \gt 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\) 를 계산할 수 있다.

 

\[ t= \frac{m}{\hat{\kappa}} \tag{12} \]

 

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

 

 

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

     1. 다음을 반복한다.

         [1] \(t\) 를 계산한다.

                     \( t \gets \gamma t = \gamma \frac{ m}{\hat{\kappa}} \)

         [2] \(\Delta \mathbf{y}\) 를 계산한다.

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

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

                     \(\mathbf{y} \gets \mathbf{y}+ \eta \Delta \mathbf{y} \)

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

                     \( \parallel \mathbf{r}_{prim} \parallel_2 \le \epsilon_{feas}\),   \(\parallel \mathbf{r}_{dual} \parallel_2 \le \epsilon_{feas}\),   \(\hat{\kappa} \le \epsilon\)

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

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

 

\[ \eta_{max} = \max⁡ \{ \eta \in [0, 1] \ | \ \mu + \eta \Delta \mu \gt 0 \} \tag{13} \]

 

그런 후 \(\eta =0.99 \eta_{max}\) 에서부터 시작하여 \(\mathbf{g}(\mathbf{x}) \lt 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 \Delta \mathbf{x}, \mu + \eta \Delta \mu, \lambda + \eta \Delta \lambda) \parallel_2 \le (1-\alpha \eta ) \parallel \mathbf{r}(\mathbf{x}, \mu, \lambda) \parallel_2\) 이면 이터레이션을 종료한다.

         [2] \(\eta \gets \beta \eta\)

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