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

 

\[ \begin{align} & \min_{\mathbf{x}}⁡ \ f(\mathbf{x}) + \frac{1}{t} \phi (\mathbf{x}) \tag{2} \\ \\ & \mbox{subject to : } \ \ A\mathbf{x}=\mathbf{b} \end{align} \]

 

 

 

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

 

\[ \phi (\mathbf{x})= - \sum_{i=1}^m \log⁡(-g_i (\mathbf{x})) \tag{3} \]

 

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

 

\[ \begin{align} & g_i (\tilde{\mathbf{x}} ) \lt 0, \ \ i=1, ...,m \tag{4} \\ \\ & A \tilde{\mathbf{x}}= \mathbf{b} \end{align} \]

 

식 (2)에서 \(t\) 를 고정시키면 등식 제약조건을 갖는 최적화 문제가 되므로 뉴턴방법(Newton's method)을 이용해서 풀 수 있다. 하지만 \(t\) 가 클수록 함수 \(f(\mathbf{x})+\frac{1}{t} \phi (\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 \gt 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) 부터 시작한다.

 

\[ 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}) \tag{5} \]

 

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

 

\[ \begin{align} d(\mu, \lambda) &= \min_{\mathbf{x}} ⁡L(\mathbf{x}, \mu, \lambda) \tag{6} \\ \\ &= \min_{\mathbf{x}} \left( f(\mathbf{x})+ \sum_{i=1}^m \mu_i g_i (\mathbf{x}) + \lambda^T (A\mathbf{x}-\mathbf{b}) \right) \end{align} \]

 

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

 

\[ \begin{align} d(\mu (t), \lambda (t)) &= \min_{\mathbf{x}} \left( f(\mathbf{x}(t)) -\frac{1}{t} \sum_{i=1}^m 1 \right) \tag{7} \\ \\ &= f(\mathbf{x}^\star (t)) - \frac{m}{t} \end{align} \]

 

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

 

\[ d(\mu (t), \lambda (t)) = f(\mathbf{x}^\star (t)) - \frac{m}{t} \le p^\star \tag{8} \]

 

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

 

\[ f(\mathbf{x}^\star (t)) - p^\star \le \frac{m}{t} \tag{9} \]

 

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

 

 

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

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

    1. 다음을 반복한다.

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

                \( \min_{\mathbf{x}} \ tf(\mathbf{x})- \sum_{i=1}^m \log⁡(-g_i (\mathbf{x})) \)
                \( \mbox{subject to : } \ \ A\mathbf{x}=\mathbf{b} \)

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

        [3] 다음 값이 종료조건 값 \( \epsilon\) 보다 작으면 이터레이션을 중지한다.

                \( \frac{m}{t} \le \epsilon \)

        [4] \(t\) 를 업데이트 한다.

                \( t \gets \gamma t \)

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

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

 

\[ g_i (\mathbf{x}) \lt 0, \ \ i=1, ..., m \tag{10} \]

 

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

 

\[ \begin{align} & s^\star = \min_{ ( \mathbf{x}, s )}⁡ s \tag{11} \\ \\ & \mbox{subject to : } \ \ g_i (\mathbf{x}) \le s, \ \ i=1, ..., m \end{align} \]

 

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