7.117 선형 계획법과 단체법

1. 선형 계획 문제의 표준형

선형 계획법(Linear Programming, LP)은 선형 목적 함수를 선형 제약 조건하에서 최적화하는 문제이다. 표준형은 다음과 같다.

$\min_{\mathbf{x}} \quad \mathbf{c}^T\mathbf{x} \quad \text{s.t.} \quad \mathbf{A}\mathbf{x} = \mathbf{b}, \quad \mathbf{x} \geq \mathbf{0}$

여기서 $\mathbf{c} \in \mathbb{R}^n$ , $\mathbf{A} \in \mathbb{R}^{m \times n}$ ( $m \leq n$ ), $\mathbf{b} \in \mathbb{R}^m$ 이다. 일반적인 부등식 형태 $\mathbf{A}'\mathbf{x} \leq \mathbf{b}'$ 는 여유 변수를 도입하여 표준형으로 변환할 수 있다.

2. 허용 영역의 기하학

LP의 허용 영역은 다면체(polyhedron)이며, 유계인 경우 다각형체(polytope)가 된다. LP의 핵심적 성질은 다음과 같다.

정리: LP의 최적해가 존재하면, 다면체의 꼭짓점(vertex), 즉 기본 허용 해(basic feasible solution, BFS)에서 최적해가 달성된다.

이 성질은 LP의 해법이 무한히 많은 내부 점이 아닌 유한 개의 꼭짓점만을 탐색하면 됨을 의미한다.

3. 기본 허용 해

표준형에서 $\mathbf{A}$ 의 열 중 $m$ 개의 선형 독립 열을 선택하여 기저(basis) $\mathbf{B} \in \mathbb{R}^{m \times m}$ 를 구성한다. 기저에 속하는 변수를 기본 변수(basic variable) $\mathbf{x}_B = \mathbf{B}^{-1}\mathbf{b}$ 로, 나머지를 비기본 변수(nonbasic variable) $\mathbf{x}_N = \mathbf{0}$ 으로 설정한다. $\mathbf{x}_B \geq \mathbf{0}$ 이면 이것이 기본 허용 해이다.

4. 단체법(Simplex Method)

단체법은 댄치그(Dantzig, 1947)가 개발한 알고리즘으로, 다면체의 꼭짓점을 따라 이동하면서 목적 함수를 감소시키는 인접 꼭짓점을 반복적으로 탐색한다.

4.1 알고리즘의 개요

초기 기본 허용 해(BFS)를 구한다.
현재 BFS에서 축소 비용(reduced cost) $\bar{c}_j = c_j - \mathbf{c}_B^T\mathbf{B}^{-1}\mathbf{a}_j$ 를 계산한다.
모든 $\bar{c}_j \geq 0$ 이면 현재 BFS가 최적이다 (종료).
$\bar{c}_j < 0$ 인 비기본 변수 $x_j$ 를 진입 변수(entering variable)로 선택한다.
비율 검정(ratio test)에 의해 이탈 변수(leaving variable)를 결정한다.
기저 교환(pivot)을 수행하고 2단계로 돌아간다.

4.2 축소 비용의 의미

축소 비용 $\bar{c}_j$ 는 비기본 변수 $x_j$ 를 1만큼 증가시킬 때 목적 함수의 변화량을 나타낸다. $\bar{c}_j < 0$ 이면 $x_j$ 의 증가가 목적 함수를 감소시키므로, 해당 변수를 기저에 진입시키는 것이 유리하다.

4.3 복잡도

단체법의 최악 경우 반복 횟수는 지수적이지만, 실용적으로는 반복 횟수가 $O(m)$ 내지 $O(m \log n)$ 으로 문제 규모에 거의 선형적이다. 단체법은 60년 이상의 역사 동안 가장 널리 사용되어 온 LP 해법이며, 대규모 산업 문제에서도 효율적으로 작동한다.

5. 내점법에 의한 LP 해법

카르마카르(Karmarkar, 1984)에 의해 제안된 LP의 내점법은 다항 시간 최악 경우 복잡도를 보장한다. 현대의 원시-쌍대 내점법은 $O(\sqrt{n}\log(1/\epsilon))$ 반복에 수렴하며, 각 반복에서 $O(n^3)$ 의 선형 시스템을 풀어야 한다. 대규모 희소 LP에서는 내점법이 단체법보다 효율적인 경우가 많으며, MOSEK, Gurobi 등의 현대 해법기는 단체법과 내점법을 모두 제공한다.

6. 로봇 공학에서의 LP 응용

$\ell_1$ 최적화: $\ell_1$ 노름 최소화 $\min \lVert \mathbf{x} \rVert_1$ subject to $\mathbf{A}\mathbf{x} = \mathbf{b}$ 는 LP로 정식화된다. 로봇 학습에서 희소 신호 복원(sparse recovery)이나 특징 선택(feature selection)에 활용된다.

체비셰프 근사: $\ell_\infty$ 노름 최소화 $\min \lVert \mathbf{A}\mathbf{x} - \mathbf{b} \rVert_\infty$ 는 LP로 정식화되며, 로봇 캘리브레이션에서 최악 경우 오차를 최소화하는 데 사용된다.

지지 다면체 계산: 접촉 계획에서 로봇의 도달 가능 공간이나 힘 다면체(force polytope)의 계산에 LP가 활용된다.

7. 참고 문헌

Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press.
Bertsimas, D., & Tsitsiklis, J. N. (1997). Introduction to Linear Optimization. Athena Scientific.
Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.

version: 1.0