📂最適化理論

線形計画問題の方程式形式における最適解の存在証明

定理 ¹

$$\begin{matrix} \text{Maximize} & \mathbf{c}^{T} \mathbf{x} \\ \text{subject to} & A \mathbf{x} = \mathbf{b} \\ & \mathbf{x} \ge \mathbf{0} \end{matrix}$$

行列$A \in \mathbb{R}^{m \times n}$、$\mathbf{b} \in \mathbb{R}^{m \times 1}$、そして$\mathbf{c} \in \mathbb{R}^{n}$に対する線形計画問題が上記のように方程式フォームで表されているとする。少なくとも1つの利用可能な解が存在し、利用可能な解の集合が$\mathbf{c}^{T} \mathbf{x}$で上に有界ならば、最適解が存在する。

---

• $\mathbf{c}^{T}$は転置を意味する。
• 利用可能な解とは、最適化とは無関係にとりあえず制約条件を満たす解を言う。

証明

戦略: この証明は本質的に、もし最適解が存在するならば、そのうちの1つは基本利用可能解であるという定理の証明と同じである。

基本利用可能解の定義: 利用可能な解 $\mathbf{x} \in \mathbb{R}^{n}$に対して、基数が$m$である集合$B \subseteq [n]$が存在し、$\exists A_{B}^{-1}$かつ$x_{j} = 0 \forall j \notin B$である$\mathbf{x} = \left( x_{1} , \cdots , x_{n} \right)$を基本利用可能解という。この集合$B$を基底と呼ぶ。

任意の利用可能な解$\mathbf{x}_{0}$に対して $$\mathbf{c}^{T} \mathbf{x}_{0} \le \mathbf{c}^{T} \mathbf{x}$$ $\mathbf{x}$を満たす中で$0$が最も多い解を$\tilde{\mathbf{x}}$としよう。

• $\tilde{\mathbf{x}}$が基本利用可能解であることを示せば、基本利用可能解が有限に存在するため、最適解の存在を示すことができる。
• だから、どんな最適解も、最適解である前に利用可能な解であり、同じ目的関数の値を持つ（最適）基本利用可能解が存在するだろう。したがって、最適解の中には少なくとも1つは基本利用可能解が存在しなければならない。

これで指数の集合 $$K = \left\{ k \in [n] : \left( \tilde{\mathbf{x}} \right)_{k} > 0 \right\}$$ を定義したとき、$A_{K}$の列ベクトルが線形独立かどうかを考えてみよう。

---

ケース1. 線形独立

基本利用可能解の定義により、$\tilde{\mathbf{x}}$は自然と基本利用可能解であり、これ以上証明することはない。

---

ケース2. 線形従属

線形独立でなく線形従属であれば、次の条件を満たす何らかの$|K|$次元ベクトル$\mathbf{v} \in \mathbb{R}^{|K|}$が存在する。 $$A_{K} \mathbf{v} = \mathbf{0}$$ これについて、$\mathbf{w}_{K} = \mathbf{v}$と$A \mathbf{w} = A_{K} \mathbf{v} = \mathbf{0}$を満たすように拡張されたベクトル$\mathbf{w} \in \mathbb{R}^{n}$を考えることができる。例えば、$K = \left\{ 2,3,5 \right\}$ならば、$\mathbf{w}$は$2,3,5$番目の成分が$\mathbf{v}$で残りが$0$であるベクトル$\mathbf{w}= (0,-2,1,0,7)$になるというものである。このとき、$\mathbf{w}$は $$\mathbf{c}^{T} \mathbf{w} > 0$$ $\mathbf{v}$の成分の符号を調整することによっても満たすことができる。これ以降言及される$\mathbf{w}$は、上記の不等式を満たすベクトルとして考えよう。

これで、$\mathbf{w}$に対して、$t \ge 0$に従属する次のベクトル$\mathbf{x}(t)$を考えてみよう。 $$\mathbf{x} (t) = \tilde{\mathbf{x}} + t \mathbf{w}$$ まず$\tilde{\mathbf{x}}$は利用可能な解であり、$A \mathbf{w} = A_{K} \mathbf{v} = \mathbf{0}$を満たすようにされた$\mathbf{w}$の定義により、全ての$t \ge 0$に対して $$\begin{align*} A \mathbf{x} (t) =& A \tilde{\mathbf{x}} + t A \mathbf{w} \\ =& A \tilde{\mathbf{x}} \\ =& \mathbf{b} \end{align*}$$ である。言い換えれば、$\mathbf{x} (t)$も$\mathbf{x}(t) \ge 0$を除くすべての制約を満たす。一方、$\mathbf{x} (t)$の$j$番目の成分$x_{j}(t)$を考えると、$x_{j}(t) = \tilde{x}_{j} + t w_{j}$のように現れ、これらの少なくとも1つは$w_{j} < 0$でなければならない。もし全ての$j$に対して、$w_{j} > 0$ならば、全ての$t$に対して$\mathbf{x} (t) = \tilde{\mathbf{x}} + t \mathbf{w} \ge 0$となり、全ての$\mathbf{x} (t)$も利用可能な解となるが、目的関数が上に有界であるという仮定と矛盾する。少なくとも1つの$w_{j_{0}}$が負であれば、$t$を$0$から$\infty$に増やしていくと、いずれ $$x_{j_{0}} \left( t_{0} \right) = \tilde{x_{j_{0}}} + t_{0} w_{j_{0}} = 0$$ を初めて満たす$t_{0} \ge 0$が存在するだろう。すると、$\mathbf{x} \left( t_{0} \right)$は$\tilde{\mathbf{x}}$に比べて$0$の成分を1つ多く持ちながらも $$\begin{align*} \mathbf{c}^{T} \mathbf{x} \left( t_{0} \right) =& \mathbf{c}^{T} \tilde{\mathbf{x}} + t_{0} \mathbf{c}^{T} \mathbf{w} \\ \ge & \mathbf{c}^{T} \mathbf{x}_{0} + t_{0} \mathbf{c}^{T} \mathbf{w} \\ \ge & \mathbf{c}^{T} \mathbf{x}_{0} \end{align*}$$ も満たす。これは、$\mathbf{c}^{T} \mathbf{x}_{0} \le \mathbf{c}^{T} \mathbf{x}$を満たしながら$0$が最も多くなるようにした$\tilde{\mathbf{x}}$の定義に矛盾する。

---

基本利用可能解の一意性: 基本利用可能解は、基底$B$によって一意に決定される。

結果として、$A_{K}$は線形従属になることはできず、$\tilde{\mathbf{x}}$は基本利用可能解でなければならず、基底の選択によって決定される基本利用可能解は一意であるため、基本利用可能解が有限に多く存在して、最適解も存在する。全ての最適解も利用可能な解であり、どの最適解に対しても、同じ目的関数の値を持つ基本利用可能解が存在し、それらも最適解であるため、最適解の中には少なくとも1つは基本利用可能解が存在しなければならない。

■

参照

線形計画法の基本定理

この定理は、線形計画法の基本定理の証明で使用される。