十文字法とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > 十文字法の意味・解説 

十文字法

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/02/28 09:56 UTC 版)

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

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

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

歴史

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

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

単体法では最適な頂点に到達するまでに接続する辺を辿って移動し、新たな頂点解を生成する。十文字法では内点法が反復によって実行可能解の内点を生成するように、反復によって実行不可能あるいは多面体の外部にある基底解を反復によって生成する。

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

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

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

説明

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

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

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

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

しかしながらダンツィークの単体法と同様に、線形計画問題に対する十文字法は多項式時間アルゴリズムでない。Terlakyの十文字法は単体法で 2D回の反復を要するKlee英語版–Minty立方体を少し修正し、D次元のひずませた立方体に対して2D個の頂点すべてを訪れることをルーシュによって示された[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の規則はそれよりも複雑な規則となっている。また十文字法は(主・双対)実行可能性を保証する必要がない解法であるため、単体法に位置づけされない解法である。しかしながら多項式時間アルゴリズムとしての保証はされていない。

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

脚注

注釈

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

出典

  1. ^ a b Illés, Szirmai & Terlaky (1999)
  2. ^ a b Stancu-Minasian, I. M. (2006-08). “A sixth bibliography of fractional programming”. Optimization 55 (4): 405–428. doi:10.1080/02331930600819613. MR2258634. 
  3. ^ a b c d e f Fukuda & Terlaky (1997)
  4. ^ a b Roos (1990)
  5. ^ 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 
  6. ^ a b c Fukuda & Terlaky (1997, p. 385)
  7. ^ a b Fukuda & Namiki (1994, p. 367)
  8. ^ 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 
  9. ^ Terlaky (1985) and Terlaky (1987)
  10. ^ Wang (1987)
  11. ^ a b Terlaky & Zhang (1993)
  12. ^ 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. 
  13. ^ Klafszky & Terlaky (1991)
  14. ^ Fukuda & Namiki (1994)
  15. ^ 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 
  16. ^ 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. http://core.ac.uk/download/pdf/6714737.pdf. 
  17. ^ 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時点におけるアーカイブ。. https://web.archive.org/web/20150923211403/http://www.cs.elte.hu/opres/orr/download/ORR03_1.pdf 2011年8月30日閲覧。. 
  18. ^ 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. 
  19. ^ Avis & Fukuda (1992, p. 297)

参考文献

関連項目

  • ジャック・エドモンズ 英語版(組み合わせ最適化と有向マトロイドの第一研究者; 福田公明英語版の博士課程指導教員)

外部リンク




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  
  •  十文字法のページへのリンク

辞書ショートカット

すべての辞書の索引

「十文字法」の関連用語

十文字法のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



十文字法のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの十文字法 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS