15-01-02 Log barrier function & barrier method

Barrier method를 소개하기 전에 먼저 indicator function을 barrier function으로 어떻게 근사할 수 있는지 살펴보도록 하자.

Approximation of indicator function

다음 그림을 보면 indicator function과 barrier function을 확인할 수 있다. 점선은 indicator function인 $I_C$이며 실선은 $t=0.5,1,2$에 대한 barrier function $\varphi (x)=-1/t\log (-x)$이다. Barrier function은 indicator function을 smooth하게 근사하고 있으며 $t=2$일 때 가장 좋은 근사를 보여주고 있다.

Logarithmic barrier function

$h_1,\cdots ,h_m:{\mathbb{R}}^n\to \mathbb{R}$가 convex이고 두번 미분가능하다고 하자. set $\{x:h_i(x)<0,i=1,\cdots ,m\}$에 대해 다음 함수를 logarithmic barrier function이라고 한다.

$$\begin{array}{r}\varphi (x)=-\sum _{i=1}^m\log (-h_i(x))\end{array}$$

여기서 set은 interior of feasible set $C$로 non-empty라고 가정한다.

Barrier method

Barrier function을 사용해서 원래 문제를 다음과 같이 근사할 수 있다. 단, $t>0$이다.

$$\begin{array}{rlrlrlrl}& \underset{x}{min}& & f(x)+\frac{1}{t}\varphi (x)& & \underset{x}{min}& & tf(x)+\varphi (x)\\ & \text{subject to }& & Ax=b& ⟺& \text{subject to }& & Ax=b\end{array}$$

이와 같이 정의된 문제를 newton’s method로 푸는 방법을 barrier method라고 한다.