📂最適化理論

線形計画問題において最適解が存在する場合、そのうちの一つは基底実行可能解である

定理 ¹

$$ \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}$ について、線形計画問題が上のように方程式の形で表されるとする。もし最適解が存在するならば、最適基底実行可能解も存在する。

---

• $\mathbf{c}^{T}$ は転置を意味する。
• 実行可能解とは、最適化とは関係なく制約条件を満たす解のことである。

証明

戦略：この証明は本質的に最適解の存在証明と同じである。

基底実行可能解の定義：実行可能解 $\mathbf{x} \in \mathbb{R}^{n}$ に対して、集合 $B \subseteq [n]$ が存在してその濃度が $m$ であり、$\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} $$ 例えば、$K = \left\{ 2,3,5 \right\}$ が $\mathbf{v} = (-2,1,7)$ であれば、$\mathbf{w}$ は $2,3,5$ 番目の成分が $\mathbf{v}$ と同じで他が $0$ のベクトル$\mathbf{w}= (0,-2,1,0,7)$ になるなど、$\mathbf{w}_{K} = \mathbf{v}$ と $A \mathbf{w} = A_{K} \mathbf{v} = \mathbf{0}$ を満たすように拡張したベクトル$\mathbf{w} \in \mathbb{R}^{n}$ を考えることができる。このとき、$\mathbf{w}$ は元の$\mathbf{v}$ の成分の符号を再調整することで $$ \mathbf{c}^{T} \mathbf{w} > 0 $$ も満たすことができる。これから言及される$\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)$ も実行可能解であるが、これは目的関数が上界を持つという仮定に矛盾するので、 $$ \mathbf{c}^{T} \mathbf{x} (t) = \mathbf{c}^{T} \tilde{\mathbf{x}} + t \mathbf{c}^{T} \mathbf{w} \to \infty $$ したがって、少なくとも1つの$w_{j_{0}}$ が負であれば、いずれ $$ 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つは基底実行可能解でなければならない。

■

参照

線形計画法の基本定理

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