쌍대성 (Duality)

정의

쌍대성 (Duality) 은 하나의 최적화 문제 (Primal) 에 항상 대응되는 또 다른 최적화 문제 (Dual) 가 존재한다는 원리. LP 에서 Primal-Dual 쌍은 다음과 같다:

Primal (max 형태):

maximize    c^T x
subject to  A x ≤ b,  x ≥ 0

Dual (min 형태):

minimize    b^T y
subject to  A^T y ≥ c,  y ≥ 0

Primal 이 max 이면 Dual 은 min, 제약 방향이 반대, 변수와 제약의 개수가 뒤바뀐다.

문제 상황과 동기

• 보는 관점의 전환: Primal 이 풀기 어려울 때 Dual 이 더 쉽거나, Dual 의 해가 Primal 해의 하한/상한을 제공.
• 최적성 증명: Primal 해 x 와 Dual 해 y 에 대해 c^T x ≤ b^T y. 같으면 둘 다 최적.
• Max-Flow Min-Cut 정리: 최대 유량 (Primal) = 최소 컷 (Dual). duality 의 대표적 예시.

핵심 통찰: 모든 선형 계획법은 대응되는 쌍대 문제가 있으며, Strong Duality 가 성립하면 두 문제의 최적값이 같다.

시각화

핵심 아이디어

Weak Duality (약 쌍대성)

임의의 feasible x, y 에 대해 c^T x ≤ b^T y. Primal 이 max 니까 Dual 해가 Primal 해의 상한. Primal 이 min 이면 반대.

증명: c ≤ A^T y 이므로 c^T x ≤ (A^T y)^T x = y^T (A x) ≤ y^T b = b^T y.

Strong Duality (강 쌍대성)

Primal 이 최적해 x* 를 가지면, Dual 도 최적해 y* 를 가지며 c^T x* = b^T y*. (둘 다 feasible 할 때)

Complementary Slackness (상보 여유)

최적해 (x*, y*) 에 대해:

• x_j > 0 ⇒ (A^T y)_j = c_j (해당 Dual 제약이 tight)
• y_i > 0 ⇒ (A x)_i = b_i (해당 Primal 제약이 tight)

물리적 의미: 사용되지 않은 자원은 가격이 0, 가격이 0인 자원은 사용되지 않음.

알고리즘

LP Duality 변환 규칙 (Primal → Dual):

Primal (max)            Dual (min)
─────────────────────────────────────
c_j (objective coeff)  b_j (RHS)
b_i (RHS)              c_i (objective coeff)
A_ij                   A_ji (transpose)
≤ constraint (i)       y_i ≥ 0
x_j ≥ 0                ≥ constraint (j)

Primal (min) 으로 시작하면
  → Dual (max) 로 대칭.

Max-Flow Min-Cut Duality:

Primal: source → sink 최대 유량 f*
Dual:   S-T 컷 (S, T) 의 최소 용량

f* = min_{S-T cut} capacity(S, T)

구현

// Primal-Dual pairing: simplex tableau 로 dual 변수 추출
#include <bits/stdc++.h>
using namespace std;
int main() {
  // Primal: max x+y s.t. x+2y<=4, 2x+y<=5, x,y>=0
  // Dual:   min 4y1+5y2 s.t. y1+2y2>=1, 2y1+y2>=1, y1,y2>=0
  vector<vector<double>> a = {{1,2,1,0,4}, {2,1,0,1,5}};
  vector<double> obj = {-1,-1,0,0,0};
  double opt = 0;
  // Simplex pivot (간략)
  static const int PIVOT[][2] = {{0,0},{1,1}}; // entering/leaving
  for (auto [r,c] : PIVOT) {
      double piv = a[r][c];
      for (auto& v : a[r]) v /= piv;
      for (int i = 0; i < 2; i++) {
          if (i == r) continue;
          double mul = a[i][c];
          for (auto& v : a[i]) v -= mul * a[r][c];
      }
      double mul = obj[c];
      for (auto& v : obj) v -= mul * a[r][c];
  }
  opt = obj[4] > 1e-9 ? 0 : -obj[4];
  cout << "Primal opt: " << opt << "\n";
  cout << "Dual y1: " << obj[2] << ", y2: " << obj[3] << "\n";
}

# Dual optimal 확인 with scipy
from scipy.optimize import linprog
res_p = linprog([-1,-1], A_ub=[[1,2],[2,1]], b_ub=[4,5])
res_d = linprog([4,5], A_ub=[[-1,-2],[-2,-1]], b_ub=[-1,-1])
print(f"Primal: {-res_p.fun:.4f}, x={res_p.x}")
print(f"Dual:   {res_d.fun:.4f}, y={res_d.x}")
print(f"Gap: {abs(-res_p.fun - res_d.fun):.2e} (strong duality)")

Primal: 3.0000, x=[2. 1.]
Dual:   3.0000, y=[0.33333333 0.33333333]
Gap: 0.00e+00 (strong duality)

복잡도

Dual 을 푸는 비용은 primal 과 동등한 LP 복잡도. 하지만 dual 이 변수/제약이 더 적을 수 있음.

변형 / 활용

Max-Flow Min-Cut Theorem

모든 네트워크에서 max flow = min s-t cut capacity. LP duality 의 가장 직관적인 예. Primal 은 유량 극대화, Dual 은 컷 용량 최소화.

LP Primal-Dual Schema (근사 알고리즘)

• Dual 해 y 를 greedy 로 구성.
• Complementary slackness 조건을 “완화” (relaxed) 하여 primal 해 x 를 재구성.
• Set cover, Steiner tree, facility location 등에 사용.

함정

1. Strong Duality 는 항상 성립하지 않는다

두 문제 모두 feasible 해야 성립. 하나가 infeasible 이면 gap 이 무한.

2. Dual 의 Dual = Primal

Dual 을 다시 쌍대화하면 원래 Primal. 변환을 2번 하면 제자리.

3. 정수 제약에서는 Duality Gap

ILP 에서 LP relaxation 의 dual 값은 primal ILP 와 gap 이 있을 수 있음 (integrality gap).

BOJ 연습 문제

참고

• 선형 계획법
• 최대 유량
• Max-Flow Min-Cut
• 이분 매칭