改訂単体法

数学的最適化において、改訂単体法は、線形計画法に対するジョージ・ダンツィグの単体法の変形である。

改訂単体法は数学的には標準単体法と等価ですが、実装が異なります。基本変数の集合に調整された制約を明示的に表す表を保持する代わりに、制約を表す行列の基底の表現を保持します。行列指向アプローチは、疎行列演算を可能にすることで計算効率を向上させます。^[1]

問題の定式化

残りの議論では、線形計画問題が次の標準形式に変換されていると仮定します。

${\displaystyle {\begin{array}{rl}{\text{minimize}}&{\boldsymbol {c}}^{\mathrm {T} }{\boldsymbol {x}}\\{\text{subject to}}&{\boldsymbol {Ax}}={\boldsymbol {b}},{\boldsymbol {x}}\geq {\boldsymbol {0}}\end{array}}}$

ここで、A ∈ ℝ ^{m × n}である。一般性を損なうことなく、制約行列Aは行フルランクを持ち、問題は実行可能である、すなわち、Ax = bとなるx ≥ 0が少なくとも1つ存在すると仮定する。A がランク不足の場合、制約が冗長であるか、問題が実行不可能であるかのいずれかである。どちらの状況も、事前解決ステップで処理できる。

アルゴリズムの説明

最適条件

線形計画法においては、カルシュ・キューン・タッカー条件は最適性にとって必要かつ十分条件である。標準形の線形計画法問題におけるKKT条件は、

${\displaystyle {\begin{aligned}{\boldsymbol {Ax}}&={\boldsymbol {b}},\\{\boldsymbol {A}}^{\mathrm {T} }{\boldsymbol {\lambda }}+{\boldsymbol {s}}&={\boldsymbol {c}},\\{\boldsymbol {x}}&\geq {\boldsymbol {0}},\\{\boldsymbol {s}}&\geq {\boldsymbol {0}},\\{\boldsymbol {s}}^{\mathrm {T} }{\boldsymbol {x}}&=0\end{aligned}}}$

ここでλとsはそれぞれ制約Ax = bとx ≥ 0に関連付けられたラグランジュ乗数である。^[2]最後の条件は、すべての1 < i < nに対してs _i x _i = 0と等価であり、相補的スラックネス条件と呼ばれる。

線型計画法の基本定理として知られる定理によれば、実行可能多面体の頂点x は、 Aの列から選ばれた基底Bと同一視できる。 ^[a] A はフルランクなので、 Bは非特異である。一般性を失うことなく、 A = [ B N ]と仮定する。すると、xは次のように与えられる。

${\displaystyle {\boldsymbol {x}}={\begin{bmatrix}{\boldsymbol {x_{B}}}\\{\boldsymbol {x_{N}}}\end{bmatrix}}={\begin{bmatrix}{\boldsymbol {B}}^{-1}{\boldsymbol {b}}\\{\boldsymbol {0}}\end{bmatrix}}}$

ここでx _B ≥ 0である。cとsを以下のように 分割する。

${\displaystyle {\begin{aligned}{\boldsymbol {c}}&={\begin{bmatrix}{\boldsymbol {c_{B}}}\\{\boldsymbol {c_{N}}}\end{bmatrix}},\\{\boldsymbol {s}}&={\begin{bmatrix}{\boldsymbol {s_{B}}}\\{\boldsymbol {s_{N}}}\end{bmatrix}}.\end{aligned}}}$

相補的緩み条件を満たすために、s _B = 0とする。従って、

${\displaystyle {\begin{aligned}{\boldsymbol {B}}^{\mathrm {T} }{\boldsymbol {\lambda }}&={\boldsymbol {c_{B}}},\\{\boldsymbol {N}}^{\mathrm {T} }{\boldsymbol {\lambda }}+{\boldsymbol {s_{N}}}&={\boldsymbol {c_{N}}},\end{aligned}}}$

これは、

${\displaystyle {\begin{aligned}{\boldsymbol {\lambda }}&=({\boldsymbol {B}}^{\mathrm {T} })^{-1}{\boldsymbol {c_{B}}},\\{\boldsymbol {s_{N}}}&={\boldsymbol {c_{N}}}-{\boldsymbol {N}}^{\mathrm {T} }{\boldsymbol {\lambda }}.\end{aligned}}}$

この時点でsN≥0で_あればKKT条件は満たされ、xは最適となります。

ピボット操作

KKT条件に違反する場合、Bの既存の列を犠牲にしてNの列を基底に導入するピボット操作が実行される。退化がない場合、ピボット操作は常にc ^T xの厳密な減少をもたらす。したがって、問題が有界である場合、修正単体法は、頂点の数が有限であるため、ピボット操作を繰り返した後に最適な頂点で終了する必要がある。^[4]

入力インデックスとして、s _q < 0となるようなインデックスm < q ≤ nを選択する。Aの対応する列A _qが基底に移動され、x q_は0から増加することが許される。

${\displaystyle {\frac {\partial ({\boldsymbol {c}}^{\mathrm {T} }{\boldsymbol {x}})}{\partial x_{q}}}=s_{q},}$

つまり 、 x _qの単位増加ごとにc ^T xが− s _q減少する。^[5]

${\displaystyle {\boldsymbol {Bx_{B}}}+{\boldsymbol {A}}_{q}x_{q}={\boldsymbol {b}},}$

x _{B は}、 x _B − Δ x _B ≥ 0を条件としてΔ x _B = B ⁻¹ A _q x _qだけ減少しなければなりません。 d = B ⁻¹ A _qとします。 d ≤ 0の場合、 x _qがどれだけ増加しても、 x _B − Δ x _Bは非負のままです。 したがって、 c ^T x は任意に減少することができ、問題は無制限です。 それ以外の場合は、インデックスp = argmin _{1≤ i ≤ m} { x _i / d _i | d _i > 0}終了インデックスとして選択します。 この選択により、実行可能性を維持しながら、 x _{p が}ゼロに減少するまで、 x _qがゼロから効果的に増加します、基底で A _{p を}A _qに置き換えることで終了します

数値例

線形計画法を考えてみましょう。

${\displaystyle {\begin{aligned}{\boldsymbol {c}}&={\begin{bmatrix}-2&-3&-4&0&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {A}}&={\begin{bmatrix}3&2&1&1&0\\2&5&3&0&1\end{bmatrix}},\\{\boldsymbol {b}}&={\begin{bmatrix}10\\15\end{bmatrix}}.\end{aligned}}}$

させて

${\displaystyle {\begin{aligned}{\boldsymbol {B}}&={\begin{bmatrix}{\boldsymbol {A}}_{4}&{\boldsymbol {A}}_{5}\end{bmatrix}},\\{\boldsymbol {N}}&={\begin{bmatrix}{\boldsymbol {A}}_{1}&{\boldsymbol {A}}_{2}&{\boldsymbol {A}}_{3}\end{bmatrix}}\end{aligned}}}$

最初は、実行可能な頂点x = [0 0 0 10 15] ^Tに対応する。この瞬間、

${\displaystyle {\begin{aligned}{\boldsymbol {\lambda }}&={\begin{bmatrix}0&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {s_{N}}}&={\begin{bmatrix}-2&-3&-4\end{bmatrix}}^{\mathrm {T} }.\end{aligned}}}$

入口インデックスとしてq = 3を選択します。するとd = [1 3] ^{Tとなり、これは}x ₃が単位増加するとx ₄とx ₅がそれぞれ1と3減少することを意味します。したがって、x ₃は5に増加し、その時点でx ₅はゼロになり、p = 5が出口インデックスになります。

ピボット操作後、

${\displaystyle {\begin{aligned}{\boldsymbol {B}}&={\begin{bmatrix}{\boldsymbol {A}}_{3}&{\boldsymbol {A}}_{4}\end{bmatrix}},\\{\boldsymbol {N}}&={\begin{bmatrix}{\boldsymbol {A}}_{1}&{\boldsymbol {A}}_{2}&{\boldsymbol {A}}_{5}\end{bmatrix}}.\end{aligned}}}$

それに応じて、

${\displaystyle {\begin{aligned}{\boldsymbol {x}}&={\begin{bmatrix}0&0&5&5&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {\lambda }}&={\begin{bmatrix}0&-4/3\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {s_{N}}}&={\begin{bmatrix}2/3&11/3&4/3\end{bmatrix}}^{\mathrm {T} }.\end{aligned}}}$

s _Nが正の場合、 xが最適であることを示します。

実用的な問題

退化

修正単体法は単体法と数学的に等価であるため、ピボット操作によってc ^T xが減少しないという退化の問題を抱えている。また、ピボット操作の連鎖によって基底が循環する。摂動法や辞書式戦略を用いることで、循環を防ぎ、基底の停止性を保証することができる。^[6]

基底表現

修正単体法には、 Bを含む2 種類の線形システムがあります。

${\displaystyle {\begin{aligned}{\boldsymbol {Bz}}&={\boldsymbol {y}},\\{\boldsymbol {B}}^{\mathrm {T} }{\boldsymbol {z}}&={\boldsymbol {y}}.\end{aligned}}}$

Bをリファクタリングする代わりに、通常はLU分解を各ピボット操作後に直接更新します。この目的のために、Forrest−Tomlin法やBartels−Golub法などのいくつかの戦略が存在します。しかし、更新を表すデータ量と数値誤差は時間の経過とともに蓄積されるため、定期的なリファクタリングが必要になります。^{[1] [7]}

注釈と参考文献

注記

1. 同じ定理は、実現可能な多面体には少なくとも1つの頂点があり、そのうち少なくとも1つの頂点は最適であるとも述べています。^[3]

参考文献

1. Morgan 1997、§2。
2. Nocedal & Wright 2006、358ページ、式13.4。
3. Nocedal & Wright 2006、363ページ、定理13.2。
4. Nocedal & Wright 2006、370ページ、定理13.4。
5. Nocedal & Wright 2006、369ページ、式13.24。
6. Nocedal & Wright 2006、381ページ、§13.5。
7. Nocedal & Wright 2006、372ページ、§13.4。

参考文献

• Morgan, SS (1997). シンプレックス法アルゴリズムの比較 (修士論文).フロリダ大学. 2011年8月7日時点のオリジナルよりアーカイブ。
• Nocedal, J.; Wright, SJ (2006). Mikosch, TV; Resnick, SI; Robinson, SM (編). 数値最適化. Springer Series in Operations Research and Financial Engineering (第2版). ニューヨーク州ニューヨーク市: S​​pringer . ISBN 978-0-387-30303-1。