내부점 방법 (Interior-Point Method)의 개념

다음 사진은 내부점 방법(interior-point method)에 대해서 1984년 11월 19일에 뉴욕 타임즈지에 실린 기사를 캡쳐한 것이다. 기사 제목은 'Breakthrough in Problem Solving'이다. 전문적인 수학 알고리즘에 대해서 과학 전문지도 아닌 일반 신문에 기사화되는 일은 매우 드문데, 그만큼 내부점 방법의 중요성을 말해주는 것 같다.

 

 

그럼 최적화 이론에서 혁명적인 방법으로 일컬어지는 내부점 방법에 대해서 알아보도록 하자.

 

 

내부점 방법은 기본적으로 KKT조건식의 해를 구하기 위한 방법이다. 하지만 KKT 조건식을 직접 푸는 대신 조금 수정한 식을 풀어서 점근적으로 최적해를 찾아가는 방법을 택했다. 제약조건이 있는 컨벡스(convex) 최적화 문제에 대해서

 

$$\begin{array}{r}\text{(1)}& & \underset{\mathbf{x}\in {\mathbb{R}}^n}{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\\ & A\mathbf{x}=\mathbf{b}\\ \\ \text{(4)}& & {\mu }_i\ge 0,i=1,...,m\\ \text{(5)}& & {\mu }_i{g}_i(\mathbf{x})=0,i=1,...,m\end{array}$$

 

내부점 방법에서는 KKT 조건식 중 마지막 식 (5)를 다음과 같이 살짝 수정한 버전을 푼다.

 

$$\begin{array}{}\text{(6)}& {\mu }_i{g}_i(\mathbf{x})=-\frac{1}{t},t>0,i=1,...,m\end{array}$$

 

여기서 $t$ 는 KKT 수정식으로 KKT 식을 근사화하기 위한 파라미터이다. 식 (5)와 (6)을 비교해 보면 $t\to \mathrm{\infty }$ 일 수록 KKT 수정식은 원래 KKT 식과 점점 같아지므로 KKT 수정식으로 구한 해도 원래의 KKT 식에서 구한 최적해에 점점 근접해진다는 것을 알 수 있다.

KKT 수정식은 KKT 식을 살짝 바꾼 것에 불과하지만 그 영향은 매우 크다. 식 (6)을 (2)에 대입해 보자. 그러면 식 (2)는 다음과 같이 된다.

 

$$\begin{array}{}\text{(7)}& {\mathrm{\nabla }}_{\mathbf{x}}f(\mathbf{x})-\frac{1}{t}\sum _{i=1}^m\frac{1}{g_i(\mathbf{x})}{\mathrm{\nabla }}_{\mathbf{x}}{g}_i(\mathbf{x})+A^T\lambda =0\end{array}$$

 

로그(log) 함수의 미분을 이용하면 위 식은 다음과 같이 된다.

 

$$\begin{array}{}\text{(8)}& {\mathrm{\nabla }}_{\mathbf{x}}f(\mathbf{x})-\frac{1}{t}\sum _{i=1}^m{\mathrm{\nabla }}_{\mathbf{x}}\log (-g_i(\mathbf{x}))+A^T\lambda =0\end{array}$$

 

식 (8)과 (6)에 의하면 부등식 제약조건인 식 (3)과 (4)는 자동으로 만족된다. 그러면 KKT 수정식은 다음과 같이 정리할 수 있다.

 

$$\begin{array}{r}\text{(9)}& & {\mathrm{\nabla }}_{\mathbf{x}}(f(\mathbf{x})-\frac{1}{t}\sum _{i=1}^m\log (-g_i(\mathbf{x})))+A^T\lambda =0\\ \text{(10)}& & A\mathbf{x}=\mathbf{b}\end{array}$$

 

결국 위 두 식은 다음과 같이 등식 제약조건을 갖는 컨벡스 최적화 문제의 KKT 조건식이라는 것을 알 수 있다.

 

$$\begin{array}{r}\text{(11)}& & \underset{\mathbf{x}\in {\mathbb{R}}^n}{min}f(\mathbf{x})-\frac{1}{t}\sum _{i=1}^m\log (-g_i(\mathbf{x}))\\ \text{subject to: }& A\mathbf{x}=\mathbf{b}\end{array}$$

 

식 (11)에서 $-\frac{1}{t}\log (-y)$ 를 로그 장벽(logarithmic barrier) 함수라고 한다.

 

 

식 (11)로 주어지는 최적화 문제는 다른 접근 방법을 이용하여 도출할 수도 있다. 이전 게시글에서 지시함수(indicator function)를 이용하면 제약조건을 목적함수에 포함시킬 수 있다고 하였다. 즉 식 (1)에서 부등식 제약조건에 대한 지시함수

 

$$\begin{array}{}\text{(12)}& I_i(g_i(\mathbf{x}))=\{\begin{array}{ll}0,& \text{if }{g}_i(\mathbf{x})\le 0\\ \mathrm{\infty },& \text{if }{g}_i(\mathbf{x})>0\end{array}\end{array}$$

 

를 이용하면 컨벡스 최적화 문제 (1)을 다음과 같은 형태로 변환할 수 있다.

 

$$\begin{array}{r}\text{(13)}& & \underset{\mathbf{x}\in {\mathbb{R}}^n}{min}f(\mathbf{x})+\sum _{i=1}^m{I}_i(g_i(\mathbf{x}))\\ \text{subject to: }& A\mathbf{x}=\mathbf{b}\end{array}$$

 

하지만 식 (12)로 주어지는 지시함수의 단점은 미분이 불가능하다는 것이다. 따라서 지시함수를 이용한 최적화 문제는 뉴턴방법(Newton's method)을 사용하여 풀 수 없다. 그래서 지시함수를 미분 가능한 함수로 근사화 필요가 있는데 이 때 로그 장벽함수를 사용하여 근사화 하는 것이다. 그러면 KKT 수정식으로 도출한 식 (11)과 같은 최적화 문제를 구성할 수 있다.

다음 그림은 $t=0.5,1,2$ 에 대해서 로그 장벽함수 $-\frac{1}{t}\log (-y)$ 를 그린 것이다. $t$ 가 큰 값을 가질수록 점점 지시함수와 근접해지는 것을 알 수 있다.

 

 

근사화 파라미터인 $t$ 가 클수록 최적해에 가까운 해를 얻을 수 있지만, 로그 장벽함수의 모양에서 알 수 있듯이 $t$ 가 너무 크면 수치적인 문제가 발생한다. 따라서 처음에는 작은 $t$ 값을 이용하여 문제를 푼 후 점차 $t$ 를 키워간다. 이렇게 하면 뉴턴방법을 사용할 때 이전 $t$ 값으로 구한 해를 초기값으로 설정할 수 있기 때문에 수치 계산을 빠르고 효율적으로 할 수 있다. 특정 $t$ 값에 대한 최적화 문제 (11)의 해를 중심점(central point)라고 하고, $t$ 값의 변화에 대한 해의 경로를 중심경로(central path)라고 한다.

$t$ 가 아주 작다면 컨벡스 최적화 문제 (11)은 다음 최적화 문제로 근사화 할 수 있다.

 

$$\begin{array}{r}\text{(14)}& & \underset{\mathbf{x}\in {\mathbb{R}}^n}{min}-\frac{1}{t}\sum _{i=1}^m\log (-g_i(\mathbf{x}))\\ \text{subject to: }& A\mathbf{x}=\mathbf{b}\end{array}$$

 

위 문제는 다시 다음과 같은 등가 최적화 문제로 변환할 수 있다.

 

$$\begin{array}{r}\text{(15)}& & \underset{\mathbf{x}\in {\mathbb{R}}^n}{min}\sum _{i=1}^m{g}_i(\mathbf{x})\\ \text{subject to: }& A\mathbf{x}=\mathbf{b}\end{array}$$

 

식 (15)에 의하면 식 (1)로 주어지는 컨벡스 최적화 문제의 최적해는 실현가능영역(feasible region)의 내부(interior)에서 점근적으로 찾아갈 수 있다는 것을 알 수 있다.

 

 

이러한 방법을 내부점 방법(interior-point method)이라고 한다.