十文字法（じゅうもんじほう、）とは、数理最適化における線形計画問題に対するアルゴリズムの一種である。十文字法と同様の解法は線形不等式付き非線形の目的関数の問題や、、二次計画問題、に対して適用されている。
ダンツィーグの単体法と同様に、十文字法は線形計画問題に対してはではない。両者のアルゴリズムも（ヴィクター・クリー、によって提案された）D次元のを巧妙にひずませたに対しては最適頂点解に到達するまでに 2D 回頂点を訪れることになるため、最悪時間計算量において指数時間を示す。しかしながら、初期の頂点解をランダムな頂点で開始した場合、十文字法はは約D回で終えるまた単体法も多面体の探索に平均でD回の反復かかる: 。すなわち、3次元の多面体では平均では3頂点を訪れ、最悪の場合では8頂点を訪れることになる。
歴史 十文字法はTamas Terlaky and 、Zhe-Min Wangのそれぞれが独立して提案した解法である。
線形計画問題に対する単体法との比較
線形計画問題では、十文字法が生成する基底解の列は単体法とは異なっている。単体法は第一段階目として（主）実行可能性を満たす基底解を探索し、二段階目でピボット規則に従って目的関数値を減少させるような点列を生成し、最終的に（双対実行可能性を満たす）最適解を求める。
一方、十文字法は一段階のみで完結する解法であるという意味で簡明な解法である。そして十文字法で使用されるピボット規則はに類似している。 Blandの規則では選択基準として被約費用の係数の符号が負の中から基底に入る変数と出る変数を決める。一方で十文字法はBlandの規則とは異なって完全に組合せ的解法であり、係数の符号のみを考慮して基底に入る変数と出る変数を選択する。十文字法は線形代数におけるいくつかの定理（など）の建設的な証明にも応用されている。
多くの単体法に類似される解法は目的関数値を改善するような解（非退化仮定の下では厳密に改善される）を生成するのに対し、十文字法に類似される解法は目的関数をより良くする保証がされないため、この面においては不利な解法である。
説明 十文字法は標準的なピボットタブロー（もしくは単体表をその都度求めるような改訂型単体法のように行列表現で実装した場合）上で実行できる。一般的な方法はピボットタブローが（主・双対）実行不可能な場合、ピボット選択規則によって実行不可能な行・列の中から一つをピボット行・列として選択する。十文字法の重要な特性として選択は（主・双対）実行可能性を満たさない添字の集合に対して行われ、（主・双対）単体法のような基底交換に基づく解法での列・行のみの添字などの区別されない点が挙げられる。 行を選択した場合は双対型のピボットによって入れ替える列の位置を特定し、あるいは列を選択した場合は主型のピボットによって入れ替える行の位置を特定する。
計算複雑度: 最悪時間計算量 アルゴリズムの時間計算量とは問題を解くために必要な算術演算の回数のを表したものである。具体例として、ガウスの消去法は高々 D3 に比例した反復を要するため、三次関数の多項式時間計算量に区分される。また多項式時間計算量を有さないアルゴリズムも存在する。具体例として、ガウスの消去法を一般化したアルゴリズムのブッフベルガーのアルゴリズムは問題の入力データ量（多項式の次数・多変数多項式の総変数）に対して指数時間計算量を有するアルゴリズムである。指数関数は多項式関数よりも急速に増大することから、指数時間計算量の解法は規模の大きな問題に対して高い性能を発揮できないことを意味する。
カチヤンの楕円体法、カーマーカーの射影変換法、中心パス追跡法等の線形計画問題に対する解法は（・において）多項式時間アルゴリズムである。楕円体法、射影変換法は十文字法より前に提案された解法である。
しかしながらダンツィークの単体法と同様に、線形計画問題に対する十文字法は多項式時間アルゴリズムでない。Terlakyの十文字法は単体法で 2D回の反復を要する–Mintyを少し修正し、D次元のひずませた立方体に対して2D個の頂点すべてを訪れることをルーシュによって示された。単体法と同様に、十文字法は3次元の場合最悪時に立方体の全8頂点訪れることになる。
立方体のランダムな頂点を初期解としたとき、十文字法は平均でD回の頂点を訪れることを1994年、並木によって主張された。これは容易に確かめることができ、単体法も立方体に対して平均 D 回の反復で終了する。単体法と同様に、十文字法は3次元の立方体の頂点を平均3回訪れる。
類似のアルゴリズム 十文字法は線形計画問題より一般的な最適化問題に対して拡張されている。
他の線形制約付き問題に対する応用 他の問題に対する十文字法の変種解法として線形計画問題、二次計画問題、単調なが挙げられる。逆に言えば、十文字法は線形相補性問題において行列が十分行列であるときのみ有限回の反復で終了する。は正定値行列およびを一般化させた行列で、小行列式がすべて正の値をとる。また十文字法はについても適用することができる。
頂点列挙 十文字法は1992年、によってを求めるアルゴリズムとして提案された。 エイビスと福田は D 次元において非退化な n 個の線形不等式系から構成される多面体に含まれる v 個の頂点を求める（また双対的には D 次元においてを構成する D 個の点を含む n 個の点の凸包のファセットを v 個列挙する）アルゴリズムを提案した。このアルゴリズムは時間計算量が O(nDv)、が である。
まとめ 十文字法は線形計画問題に対する簡明な解法である。そして線形計画問題に対する2番目に提案された完全に組合せ的アルゴリズムとして知られている。特にBlandの選択規則による単体法はいくつかの（実行不可能な）有向マトロイドに対して用いられる。最初の完全に組合せ的アルゴリズムはToddによって提案されており、初期実行可能基底解が生成された後は常に（主）実行可能性を維持し続けるという点で単体法に類似しているが、Toddの規則はそれよりも複雑な規則となっている。また十文字法は（主・双対）実行可能性を保証する必要がない解法であるため、単体法に位置づけされない解法である。しかしながら多項式時間アルゴリズムとしての保証はされていない。
研究者らは十文字法を線形分数計画問題を含む最適化問題に対して発展させた。また二次計画問題、線形相補性問題、有向マトロイドに拡張した解法である。より一般的な問題に対しても十文字法は単純な規則に従って実行される。
脚注
注釈
出典
参考文献
関連項目 （組み合わせ最適化と有向マトロイドの第一研究者; の博士課程指導教員）
外部リンク Komei Fukuda (ETH Zentrum, Zurich) with publications Tamás Terlaky (Lehigh University) with publications