강한 쌍대성 정리 - 실험 도서관

1. 선형계획법의 쌍대성

선형계획 문제는 두 가지 형태로 나타낼 수 있다: 원문제(Primal Problem)와 쌍대문제(Dual Problem). 원문제는 일반적으로 아래와 같은 형태로 주어진다.

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

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

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

이 원문제에 대응하는 쌍대문제는 다음과 같이 정의된다.

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

$\text{제약 조건 } \mathbf{A}^\top \mathbf{y} \geq \mathbf{c}, \quad \mathbf{y} \geq 0$

여기서 $\mathbf{y} \in \mathbb{R}^{m}$ 는 쌍대 변수 벡터이다. 쌍대문제는 원문제와 밀접한 관계를 가지며, 둘 사이에는 약한 쌍대성과 강한 쌍대성이라는 중요한 정리들이 존재한다.

2. 약한 쌍대성

약한 쌍대성 정리는 모든 가능한 $\mathbf{x}$ 와 $\mathbf{y}$ 에 대해, 원문제의 목적 함수 값이 쌍대문제의 목적 함수 값보다 크거나 같다는 것을 말한다. 즉,

$\mathbf{c}^\top \mathbf{x} \leq \mathbf{b}^\top \mathbf{y}$

이는 모든 가능한 해에 대해 성립하며, 이는 원문제의 해가 최적화되지 않았을 경우에도 해당된다.

3. 강한 쌍대성

강한 쌍대성 정리는 원문제와 쌍대문제의 최적해에서 목적 함수 값이 일치한다는 것을 말한다. 즉, 원문제와 쌍대문제 모두 최적해를 가질 때,

$\mathbf{c}^\top \mathbf{x}^* = \mathbf{b}^\top \mathbf{y}^*$

여기서: - $\mathbf{x}^*$ 는 원문제의 최적해, - $\mathbf{y}^*$ 는 쌍대문제의 최적해이다.

이 정리는 최적해가 존재할 때에만 적용되며, 선형계획법 문제에서 중요한 결과를 제공한다.

4. 강한 쌍대성의 직관적 의미

강한 쌍대성 정리는 원문제와 쌍대문제의 상호관계를 명확하게 보여준다. 원문제에서 자원을 최적으로 사용하여 얻을 수 있는 최대 이익과 쌍대문제에서 자원의 가격을 최적으로 설정하여 발생할 수 있는 최소 비용이 동일하다는 의미를 지닌다.

원문제와 쌍대문제의 역할

원문제(Primal Problem): 자원의 효율적 사용을 목표로 하는 문제이다. 주어진 자원(예: 시간, 자본) 내에서 이익을 최대화하는 것이 목표이다.
쌍대문제(Dual Problem): 자원의 가치에 초점을 맞추는 문제이다. 각 자원에 가격을 설정하고, 이러한 가격에 따라 자원을 사용하는 데 드는 비용을 최소화하는 것을 목표로 한다.

따라서 강한 쌍대성 정리에서 말하는 것은, 원문제에서 자원을 어떻게 배분하든 그 자원에 적절한 가격을 설정하면 원문제와 쌍대문제의 목적 함수 값이 동일해진다는 것이다.

예시를 통한 설명

한 예로, 공장에서 제품을 생산하는 문제가 있다고 가정하자. 공장의 자원은 작업 시간, 인력, 재료 등의 제한된 자원으로 구성된다. 이 경우 원문제는 주어진 자원을 사용하여 제품을 얼마나 많이 생산할 수 있는지에 대한 최적화 문제이다. 반면에 쌍대문제는 자원 하나하나에 대해 어떤 가격을 매겨야 그 자원들을 최적으로 사용하고 비용을 최소화할 수 있을지를 결정하는 문제이다.

이 두 문제에서 강한 쌍대성 정리에 따라, 최적의 자원 배분(원문제의 해)과 최적의 자원 가격 설정(쌍대문제의 해)은 동일한 결과를 낳습니다.

5. 강한 쌍대성의 수학적 증명 개요

강한 쌍대성 정리는 특정 조건에서 증명될 수 있다. 그중 하나가 슬레이터 조건(Slater's Condition)이다. 이 조건에 따르면, 문제에 대한 엄격한 허용 해가 존재할 경우, 강한 쌍대성이 성립한다.

슬레이터 조건(Slater's Condition)

슬레이터 조건은 다음과 같다. 원문제의 제약 조건에서, 모든 제약이 엄격하게 충족되는 $\mathbf{x}$ 가 존재한다면 (즉, $\mathbf{A} \mathbf{x} < \mathbf{b}$ ), 강한 쌍대성은 자동으로 성립한다.

이를 수학적으로 표현하면:

$\exists \, \mathbf{x} \text{ such that } \mathbf{A} \mathbf{x} < \mathbf{b} \quad \Rightarrow \quad \mathbf{c}^\top \mathbf{x}^* = \mathbf{b}^\top \mathbf{y}^*$

즉, 제약 조건이 엄격하게 충족되는 허용해(feasible solution)가 존재한다면, 원문제와 쌍대문제는 모두 최적해를 갖게 되고, 그 값은 동일하게 된다.

6. 강한 쌍대성의 증명 과정

강한 쌍대성 정리를 수학적으로 증명하기 위해서는 여러 단계의 논리가 필요하다. 여기서는 강한 쌍대성 정리의 증명 과정의 주요 단계를 설명한다.

1. 라그랑주 함수 (Lagrangian Function)

강한 쌍대성 정리는 라그랑주 이론(Lagrange Theory)을 기반으로 증명된다. 원문제의 라그랑주 함수는 다음과 같이 정의된다.

$\mathcal{L}(\mathbf{x}, \mathbf{y}) = \mathbf{c}^\top \mathbf{x} + \mathbf{y}^\top (\mathbf{b} - \mathbf{A} \mathbf{x})$

여기서: - $\mathbf{x}$ 는 원문제의 변수, - $\mathbf{y}$ 는 쌍대문제의 변수(라그랑주 승수).

라그랑주 함수는 원문제의 목적 함수와 제약 조건을 통합하여 문제를 풀 수 있게 해준다. 이 함수를 통해 원문제와 쌍대문제의 목적 함수 값을 비교할 수 있다.

2. 원문제의 최적 조건 (Primal Optimality Conditions)

원문제의 최적해 $\mathbf{x}^*$ 는 다음과 같은 조건을 만족해야 한다.

$\mathbf{A} \mathbf{x}^* \leq \mathbf{b}, \quad \mathbf{x}^* \geq 0$

즉, 원문제의 제약 조건을 만족하는 해가 되어야 하며, 이 해는 라그랑주 함수에서 기울기 조건을 만족하게 된다.

3. 쌍대문제의 최적 조건 (Dual Optimality Conditions)

쌍대문제의 최적해 $\mathbf{y}^*$ 는 아래와 같은 조건을 만족해야 한다.

$\mathbf{A}^\top \mathbf{y}^* \geq \mathbf{c}, \quad \mathbf{y}^* \geq 0$

이 조건은 쌍대문제가 원문제와 제약 조건을 상호 보완하여 최적화된 상태에 도달함을 의미한다.

4. 쌍대성 차이 (Duality Gap)

쌍대성 차이(Duality Gap)는 원문제의 목적 함수 값과 쌍대문제의 목적 함수 값의 차이이다. 강한 쌍대성에서는 이 차이가 0이 되어야 한다.

$\mathbf{c}^\top \mathbf{x}^* - \mathbf{b}^\top \mathbf{y}^* = 0$

쌍대성 차이가 0이라는 것은 원문제와 쌍대문제가 최적해에서 동일한 값을 가진다는 것을 의미한다. 강한 쌍대성 정리에서는 이 쌍대성 차이가 항상 0으로 수렴한다는 것을 증명한다.

5. 증명 마무리

라그랑주 승수와 슬레이터 조건을 사용하여, 쌍대성 차이가 0임을 보이는 것이 강한 쌍대성 정리의 증명 마무리 단계이다. 이로써 원문제와 쌍대문제는 모두 동일한 최적해를 가지며, 그 목적 함수 값 또한 동일하다는 결론에 도달할 수 있다.