장벽 내부점 방법 (Barrier 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 수정식이나 지시함수(indicator function)를 이용하면 다음과 같이 등식 제약조건만을 갖는 컨벡스 최적화 문제로 근사화할 수 있다.

 

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

 

 

 

여기서 $t$ 는 KKT식의 근사화 파라미터이고, $\varphi (\mathbf{x})$ 는 로그 장벽함수(log barrier)이며 다음과 같이 주어진다.

 

$$\begin{array}{}\text{(3)}& \varphi (\mathbf{x})=-\sum _{i=1}^m\log (-g_i(\mathbf{x}))\end{array}$$

 

위 최적화 문제에서는 다음 조건을 만족하는 어떤 $\tilde{\mathbf{x}}$ 가 존재한다고 가정한다. 이 가정이 성립하는 식 (1)의 문제를 엄격한 의미의 실현가능(strictly feasible)한 문제라고 한다.

 

$$\begin{array}{r}\text{(4)}& & g_i(\tilde{\mathbf{x}})<0,i=1,...,m\\ & A\tilde{\mathbf{x}}=\mathbf{b}\end{array}$$

 

식 (2)에서 $t$ 를 고정시키면 등식 제약조건을 갖는 최적화 문제가 되므로 뉴턴방법(Newton's method)을 이용해서 풀 수 있다. 하지만 $t$ 가 클수록 함수 $f(\mathbf{x})+\frac{1}{t}\varphi (\mathbf{x})$ 의 경계 지역에서 헤시안(Hessian)이 급격히 변하기 때문에 뉴턴방법을 바로 적용하기는 어렵다. 따라서 처음에는 작은 $t$ 값을 이용하여 문제를 푼 후 점차 $t$ 를 키워 나가는 방법을 취한다. 이렇게 하면 뉴턴방법을 사용할 때 이전 $t$ 값으로 구한 해를 다음 단계의 초기값으로 설정할 수 있기 때문에 수치 계산을 빠르고 효율적으로 할 수 있다.

이와 같이 최적화 문제 (1)을 (2)로 근사화 한 후, 작은 $t$ 에서 시작하여 점차 $t$ 를 증가시키면서 순차적으로 최적해를 구해 나가는 방법을 장벽 내부점 방법 (barrier interior-point method)이라고 한다. 이 때 특정 $t$ 값에서 최적해 ${\mathbf{x}}^{\star }(t)$ 를 구하는 과정을 센터링(centering)이라고 하고, 해를 중심점(central point)이라고 하며, $t$ 값의 변화에 대한 최적해의 경로 ${\mathbf{x}}^{\star }(t),t>0$ 를 중심경로(central path)라고 한다.

 

 

장벽 내부점 방법은 내부 이터레이션과 외부 이터레이션 등 두 개의 이터레이션(iteration) 루프로 구성된다. 내부 이터레이션은 특정 $t$ 값에서 뉴턴방법을 사용하기 때문에, 외부 이터레이션은 $t$ 를 증가시키면서 최적해를 찾아 나가기 때문에 필요한 것이다.

이러한 내부와 외부 이터레이션을 한 개의 이터레이션으로 통합한 알고리즘이 있는데 이에 대해서는 다음에 설명하기로 한다.

그렇다면 특정 $t$ 에서 구한 최적값 $f({\mathbf{x}}^{\star }(t))$ 와 식 (1)의 최적값 $p^{\star }$ 의 차이는 어떻게 계산할 수 있을까. $t$ 값의 증가를 어딘가에서 멈추려면 이 값을 아는 것이 중요하다. $f({\mathbf{x}}^{\star }(t))-p^{\star }$ 를 계산하기 위해서, 식 (1)의 라그랑지안 (Lagrangian) 부터 시작한다.

 

$$\begin{array}{}\text{(5)}& L(\mathbf{x},\mu ,\lambda )=f(\mathbf{x})+\sum _{i=1}^m{\mu }_i{g}_i(\mathbf{x})+{\lambda }^T(A\mathbf{x}-\mathbf{b})\end{array}$$

 

이에 대한 라그랑지 듀얼 함수(Lagrange dual function)는 다음과 같다.

 

$$\begin{array}{r}\text{(6)}& d(\mu ,\lambda )& =\underset{\mathbf{x}}{min}L(\mathbf{x},\mu ,\lambda )\\ & =\underset{\mathbf{x}}{min}(f(\mathbf{x})+\sum _{i=1}^m{\mu }_i{g}_i(\mathbf{x})+{\lambda }^T(A\mathbf{x}-\mathbf{b}))\end{array}$$

 

⁡ 여기서 $A\mathbf{x}=\mathbf{b}$ 이고 KKT 수정식에서는 ${\mu }_i=-\frac{1}{t{g}_i(\mathbf{x})}$ 이기 때문에 위 식에 대입하면 다음과 같이 된다.

 

$$\begin{array}{r}\text{(7)}& d(\mu (t),\lambda (t))& =\underset{\mathbf{x}}{min}(f(\mathbf{x}(t))-\frac{1}{t}\sum _{i=1}^{m}1)\\ & =f({\mathbf{x}}^{\star }(t))-\frac{m}{t}\end{array}$$

 

⁡ 식 (7)에 의하면 특정 $t$ 에서 듀얼리티 갭(duality gap)은 $\frac{m}{t}$ 임을 알 수 있다. 라그랑지 듀얼 함수는 프라이멀 최적화 문제의 해 $p^{\star }$ 보다 항상 같거나 작기 때문에 모든 $t>0$ 에 대해서 다음 부등식이 성립한다.

 

$$\begin{array}{}\text{(8)}& d(\mu (t),\lambda (t))=f({\mathbf{x}}^{\star }(t))-\frac{m}{t}\le p^{\star }\end{array}$$

 

식 (8)에 의하면 $f({\mathbf{x}}^{\star }(t))-p^{\star }$ 는 다음과 같게 되므로 $t\to \mathrm{\infty }$ 일수록 ${\mathbf{x}}^{\star }(t)$ 는 최적해에 근접해 나가는 것을 알 수 있다.

 

$$\begin{array}{}\text{(9)}& f({\mathbf{x}}^{\star }(t))-p^{\star }\le \frac{m}{t}\end{array}$$

 

식 (9)에서 $\frac{m}{t}$ 이 일정값 이하로 작아지면 최적해에 거의 근접했다는 신호로 볼 수 있으므로 $t$ 에 대한 이테레이션을 멈출 수 있다.

 

 

장벽 내부점 방법을 정리하면 다음과 같다.

    0. 시작값 $\mathbf{x}$ 와 KKT식 근사화 파라미터 $t$ 의 초기값, 파라미터 종료조건 값 $ϵ>0$, 스텝사이즈 $\gamma >1$ 을 설정한다.

    1. 다음을 반복한다.

        [1] 다음 최적화 문제를 등식제약 뉴턴방법으로 푼다.

                $\underset{\mathbf{x}}{min}tf(\mathbf{x})-\sum _{i=1}^m\log (-g_i(\mathbf{x}))$
                $\text{subject to : }A\mathbf{x}=\mathbf{b}$

        [2] $\mathbf{x}$ 를 업데이트 한다.

        [3] 다음 값이 종료조건 값 $ϵ$ 보다 작으면 이터레이션을 중지한다.

                $\frac{m}{t}\le ϵ$

        [4] $t$ 를 업데이트 한다.

                $t\leftarrow \gamma t$

위 알고리즘에서 [1]에서 시작값 $\mathbf{x}$ 가 등식 제약조건을 $A\mathbf{x}=\mathbf{b}$ 를 만족하느냐 못하느냐에 따라서 표준 등식제약 뉴턴방법이나 infeasible-start 뉴턴방법을 선택한다. 여기서 중요한 것은 중심점 ${\mathbf{x}}^{\star }(t)$ 는 정확도가 높을 필요가 없다는 점이다. ${\mathbf{x}}^{\star }(t)$ 는 최종적인 최적해로 접근에 나가는 과정에서 나타나는 해에 불과하기 때문이다.

장벽 내부점 방법에서 중요한 것은 시작값 $\mathbf{x}$ 를 다음과 같이 부등식 제약조건을 만족하도록 정하는데 있다.

 

$$\begin{array}{}\text{(10)}& g_i(\mathbf{x})<0,i=1,...,m\end{array}$$

 

이에 대해서 많이 사용되는 방법은 다음과 같은 최적화 문제의 최적해를 구하는 것이다.

 

$$\begin{array}{r}\text{(11)}& & s^{\star }=\underset{(\mathbf{x},s)}{min}s\\ & \text{subject to : }{g}_i(\mathbf{x})\le s,i=1,...,m\end{array}$$

 

만약 $s^{\star }<0$ 이면 식 (10)의 조건을 만족하는 $\mathbf{x}$ 를 구한 것이다. 이 때도 최적해 $s^{\star }$ 의 정확도가 높을 필요는 없고 $g_i(\mathbf{x})<0$ 의 조건만 만족할 정도면 충분하다.