프리멀-듀얼 내부점 방법

프리멀-듀얼 내부점 방법의 기본 개념

프리멀-듀얼 내부점 방법은 선형계획법 문제에서 프리멀 문제와 그에 대응하는 듀얼 문제를 동시에 해결하는 방법이다. 이 방법은 주로 카르마르카르 알고리즘과 같은 내부점 방법의 확장으로, 대규모 선형계획 문제에서 매우 효율적으로 작동한다.

프리멀 문제는 다음과 같은 형태로 주어진다.

$\text{최소화} \quad \mathbf{c}^\top \mathbf{x}$

$\text{제약조건} \quad \mathbf{A} \mathbf{x} = \mathbf{b}, \quad \mathbf{x} \geq 0$

여기서: - $\mathbf{c} \in \mathbb{R}^n$ 은 목적 함수의 계수 벡터, - $\mathbf{x} \in \mathbb{R}^n$ 은 결정 변수 벡터, - $\mathbf{A} \in \mathbb{R}^{m \times n}$ 은 제약 조건을 나타내는 행렬, - $\mathbf{b} \in \mathbb{R}^m$ 은 제약 조건의 우변 값이다.

듀얼 문제는 다음과 같은 형태로 정의된다.

$\text{최대화} \quad \mathbf{b}^\top \mathbf{y}$

$\text{제약조건} \quad \mathbf{A}^\top \mathbf{y} \leq \mathbf{c}, \quad \mathbf{y} \in \mathbb{R}^m$

여기서: - $\mathbf{y} \in \mathbb{R}^m$ 은 듀얼 변수 벡터이다.

프리멀-듀얼 내부점 방법에서는 프리멀 문제와 듀얼 문제의 해를 동시에 찾아나가며, 이를 위해 각 문제에 대한 해를 점진적으로 개선하는 과정을 거친다. 이 과정에서 중심 경로(central path)를 따라 해를 찾는 방식이 주로 사용된다.

중심 경로와 로그 장벽 함수

내부점 방법에서 해가 제약 조건 경계에 위치하지 않도록 하기 위해 로그 장벽 함수(log barrier function)를 사용한다. 프리멀 문제에 대한 로그 장벽 함수는 다음과 같이 정의된다.

$L(\mathbf{x}, \mu) = \mathbf{c}^\top \mathbf{x} - \mu \sum_{i=1}^{n} \log(x_i)$

여기서 $\mu$ 는 장벽 매개변수(barrier parameter)이며, 이 매개변수가 점차 줄어들면서 해는 점차 제약 조건의 경계로 수렴하게 된다. 듀얼 문제에 대해서도 비슷한 방식으로 로그 장벽 함수를 정의할 수 있다.

프리멀-듀얼 간의 상호작용

프리멀-듀얼 내부점 방법에서는 프리멀 변수 $\mathbf{x}$ , 듀얼 변수 $\mathbf{y}$ , 그리고 듀얼 슬랙 변수 $\mathbf{s}$ 사이의 상호작용이 매우 중요하다. 듀얼 슬랙 변수 $\mathbf{s}$ 는 다음과 같이 정의된다.

$\mathbf{s} = \mathbf{c} - \mathbf{A}^\top \mathbf{y}$

이 프리멀-듀얼 시스템에서 각 변수 간의 관계를 고려하여 Newton's Method를 사용해 해를 점진적으로 개선한다.

KKT 조건과 뉴턴법

프리멀-듀얼 내부점 방법은 KKT 조건(Karush-Kuhn-Tucker conditions)을 만족시키는 해를 찾는 과정을 따른다. KKT 조건은 프리멀 문제와 듀얼 문제 간의 최적성을 보장하는 조건들로, 아래와 같이 표현된다.

프리멀 가능성 조건:

$\mathbf{A} \mathbf{x} = \mathbf{b}$

듀얼 가능성 조건:

$\mathbf{A}^\top \mathbf{y} + \mathbf{s} = \mathbf{c}, \quad \mathbf{s} \geq 0$

슬랙 조건:

$\mathbf{x}_i \mathbf{s}_i = 0 \quad \forall i$

비음성 조건:

$\mathbf{x} \geq 0, \quad \mathbf{s} \geq 0$

이 조건들을 만족하는 프리멀 변수 $\mathbf{x}$ , 듀얼 변수 $\mathbf{y}$ , 그리고 듀얼 슬랙 변수 $\mathbf{s}$ 를 찾는 것이 내부점 방법의 목표이다.

뉴턴법을 사용하여 이 시스템을 풀기 위해서는 위의 KKT 시스템을 행렬식으로 표현하여 이를 동시에 풀어나가는 과정이 필요하다. 먼저, 프리멀 문제와 듀얼 문제의 잔차(residuals)를 정의하자.

잔차(residual) 정의

프리멀-듀얼 시스템에서 잔차는 아래와 같이 정의된다.

프리멀 잔차 $\mathbf{r}_\text{prim}$ :

$\mathbf{r}_\text{prim} = \mathbf{A} \mathbf{x} - \mathbf{b}$

듀얼 잔차 $\mathbf{r}_\text{dual}$ :

$\mathbf{r}_\text{dual} = \mathbf{A}^\top \mathbf{y} + \mathbf{s} - \mathbf{c}$

슬랙 잔차 $\mathbf{r}_\text{slack}$ :

$\mathbf{r}_\text{slack} = \mathbf{X} \mathbf{S} \mathbf{e} - \mu \mathbf{e}$

여기서 $\mathbf{X}$ 는 $\mathbf{x}$ 의 대각행렬, $\mathbf{S}$ 는 $\mathbf{s}$ 의 대각행렬, $\mathbf{e}$ 는 모든 성분이 1인 벡터, 그리고 $\mu$ 는 장벽 매개변수(barrier parameter)이다.

뉴턴 방향(Newton Direction)

프리멀-듀얼 내부점 방법에서 뉴턴 방향은 프리멀 변수, 듀얼 변수, 그리고 듀얼 슬랙 변수에 대한 미분을 통해 계산된다. 이를 위해 프리멀-듀얼 시스템의 선형화를 수행해야 하며, 이를 위해 잔차 방정식의 Jacobian을 계산한다.

다음은 뉴턴법을 적용하여 구한 선형 시스템이다.

$\begin{bmatrix} \mathbf{A} & 0 & 0 \\ 0 & \mathbf{A}^\top & \mathbf{I} \\ \mathbf{S} & 0 & \mathbf{X} \end{bmatrix} \begin{bmatrix} \Delta \mathbf{x} \\ \Delta \mathbf{y} \\ \Delta \mathbf{s} \end{bmatrix} = \begin{bmatrix} -\mathbf{r}_\text{prim} \\ -\mathbf{r}_\text{dual} \\ -\mathbf{r}_\text{slack} \end{bmatrix}$

여기서 $\Delta \mathbf{x}, \Delta \mathbf{y}, \Delta \mathbf{s}$ 는 각각 프리멀 변수, 듀얼 변수, 듀얼 슬랙 변수의 변화량이다. 이 선형 시스템을 풀어 뉴턴 방향을 계산한 후, 이를 이용해 해를 점진적으로 개선해 나간다.

뉴턴법의 단계와 갱신

뉴턴 방향 $\Delta \mathbf{x}, \Delta \mathbf{y}, \Delta \mathbf{s}$ 을 구한 후, 이를 이용해 프리멀 변수, 듀얼 변수, 그리고 듀얼 슬랙 변수를 갱신한다. 갱신은 다음과 같은 형태로 이루어진다.

$\mathbf{x}^{(k+1)} = \mathbf{x}^{(k)} + \alpha \Delta \mathbf{x}$

$\mathbf{y}^{(k+1)} = \mathbf{y}^{(k)} + \alpha \Delta \mathbf{y}$

$\mathbf{s}^{(k+1)} = \mathbf{s}^{(k)} + \alpha \Delta \mathbf{s}$

여기서 $\alpha$ 는 스텝 크기(step size)로, 일반적으로 0과 1 사이의 값이다. 스텝 크기는 보통 선형 탐색(line search)을 통해 결정되며, 이 과정에서 프리멀 및 듀얼 변수들이 비음성 조건을 만족하도록 해야 한다.