十文字法

eA three-dimensional cub — 十文字法は3次元のKlee-Minty立方体（英語版）に対しては最悪ケースの全8頂点を訪れる。3次元の場合平均的には3頂点を訪れる。Klee-Minty立方体は正立方体を巧妙にひずませたものである。

十文字法（じゅうもんじほう、英: criss-cross alogorithm）とは、数理最適化における線形計画問題に対するアルゴリズムの一種である。十文字法と同様の解法は線形不等式付き非線形の目的関数の問題や、分数計画問題（英語版）^[1]^[2]、二次計画問題、線形相補性問題（英語版）に対して適用されている^[3]。

ダンツィーグの単体法と同様に、十文字法は線形計画問題に対しては多項式時間アルゴリズムではない。両者のアルゴリズムも（ヴィクター・クレー（英語版）、ジョージ・ミンティ（英語版）によって提案された）D次元の立方体（英語版）を巧妙にひずませたKlee-Minty立方体（英語版）に対しては最適頂点解に到達するまでに 2^D 回頂点を訪れることになるため、最悪時間計算量において指数時間を示す^[4]^[5]。しかしながら、初期の頂点解をランダムな頂点で開始した場合、十文字法は平均反復回数（英語版）は約D回で終える^[6]^[7]^[8]。すなわち、3次元の多面体では平均では3頂点を訪れ、最悪の場合では8頂点を訪れることになる。

歴史

十文字法はTamas Terlaky^[9]、Zhe-Min Wang^[10]のそれぞれが独立して提案した解法である^[3]。

線形計画問題に対する単体法との比較

→「線形計画法」および「単体法」も参照

線形計画問題では、十文字法が生成する基底解の列は単体法とは異なっている。単体法は第一段階目として（主）実行可能性を満たす基底解を探索し、二段階目でピボット規則に従って目的関数値を減少させるような点列を生成し、最終的に（双対実行可能性を満たす）最適解を求める^[3]^[11]。

一方、十文字法は一段階のみで完結する解法であるという意味で簡明な解法である。そして十文字法で使用されるピボット規則はBlandの最小添字規則（英語版）に類似している^[12]。 Blandの規則では選択基準として被約費用の係数の符号が負の中から基底に入る変数と出る変数を決める^[12]^{[注釈 1]}。一方で十文字法はBlandの規則とは異なって完全に組合せ的解法であり、係数の符号のみを考慮して基底に入る変数と出る変数を選択する^[3]^[11]。十文字法は線形代数におけるいくつかの定理（ファルカスの補題（英語版）など）の建設的な証明にも応用されている^[13]。

多くの単体法に類似される解法は目的関数値を改善するような解（非退化仮定の下では厳密に改善される）を生成するのに対し、十文字法に類似される解法は目的関数をより良くする保証がされないため、この面においては不利な解法である。

説明

十文字法は標準的なピボットタブロー（もしくは単体表をその都度求めるような改訂型単体法のように行列表現で実装した場合）上で実行できる。一般的な方法はピボットタブローが（主・双対）実行不可能な場合、ピボット選択規則によって実行不可能な行・列の中から一つををピボット行・列として選択する。十文字法の重要な特性として選択は（主・双対）実行可能性を満たさない添字の集合に対して行われ、（主・双対）単体法のような基底交換に基づく解法での列・行のみの添字などの区別されない点が挙げられる。行を選択した場合は双対型のピボットによって入れ替える列の位置を特定し、あるいは列を選択した場合は主型のピボットによって入れ替える行の位置を特定する。

計算複雑度: 最悪時間計算量

アルゴリズムの時間計算量とは問題を解くために必要な算術演算の回数のを表したものである。具体例として、ガウスの消去法は高々 D³ に比例した反復を要するため、三次関数の多項式時間計算量に区分される。また多項式時間計算量を有さないアルゴリズムも存在する。具体例として、ガウスの消去法を一般化したアルゴリズムのブッフベルガーのアルゴリズムは問題の入力データ量（多項式の次数・多変数多項式の総変数）に対して指数時間計算量を有するアルゴリズムである。指数関数は多項式関数よりも急速に増大することから、指数時間計算量の解法は規模の大きな問題に対して高い性能を発揮できないことを意味する。

カチヤンの楕円体法、カーマーカーの射影変換法、中心パス追跡法等の線形計画問題に対する解法は（最悪時（英語版）・平均時間計算量（英語版）において）多項式時間アルゴリズムである。楕円体法、射影変換法は十文字法より前に提案された解法である。

しかしながらダンツィークの単体法と同様に、線形計画問題に対する十文字法は多項式時間アルゴリズムでない。Terlakyの十文字法は単体法で 2^D回の反復を要するKlee（英語版）–Minty立方体（英語版）を少し修正し、D次元のひずませた立方体に対して2^D個の頂点すべてを訪れることをルーシュによって示された^[3]^[4]^[5]。単体法と同様に、十文字法は3次元の場合最悪時に立方体の全8頂点訪れることになる。

立方体のランダムな頂点を初期解としたとき、十文字法は平均でD回の頂点を訪れることを1994年福田（英語版）、並木によって主張された^[6]^[7]。これは容易に確かめることができ、単体法も立方体に対して平均 D 回の反復で終了する^[8]^{[注釈 2]}。単体法と同様に、十文字法は3次元の立方体の頂点を平均3回訪れる。

類似のアルゴリズム

十文字法は線形計画問題より一般的な最適化問題に対して拡張されている。

他の線形制約付き問題に対する応用

他の問題に対する十文字法の変種解法として線形計画問題、二次計画問題、単調な線形相補性問題（英語版）が挙げられる^[3]^[6]^[14]^[15]^[16]^[17]。逆に言えば、十文字法は線形相補性問題において行列が十分行列であるときのみ有限回の反復で終了する^[16]^[17]。十分行列（英語版）は正定値行列およびP行列（英語版）を一般化させた行列で、小行列式がすべて正の値をとる^[16]^[17]^[18]。また十文字法は分数計画問題（英語版）についても適用することができる^[1]^[2]。

頂点列挙

十文字法は1992年ディビッド・エイビス（英語版）、福田公明（英語版）によって多面体の全頂点列挙（英語版）を求めるアルゴリズムとして提案された^[19]。エイビスと福田は D 次元において非退化な n 個の線形不等式系から構成される多面体に含まれる v 個の頂点を求める（また双対的には D 次元においてファセットを構成する D 個の点を含む n 個の点の凸包のファセットを v 個列挙する）アルゴリズムを提案した。このアルゴリズムは時間計算量が O(nDv)、空間計算量（英語版）が $O(nD)$ である^{[注釈 3]}。

まとめ

十文字法は線形計画問題に対する簡明な解法である。そして線形計画問題に対する2番目に提案された完全に組合せ的アルゴリズムとして知られている。特にBlandの選択規則による単体法はいくつかの（実行不可能な）有向マトロイドに対して用いられる。最初の完全に組合せ的アルゴリズムはToddによって提案されており、初期実行可能基底解が生成された後は常に（主）実行可能性を維持し続けるという点で単体法に類似しているが、Toddの規則はそれよりも複雑な規則となっている。また十文字法は（主・双対）実行可能性を保証する必要がない解法であるため、単体法に位置づけされない解法である。しかしながら多項式時間アルゴリズムとしての保証はされていない。

研究者らは十文字法を線形分数計画問題を含む最適化問題に対して発展させた。また二次計画問題、線形相補性問題、有向マトロイドに拡張した解法である。より一般的な問題に対しても十文字法は単純な規則に従って実行される。

脚注

[脚注の使い方]

注釈

^ Blandの規則はKatta G. Murtyによって提案された線形相補性問題（英語版）で用いられるピボット規則の最小添字規則にも関連しているFukuda & Namiki (1994)。
^ より一般的に言えば、ユーリクッド空間の単位球面上にランダムに頂点を生成した線形計画問題に対して単体法を用いると次元数 D に比例した反復回数に収束することがボルクヴァルト・スメイルによって示された。
^ D 次元において n 個の超平面の単純な方程式系で表された多面体に含まれる v 個の頂点を求める場合は時間計算量が $O(n_{2}Dv)$ 、空間計算量（英語版）が $O(nD)$ である。

出典

^ ^a ^b Illés, Szirmai & Terlaky (1999)
^ ^a ^b Stancu-Minasian, I. M. (2006-08). “A sixth bibliography of fractional programming”. Optimization 55 (4): 405–428. doi:10.1080/02331930600819613. MR 2258634.
^ ^a ^b ^c ^d ^e ^f Fukuda & Terlaky (1997)
^ ^a ^b Roos (1990)
^ ^a ^b Klee, Victor; Minty, George J. (1972). “How good is the simplex algorithm?”. In Shisha, Oved. Inequalities III (Proceedings of the Third Symposium on Inequalities held at the University of California, Los Angeles, Calif., September 1–9, 1969, dedicated to the memory of Theodore S. Motzkin). New York-London: Academic Press. pp. 159–175. MR332165
^ ^a ^b ^c Fukuda & Terlaky (1997, p. 385)
^ ^a ^b Fukuda & Namiki (1994, p. 367)
^ ^a ^b また単体法も多面体の探索に平均でD回の反復かかるBorgwardt (1987): Borgwardt, Karl-Heinz (1987). The simplex method: A probabilistic analysis. Algorithms and Combinatorics (Study and Research Texts). 1. Berlin: Springer-Verlag. pp. xii+268. ISBN 978-3-540-17096-9. MR868467
^ Terlaky (1985) and Terlaky (1987)
^ Wang (1987)
^ ^a ^b Terlaky & Zhang (1993)
^ ^a ^b Bland, Robert G. (1977-05). “New finite pivoting rules for the simplex method”. Mathematics of Operations Research 2 (2): 103–107. doi:10.1287/moor.2.2.103. JSTOR 3689647. MR459599.
^ Klafszky & Terlaky (1991)
^ Fukuda & Namiki (1994)
^ Björner, Anders; Las Vergnas, Michel; Sturmfels, Bernd; White, Neil; Ziegler, Günter (1999). “10 Linear programming”. Oriented Matroids. Cambridge University Press. pp. 417–479. doi:10.1017/CBO9780511586507. ISBN 978-0-521-77750-6. MR1744046
^ ^a ^b ^c den Hertog, D.; Roos, C.; Terlaky, T. (1993-07-01). “The linear complementarity problem, sufficient matrices, and the criss-cross method”. Linear Algebra and Its Applications 187: 1–14. doi:10.1016/0024-3795(93)90124-7.
^ ^a ^b ^c Csizmadia, Zsolt; Illés, Tibor (2006). “New criss-cross type algorithms for linear complementarity problems with sufficient matrices” (pdf). Optimization Methods and Software 21 (2): 247–266. doi:10.1080/10556780500095009. MR2195759. オリジナルの2015-09-23時点におけるアーカイブ。 2011年8月30日閲覧。.
^ Cottle, R. W.; Pang, J.-S.; Venkateswaran, V. (1989年3-4月). “Sufficient matrices and the linear complementarity problem”. Linear Algebra and Its Applications 114–115: 231–249. doi:10.1016/0024-3795(89)90463-1. MR986877.
^ Avis & Fukuda (1992, p. 297)

参考文献

Avis, David; Fukuda, Komei (1992-12). “A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra”. Discrete and Computational Geometry 8 (ACM Symposium on Computational Geometry (North Conway, NH, 1991) number 1): 295–313. doi:10.1007/BF02293050. MR1174359.
Csizmadia, Zsolt; Illés, Tibor (2006). “New criss-cross type algorithms for linear complementarity problems with sufficient matrices” (pdf). Optimization Methods and Software 21 (2): 247–266. doi:10.1080/10556780500095009. MR2195759. オリジナルの2015-09-23時点におけるアーカイブ。 2011年8月30日閲覧。.
Fukuda, Komei; Namiki, Makoto (March 1994). “On extremal behaviors of Murty's least index method”. Mathematical Programming 64 (1): 365–370. doi:10.1007/BF01582581. MR1286455.
Fukuda, Komei; Terlaky, Tamás (1997). Liebling, Thomas M.; de Werra, Dominique. eds. “Criss-cross methods: A fresh view on pivot algorithms”. Mathematical Programming, Series B 79 (Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997, number 1–3): 369–395. doi:10.1007/BF02614325. MR1464775. Postscript preprint.
den Hertog, D.; Roos, C.; Terlaky, T. (1993-07-01). “The linear complementarity problem, sufficient matrices, and the criss-cross method”. Linear Algebra and Its Applications 187: 1–14. doi:10.1016/0024-3795(93)90124-7. MR1221693.
Illés, Tibor; Szirmai, Ákos; Terlaky, Tamás (1999). “The finite criss-cross method for hyperbolic programming”. European Journal of Operational Research 114 (1): 198–214. doi:10.1016/S0377-2217(98)00049-6. Zbl 0953.90055. Postscript preprint.
Klafszky, Emil; Terlaky, Tamás (June 1991). “The role of pivoting in proving some fundamental theorems of linear algebra”. Linear Algebra and Its Applications 151: 97–118. doi:10.1016/0024-3795(91)90356-2. MR1102142.
Roos, C. (1990). “An exponential example for Terlaky's pivoting rule for the criss-cross simplex method”. Mathematical Programming. Series A 46 (1): 79–84. doi:10.1007/BF01585729. MR1045573.
Terlaky, T. (1985). “A convergent criss-cross method”. Optimization: A Journal of Mathematical Programming and Operations Research 16 (5): 683–690. doi:10.1080/02331938508843067. ISSN 0233-1934. MR798939.
Terlaky, Tamás (1987). “A finite crisscross method for oriented matroids”. Journal of Combinatorial Theory. Series B 42 (3): 319–327. doi:10.1016/0095-8956(87)90049-9. ISSN 0095-8956. MR888684.
Terlaky, Tamás; Zhang, Shu Zhong (1993). “Pivot rules for linear programming: A Survey on recent theoretical developments”. Annals of Operations Research 46–47 (Degeneracy in optimization problems, number 1): 203–233. doi:10.1007/BF02096264. ISSN 0254-5330. MR1260019.
Wang, Zhe Min (1987). “A finite conformal-elimination free algorithm over oriented matroid programming”. Chinese Annals of Mathematics (Shuxue Niankan B Ji). Series B 8 (1): 120–125. ISSN 0252-9599. MR886756.