1 개요: LP가 선형대수와 다른 단 두 가지
선형대수에서 \(A\mathbf{x} = \mathbf{b}\) 를 푸는 것은 등식만 다루는 일이다. 해가 존재하면 그것이 답이고, 무한히 많으면 자유 변수로 매개화한다. 선형계획법(Linear Programming, LP) 은 여기에 두 가지를 더한다 (Strang, 2009, §8.4).
- 부등식: \(\mathbf{x} \geq \mathbf{0}\) — 모든 변수가 음이 아니어야 한다.
- 최소화: \(\mathbf{c}^\top \mathbf{x}\) 를 가장 작게 만드는 해를 고른다.
이 두 조건이 추가되는 순간, 문제의 성격이 완전히 달라진다. 등식만 있을 때는 해 집합이 부분공간(또는 아핀 집합)이었지만, 부등식이 더해지면 해 집합이 다면체(polyhedron) 가 되고, 최적해는 그 다면체의 꼭짓점(코너) 에서 나온다. 이 기하학적 사실이 LP의 핵심이다.
선형대수: “해를 찾아라” \(\to\) LP: “해 중에서 가장 싼 것을 골라라”
등식이 만드는 평면(plane)을 부등식이 다면체로 깎고, 비용 함수가 다면체 위를 훑으며 가장 먼저 닿는 코너가 답이다.
2 문제 설정: 표준형
LP의 표준형(standard form) 은 다음과 같다.
\[ \min_{\mathbf{x}} \; \mathbf{c}^\top \mathbf{x} \quad \text{subject to} \quad A\mathbf{x} = \mathbf{b}, \quad \mathbf{x} \geq \mathbf{0} \]
여기서:
- \(A\) 는 \(m \times n\) 행렬 (\(n > m\), 변수가 등식보다 많다)
- \(\mathbf{b} \in \mathbb{R}^m\) 는 제약 조건의 우변
- \(\mathbf{c} \in \mathbb{R}^n\) 는 비용 벡터
- \(\mathbf{x} \in \mathbb{R}^n\) 는 의사결정 변수
\(n > m\) 이므로 \(A\mathbf{x} = \mathbf{b}\) 의 해가 (존재한다면) 무한히 많다. 그 무한한 해 중에서 \(\mathbf{x} \geq \mathbf{0}\) 을 만족하면서 비용 \(\mathbf{c}^\top \mathbf{x}\) 를 최소화하는 \(\mathbf{x}^*\) 를 찾는 것이 LP다.
2.1 왜 표준형이 이 모양인가
실무에서 만나는 LP는 보통 부등식 제약으로 주어진다.
\[ \min \; \mathbf{c}^\top \mathbf{x} \quad \text{s.t.} \quad A'\mathbf{x} \leq \mathbf{b}', \quad \mathbf{x} \geq \mathbf{0} \]
이것을 표준형으로 바꾸려면 슬랙 변수(slack variable) \(\mathbf{s} \geq \mathbf{0}\) 를 도입한다.
\[ A'\mathbf{x} + \mathbf{s} = \mathbf{b}', \quad \mathbf{x} \geq \mathbf{0}, \; \mathbf{s} \geq \mathbf{0} \]
슬랙 변수는 “제약의 여유분”을 흡수하는 역할이다. 부등식 \(3x_1 + 2x_2 \leq 10\) 에서 \(s = 10 - 3x_1 - 2x_2\) 는 “자원 10 중 아직 안 쓴 양”이다. 이렇게 모든 부등식을 등식으로 바꿀 수 있으므로, 이론적으로는 표준형만 다루면 충분하다.
3 직관: 실행가능 영역과 코너 최적성
3.1 Strang 의 예제
다음 LP를 생각한다 (Strang, 2009, §8.4).
\[ \min \; 5x_1 + 3x_2 + 8x_3 \quad \text{s.t.} \quad x_1 + x_2 + 2x_3 = 4, \quad x_1, x_2, x_3 \geq 0 \]
여기서 \(A = [1 \;\; 1 \;\; 2]\) (\(m = 1\), \(n = 3\))이다.
기하학적 해석:
- \(x_1 + x_2 + 2x_3 = 4\) 는 3차원 공간의 평면이다.
- \(x_1, x_2, x_3 \geq 0\) 은 그 평면을 양의 사분면 안으로 잘라낸다.
- 결과적으로 세 꼭짓점 \(P\), \(Q\), \(R\) 을 가진 삼각형이 실행가능 영역(feasible region)이 된다.
| 코너 | 좌표 | 비용 \(5x_1 + 3x_2 + 8x_3\) | 해석 |
|---|---|---|---|
| \(P\) | \((4, 0, 0)\) | 20 | \(x_1\) 만 양수 |
| \(Q\) | \((0, 4, 0)\) | 12 | \(x_2\) 만 양수 |
| \(R\) | \((0, 0, 2)\) | 16 | \(x_3\) 만 양수 |
비용이 가장 작은 코너는 \(Q = (0, 4, 0)\) 이고, 최소 비용은 12다.
3.2 왜 최적해는 코너에서 나오는가
비용 함수 \(\mathbf{c}^\top \mathbf{x} = C\) 는 상수 \(C\) 에 대해 평행한 초평면들의 집합이다. \(C\) 를 0에서부터 키워가면, 이 평행 평면들이 원점에서 멀어지며 이동한다.
이 평행 평면이 실행가능 영역(다면체)에 처음 닿는 점이 최적해다. 다면체는 볼록(convex)하므로, 평면이 다면체의 내부보다 코너에 먼저 닿는다. 이것은 볼록 집합 위에서 선형 함수가 극값을 경계에서 달성한다는 사실의 직접적 결과다.
실행가능 영역이 비어있지 않고 유계(bounded)이면, 목적함수 \(\mathbf{c}^\top \mathbf{x}\) 의 최솟값은 반드시 실행가능 영역의 꼭짓점(코너, vertex) 에서 달성된다.
직관적으로: 비용 등고선(평행한 초평면)이 다면체에 처음 닿는 점은 꼭짓점이다. 다면체의 한쪽 면에 정확히 평행하게 닿는 퇴화(degenerate) 경우에도, 그 면의 꼭짓점 중 하나가 최적해에 포함된다.
이 정리 덕분에 무한한 연속 영역을 탐색할 필요 없이, 유한 개의 코너만 비교하면 최적해를 찾을 수 있다. 이것이 LP를 다루기 쉽게(tractable) 만드는 결정적 이유다.
3.3 코너의 대수적 특성
코너를 기하학이 아니라 대수로 표현하면 다음과 같다.
\(m\) 개의 등식과 \(n\) 개의 변수가 있을 때, 코너에서는 \(n - m\) 개의 변수가 0이고 나머지 \(m\) 개만 양수이다. 이 \(m\) 개의 양수 변수를 기저 변수(basic variable), 0인 변수를 비기저 변수(nonbasic variable) 라고 부른다.
코너의 최대 개수는 \(n\) 개 중 \(m\) 개를 고르는 조합이다.
\[ \text{코너 수} \leq \binom{n}{m} = \frac{n!}{m!(n-m)!} \]
\(n = 20\), \(m = 8\) 만 되어도 \(\binom{20}{8} = 125,970\) 이고, 실무에서는 수천~수만 개의 변수를 다루므로 전수조사는 불가능하다. 이것이 단체법(Simplex method)이 필요한 이유다.
3.4 특수한 경우: 비정상적 LP
모든 LP가 깔끔한 해를 갖는 것은 아니다.
| 경우 | 설명 | 예시 |
|---|---|---|
| 실행불가능(Infeasible) | \(A\mathbf{x} = \mathbf{b}\), \(\mathbf{x} \geq \mathbf{0}\) 을 동시에 만족하는 \(\mathbf{x}\) 가 없다 | \(x_1 + x_2 + x_3 = -1\), \(\mathbf{x} \geq \mathbf{0}\) |
| 비유계(Unbounded) | 실행가능 영역이 무한히 뻗어서 비용을 \(-\infty\) 로 밀 수 있다 | 비용이 음수인 방향으로 영역이 열려 있을 때 |
| 퇴화(Degenerate) | 코너에서 \(m\) 개보다 많은 변수가 0이다 | 순환(cycling) 위험 |
Strang은 비유계 경우를 다음처럼 설명한다: \(x_1 + x_2 - 2x_3 = 4\) 로 제약이 바뀌면 \(R\) 이 무한대로 날아간다. 비용이 \(-x_1 - x_2 + x_3\) 이면 \((100, 100, 98)\) 의 비용은 \(-102\), \((1000, 1000, 998)\) 의 비용은 \(-1002\) 로 끝없이 감소한다. 현실 응용에서는 자원 제약이 있으므로 대부분 이런 일이 발생하지 않는다.
4 Simplex 방법: 코너를 효율적으로 순회하는 알고리즘
4.1 핵심 아이디어
단체법(Simplex method)은 George Dantzig가 1947년에 개발한 알고리즘이다. 아이디어는 놀라울 정도로 단순하다.
“소거법(elimination)이 선형 방정식의 일꾼이라면, 단체법은 선형 부등식의 일꾼이다.” — Strang
- 실행가능한 코너 하나에서 출발한다.
- 인접 코너 중 비용이 줄어드는 곳으로 이동한다.
- 비용이 줄어드는 인접 코너가 없으면 현재 코너가 최적해다.
이것은 가우스 소거법의 사촌이다. 소거법이 행 연산(row operation)으로 \(A\mathbf{x} = \mathbf{b}\) 를 풀어가듯, 단체법은 피벗 교환(pivot exchange) 으로 비용을 줄여간다.
4.2 기저 변수와 피벗 교환
현재 코너에서 \(m\) 개의 기저 변수는 양수이고, \(n - m\) 개의 비기저 변수는 0이다. 단체법의 한 단계(iteration)는 다음과 같다.
진입 변수(entering variable) 결정: 비기저 변수 중 하나를 0에서 양수로 만든다고 가정하고, 비용 변화를 계산한다. 이 변화량을 환산비용(reduced cost) \(r\) 이라 한다. \(r < 0\) 인 변수가 있으면 비용을 줄일 수 있으므로, 가장 많이 줄이는 변수를 진입 변수로 선택한다.
이탈 변수(leaving variable) 결정: 진입 변수를 키울수록 비용이 줄지만, \(A\mathbf{x} = \mathbf{b}\) 를 유지하려면 다른 기저 변수가 조정되어야 한다. 어떤 기저 변수가 0에 도달하면 — 그 변수가 이탈 변수가 되고, 새 코너에 도착한다.
종료 조건: 모든 환산비용 \(r \geq 0\) 이면, 어떤 비기저 변수를 양수로 만들어도 비용이 줄지 않는다. 현재 코너가 최적 \(\mathbf{x}^*\) 이다.
4.3 Strang의 예제 1: 한 걸음씩 따라가기
현재 코너가 \(P = (4, 0, 0)\) 이라 하자 (비용 20).
| 시도 | 진입 변수 | 새 \(\mathbf{x}\) | 비용 | 환산비용 \(r\) |
|---|---|---|---|---|
| \(x_2\) 를 1로 | \(x_2\) | \((3, 1, 0)\) | 18 | \(-2\) |
| \(x_3\) 를 1로 | \(x_3\) | \((2, 0, 1)\) | 18 | \(-2\) |
둘 다 \(r = -2\) 이므로 비용을 줄일 수 있다. \(x_2\) 를 진입 변수로 선택하면, \(x_2\) 를 최대한 키운다. \(x_1 + x_2 = 4\) 에서 \(x_2 = 4\) 이면 \(x_1 = 0\) 이 되므로 \(x_1\) 이 이탈한다. 새 코너는 \(Q = (0, 4, 0)\) 이고 비용은 12다.
\(Q\) 에서 다시 환산비용을 계산하면 모두 양수이므로, \(Q\) 가 최적해다.
4.4 Strang의 예제 2: 4변수 문제
\[ \min \; 3x_1 + x_2 + 9x_3 + x_4 \]
\[ \text{s.t.} \quad x_1 + 2x_3 + x_4 = 4, \quad x_2 + x_3 - x_4 = 2, \quad \mathbf{x} \geq \mathbf{0} \]
\(m = 2\), \(n = 4\) 이다. 시작 코너 \(\mathbf{x} = (4, 2, 0, 0)\) 의 비용은 14다.
1단계: 비기저 변수 \(x_3\), \(x_4\) 의 환산비용을 계산한다.
- \(x_3 = 1\) 이면 \(\mathbf{x} = (2, 1, 1, 0)\), 비용 = 16, \(r_3 = +2\) (증가 — 나쁘다)
- \(x_4 = 1\) 이면 \(\mathbf{x} = (3, 3, 0, 1)\), 비용 = 13, \(r_4 = -1\) (감소 — 좋다)
\(x_4\) 가 진입 변수다. \(x_4\) 를 최대한 키우면: \(x_4 = 4\) 일 때 \(x_1 = 0\) (이탈), \(x_2 = 6\). 새 코너 \(\mathbf{x} = (0, 6, 0, 4)\), 비용 = 10.
2단계: 새 코너에서 환산비용을 다시 계산한다.
- \(x_1 = 1\) 이면 비용 = 11, \(r_1 = +1\)
- \(x_3 = 1\) 이면 비용 = 14, \(r_3 = +4\)
모든 \(r > 0\) 이므로 \(\mathbf{x}^* = (0, 6, 0, 4)\) 가 최적해이고, 최소 비용은 10이다.
4.5 복잡도와 실용적 성능
단체법의 최악 복잡도(worst-case complexity) 는 지수적이다. Klee와 Minty(1972)가 \(n\) 차원에서 \(2^n - 1\) 개의 코너를 모두 방문하는 예를 구성했다. 그러나 실제 문제에서 단체법은 평균적으로 \(O(m)\) ~ \(O(m^2)\) 번의 피벗으로 해결된다. 수십만 개의 변수를 가진 산업 규모 LP도 수초 내에 풀리는 경우가 많다.
이 “이론적으로 느리지만 실용적으로 빠른” 현상은 수학적으로 흥미로운 주제이며, Spielman과 Teng(2004)의 smoothed analysis 가 이를 부분적으로 설명한다.
5 쌍대성: 최소화와 최대화의 거울
5.1 원문제와 쌍대문제
LP의 가장 깊은 결과는 쌍대성 정리(duality theorem) 다. 모든 LP(원문제, primal)에는 대응하는 쌍대문제(dual)가 존재하고, 두 문제의 최적값은 같다.
| 원문제 (Primal) | 쌍대문제 (Dual) | |
|---|---|---|
| 목적 | \(\min \; \mathbf{c}^\top \mathbf{x}\) | \(\max \; \mathbf{b}^\top \mathbf{y}\) |
| 제약 | \(A\mathbf{x} = \mathbf{b}\), \(\mathbf{x} \geq \mathbf{0}\) | \(A^\top \mathbf{y} \leq \mathbf{c}\), \(\mathbf{y}\) 자유 |
행렬 \(A\) 가 전치되고, \(\mathbf{b}\) 와 \(\mathbf{c}\) 의 역할이 뒤바뀐다. 등식 제약은 부등식 제약이 되고, 비음 조건은 자유 변수가 된다.
5.2 Strang의 숙제 비유
Strang은 쌍대성을 “속이는 사람(cheater)”의 비유로 설명한다.
- 원문제: PhD ($$\(5/시간), 학생 (\)$\(3/시간), 기계 (\)$$8/시간)가 숙제 4문제를 최소 비용으로 해결한다. 최적해: 학생이 4시간 일하면 $$$12.
- 쌍대문제: 속이는 사람이 문제당 \(y\) 달러를 받고 답을 판다. 단, PhD보다 비쌀 수 없고 (\(y \leq 5\)), 학생보다 비쌀 수 없고 (\(y \leq 3\)), 기계 2문제보다 비쌀 수 없다 (\(2y \leq 8\)). 수입 \(4y\) 를 최대화한다. 최적해: \(y^* = 3\), 수입 = $$$12.
최소 비용 = 최대 수입 = $$$12. 이것이 강쌍대성이다.
5.3 약쌍대성의 증명: 한 줄
약쌍대성(weak duality)은 “쌍대 문제의 목적값이 원문제의 목적값을 넘지 못한다”는 부등식이다. 증명은 놀랍도록 짧다.
\(\mathbf{x}\) 가 원문제의 실행가능해이고 \(\mathbf{y}\) 가 쌍대문제의 실행가능해이면:
\[ \mathbf{b}^\top \mathbf{y} = (A\mathbf{x})^\top \mathbf{y} = \mathbf{x}^\top (A^\top \mathbf{y}) \leq \mathbf{x}^\top \mathbf{c} = \mathbf{c}^\top \mathbf{x} \]
첫 등호는 \(A\mathbf{x} = \mathbf{b}\) 이고, 부등호는 \(A^\top \mathbf{y} \leq \mathbf{c}\) (성분별)와 \(\mathbf{x} \geq \mathbf{0}\) 에서 온다. 음이 아닌 벡터와 성분별로 작은 벡터의 내적은 음이 아닌 벡터와 큰 벡터의 내적보다 작거나 같다.
따라서 임의의 쌍대 실행가능해의 목적값은 임의의 원문제 실행가능해의 목적값 이하다.
\[ \max \; \mathbf{b}^\top \mathbf{y} \leq \min \; \mathbf{c}^\top \mathbf{x} \]
5.4 강쌍대성: min = max
강쌍대성 정리(Strong Duality Theorem)는 이 부등호가 등호가 되는 \(\mathbf{x}^*\), \(\mathbf{y}^*\) 가 존재한다는 것이다.
원문제와 쌍대문제가 모두 실행가능하면,
\[ \mathbf{c}^\top \mathbf{x}^* = \mathbf{b}^\top \mathbf{y}^* \]
를 만족하는 최적해 \(\mathbf{x}^*\), \(\mathbf{y}^*\) 가 존재한다. 즉 최소 비용 = 최대 수입이다.
5.5 상보 슬랙 조건
등호가 성립하려면 약쌍대성 증명의 부등호 단계에서 등호가 되어야 한다. 즉:
\[ \mathbf{x}^\top (\mathbf{c} - A^\top \mathbf{y}) = 0 \]
슬랙 \(\mathbf{s} = \mathbf{c} - A^\top \mathbf{y} \geq \mathbf{0}\) 으로 쓰면:
\[ x_j^* s_j^* = 0 \quad \text{for all } j \]
이것이 상보 슬랙 조건(complementary slackness) 이다. 각 변수에 대해 \(x_j^* = 0\) 이거나 \(s_j^* = 0\) 이다 — 둘 중 적어도 하나는 반드시 0이어야 한다.
직관적으로: 자원 \(j\) 를 사용하고 있다면 (\(x_j^* > 0\)), 그 자원의 쌍대 제약에 여유가 없어야 한다 (\(s_j^* = 0\)). 자원 \(j\) 의 쌍대 제약에 여유가 있다면 (\(s_j^* > 0\)), 그 자원은 사용하지 않는 것이 최적이다 (\(x_j^* = 0\)).
5.6 쌍대성이 왜 중요한가
쌍대성은 단순한 이론적 아름다움이 아니라 실용적 도구다.
| 용도 | 설명 |
|---|---|
| 최적성 인증 | \(\mathbf{c}^\top \mathbf{x} = \mathbf{b}^\top \mathbf{y}\) 이면 \(\mathbf{x}\) 와 \(\mathbf{y}\) 가 동시에 최적임을 즉시 확인할 수 있다 |
| 감도 분석 | 쌍대 변수 \(y_i^*\) 는 제약 \(i\) 의 우변 \(b_i\) 를 한 단위 늘렸을 때 최적값의 변화량이다 (그림자 가격, shadow price) |
| 알고리즘 | Simplex 방법은 원문제를 풀면서 쌍대해 \(\mathbf{y}^*\) 를 동시에 얻는다 |
| 경제적 해석 | 쌍대 변수는 자원의 한계 가치(marginal value)를 나타낸다 |
6 내부점법: 다면체 안을 관통하는 또 다른 길
6.1 Simplex 의 한계와 내부점법의 등장
단체법은 다면체의 변(edge) 을 따라 코너에서 코너로 이동한다. Karmarkar(1984)는 다면체의 내부 를 관통하여 최적해에 더 직접적으로 접근하는 알고리즘을 제안했다. 이것이 내부점법(interior point method) 의 시작이다.
내부점법은 최악 복잡도가 다항시간 \(O(n^{3.5} L)\) 이라는 이론적 장점이 있고, 대규모 LP에서 Simplex와 비슷하거나 더 빠른 성능을 보인다.
6.2 장벽 함수: 경계에서 밀어내기
내부점법의 핵심 아이디어는 장벽 함수(barrier function) 다. 변수가 0에 가까워지면 무한대로 발산하는 로그 장벽을 비용에 추가한다.
\[ \min \; \mathbf{c}^\top \mathbf{x} - \theta \sum_{j=1}^{n} \log x_j \quad \text{s.t.} \quad A\mathbf{x} = \mathbf{b} \]
여기서 \(\theta > 0\) 은 장벽의 세기를 조절하는 매개변수다.
- \(\theta\) 가 클 때: 로그 장벽이 강해서 해가 내부 깊숙이 머문다.
- \(\theta \to 0\) 일 때: 장벽이 약해지면서 해가 진짜 최적 코너 \(\mathbf{x}^*\) 에 수렴한다.
\(\mathbf{x} \geq \mathbf{0}\) 제약을 명시적으로 부과할 필요가 없다 — \(x_j \to 0\) 이면 \(-\log x_j \to \infty\) 이므로 자연스럽게 경계를 피한다.
6.3 라그랑주 함수와 KKT 조건
등식 제약 \(A\mathbf{x} = \mathbf{b}\) 에 대한 라그랑주 승수 \(\mathbf{y}\) 를 도입한다.
\[ L(\mathbf{x}, \mathbf{y}, \theta) = \mathbf{c}^\top \mathbf{x} - \theta \sum_{j=1}^{n} \log x_j - \mathbf{y}^\top (A\mathbf{x} - \mathbf{b}) \]
최적 조건:
\[ \frac{\partial L}{\partial x_j} = c_j - \frac{\theta}{x_j} - (A^\top \mathbf{y})_j = 0 \quad \Rightarrow \quad x_j s_j = \theta \]
여기서 \(s_j = c_j - (A^\top \mathbf{y})_j\) 는 쌍대 슬랙이다. 진짜 LP의 상보 슬랙 조건은 \(x_j s_j = 0\) 인데, 장벽 문제에서는 \(x_j s_j = \theta\) 다. \(\theta \to 0\) 이면 원래 조건으로 수렴한다.
6.4 중심 경로와 뉴턴 단계
각 \(\theta\) 값에 대한 최적해 \(\mathbf{x}^*(\theta)\) 를 이으면 중심 경로(central path) 가 된다. 이 경로는 다면체 내부를 관통하면서 \(\theta = 0\) 에서 진짜 최적해에 도달한다.
\(\theta\) 를 줄여가며 \(x_j s_j = \theta\) 를 풀기 위해 뉴턴법(Newton’s method) 을 사용한다. 현재 점 \((\mathbf{x}, \mathbf{y}, \mathbf{s})\) 에서 보정량 \((\Delta\mathbf{x}, \Delta\mathbf{y}, \Delta\mathbf{s})\) 를 구하는 선형 시스템은 다음과 같다.
\[ A \Delta\mathbf{x} = \mathbf{0} \]
\[ A^\top \Delta\mathbf{y} + \Delta\mathbf{s} = \mathbf{0} \]
\[ s_j \Delta x_j + x_j \Delta s_j = \theta - x_j s_j \quad \text{for all } j \]
이것은 선형 연립방정식이므로 각 뉴턴 단계마다 한 번의 행렬 분해로 풀 수 있다. 비선형 문제를 매 단계 선형화하여 풀어가는 것이다.
6.5 Simplex vs 내부점법 비교
| 항목 | Simplex | 내부점법 |
|---|---|---|
| 이동 경로 | 다면체의 변(edge)을 따라 코너 순회 | 다면체 내부를 관통 |
| 최악 복잡도 | 지수적 (Klee-Minty 반례) | 다항적 \(O(n^{3.5} L)\) |
| 실용 성능 | 중소규모에서 매우 빠름 | 대규모에서 강점 |
| 해의 특성 | 정확한 코너 해 | 코너에 수렴하는 근사해 |
| warm-start | 용이 (기존 기저에서 재시작) | 어려움 |
| 정보 부산물 | 쌍대해를 자연스럽게 제공 | 원-쌍대 해를 동시에 생성 |
현대 LP 솔버(CPLEX, Gurobi, HiGHS 등)는 두 방법을 모두 구현하고 있으며, 문제 크기와 구조에 따라 자동으로 선택하거나 사용자가 지정할 수 있다.
7 왜 LP가 필요한가: 데이터 사이언스와 ML 연결
LP는 경영과학(Operations Research)의 핵심 도구이면서, 머신러닝과 데이터 사이언스에도 깊이 연결된다.
| 분야 | LP와의 연결 | 구체적 예시 |
|---|---|---|
| L1 정규화 | LASSO의 쌍대 문제는 LP로 표현 가능 | \(\min \lVert \mathbf{y} - X\boldsymbol{\beta} \rVert_1\) 은 LP로 재정식화 |
| SVM | 선형 SVM의 쌍대 형태가 LP/QP | 분류 경계의 마진 최대화 |
| 최적 운송 | Kantorovich 정식화가 LP | 두 분포 사이의 최소 비용 운송 계획 |
| 공정 분배 | 자원 배분 문제의 LP 완화 | 복지·의료 자원 최적 할당 |
| 강화학습 | policy iteration의 LP 표현 | 할인 MDP의 최적 정책 |
| 네트워크 흐름 | 최소비용 유량, 최대유량-최소절단 | 공급망 최적화, 통신 네트워크 |
| 회귀 | \(L_1\) 회귀(LAD regression)가 LP | 이상치에 강건한 회귀 |
절대값 \(|r_i|\) 는 보조 변수 \(r_i = u_i - v_i\), \(u_i, v_i \geq 0\) 으로 분해된다. 이 변환을 적용하면 \(\min \sum |r_i|\) 는 \(\min \sum (u_i + v_i)\) 가 되고, 이것은 선형 목적함수 + 선형 제약 = LP다. LASSO가 희소해(sparse solution)를 만드는 것은 LP의 코너 최적성과 같은 원리다 — 코너에서는 많은 변수가 0이고, 이것이 희소성이다.
8 코드 예시
8.1 Step 1: Low-level 구현 (원리 이해)
import numpy as np
def lp_brute_force(A, b, c):
"""
LP 전수조사: 모든 코너를 열거하여 최소 비용 코너를 찾는다.
소규모 문제에서만 사용 — 코너 최적성 원리를 직접 확인하기 위한 코드.
"""
from itertools import combinations
m, n = A.shape
best_cost = np.inf
best_x = None
corners = []
# 모든 m-조합을 시도: 어떤 m개의 열이 기저가 되는가
for cols in combinations(range(n), m):
B = A[:, cols] # 기저 행렬 (m x m)
if np.abs(np.linalg.det(B)) < 1e-10:
continue # 특이 행렬이면 건너뜀
x_B = np.linalg.solve(B, b) # 기저 변수 값
if np.all(x_B >= -1e-10): # 비음 조건 확인
x = np.zeros(n)
for i, col in enumerate(cols):
x[col] = max(x_B[i], 0)
cost = c @ x
corners.append((x.copy(), cost, cols))
if cost < best_cost:
best_cost = cost
best_x = x.copy()
return best_x, best_cost, corners
# Strang 예제: min 5x1 + 3x2 + 8x3, s.t. x1 + x2 + 2x3 = 4, x >= 0
A = np.array([[1, 1, 2]])
b = np.array([4])
c = np.array([5, 3, 8])
x_opt, cost_opt, all_corners = lp_brute_force(A, b, c)
print("== 모든 코너 ==")
for x, cost, cols in all_corners:
print(f" 기저 열 {cols}: x = {x}, 비용 = {cost:.1f}")
print(f"\n최적해: x* = {x_opt}, 최소 비용 = {cost_opt:.1f}")
# 출력:
# 기저 열 (0,): x = [4. 0. 0.], 비용 = 20.0
# 기저 열 (1,): x = [0. 4. 0.], 비용 = 12.0
# 기저 열 (2,): x = [0. 0. 2.], 비용 = 16.0
# 최적해: x* = [0. 4. 0.], 최소 비용 = 12.0이 코드에서 핵심은 combinations(range(n), m) 으로 모든 코너를 열거하는 부분이다. \(\binom{n}{m}\) 개의 코너를 전수조사하므로 대규모 문제에서는 사용할 수 없지만, “최적해는 코너에서 나온다”는 원리를 직접 확인할 수 있다.
8.2 Step 2: SciPy를 이용한 실무 코드
from scipy.optimize import linprog
# Strang 예제
c = [5, 3, 8]
A_eq = [[1, 1, 2]]
b_eq = [4]
# linprog는 기본적으로 x >= 0을 가정한다
result = linprog(c, A_eq=A_eq, b_eq=b_eq, method='highs')
print(f"최적해: x* = {result.x}")
print(f"최소 비용: {result.fun:.1f}")
print(f"상태: {result.message}")
# 출력:
# 최적해: x* = [0. 4. 0.]
# 최소 비용: 12.0
# 상태: Optimization terminated successfully.8.3 Step 3: 쌍대 문제 확인
# 원문제: min 5x1 + 3x2 + 8x3, s.t. x1 + x2 + 2x3 = 4, x >= 0
# 쌍대: max 4y, s.t. y <= 5, y <= 3, 2y <= 8
# 쌍대 문제를 원문제 형태로 변환: min -4y, s.t. y <= 5, y <= 3, 2y <= 8
c_dual = [-4]
A_ub_dual = [[1], [1], [2]]
b_ub_dual = [5, 3, 8]
result_dual = linprog(c_dual, A_ub=A_ub_dual, b_ub=b_ub_dual)
print(f"쌍대 최적해: y* = {result_dual.x[0]:.1f}")
print(f"쌍대 최적값 (최대 수입): {-result_dual.fun:.1f}")
# 출력:
# 쌍대 최적해: y* = 3.0
# 쌍대 최적값 (최대 수입): 12.0
# 원문제 최소 비용 = 쌍대 최대 수입 = 12 (강쌍대성 확인)9 요약: LP의 핵심 아이디어 네 가지
| 핵심 아이디어 | 직관 | 수학적 표현 |
|---|---|---|
| 코너 최적성 | 비용 등고면이 다면체에 처음 닿는 곳은 꼭짓점이다 | \(\mathbf{x}^*\) 는 기저 실행가능해 (BFS) |
| Simplex | 인접 코너로 비용을 줄이며 이동 | 환산비용 \(r < 0\) 인 변수를 피벗 진입 |
| 쌍대성 | 최소 비용 = 최대 수입 | \(\mathbf{c}^\top \mathbf{x}^* = \mathbf{b}^\top \mathbf{y}^*\) |
| 내부점법 | 다면체 안을 관통하여 코너에 수렴 | \(x_j s_j = \theta \to 0\) |
LP는 선형대수의 핵심 도구 — 가우스 소거, 행렬 분해, 부분공간 — 위에 부등식과 최적화를 얹은 것이다. Simplex는 소거법의 사촌이고, 쌍대성은 행(row)과 열(column)의 rank 쌍대성의 연장이며, 내부점법은 뉴턴법 + 라그랑주 승수로 돌아간다. Ch.1~7에서 배운 모든 것이 여기서 만난다.
10 관련 주제
선행 지식
- Ch.3 §3.3 — Rank와 Row Reduced Form — 기저 변수와 자유 변수 개념
- Ch.3 §3.4 — Ax = b의 완전해 — 해집합의 구조
- Ch.6 §6.5 — 양정치 행렬 — 에너지 최소화와 볼록성
후속 주제
- Ch.8 Applications 종합 개요 — LP를 포함한 7가지 응용의 조감도
- Lagrange Multiplier Method — 제약 최적화의 일반 이론
- Convex Optimization — LP를 포함하는 상위 이론
다른 카테고리 연결
- SVM과 마진 최대화 — LP/QP의 ML 응용
- L1 정규화와 LASSO — LP와 희소성의 연결