카르마르카르 알고리즘

개요

카르마르카르(Karmarkar) 알고리즘은 선형계획법을 해결하기 위한 내부점 방법 중 하나로, 1984년 Narendra Karmarkar가 제안한 방법이다. 이 알고리즘은 전통적인 단체법과 달리 다면체의 경계점을 따라 움직이지 않고, 내부에서 해를 탐색하는 방식이다. 이는 대규모 선형계획 문제를 효율적으로 해결하는 데 매우 유용하다.

알고리즘의 기본 원리

카르마르카르 알고리즘은 선형계획 문제를 다음과 같이 정의한다:

$\min \quad \mathbf{c}^T \mathbf{x}$

$\text{subject to} \quad \mathbf{A} \mathbf{x} = \mathbf{b}, \quad \mathbf{x} \geq 0$

여기서: - $\mathbf{c}$ 는 목적 함수의 계수 벡터, - $\mathbf{x}$ 는 해 벡터, - $\mathbf{A}$ 는 제약 조건의 계수 행렬, - $\mathbf{b}$ 는 우변 벡터이다.

카르마르카르 알고리즘은 이 문제를 단순히 해 공간의 경계에서 탐색하는 대신, 문제의 내부 점에서 시작하여 최적 해를 향해 점진적으로 이동하는 방식을 취한다.

반복 과정

이 알고리즘은 다음의 반복적인 과정을 거친다:

내부 점 선택: 초기 내부 점 $\mathbf{x}_0$ 를 선택한다. 이는 문제의 모든 제약 조건을 만족하면서도 경계에 위치하지 않는 점이어야 한다.
좌표 변환: 기존의 좌표계를 새로운 좌표계로 변환하여 문제를 단순화한다. 변환된 좌표계에서는 해가 내부에 있는 것이 보장된다.
방향 결정: 목적 함수의 기울기를 계산하고, 이를 통해 다음 탐색 방향을 결정한다. 이때 내부의 모든 점들이 유효한 해로 유지될 수 있도록 방향이 설정된다.
스텝 크기 결정: 탐색 방향으로 얼마만큼 이동할지를 결정하는 스텝 크기를 설정한다. 스텝 크기는 해가 유효 범위를 벗어나지 않도록 조정된다.
해 갱신: 현재의 해를 갱신하여, 최적해에 더욱 가까운 새로운 내부 점으로 이동한다.

좌표 변환

카르마르카르 알고리즘의 중요한 특징 중 하나는 좌표 변환을 통해 문제를 단순화한다는 점이다. 이를 위해서는 현재 내부 점 $\mathbf{x}_k$ 를 중심으로 변환하여, 새로운 좌표계에서 탐색을 수행한다.

변환된 좌표계에서의 문제는 다음과 같이 표현될 수 있다:

$\min \quad \mathbf{c}^T \mathbf{y}$

$\text{subject to} \quad \mathbf{A} \mathbf{y} = \mathbf{b}, \quad \mathbf{y} \geq 0$

여기서 $\mathbf{y}$ 는 변환된 좌표에서의 해 벡터를 의미한다.

중심 경로와 스텝 크기

카르마르카르 알고리즘에서 중요한 개념은 중심 경로(central path)이다. 중심 경로는 내부점 방법에서 해를 탐색할 때 최적해로 수렴하는 경로를 나타낸다. 알고리즘은 이 경로를 따라 이동하며, 매 반복마다 중심을 향해 한 걸음씩 나아간다.

중심 경로는 다음과 같이 정의할 수 있다:

$\mathbf{x}(\mu) = \arg\min \{ \mathbf{c}^T \mathbf{x} + \mu \sum_{i=1}^n \log(x_i) \mid \mathbf{A} \mathbf{x} = \mathbf{b}, \mathbf{x} > 0 \}$

여기서: - $\mu$ 는 경로의 매개변수로, 알고리즘이 수렴할수록 이 값은 점점 작아진다. - $\log(x_i)$ 항은 내부점이 경계에 가까워지지 않도록 하는 역할을 한다.

스텝 크기 결정

스텝 크기 $\alpha$ 는 각 반복에서 이동할 거리이다. 스텝 크기는 해가 경계에 너무 가깝게 이동하지 않도록 조절된다. 스텝 크기는 다음 조건을 만족하도록 설정된다:

$\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha \mathbf{d}_k$

여기서 $\mathbf{d}_k$ 는 탐색 방향을 나타내는 벡터이다. 이 벡터는 목적 함수의 기울기에 반비례하며, 다음과 같이 구할 수 있다:

$\mathbf{d}_k = -\nabla f(\mathbf{x}_k)$

스텝 크기 $\alpha$ 는 $0 < \alpha < 1$ 의 값을 가지며, 최적화 과정에서 적절히 조정된다.

경계와의 거리 유지

카르마르카르 알고리즘은 경계점에 너무 가까이 가지 않도록 내부에서 탐색을 진행한다. 이를 위해 로그 장벽(log barrier) 함수가 도입된다. 이 함수는 해가 경계에 가까워질수록 큰 값을 가지게 되어 경계를 피하도록 유도한다.

로그 장벽 함수는 다음과 같이 정의된다:

$\phi(\mathbf{x}) = -\sum_{i=1}^{n} \log(x_i)$

이 함수는 경계에서의 거리를 유지하며 해가 내부에서 최적화되도록 하는 역할을 한다. 내부에서 탐색을 유지하는 것은 카르마르카르 알고리즘이 대규모 문제에서도 효율적으로 동작할 수 있는 이유 중 하나이다.

수렴 조건

카르마르카르 알고리즘은 반복 과정을 통해 최적해에 수렴한다. 수렴의 주요 조건은 목적 함수의 값이 어느 임계값 이하로 떨어지는지 여부이다. 수렴 기준은 다음과 같이 설정된다:

$\|\mathbf{c}^T \mathbf{x}_k - z^*\| < \epsilon$

여기서: - $z^*$ 는 최적 해의 목적 함수 값, - $\epsilon$ 은 미리 설정된 허용 오차이다.

이 조건을 만족하면 알고리즘은 종료된다.