📂最適化理論

線形計画問題の基底解

定義 ¹

$$ \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{x} \in \mathbb{R}^{n}$ に対して、次の二つの条件を満たすとき、基数 $m$ の集合 $B \subseteq [n]$ が存在し、$\mathbf{x} = \left( x_{1} , \cdots , x_{n} \right)$ を基底可能解^{basic Feasible Solution}という。

• (i): $\exists A_{B}^{-1}$
• (ii): $x_{j} = 0 \forall j \notin B$

この場合、$x_{j}$を基底変数^{basic variable}、集合 $B$ を基底^basisと呼ぶ。基底可能解である可能解は形容詞形を使用して、可能解がベーシック^basicであると言える。

---

• $\mathbf{c}^{T}$は[転置]を意味する。
• [可能解]とは、最適化とは無関係に、制約条件を満たす解のことである。
• $[n] = \left\{ 1, \cdots , n \right\}$は $1$ から $n$ までの自然数の集合である。
• $A_{B}$は、行列 $A$ から集合 $B$ に列挙された列のみを取った正方行列である。

説明

定義は言葉が多くて難しそうに見えるけど、実はたいしたことないから、怖がらないでほしい。

基底可能解は、とにかく可能解に関する議論であって、$\mathbf{c} \in \mathbb{R}^{n}$は全く関係ない。

例

$$ \begin{align*} A =& \begin{bmatrix} 1 & 5 & 3 & 4 & 6 \\ 0 & 1 & 3 & 5 & 6 \end{bmatrix} \\ \mathbf{b} =& \begin{bmatrix} 14 \\ 7 \end{bmatrix} \end{align*} $$ とするとき、$\mathbf{x} = (0,2,0,1,0)$は方程式フォームで二つの制約 $$ \begin{align*} 1 x_{1} + 5 x_{2} + 3 x_{3} + 4 x_{4} + 6 x_{5} =& 14 \\ 0 x_{1} + 1 x_{2} + 3 x_{3} + 5 x_{4} + 6 x_{5} =& 7 \end{align*} $$ を満たす可能解である。ここで、$\mathbf{x}$の成分としては、$x_{2}, x_{4}$のみが使用された^条件(ii)、かつ $$ A_{B} = \begin{bmatrix} 5 & 4 \\ 1 & 5 \end{bmatrix} $$ が非特異^nonsingularである^条件(i)ため、可能解$\mathbf{x}$は基底可能解である。

幾何学的説明

$A \in \mathbb{R}^{1 \times 3}$の場合、つまり制約が$m=1$個で解空間の次元が$n = 3$の線型計画問題を考えてみよう。

はっきり言って、基底可能解とは上の図の三角錐で$\mathbf{0}$でない頂点^vertexのことを言う。現在、最適解ではなく可能解のみを考慮しているが、目的関数が非線形で曲がっていないのだから、最適解が辺^edgeの真ん中にあるとは思えないよね？もし最適解が存在するなら、それはその三つの頂点の中の一つにあるだろうし、これを抽象化して一般化したものが基底可能解の概念である。

一方、この解空間はまさに単体であり、ここから単体法のアイデアが生まれる。

代数的説明

$A_{B} \in \mathbb{R}^{m \times m}$ の逆行列 $A_{B}^{-1}$ が存在するということは、正方行列 $A_{B}$ の列ベクトルが線形独立であることを意味し、これは$n$個のすべての変数ではなく、正確に必要な$m \le n$個の変数だけを考えても十分であることを意味する。上の段落で幾何学的に見たとき、三つの頂点を表現するためにそれぞれ一つの次元だけを必要としたこととピッタリ合う。