📂最適化理論

シンプレックス・メソッドのサイクリング

定義

$$\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}$について、線形計画問題が上のように方程式フォームで表示されるとし、$i = 1 , \cdots , m$に対してその辞書を次のように示そう。 $$\begin{align*} \zeta &=& & & \sum_{j=1}^{n} c_{j} x_{j} \\ x_{n+i} &=& b_{i} &-& \sum_{j=1}^{n} a_{ij} x_{j} \end{align*}$$

ある$i \in \mathcal{B}$に対して$b_{i} = 0$ならば、この辞書は変性している^degenerateと言い、これが原因でシンプレックス法が進まない現象をサイクリング^cyclingと呼ぶ¹。

説明

変性…？

Naverで検索すると、Degenerateは悪化する、堕落的な、変性した、退化した、退行したなどと翻訳される。当然ながら、STEM分野で最も有名な用例は、異なる二つの波動関数が同じ固有値を持つ時を指す量子力学での変性であり、線形代数でもあるベクトルが他のベクトルの線形結合で表される時に時々使われることもある。英語のまま受け入れると、$b_{i} = 0$の時にDegenerateと言うのは非常に論理的だ。問題は、韓国語に翻訳するときに変性という意味が全く合わないことだ。まったく別の表現を見つけることも可能だったかもしれないが、考えてみればシンプレックス法がうまくいかないという意味で変性も全然間違った言葉ではないように思えるので、そのまま変性として和らげた。

例

$$\begin{matrix} \text{Maximize} & & & & x_{2} \\ \text{subject to} &-& x_{1} & + & x_{2} & \le & 0 \\ & & 1_{2} & & & \le & 2 \end{matrix}$$

例えば、上述の線形計画問題を辞書で書き下すと次のようになる。 $$\begin{matrix} \zeta & = & & & & & & x_{2} \\ x_{3} & = & & & & x_{1} & - & x_{2} \\ x_{4} & = & & 2 & - & x_{1} & & \end{matrix}$$

この時、$i = 3$に対して$b_{i} = 0$ならば、変数を置き換えても目的値^{objective value}は変わらず、グルグル回ってしまう。つまり、$t$番目の辞書を$D_{t}$だとした時、次を満たす何らかの$k \in \mathbb{N}$が存在することになる。 $$D_{t} = D_{t+k}$$

これは非常に単純な例で見ると、なぜこんなことが起きるのか不思議に思うかもしれないが、人の目で一度に読み取るのが難しいほど大きな$A$だけでも、いつどんなサイクルが起きるかわからない。例えば、置換をしていて$b_{i_{1}} = -b_{i_{2}}$がぴったり合って$0$が発生するような形だ。プログラミング的にこれを検出すること自体はそこまで難しくないが、どのように抜け出すかが問題だ。

解決法: ブランドのルール

入る変数^{entering variable}と出る変数^{leaving variable}をそれぞれ$\mathcal{N}$と$\mathcal{B}$からインデックスが最も小さいものを選ぶことで、サイクルに陥ることがない。この選択法をブランドのルール^{Brand’s rule}と呼ぶ。

逆に、シンプレックス法が終わらない時、辞書がサイクルに陥っていることを次の定理で保証できる。

定理

もしシンプレックス法が終わらないならば、辞書はサイクルに陥っている。

証明

線形計画問題で基底可能解になる全てのケースを貪欲アルゴリズムで、つまり想像できる最悪の方法で見つけると考える。$n+m$の変数の中から$n$の基底変数を見つけるケースの数は $$\binom{n+m}{n} = {{ (n+m)! } \over { n!m! }}$$ となり、かなり大きい数だが、とにかく有限である。これら全てのケースを計算すれば、最適化を必ず終えることができるにもかかわらず、シンプレックス法が止まらないということは、サイクルに陥っているという意味になる。

■

線形計画法の基本定理

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