https://orsj-ml.org/orwiki/wiki/index.php?action=history&feed=atom&title=%E5%86%85%E7%82%B9%E6%B3%95
内点法 - 版の履歴
2026-04-15T09:09:24Z
このウィキのこのページに関する変更履歴
MediaWiki 1.35.3
https://orsj-ml.org/orwiki/wiki/index.php?title=%E5%86%85%E7%82%B9%E6%B3%95&diff=10815&oldid=prev
2008年11月13日 (木) 04:19にAlbeit-Kunによる
2008-11-13T04:19:22Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2008年11月13日 (木) 04:19時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l64" >64行目:</td>
<td colspan="2" class="diff-lineno">64行目:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category:線形計画|ないてんほう]]</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category:線形計画|ないてんほう]]</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">[[Category:非線形計画|ないてんほう]]</ins></div></td></tr>
</table>
Albeit-Kun
https://orsj-ml.org/orwiki/wiki/index.php?title=%E5%86%85%E7%82%B9%E6%B3%95&diff=9995&oldid=prev
Tamura: リンク法の修正と読書案内という見出しの追加
2008-08-22T07:24:58Z
<p>リンク法の修正と読書案内という見出しの追加</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2008年8月22日 (金) 07:24時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l29" >29行目:</td>
<td colspan="2" class="diff-lineno">29行目:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> 内点法における大きな課題の1つは, 条件のよい許容領域内部の初期点をいかに用意するかという問題である. この課題の解決策として [[非許容初期点内点法]] (infeasible interior point method) や, 理論的にはさらに優れた [[同次自己双対内点法]] (homogeneous self-dual interior point method) が提案されており, 実装の際にはどちらかが用いられることが多い.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> 内点法における大きな課題の1つは, 条件のよい許容領域内部の初期点をいかに用意するかという問題である. この課題の解決策として [[非許容初期点内点法]] (infeasible interior point method) や, 理論的にはさらに優れた [[同次自己双対内点法]] (homogeneous self-dual interior point method) が提案されており, 実装の際にはどちらかが用いられることが多い.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> 以上の解法の中で, アフィン変換法以外の解法は多項式時間解法であることが示されている. ネステロフとネミロフスキーは, [[自己整合障壁関数]]の概念を導入した上で, 内点法という解法のクラスの中で, 多項式時間解法である解法からなる, 1つの大きなクラスを示した [2]. この研究は, 1990年代から活発に行なわれている, [[半正定値計画]]<del class="diffchange diffchange-inline">問題や</del>[[2次錐計画]]<del class="diffchange diffchange-inline">問題等に内点法を適用する研究の重要な基礎となっている</del>.</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> 以上の解法の中で, アフィン変換法以外の解法は多項式時間解法であることが示されている. ネステロフとネミロフスキーは, [[自己整合障壁関数]]の概念を導入した上で, 内点法という解法のクラスの中で, 多項式時間解法である解法からなる, 1つの大きなクラスを示した [2]. この研究は, 1990年代から活発に行なわれている, [[半正定値計画<ins class="diffchange diffchange-inline">|半正定値計画問題</ins>]]<ins class="diffchange diffchange-inline">や</ins>[[2次錐計画<ins class="diffchange diffchange-inline">|2次錐計画問題</ins>]]<ins class="diffchange diffchange-inline">等に内点法を適用する研究の重要な基礎となっている</ins>.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">=== 読書案内 ===</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> 近年内点法が記述された教科書も多く出版されている. [12] は内点法を総合的に扱った和書である. 線形計画法のみならず, 半正定値計画問題, 非線形計画問題に対する内点法についも述べている. その他の洋書の多くは主双対内点法と非許容初期点内点法を基本とした内容であるが, カーマーカー法については [3], [9], アフィン変換法については [4], [6], 同次自己双対内点法については, [6], [10] 等にそれぞれ詳しく述べられている. [8], [9], [10] はそれぞれ線形計画法の教科書であり, 図表が多く入門的な内容であるが, [8] は単体法, [9] は内点法を包括する理論, [10] は実装 にそれぞれ重きを置いている点が特徴である. また, 内点法に関する論文の多くは, インターネットを通じて入手可能である [11].</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> 近年内点法が記述された教科書も多く出版されている. [12] は内点法を総合的に扱った和書である. 線形計画法のみならず, 半正定値計画問題, 非線形計画問題に対する内点法についも述べている. その他の洋書の多くは主双対内点法と非許容初期点内点法を基本とした内容であるが, カーマーカー法については [3], [9], アフィン変換法については [4], [6], 同次自己双対内点法については, [6], [10] 等にそれぞれ詳しく述べられている. [8], [9], [10] はそれぞれ線形計画法の教科書であり, 図表が多く入門的な内容であるが, [8] は単体法, [9] は内点法を包括する理論, [10] は実装 にそれぞれ重きを置いている点が特徴である. また, 内点法に関する論文の多くは, インターネットを通じて入手可能である [11].</div></td></tr>
</table>
Tamura
https://orsj-ml.org/orwiki/wiki/index.php?title=%E5%86%85%E7%82%B9%E6%B3%95&diff=9994&oldid=prev
2008年8月22日 (金) 07:22にTamuraによる
2008-08-22T07:22:31Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2008年8月22日 (金) 07:22時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l25" >25行目:</td>
<td colspan="2" class="diff-lineno">25行目:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>(<math>A\,</math>は<math>m \times n\,</math>行列, <math>c \in \mathbf{R}^n</math>, <math>e \in \mathbf{R}^n</math>は要素がすべて<math>1\,</math>のベクトル)を対象とし, 対数障壁関数を用いた[[ポテンシャル関数 (内点法の)|ポテンシャル関数]](potential function) の値で最適解からの誤差を測り, [[射影変換]] (projective transformation) を用いて探索方向を決定するという特徴をもつ. 対数障壁関数を用いるという点で非線形計画法の一解法とも考えられるが, 着想, 解析共に従来の常識とは異なる斬新な解法であった. より一般的で記述が簡潔なアルゴリズムとして提案された解法が, [[アフィン変換法]](affine scaling method) である. その後1988年に, ロシアの数学者ディキン(I. Dikin) が20年以上前の1967年に同じ解法を提案していたことが明かになり, 話題となった. アフィン変換法は実用的であり, 大域的収束性が示されているが, 解法の多項式時間性については未だ不明である.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>(<math>A\,</math>は<math>m \times n\,</math>行列, <math>c \in \mathbf{R}^n</math>, <math>e \in \mathbf{R}^n</math>は要素がすべて<math>1\,</math>のベクトル)を対象とし, 対数障壁関数を用いた[[ポテンシャル関数 (内点法の)|ポテンシャル関数]](potential function) の値で最適解からの誤差を測り, [[射影変換]] (projective transformation) を用いて探索方向を決定するという特徴をもつ. 対数障壁関数を用いるという点で非線形計画法の一解法とも考えられるが, 着想, 解析共に従来の常識とは異なる斬新な解法であった. より一般的で記述が簡潔なアルゴリズムとして提案された解法が, [[アフィン変換法]](affine scaling method) である. その後1988年に, ロシアの数学者ディキン(I. Dikin) が20年以上前の1967年に同じ解法を提案していたことが明かになり, 話題となった. アフィン変換法は実用的であり, 大域的収束性が示されているが, 解法の多項式時間性については未だ不明である.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> 他方, 従来のSUMT法, ホモトピー法, <del class="diffchange diffchange-inline">ニュートン法といった枠組を用いて内点法を構築する試みも行なわれた</del>. 中でも大きな役割を果たしたのは, ゾンネべンド(Gy. Sonnevend)が提唱した[[中心パス]](path of centers) であり, この概念を利用してレネガー(J. Renegar)はニュートン法を用いた初めての 多項式時間解法を提案した. さらに, 主問題と双対問題の双方を1つの問題とみなした場合の解析的 中心に関する研究も行なわれ, [[主双対内点法]](primal-dual interior point method) の提案へと結び付いた. 主双対内点法を改良した[[予測子修正子内点法]](predictor-corrector interior point method) は, 現在もっとも普及している内点法の1つである. これらの解法については [5] 等を参照されたい.</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> 他方, 従来のSUMT法, ホモトピー法, <ins class="diffchange diffchange-inline">[[ニュートン法]]といった枠組を用いて内点法を構築する試みも行なわれた</ins>. 中でも大きな役割を果たしたのは, ゾンネべンド(Gy. Sonnevend)が提唱した[[中心パス]](path of centers) であり, この概念を利用してレネガー(J. Renegar)はニュートン法を用いた初めての 多項式時間解法を提案した. さらに, 主問題と双対問題の双方を1つの問題とみなした場合の解析的 中心に関する研究も行なわれ, [[主双対内点法]](primal-dual interior point method) の提案へと結び付いた. 主双対内点法を改良した[[予測子修正子内点法]](predictor-corrector interior point method) は, 現在もっとも普及している内点法の1つである. これらの解法については [5] 等を参照されたい.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> 内点法における大きな課題の1つは, 条件のよい許容領域内部の初期点をいかに用意するかという問題である. この課題の解決策として [[非許容初期点内点法]] (infeasible interior point method) や, 理論的にはさらに優れた [[同次自己双対内点法]] (homogeneous self-dual interior point method) が提案されており, 実装の際にはどちらかが用いられることが多い.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> 内点法における大きな課題の1つは, 条件のよい許容領域内部の初期点をいかに用意するかという問題である. この課題の解決策として [[非許容初期点内点法]] (infeasible interior point method) や, 理論的にはさらに優れた [[同次自己双対内点法]] (homogeneous self-dual interior point method) が提案されており, 実装の際にはどちらかが用いられることが多い.</div></td></tr>
</table>
Tamura
https://orsj-ml.org/orwiki/wiki/index.php?title=%E5%86%85%E7%82%B9%E6%B3%95&diff=9993&oldid=prev
2008年8月22日 (金) 07:20にTamuraによる
2008-08-22T07:20:22Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2008年8月22日 (金) 07:20時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l5" >5行目:</td>
<td colspan="2" class="diff-lineno">5行目:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== 詳説 ===</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== 詳説 ===</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> [[内点法]](interior point method) は[[最適化問題]]の制約領域の境界上ではなく内部に, 最適解に収束する点列を生成する逐次反復解法である. 特に[[線形計画|線形計画問題]]に対しては, 最適値に十分に近い近似解が得られれば, 変数次元の連立方程式を1回解く手間で最適解が得られることから, 内点法で最適解を得るまでに必要な計算の手間(算術演算回数)を算出することが可能であり, 多くの理論的な成果が報告されている. また実用面では, 特に大規模な問題に対して単体法よりも計算効率が 優れていることが確認されており, この解法を取り入れた商用コードも多く存在する. 線形計画問題以外への応用も積極的に行なわれており, 凸2次計画問題, [[相補性問題]], あるいは半正定値計画問題, <del class="diffchange diffchange-inline">2次錐計画問題等の凸計画問題に対しても有効な解法であることが示されている</del>.</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> [[内点法]](interior point method) は[[最適化問題]]の制約領域の境界上ではなく内部に, 最適解に収束する点列を生成する逐次反復解法である. 特に[[線形計画|線形計画問題]]に対しては, 最適値に十分に近い近似解が得られれば, 変数次元の連立方程式を1回解く手間で最適解が得られることから, 内点法で最適解を得るまでに必要な計算の手間(算術演算回数)を算出することが可能であり, 多くの理論的な成果が報告されている. また実用面では, 特に大規模な問題に対して単体法よりも計算効率が 優れていることが確認されており, この解法を取り入れた商用コードも多く存在する. 線形計画問題以外への応用も積極的に行なわれており, 凸2次計画問題, [[相補性問題]], あるいは半正定値計画問題, <ins class="diffchange diffchange-inline">[[2次錐計画|2次錐計画問題]]等の凸計画問題に対しても有効な解法であることが示されている</ins>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> 1979年に提案された楕円体法は, 線形計画問題に対する初めての[[多項式時間解法]]であるが, 実用的な解法としては単体法に及ばなかった. これに対して1984年にATTベル研究所のカーマーカー(N. Karmarkar) によって提案された初めての内点法(interior point)である[[カーマーカー法]](Karmarkar's algorithm) [1] は, 多項式時間解法である上に, カーマーカー自身の計算機実験では 単体法を遥かに上回る結果であると報告された. この論文および報告を機として, 多くの最適化分野の研究者がこの解法に興味をもち, この結果多様なバリエーションが生み出された.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> 1979年に提案された楕円体法は, 線形計画問題に対する初めての[[多項式時間解法]]であるが, 実用的な解法としては単体法に及ばなかった. これに対して1984年にATTベル研究所のカーマーカー(N. Karmarkar) によって提案された初めての内点法(interior point)である[[カーマーカー法]](Karmarkar's algorithm) [1] は, 多項式時間解法である上に, カーマーカー自身の計算機実験では 単体法を遥かに上回る結果であると報告された. この論文および報告を機として, 多くの最適化分野の研究者がこの解法に興味をもち, この結果多様なバリエーションが生み出された.</div></td></tr>
</table>
Tamura
https://orsj-ml.org/orwiki/wiki/index.php?title=%E5%86%85%E7%82%B9%E6%B3%95&diff=9992&oldid=prev
2008年8月22日 (金) 07:19にTamuraによる
2008-08-22T07:19:07Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2008年8月22日 (金) 07:19時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l2" >2行目:</td>
<td colspan="2" class="diff-lineno">2行目:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== 概要 ===</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== 概要 ===</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>線形計画問題に対するカーマーカー法によって触発され,発展した制約付き最適化問題の反復解法の総称. 実行可能領域の内部を通って最適解へ近づくのでこう呼ばれる.特に大規模問題に有効とされ, 凸計画問題, <del class="diffchange diffchange-inline">半正定値計画問題等へも拡張されている</del>. 主問題または双対問題のどちらか一方の実行可能領域に点列を生成する内点法を主内点法, 主問題および双対問題の双方の実行可能領域に点列を生成する内点法を主双対内点法と呼ぶ.</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>線形計画問題に対するカーマーカー法によって触発され,発展した制約付き最適化問題の反復解法の総称. 実行可能領域の内部を通って最適解へ近づくのでこう呼ばれる.特に大規模問題に有効とされ, <ins class="diffchange diffchange-inline">[[</ins>凸計画問題<ins class="diffchange diffchange-inline">]]</ins>, <ins class="diffchange diffchange-inline">[[半正定値計画問題]]等へも拡張されている</ins>. 主問題または双対問題のどちらか一方の実行可能領域に点列を生成する内点法を主内点法, 主問題および双対問題の双方の実行可能領域に点列を生成する内点法を主双対内点法と呼ぶ.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== 詳説 ===</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== 詳説 ===</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> [[内点法]](interior point method) <del class="diffchange diffchange-inline">は最適化問題の制約領域の境界上ではなく内部に</del>, 最適解に収束する点列を生成する逐次反復解法である. <del class="diffchange diffchange-inline">特に線形計画問題に対しては</del>, 最適値に十分に近い近似解が得られれば, 変数次元の連立方程式を1回解く手間で最適解が得られることから, 内点法で最適解を得るまでに必要な計算の手間(算術演算回数)を算出することが可能であり, 多くの理論的な成果が報告されている. また実用面では, 特に大規模な問題に対して単体法よりも計算効率が 優れていることが確認されており, この解法を取り入れた商用コードも多く存在する. 線形計画問題以外への応用も積極的に行なわれており, 凸2次計画問題, 相補性問題, あるいは半正定値計画問題, 2次錐計画問題等の凸計画問題に対しても有効な解法であることが示されている.</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> [[内点法]](interior point method) <ins class="diffchange diffchange-inline">は[[最適化問題]]の制約領域の境界上ではなく内部に</ins>, 最適解に収束する点列を生成する逐次反復解法である. <ins class="diffchange diffchange-inline">特に[[線形計画|線形計画問題]]に対しては</ins>, 最適値に十分に近い近似解が得られれば, 変数次元の連立方程式を1回解く手間で最適解が得られることから, 内点法で最適解を得るまでに必要な計算の手間(算術演算回数)を算出することが可能であり, 多くの理論的な成果が報告されている. また実用面では, 特に大規模な問題に対して単体法よりも計算効率が 優れていることが確認されており, この解法を取り入れた商用コードも多く存在する. 線形計画問題以外への応用も積極的に行なわれており, 凸2次計画問題, <ins class="diffchange diffchange-inline">[[</ins>相補性問題<ins class="diffchange diffchange-inline">]]</ins>, あるいは半正定値計画問題, 2次錐計画問題等の凸計画問題に対しても有効な解法であることが示されている.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> 1979年に提案された楕円体法は, 線形計画問題に対する初めての[[多項式時間解法]]であるが, 実用的な解法としては単体法に及ばなかった. これに対して1984年にATTベル研究所のカーマーカー(N. Karmarkar) によって提案された初めての内点法(interior point)である[[カーマーカー法]](Karmarkar's algorithm) [1] は, 多項式時間解法である上に, カーマーカー自身の計算機実験では 単体法を遥かに上回る結果であると報告された. この論文および報告を機として, 多くの最適化分野の研究者がこの解法に興味をもち, この結果多様なバリエーションが生み出された.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> 1979年に提案された楕円体法は, 線形計画問題に対する初めての[[多項式時間解法]]であるが, 実用的な解法としては単体法に及ばなかった. これに対して1984年にATTベル研究所のカーマーカー(N. Karmarkar) によって提案された初めての内点法(interior point)である[[カーマーカー法]](Karmarkar's algorithm) [1] は, 多項式時間解法である上に, カーマーカー自身の計算機実験では 単体法を遥かに上回る結果であると報告された. この論文および報告を機として, 多くの最適化分野の研究者がこの解法に興味をもち, この結果多様なバリエーションが生み出された.</div></td></tr>
</table>
Tamura
https://orsj-ml.org/orwiki/wiki/index.php?title=%E5%86%85%E7%82%B9%E6%B3%95&diff=9663&oldid=prev
Imahori: 基礎編と用語編のマージ
2008-03-13T13:39:41Z
<p>基礎編と用語編のマージ</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2008年3月13日 (木) 13:39時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >1行目:</td>
<td colspan="2" class="diff-lineno">1行目:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''【ないてんほう (interior point method)】'''</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''【ないてんほう (interior point method)】'''</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">=== 概要 ===</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>線形計画問題に対するカーマーカー法によって触発され,発展した制約付き最適化問題の反復解法の総称. 実行可能領域の内部を通って最適解へ近づくのでこう呼ばれる.特に大規模問題に有効とされ, 凸計画問題, 半正定値計画問題等へも拡張されている. 主問題または双対問題のどちらか一方の実行可能領域に点列を生成する内点法を主内点法, 主問題および双対問題の双方の実行可能領域に点列を生成する内点法を主双対内点法と呼ぶ.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>線形計画問題に対するカーマーカー法によって触発され,発展した制約付き最適化問題の反復解法の総称. 実行可能領域の内部を通って最適解へ近づくのでこう呼ばれる.特に大規模問題に有効とされ, 凸計画問題, 半正定値計画問題等へも拡張されている. 主問題または双対問題のどちらか一方の実行可能領域に点列を生成する内点法を主内点法, 主問題および双対問題の双方の実行可能領域に点列を生成する内点法を主双対内点法と呼ぶ.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">詳しくは</del>[[<del class="diffchange diffchange-inline">《内点法》</del>|<del class="diffchange diffchange-inline">基礎編：内点法</del>]]<del class="diffchange diffchange-inline">を参照</del>.</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">=== 詳説 ===</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> </ins>[[<ins class="diffchange diffchange-inline">内点法]](interior point method) は最適化問題の制約領域の境界上ではなく内部に, 最適解に収束する点列を生成する逐次反復解法である. 特に線形計画問題に対しては, 最適値に十分に近い近似解が得られれば, 変数次元の連立方程式を1回解く手間で最適解が得られることから, 内点法で最適解を得るまでに必要な計算の手間(算術演算回数)を算出することが可能であり, 多くの理論的な成果が報告されている. また実用面では, 特に大規模な問題に対して単体法よりも計算効率が 優れていることが確認されており, この解法を取り入れた商用コードも多く存在する. 線形計画問題以外への応用も積極的に行なわれており, 凸2次計画問題, 相補性問題, あるいは半正定値計画問題, 2次錐計画問題等の凸計画問題に対しても有効な解法であることが示されている.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 1979年に提案された楕円体法は, 線形計画問題に対する初めての[[多項式時間解法]]であるが, 実用的な解法としては単体法に及ばなかった. これに対して1984年にATTベル研究所のカーマーカー(N. Karmarkar) によって提案された初めての内点法(interior point)である[[カーマーカー法]](Karmarkar's algorithm) [1] は, 多項式時間解法である上に, カーマーカー自身の計算機実験では 単体法を遥かに上回る結果であると報告された. この論文および報告を機として, 多くの最適化分野の研究者がこの解法に興味をもち, この結果多様なバリエーションが生み出された.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> カーマーカー法は, 特殊な線形計画問題</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"><table align="center"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"><tr></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"><td></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"><math>\begin{array}{llllll}</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">\mbox{max.} & c^{\top}x & \mbox{s. t.} & Ax = 0,</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">& e^{\top}x = 1, & x \geq 0, </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">\end{array}</math></td></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"></tr></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"></table></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">(<math>A\,</math>は<math>m \times n\,</math>行列, <math>c \in \mathbf{R}^n</math>, <math>e \in \mathbf{R}^n</math>は要素がすべて<math>1\,</math>のベクトル)を対象とし, 対数障壁関数を用いた[[ポテンシャル関数 (内点法の)</ins>|<ins class="diffchange diffchange-inline">ポテンシャル関数]](potential function) の値で最適解からの誤差を測り, [[射影変換]] (projective transformation) を用いて探索方向を決定するという特徴をもつ. 対数障壁関数を用いるという点で非線形計画法の一解法とも考えられるが, 着想, 解析共に従来の常識とは異なる斬新な解法であった. より一般的で記述が簡潔なアルゴリズムとして提案された解法が, [[アフィン変換法]](affine scaling method) である. その後1988年に, ロシアの数学者ディキン(I. Dikin) が20年以上前の1967年に同じ解法を提案していたことが明かになり, 話題となった. アフィン変換法は実用的であり, 大域的収束性が示されているが, 解法の多項式時間性については未だ不明である.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 他方, 従来のSUMT法, ホモトピー法, ニュートン法といった枠組を用いて内点法を構築する試みも行なわれた. 中でも大きな役割を果たしたのは, ゾンネべンド(Gy. Sonnevend)が提唱した[[中心パス]](path of centers) であり, この概念を利用してレネガー(J. Renegar)はニュートン法を用いた初めての 多項式時間解法を提案した. さらに, 主問題と双対問題の双方を1つの問題とみなした場合の解析的 中心に関する研究も行なわれ, [[主双対内点法]](primal-dual interior point method) の提案へと結び付いた. 主双対内点法を改良した[[予測子修正子内点法]](predictor-corrector interior point method) は, 現在もっとも普及している内点法の1つである. これらの解法については [5] 等を参照されたい.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 内点法における大きな課題の1つは, 条件のよい許容領域内部の初期点をいかに用意するかという問題である. この課題の解決策として [[非許容初期点内点法]] (infeasible interior point method) や, 理論的にはさらに優れた [[同次自己双対内点法]] (homogeneous self-dual interior point method) が提案されており, 実装の際にはどちらかが用いられることが多い.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 以上の解法の中で, アフィン変換法以外の解法は多項式時間解法であることが示されている. ネステロフとネミロフスキーは, [[自己整合障壁関数]</ins>]<ins class="diffchange diffchange-inline">の概念を導入した上で, 内点法という解法のクラスの中で, 多項式時間解法である解法からなる, 1つの大きなクラスを示した [2</ins>]. <ins class="diffchange diffchange-inline">この研究は, 1990年代から活発に行なわれている, [[半正定値計画]]問題や[[2次錐計画]]問題等に内点法を適用する研究の重要な基礎となっている.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 近年内点法が記述された教科書も多く出版されている. [12] は内点法を総合的に扱った和書である. 線形計画法のみならず, 半正定値計画問題, 非線形計画問題に対する内点法についも述べている. その他の洋書の多くは主双対内点法と非許容初期点内点法を基本とした内容であるが, カーマーカー法については [3], [9], アフィン変換法については [4], [6], 同次自己双対内点法については, [6], [10] 等にそれぞれ詳しく述べられている. [8], [9], [10] はそれぞれ線形計画法の教科書であり, 図表が多く入門的な内容であるが, [8] は単体法, [9] は内点法を包括する理論, [10] は実装 にそれぞれ重きを置いている点が特徴である. また, 内点法に関する論文の多くは, インターネットを通じて入手可能である [11].</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">----</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">'''参考文献'''</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[1] K. Karmarkar, "A New Polynomial-Time Algorithm for Linear Programming," ''Combinatorica'', '''4''' (1984), 373-395.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[2] Y. Nesterov and A. S. Nemirovskii, ''Interior Point Polynomial Algorithms in Convex Programming'', SIAM, 1994.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[3] S.-C. Fang and S. Puthenpra, ''Linear Optimization and Extentions'' Prentice Hall, 1993.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[4] R. Saigal, ''Linear Programming: A Modern Integrated Analysis'' Kluwer Academic Publishers, 1995.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[5] J. Wright, ''Primal-Dual Interior-Point Methods'', SIAM, 1996.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[6] T. Terlaky, eds., ''Interior Point Methods of Mathematical Programming'', Kluwer Academic Publishers, 1996.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[7] Y. Ye, ''Interior Point Algorithms: Theory and Analysis'', Jhon Wiley & Sons, 1997</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[8] D. Bertsimas and J. N. Tsisiklis, ''Introduction to Linear Optimization'', Athena Scientific, 1997.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[9] C. Roos, T. Terlaky and J.-Ph. Vial ''Theory and Algorithns for Linear Optimization'', John Wiley & Sons, 1997.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[10] R. J. Vanderbei, ''Linear Programming: Foundations and Extensions'', Kluwer Academic Publishers, 1998.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[11] http://www-unix.mcs.anl.gov/otc/InteriorPoint</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[12] 小島政和, 土谷隆, 水野眞治, 矢部博, 『内点法』, 朝倉書店, 2001.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[[Category:線形計画|ないてんほう]]</ins></div></td></tr>
</table>
Imahori
https://orsj-ml.org/orwiki/wiki/index.php?title=%E5%86%85%E7%82%B9%E6%B3%95&diff=8313&oldid=prev
2007年8月8日 (水) 11:22にKanda.kによる
2007-08-08T11:22:00Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2007年8月8日 (水) 11:22時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l3" >3行目:</td>
<td colspan="2" class="diff-lineno">3行目:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>線形計画問題に対するカーマーカー法によって触発され,発展した制約付き最適化問題の反復解法の総称. 実行可能領域の内部を通って最適解へ近づくのでこう呼ばれる.特に大規模問題に有効とされ, 凸計画問題, 半正定値計画問題等へも拡張されている. 主問題または双対問題のどちらか一方の実行可能領域に点列を生成する内点法を主内点法, 主問題および双対問題の双方の実行可能領域に点列を生成する内点法を主双対内点法と呼ぶ.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>線形計画問題に対するカーマーカー法によって触発され,発展した制約付き最適化問題の反復解法の総称. 実行可能領域の内部を通って最適解へ近づくのでこう呼ばれる.特に大規模問題に有効とされ, 凸計画問題, 半正定値計画問題等へも拡張されている. 主問題または双対問題のどちらか一方の実行可能領域に点列を生成する内点法を主内点法, 主問題および双対問題の双方の実行可能領域に点列を生成する内点法を主双対内点法と呼ぶ.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>詳しくは[[《内点法》|基礎編：内点法]]<del class="diffchange diffchange-inline">を参照。</del></div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>詳しくは[[《内点法》|基礎編：内点法]]<ins class="diffchange diffchange-inline">を参照.</ins></div></td></tr>
</table>
Kanda.k
https://orsj-ml.org/orwiki/wiki/index.php?title=%E5%86%85%E7%82%B9%E6%B3%95&diff=7695&oldid=prev
2007年8月6日 (月) 07:47にKanda.kによる
2007-08-06T07:47:08Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2007年8月6日 (月) 07:47時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l2" >2行目:</td>
<td colspan="2" class="diff-lineno">2行目:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>線形計画問題に対するカーマーカー法によって触発され,発展した制約付き最適化問題の反復解法の総称. 実行可能領域の内部を通って最適解へ近づくのでこう呼ばれる.特に大規模問題に有効とされ, 凸計画問題, 半正定値計画問題等へも拡張されている. 主問題または双対問題のどちらか一方の実行可能領域に点列を生成する内点法を主内点法, 主問題および双対問題の双方の実行可能領域に点列を生成する内点法を主双対内点法と呼ぶ.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>線形計画問題に対するカーマーカー法によって触発され,発展した制約付き最適化問題の反復解法の総称. 実行可能領域の内部を通って最適解へ近づくのでこう呼ばれる.特に大規模問題に有効とされ, 凸計画問題, 半正定値計画問題等へも拡張されている. 主問題または双対問題のどちらか一方の実行可能領域に点列を生成する内点法を主内点法, 主問題および双対問題の双方の実行可能領域に点列を生成する内点法を主双対内点法と呼ぶ.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">詳しくは[[《内点法》|基礎編：内点法]]を参照。</ins></div></td></tr>
</table>
Kanda.k
https://orsj-ml.org/orwiki/wiki/index.php?title=%E5%86%85%E7%82%B9%E6%B3%95&diff=6621&oldid=prev
Orsjwiki: "内点法" を保護しました。 [edit=sysop:move=sysop]
2007-07-20T01:14:21Z
<p>"内点法" を保護しました。 [edit=sysop:move=sysop]</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<tr class="diff-title" lang="ja">
<td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">2007年7月20日 (金) 01:14時点における版</td>
</tr><tr><td colspan="2" class="diff-notice" lang="ja"><div class="mw-diff-empty">(相違点なし)</div>
</td></tr></table>
Orsjwiki
https://orsj-ml.org/orwiki/wiki/index.php?title=%E5%86%85%E7%82%B9%E6%B3%95&diff=5461&oldid=prev
2007年7月17日 (火) 07:26に122.17.2.240による
2007-07-17T07:26:58Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2007年7月17日 (火) 07:26時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >1行目:</td>
<td colspan="2" class="diff-lineno">1行目:</td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>【ないてんほう (interior point method)】</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">'''</ins>【ないてんほう (interior point method)】<ins class="diffchange diffchange-inline">'''</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>線形計画問題に対するカーマーカー法によって触発され,発展した制約付き最適化問題の反復解法の総称. 実行可能領域の内部を通って最適解へ近づくのでこう呼ばれる.特に大規模問題に有効とされ, 凸計画問題, 半正定値計画問題等へも拡張されている. 主問題または双対問題のどちらか一方の実行可能領域に点列を生成する内点法を主内点法, 主問題および双対問題の双方の実行可能領域に点列を生成する内点法を主双対内点法と呼ぶ.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>線形計画問題に対するカーマーカー法によって触発され,発展した制約付き最適化問題の反復解法の総称. 実行可能領域の内部を通って最適解へ近づくのでこう呼ばれる.特に大規模問題に有効とされ, 凸計画問題, 半正定値計画問題等へも拡張されている. 主問題または双対問題のどちらか一方の実行可能領域に点列を生成する内点法を主内点法, 主問題および双対問題の双方の実行可能領域に点列を生成する内点法を主双対内点法と呼ぶ.</div></td></tr>
</table>
122.17.2.240