---
lang: ja
tags: MTNS-2022, lecture, linear programming
---
# 2022年度 交通社会システム論<br>第4回：線形計画問題(3) 双対定理
[ポータルへ戻る](https://hackmd.io/@nagae/MTNS_2022)
<div style="text-align: center">

このページへは以下のQRコードまたはURLからアクセスできます：

<code style="font-size:20pt">https://hackmd.io/@nagae/MTNS_2022-Ch03</code>

</div>

# 用語の整理 | Notation and Definition
**主問題(primal)**
$$
\text{(P)} \max_{\boldsymbol{x}} \left\{\left.
\boldsymbol{c}^{\top} \boldsymbol{x}
\right| \boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b}, \boldsymbol{x} \geq \boldsymbol{0}
\right\}
$$

**双対問題(dual)**
$$
\text{(D)} \min_{\boldsymbol{y}} \left\{\left.
\boldsymbol{b}^{\top} \boldsymbol{y}
\right| \boldsymbol{A}^{\top} \boldsymbol{y} \geq \boldsymbol{c}, \boldsymbol{y} \geq \boldsymbol{0} \right\}
$$

- **標準最大化問題** の未知変数$\boldsymbol{x}$ が制約条件 $\boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b}, \boldsymbol{x} \geq \boldsymbol{0}$ を満たしている時や，その**双対問題** の未知変数$\boldsymbol{y}$ が制約条件 $\boldsymbol{A}^{\top}\boldsymbol{y} \geq \boldsymbol{c}, \boldsymbol{y} \geq \boldsymbol{0}$ を満たしている時，これらを ==**許容/実行可能**== (feasible) であるという．**許容** な未知変数を ==**許容解/実行可能解**== (feasible solution)という．
When the unknown variable $\boldsymbol{x}$ of a **standard maximization problem** satisfies $\boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b}$ and $\boldsymbol{x} \geq \boldsymbol{0}$, it is referred to as **feasible solution**.
- **許容解** の集合を ==**許容領域/実行可能集合**== (feasible set) という．
The set of feasible solutions are referred to as the feasible set.
- 線形計画問題の **許容領域** が空でないなら,この問題は ==**許容/ 実行可能**== (feasible) であるといい, そうでなければ ==**不能/実行不可能**== (infeasible) であるという.
A liner programming problem with non-empty feasible set is referred to as **feasible**. Otherwise, it is referred to as **infeasible**.
- **許容** な **標準最大化問題** の目的関数をどこまでも大きくできる時, その問題は ==**無界/非有界**== (unbounded) であるといい, そうでなければ ==**有界**== (bounded) であるという.
A feasible standard maximization problem is referred to as **unbounded** when its objective function is infinite. Otherwise, it is referred to as **bounded**.
- **許容** かつ **有界** な **標準最大化問題** の **許容解** $\boldsymbol{x}$ の中で目的関数 が最も大きいものをこの問題の ==**最適解**== (optimal solution) と 呼び, $\boldsymbol{x}^{\ast}$ で表す. **最適解**における目的関数の値 $\boldsymbol{c}^{\top} \boldsymbol{x}^{\ast}$ を, ==**最適値**== (objective value) と呼ぶ.
When a standard maximization problem is feasible and and bounded, its feasible solutions that maximize the objective are referred to as the **optimal solutions** and represented by $\boldsymbol{x}^{\ast}$. The value of the objective function at the optimal solution, $\boldsymbol{c}^{\top} \boldsymbol{x}^{\ast}$ is referred to as the **objective value**.
- **未知変数**,**実行可能性**,**許容領域**,**最適解**などを**主問題**もしくは**双対問題**について区別するとき, 主問題に関する諸概念は, ==**主変数**== (primal variables), ==**主実行可能**== (primal feasible), ==**主最適解**== (primal optimal solution) のように ==**主—**== (primal —) といい, 双対問題のこれらは ==**双対変数**== (dual variables), ==**双対実行可能**== (dual feasible) や ==**双対最適解**== (dual optimal solution) のように ==**双対—**== (dual —) という.
When it is necessary to distinguish the unknown variables, feasibility/constraints, and optimal solutions, etc. with respect to the primal problem and dual problem, we use the prefixes "primal-" and "dual-", respectively.

# 双対問題に関する各種定理 | Duality Theorems
## 基本定理 | Basic Theory
:::success
**実行可能** で **有界** な線形計画問題は **最適解** を持つ.
If a LP is feasible and bounded, it has an optimal solution.
:::

## 弱双対定理 | Weak Duality Theorem
:::success
$\text{(P)}$および$\text{(D)}$ の任意の **許容解** $\boldsymbol{x}, \boldsymbol{y}$ に対して，*$\text{(P)}$の目的関数値は $\boldsymbol{(D)}$ の目的関数値を超えない*：
$$
\boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b}, \boldsymbol{x} \geq \boldsymbol{0} \text{ and }
\boldsymbol{A}^{\top} \boldsymbol{y} \geq \boldsymbol{c}, \boldsymbol{y} \geq \boldsymbol{0}
\rightarrow
\boldsymbol{c}^{\top} \boldsymbol{x} \leq \boldsymbol{b}^{\top} \boldsymbol{y}
$$
If $\boldsymbol{x}$ is a feasible solution of the primal problem $\text{(P)}$ and $\boldsymbol{y}$ is a feasible solution of the dual problem $\text{(D)}$, then the primal objective does not exceed the dual objective. That is,
$$
\boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b}, \boldsymbol{x} \geq \boldsymbol{0} \text{ and }
\boldsymbol{A}^{\top} \boldsymbol{y} \geq \boldsymbol{c}, \boldsymbol{y} \geq \boldsymbol{0}
\rightarrow
\boldsymbol{c}^{\top} \boldsymbol{x} \leq \boldsymbol{b}^{\top} \boldsymbol{y}
$$
:::

## 双対定理 | Strong Duality Theorem
:::success
$\text{(P)}$または$\text{(D)}$が **最適解** を持つならば，他方も最適解を持ち，その **最適値** は等しい:
$$
\boldsymbol{c}^{\top} \boldsymbol{x}^{\ast} =
{\boldsymbol{b}}^{\top} \boldsymbol{y}^{\ast}
$$
If a primal problem $\text{(P)}$ has an optimal solution, its dual $\text{(D)}$ also has an optimal solution, and their optimal values are equivalent:
$$
\boldsymbol{c}^{\top} \boldsymbol{x}^{\ast} =
{\boldsymbol{b}}^{\top} \boldsymbol{y}^{\ast}
$$

:::

## 相補性定理 | Complementarity Theorem
:::success
$\text{(P)}$および$\text{(D)}$のそれぞれの **許容解** $\boldsymbol{x}$ および$\boldsymbol{y}$ がともに **最適解** であるための ==**必要十分条件**== は，以下の2つの条件がともに成立することである：
$$
\boldsymbol{x}^{\top} \left(
\boldsymbol{c} - \boldsymbol{A}^{\top} \boldsymbol{y}
\right) = 0
\qquad
\left(\boldsymbol{A} \boldsymbol{x} - \boldsymbol{b}\right)^{\top} \boldsymbol{y} = 0
$$

Suppose $\boldsymbol{x}$ and $\boldsymbol{y}$ are a primal feasible solution and a dual feasible solution, then these are optimal if and only if:

$$
\boldsymbol{x}^{\top} \left(
\boldsymbol{c} - \boldsymbol{A}^{\top} \boldsymbol{y}
\right) = 0
\qquad
\left(\boldsymbol{A} \boldsymbol{x} - \boldsymbol{b}\right)^{\top} \boldsymbol{y} = 0
$$
:::
上記2つの条件を合わせて ==**相補性条件**== (complementarity condition)と呼ぶ． なお， ==**相補性条件**== は以下のように展開表示できる：
These two conditions are referred to as **complementarity conditions**, which can be written down as follows:

$$\begin{align*}
\boldsymbol{x}^{\top}\left(\boldsymbol{c} - \boldsymbol{A}^{\top} \boldsymbol{y}\right) = 0
&\Leftrightarrow
\sum_{i=1}^{N} x_{i} \left(c_{i} - \sum_{j=1}^{M} a_{ij} y_{j}\right) = 0\\
&\Leftrightarrow
x_{i} \left(c_{i} - \sum_{j=1}^{M} a_{ij} y_{j}\right) = 0, \quad \forall i = 1, \cdots, N\\
&\Leftrightarrow
\begin{cases}
x_{i} > 0 &\rightarrow
\sum_{j=1}^{M} a_{ij} y_{j} = c_{i} \\
x_{i} = 0 &\leftarrow
\sum_{j=1}^{M} a_{ij} y_{j} > c_{i}
\end{cases}
\quad & i = 1, \cdots, N\\
\end{align*}$$

$$
\begin{align*}
\left(\boldsymbol{A}\boldsymbol{x} - \boldsymbol{b}\right)^{\top} \boldsymbol{y} = 0 &\Leftrightarrow
\sum_{j=1}^{M} y_{j} \left(\sum_{i=1}^{N} a_{ij} x_{i} - b_{i}\right) = 0
\\
&\Leftrightarrow y_{j}\left(\sum_{i=1}^{N} a_{ij} x_{i} - b_{i}\right) = 0, \quad \forall j = 1, \cdots, M
\\
&\Leftrightarrow \begin{cases}
y_{j} > 0 &\rightarrow
\sum_{i=1}^{N} a_{ij} x_{i} = b_{j} \\
y_{j} = 0 &\leftarrow
\sum_{i=1}^{N} a_{ij} x_{i} < b_{j}
\end{cases}
\quad & j = 1, \cdots, M\\
\end{align*}
$$

# 弱双対定理の証明 | Proof of Weak Duality Theorem
$\boldsymbol{x}, \boldsymbol{y}$ を主許容解および双対許容解とすれば，
Suppose that $\boldsymbol{x}$ is a primal feasible solution and $\boldsymbol{y}$ is a dual feasible solution. Then
$$
\begin{align*}
\boldsymbol{c}^{\top} \boldsymbol{x} &\leq
\left(\boldsymbol{y}^{\top} \boldsymbol{A}\right) \boldsymbol{x}
&& \text{[} \because \boldsymbol{y}^{\top} \boldsymbol{A} \geq \boldsymbol{c}^{\top}, \boldsymbol{x} \geq \boldsymbol{0} \text{]} \\
&= \boldsymbol{y}^{\top} \boldsymbol{A} \boldsymbol{x} \\
& \leq \boldsymbol{y}^{\top} \boldsymbol{b} &&\text{[} \because \boldsymbol{A}\boldsymbol{x} \leq \boldsymbol{b}, \boldsymbol{y} \geq \boldsymbol{0}\text{]}
\end{align*}
$$
(Q.E.D)．

## 弱双対定理の系 | Corollaries of Weak Duality Theorem
**弱双対定理**より，以下の系が直ちに導かれる．
From the weak duality theorem, the following corollaries can be obtained.

### 系(1) | Corollary (1)
$\text{(P)}$ または $\text{(D)}$ が **無界** ならば，他方は **不能** である．
If a primal is **unbounded**, then its dual is **infeasible**.

### 系(2)(目的関数が一致する→最適解)| Corollary (2)
**主許容解**$\boldsymbol{x}$ および**双対許容解**$\boldsymbol{y}$ の*目的関数値が一致する*：
$$
\boldsymbol{c}^{\top} \boldsymbol{x} = \boldsymbol{b}^{\top} \boldsymbol{y}
$$
ならば，これらは，それぞれ，主問題および双対問題の **最適解** である．

If the objective of a primal feasible solution $\boldsymbol{x}$ and that of a dual feasible solution are equivalent:
$$
\boldsymbol{c}^{\top} \boldsymbol{x} = \boldsymbol{b}^{\top} \boldsymbol{y},
$$
then $\boldsymbol{x}$ is a primal optimal solution as well as $\boldsymbol{y}$ is a dual optimal solution.

# Farkas の補題 | Farkas' Lemma
**双対定理**の証明に入る前に, ==**Farkas の補題**== を紹介しておこう．
In order to prove the strong duality theorem, let me introduce Farkas' lemma.

## Farkasの補題 | Farkas' lemma
$M+1$ 本の$N$次元列ベクトル$\boldsymbol{a}_{1}, \cdots, \boldsymbol{a}_{M}$および$\boldsymbol{c}$が与えられたとき，以下の ==**いずれか一方のみ**== が常に成り立つ：
1. $\sum_{j=1}^{M} \boldsymbol{a}_{j} y_{j} = \boldsymbol{c}$ なる$M$個の **非負の実数** $y_{1}, \cdots, y_{M}$ が存在する;
2. 任意の$j=1, \cdots, M$に対して $\boldsymbol{a}_{j}^{\top} \boldsymbol{x} \geq 0$ かつ $\boldsymbol{c}^{\top}\boldsymbol{x} < 0$なる$N$次元列ベクトル$\boldsymbol{x}$が存在する．

これらは$M\times{}N$行列$\boldsymbol{A} = \begin{bmatrix}\boldsymbol{a}_{1}^{\top} \\ \vdots \\ \boldsymbol{a}_{M}^{\top}\end{bmatrix}$を用いて以下のようにも表現できる：
1. $\boldsymbol{A}^{\top} \boldsymbol{y} = \boldsymbol{c}, \boldsymbol{y} \geq \boldsymbol{0}$なるベクトル$\boldsymbol{y} \in \mathcal{R}^{M}$が存在する;
2. $\boldsymbol{A}\boldsymbol{x} \geq \boldsymbol{0}$かつ$\boldsymbol{c}^{\top} \boldsymbol{x} < 0$ なるベクトル$\boldsymbol{x} \in \mathcal{R}^{N}$が存在する.

Given $M+1$ column vectors with $N$ dimension $\boldsymbol{a}_{1}, \cdots, \boldsymbol{a}_{M}$ and $\boldsymbol{c}$, only one of the following two conditions is always satisfied:
1. There is $M$ non-negative real values $y_{1}, \cdots, y_{M}$ that satisfy $\sum_{j=1}^{M} \boldsymbol{a}_{j} y_{j} = \boldsymbol{c}$;
2. There is a $N$-dimensional column $\boldsymbol{x}$ that satisfies $\boldsymbol{c}^{\top}\boldsymbol{x} < 0$ and $\boldsymbol{a}_{j}^{\top} \boldsymbol{x} \geq 0$ for any $j=1, \cdots, M$.

These propositions can be rewritten by using a $M\times{}N$ matrix $\boldsymbol{A} = \begin{bmatrix}\boldsymbol{a}_{1}^{\top} \\ \vdots \\ \boldsymbol{a}_{M}^{\top}\end{bmatrix}$as follows.
1. A vector $\boldsymbol{y} \in \mathcal{R}^{M}$ exists such that $\boldsymbol{A}^{\top} \boldsymbol{y} = \boldsymbol{c}, \boldsymbol{y} \geq \boldsymbol{0}$;
2. A vector $\boldsymbol{x} \in \mathcal{R}^{N}$ exists such that $\boldsymbol{A}\boldsymbol{x} \geq \boldsymbol{0}$ and $\boldsymbol{c}^{\top} \boldsymbol{x} < 0$.

## Farkasの補題の幾何学的イメージ | Geometric Image of Farkas' Lemma
$N=2$, $M=3$の場合を考え， 3つのベクトル$\boldsymbol{a}_{1}, \boldsymbol{a}_{2}, \boldsymbol{a}_{3}$から生成される凸錐(cone)を $\mathcal{C}$ とする．
Suppose $N=2$ and $M=3$. Let $\mathcal{C}$ be the convex cone consists of three columns $\boldsymbol{a}_{1}, \boldsymbol{a}_{2}$ and $\boldsymbol{a}_{3}$.

■ $\boldsymbol{c}\in\mathcal{C}$ の場合 (たとえば$\boldsymbol{c}=\boldsymbol{c}_{1}$) | Case with $\boldsymbol{c} \in \mathcal{C}$ (e.g. $\boldsymbol{c}=\boldsymbol{c}_{1}$)
このとき，$\boldsymbol{c}$は$\boldsymbol{a}_{1}, \boldsymbol{a}_{2}, \boldsymbol{a}_{3}$の**線形結合**で表される:
In this case, $\boldsymbol{c}$ can be represented by a convex combination of $\boldsymbol{a}_{1}, \boldsymbol{a}_{2}, \boldsymbol{a}_{3}$:
$$
\boldsymbol{c} = \boldsymbol{a}_{1} y_{1} + \boldsymbol{a}_{2} y_{2} + \boldsymbol{a}_{3} y_{3}, \quad
y_{1}, y_{2}, y_{3} \geq 0
$$
このことは，上述の1が成立することを意味する:
This implies that the condition 1 is met:
$$\exists \boldsymbol{y} \in \mathcal{R}^{M}: \boldsymbol{A}^{\top}\boldsymbol{y} = \boldsymbol{c}, \boldsymbol{y} \geq \boldsymbol{0}.$$

■ $\boldsymbol{c}\not\in\mathcal{C}$ の場合(たとえば$\boldsymbol{c}=\boldsymbol{c}_{2}$) | Case with $\boldsymbol{c} \not\in \mathcal{C}$ (e.g. $\boldsymbol{c}=\boldsymbol{c}_{2}$)
このとき，凸錐 $\mathcal{C}$ とベクトル $\boldsymbol{c}$ を**分離する超平面**(図の破線)が(無数に)存在し， そうした分離超平面の中で，法線ベクトル$\boldsymbol{x}$ が $\boldsymbol{x}^{\top} \boldsymbol{c}<0$ なるものを選べば，$\boldsymbol{a}_{1}^{\top}\boldsymbol{x} \geq 0, \boldsymbol{a}_{2}^{\top}\boldsymbol{x} \geq 0,\boldsymbol{a}_{3}^{\top}\boldsymbol{x} \geq 0$が成り立つ． このことは，上述の2が成立することを意味する:
In this case, there exist a hyperplane that separate the convex cone $\mathcal{C}$ and the vector $\boldsymbol{c}$ with normal $\boldsymbol{x}$ that satisfies $\boldsymbol{x}^{\top} \boldsymbol{c} < 0$ (the dashed line in the above figure). Then it satisfies $\boldsymbol{a}_{1}^{\top}\boldsymbol{x} \geq 0, \boldsymbol{a}_{2}^{\top}\boldsymbol{x} \geq 0$ and $\boldsymbol{a}_{3}^{\top}\boldsymbol{x} \geq 0$. This implies that the condition 2 is met:
$$\exists \boldsymbol{x} \in \mathcal{R}^{N}:
\boldsymbol{A}\boldsymbol{x} \geq \boldsymbol{0} \text{ and } \boldsymbol{c}^{\top} \boldsymbol{x} < 0
$$

# 双対定理の証明 | Proof of Strong Duality Theorem
背理法を用いて証明する．$\text{(P)}$が最適解$\boldsymbol{x}^{\ast}$をもつとしよう．このとき，$\text{(D)}$が${\boldsymbol{b}}^{\top}\boldsymbol{y}^{\ast} \leq \boldsymbol{c}^{\top} \boldsymbol{x}^{\ast}$ となる許容解を持てば，**弱双対定理**とその **[系(2)](https://hackmd.io/QgXgc9XqRNmAiGB-D1QDzQ?both#%E7%B3%BB2%E7%9B%AE%E7%9A%84%E9%96%A2%E6%95%B0%E3%81%8C%E4%B8%80%E8%87%B4%E3%81%99%E3%82%8B%E2%86%92%E6%9C%80%E9%81%A9%E8%A7%A3)** より$\boldsymbol{y}^{\ast}$は**双対最適解**となる． ここでは，*そのような$\boldsymbol{y}^{\ast}$が存在しないとして，矛盾を導く*．
Suppose that $\text{(P)}$ has an optimal solution $\boldsymbol{x}^{\ast}$. If $\text{(D)}$ has a feasible solution $\boldsymbol{y}^{\ast}$ that satisfies $\boldsymbol{b}^{\top} \boldsymbol{y}^{\ast} \leq \boldsymbol{c}^{\top} \boldsymbol{x}^{\ast}$, it is dual optimal from weak duality theorem and its corollary (2). Assuming that no such $\boldsymbol{y}^{\ast}$ exists, we derive a contradiction.

まず，${\boldsymbol{b}}^{\top} \boldsymbol{y}^{\ast} \leq \boldsymbol{c}^{\top} \boldsymbol{x}^{\ast}$ なる$\text{(D)}$ の**許容解**，すなわち
$$
\boldsymbol{b}^{\top} \boldsymbol{y} \leq \boldsymbol{c}^{\top} \boldsymbol{x}^{\ast}, \quad
\boldsymbol{A}^{\top} \boldsymbol{y} \geq \boldsymbol{c}, \quad \boldsymbol{y} \geq \boldsymbol{0}
$$
を満足する ***$\boldsymbol{y}$が存在しない**と仮定する*．これは，
$$
\begin{bmatrix}
\boldsymbol{b}^{\top} &\boldsymbol{0}^{\top} &1 \\
-\boldsymbol{A}^{\top} & \boldsymbol{I} & \boldsymbol{0}
\end{bmatrix}\begin{bmatrix}
\boldsymbol{y} \\ \boldsymbol{u} \\ v
\end{bmatrix}
=\begin{bmatrix}
\boldsymbol{c}^{\top} \boldsymbol{x}^{\ast} \\
-\boldsymbol{c}
\end{bmatrix}, \quad \begin{bmatrix}
\boldsymbol{y} \\ \boldsymbol{u} \\ v
\end{bmatrix} \geq \boldsymbol{0}
$$
を満たす ***$(\boldsymbol{y}, \boldsymbol{u}, v) \in \mathcal{R}^{M+N+1}$が存在しない*** ことと等価である．
なお，上の2つの式が等価であることは， 上式を
$$
\begin{cases}
\boldsymbol{b}^{\top} \boldsymbol{y} + v = \boldsymbol{c}^{\top} \boldsymbol{x}^{\ast} \\
-\boldsymbol{A}^{\top} \boldsymbol{y} + \boldsymbol{u} = - \boldsymbol{c} \\
\boldsymbol{y}, \boldsymbol{u}, v \geq \boldsymbol{0}
\end{cases}
$$
と展開すれば明らか．

First, we assume that there is no feasible solution $\boldsymbol{y}^{\ast}$of $\text{(D)}$ that satisfies ${\boldsymbol{b}}^{\top} \boldsymbol{y}^{\ast} \leq \boldsymbol{c}^{\top} \boldsymbol{x}^{\ast}$ なる$\text{(D)}$. That is, assume that there is no $\boldsymbol{y}$ such that
$$
\boldsymbol{b}^{\top} \boldsymbol{y} \leq \boldsymbol{c}^{\top} \boldsymbol{x}^{\ast}, \quad
\boldsymbol{A}^{\top} \boldsymbol{y} \geq \boldsymbol{c}, \quad \boldsymbol{y} \geq \boldsymbol{0}.
$$
This is equivalent to assume that there is no $(\boldsymbol{y}, \boldsymbol{u}, v) \in \mathcal{R}^{M+N+1}$ such that
$$
\begin{bmatrix}
\boldsymbol{b}^{\top} &\boldsymbol{0}^{\top} &1 \\
-\boldsymbol{A}^{\top} & \boldsymbol{I} & \boldsymbol{0}
\end{bmatrix}\begin{bmatrix}
\boldsymbol{y} \\ \boldsymbol{u} \\ v
\end{bmatrix}
=\begin{bmatrix}
\boldsymbol{c}^{\top} \boldsymbol{x}^{\ast} \\
-\boldsymbol{c}
\end{bmatrix}, \quad \begin{bmatrix}
\boldsymbol{y} \\ \boldsymbol{u} \\ v
\end{bmatrix} \geq \boldsymbol{0}
$$
A straightforward mathematics shows that the above two equations are equivalent: the above equation can be written down as
$$
\begin{cases}
\boldsymbol{b}^{\top} \boldsymbol{y} + v = \boldsymbol{c}^{\top} \boldsymbol{x}^{\ast} \\
-\boldsymbol{A}^{\top} \boldsymbol{y} + \boldsymbol{u} = - \boldsymbol{c} \\
\boldsymbol{y}, \boldsymbol{u}, v \geq \boldsymbol{0}
\end{cases}\Leftrightarrow
\begin{cases}
\boldsymbol{b}^{\top} \boldsymbol{y} \leq \boldsymbol{c}^{\top} \boldsymbol{x}^{\ast}\\
\boldsymbol{A}^{\top} \boldsymbol{y} \geq \boldsymbol{c}\\
\boldsymbol{y} \geq \boldsymbol{0}
\end{cases}
$$
このとき，**Farkasの補題**より，以下を満足する$(w, \boldsymbol{z}) \in \mathcal{R}^{1+N}$が存在する:
From Farkas' lemma, there exists $(w, \boldsymbol{z}) \in \mathcal{R}^{1+N}$ that satisfies
$$
\begin{bmatrix}
\boldsymbol{b} & -\boldsymbol{A} \\
\boldsymbol{0} & \boldsymbol{I} \\
1 & \boldsymbol{0}^{\top}
\end{bmatrix}\begin{bmatrix}
w \\ \boldsymbol{z}
\end{bmatrix} \geq \boldsymbol{0} \text{ and }
\left(\boldsymbol{c}^{\top} \boldsymbol{x}^{\ast} \right) w - \boldsymbol{c}^{\top}\boldsymbol{z} < 0.
$$
すなわち，以下を満たす非負変数のペア$w \in \mathcal{R}_{+}$ および $\boldsymbol{z} \in \mathcal{R}_{+}^{N}$ が存在する．
Or, equivalently, there exists a pair of non-negative variables $w \in \mathcal{R}_{+}$ and $\boldsymbol{z} \in \mathcal{R}_{+}^{N}$ such that
$$
\boldsymbol{A}\boldsymbol{z} \leq \boldsymbol{b}w, \qquad
\left(\boldsymbol{c}^{\top} \boldsymbol{x}^{\ast} \right) w < \boldsymbol{c}^{\top}\boldsymbol{z}
$$
以降，$w=0$の場合と$w>0$の場合のそれぞれで矛盾を導く．
Let us derive a contradiction for each of the cases with $w=0$ and $w>0$.

■ $w=0$ の場合 | Case with $w=0$.
$\boldsymbol{z} \in \mathcal{R}^{N}$は$\boldsymbol{A}\boldsymbol{z} \leq \boldsymbol{0}, \boldsymbol{z}\geq \boldsymbol{0}$かつ$\boldsymbol{c}^{\top} \boldsymbol{z} > 0$を満たすため，任意の正の数$\lambda$に対して， $\boldsymbol{x}^{\ast} + \lambda \boldsymbol{z}$ は
$$
\boldsymbol{A}\left(\boldsymbol{x}^{\ast} + \lambda \boldsymbol{z} \right) \leq \boldsymbol{b}, \qquad \boldsymbol{x}^{\ast} + \lambda \boldsymbol{z} \geq \boldsymbol{0}, \qquad \boldsymbol{c}^{\top} \left(\boldsymbol{x}^{\ast} + \lambda \boldsymbol{z}\right) > \boldsymbol{c}^{\top} \boldsymbol{x}^{\ast}
$$
を満たす(i.e. $\boldsymbol{x}^{\ast}+\lambda \boldsymbol{z}$は主実行可能かつ$\boldsymbol{x}^{\ast}$よりも高い目的関数を実現する)． これは$\boldsymbol{x}^{\ast}$が$\text{(P)}$の最適解であるという仮定に ==**矛盾する**==.

Since $\boldsymbol{z} \in \mathcal{R}^{N}$ satisfies $\boldsymbol{A}\boldsymbol{z} \leq \boldsymbol{0}, \boldsymbol{z}\geq \boldsymbol{0}$ and $\boldsymbol{c}^{\top} \boldsymbol{z} > 0$, for any non-negative scholar $\lambda$, $\boldsymbol{x}^{\ast} + \lambda \boldsymbol{z}$ satisfies the following inequality:
$$
\boldsymbol{A}\left(\boldsymbol{x}^{\ast} + \lambda \boldsymbol{z} \right) \leq \boldsymbol{b}, \qquad \boldsymbol{x}^{\ast} + \lambda \boldsymbol{z} \geq \boldsymbol{0}, \qquad \boldsymbol{c}^{\top} \left(\boldsymbol{x}^{\ast} + \lambda \boldsymbol{z}\right) > \boldsymbol{c}^{\top} \boldsymbol{x}^{\ast}
$$
In other words, $\boldsymbol{x}^{\ast} + \lambda \boldsymbol{z}$ is primally feasible and has a larger objective than $\boldsymbol{x}^{\ast}$. This **contradicts** the assumption that $\boldsymbol{x}^{\ast}$ is an optimal solution of $\text{(P)}$.

■ $w>0$の場合 | Case with $w>0$
$\boldsymbol{z}/w$は$\text{(P)}$の許容解であり，かつ$\boldsymbol{c}^{\top} (\boldsymbol{z}/w) > \boldsymbol{c}^{\top} \boldsymbol{x}^{\ast}$ となるため，やはり$\boldsymbol{x}^{\ast}$ が最適解であるという仮定に ==**矛盾する**==．
Since $\boldsymbol{z}/w$ is a feasible solution of $\text{(P)}$ and $\boldsymbol{c}^{\top} (\boldsymbol{z}/w) > \boldsymbol{c}^{\top} \boldsymbol{x}^{\ast}$. This also contradicts the assumption that $\boldsymbol{x}^{\ast}$ is an optimal solution.

以上のことから，$\text{(P)}$が最適解$\boldsymbol{x}^{\ast}$を持つとき， $\text{(D)}$は
$$\boldsymbol{b}^{\top}\boldsymbol{y}^{\ast} \leq \boldsymbol{c}^{\top} \boldsymbol{x}^{\ast}$$
満たす許容解$\boldsymbol{y}^{\ast}$を持つ． **[弱双対定理](https://hackmd.io/@nagae/MTNS_2020-Ch03#%E5%BC%B1%E5%8F%8C%E5%AF%BE%E5%AE%9A%E7%90%86)** ($\boldsymbol{c}^{\top}\boldsymbol{x} \leq \boldsymbol{y}^{\top} \boldsymbol{b}$)より，このとき
$$
\boldsymbol{b}^{\top}\boldsymbol{y}^{\ast} = \boldsymbol{c}^{\top} \boldsymbol{x}^{\ast}
$$
が成り立つから， $\boldsymbol{y}^{\ast}$ は$\text{(D)}$ の最適解に他ならない． (証明終わり)

Accordingly, when $\text{(P)}$ has an optimal solution $\boldsymbol{x}^{\ast}$, the dual $\text{(D)}$ has a feasible solution $\boldsymbol{y}^{\ast}$ that satisfies
$$\boldsymbol{b}^{\top}\boldsymbol{y}^{\ast} \leq \boldsymbol{c}^{\top} \boldsymbol{x}^{\ast}.$$
From weak duality theorem (i.e. $\boldsymbol{c}^{\top}\boldsymbol{x} \leq \boldsymbol{y}^{\top} \boldsymbol{b}$), we have
$$
\boldsymbol{b}^{\top}\boldsymbol{y}^{\ast} = \boldsymbol{c}^{\top} \boldsymbol{x}^{\ast}.
$$
This implies that $\boldsymbol{y}^{\ast}$ is an optimal solution of $\text{(D)}$. (Q.E.D.)

# 相補性定理の証明 | Proof of Complementarity Theorem
[弱双対定理](https://hackmd.io/@nagae/MTNS_2020-Ch03#%E5%BC%B1%E5%8F%8C%E5%AF%BE%E5%AE%9A%E7%90%86)と[双対定理](https://hackmd.io/@nagae/MTNS_2020-Ch03#%E5%8F%8C%E5%AF%BE%E5%AE%9A%E7%90%86)より，$\text{(P)}$および$\text{(D)}$の許容解$\boldsymbol{x}$および$\boldsymbol{y}$が最適解であるための ==**必要十分条件**== は，
$$
\boldsymbol{c}^{\top} \boldsymbol{x} = \boldsymbol{y}^{\top} \boldsymbol{b}
$$
なので，これを示す．$\boldsymbol{x}$と$\boldsymbol{y}$は許容であるから，
$$
\boldsymbol{y}^{\top} \boldsymbol{b} \geq \boldsymbol{y}^{\top} \left(\boldsymbol{A}\boldsymbol{x}\right)
= \left(\boldsymbol{y}^{\top} \boldsymbol{A} \right) \boldsymbol{x} \geq \boldsymbol{c}^{\top} \boldsymbol{x}
$$
が成り立つ．

$\boldsymbol{c}^{\top} \boldsymbol{x} = \boldsymbol{y}^{\top} \boldsymbol{b}$ となるための必要十分条件は，上式の2つの不等式で等号が成り立つ，すなわち，
$$
\begin{cases}
\boldsymbol{y}^{\top} \boldsymbol{b} = \boldsymbol{y}^{\top}\left(\boldsymbol{A}\boldsymbol{x}\right) \\
\left(\boldsymbol{y}^{\top}\boldsymbol{A}\right)\boldsymbol{x} = \boldsymbol{c}^{\top} \boldsymbol{x}
\end{cases}
\Leftrightarrow
\begin{cases}
\boldsymbol{y}^{\top} \left(
\boldsymbol{b} - \boldsymbol{A}\boldsymbol{x}\right) =0\\
\left(\boldsymbol{y}^{\top}\boldsymbol{A}-\boldsymbol{c}^{\top}\right)\boldsymbol{x} = 0
\end{cases}
$$
が満たされることである．これは相補性条件に他ならない．
(証明終わり)

From weak and strong duality theorems, a feasible solution $\boldsymbol{x}$ of $\text{(P)}$ and a feasible solution $\boldsymbol{y}$ of $\text{(D)}$ are optimal if and only if
$$
\boldsymbol{c}^{\top} \boldsymbol{x} = \boldsymbol{y}^{\top} \boldsymbol{b}.
$$
Since $\boldsymbol{x}$ is primally feasible as well as $\boldsymbol{y}$ is dually feasible, the following is met.
$$
\boldsymbol{y}^{\top} \boldsymbol{b} \geq \boldsymbol{y}^{\top} \left(\boldsymbol{A}\boldsymbol{x}\right)
= \left(\boldsymbol{y}^{\top} \boldsymbol{A} \right) \boldsymbol{x} \geq \boldsymbol{c}^{\top} \boldsymbol{x}
$$
From this inequality, $\boldsymbol{c}^{\top} \boldsymbol{x} = \boldsymbol{y}^{\top} \boldsymbol{b}$ holds if and only if both of two inequalities hold equality. That is,
$$
\boldsymbol{c}^{\top} \boldsymbol{x} = \boldsymbol{y}^{\top} \boldsymbol{b}
\Leftrightarrow
\begin{cases}
\boldsymbol{y}^{\top} \boldsymbol{b} = \boldsymbol{y}^{\top}\left(\boldsymbol{A}\boldsymbol{x}\right) \\
\left(\boldsymbol{y}^{\top}\boldsymbol{A}\right)\boldsymbol{x} = \boldsymbol{c}^{\top} \boldsymbol{x}
\end{cases}
\Leftrightarrow
\begin{cases}
\boldsymbol{y}^{\top} \left(
\boldsymbol{b} - \boldsymbol{A}\boldsymbol{x}\right) =0\\
\left(\boldsymbol{y}^{\top}\boldsymbol{A}-\boldsymbol{c}^{\top}\right)\boldsymbol{x} = 0
\end{cases}
$$
(Q.E.D.)