「同次自己双対内点法」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: '【どうじじこそうついないてんほう (homogeneous self-dual interior point method)】 線形計画問題の最適性の条件に新たに$2$つのパラメータ...') |
|||
| 1行目: | 1行目: | ||
【どうじじこそうついないてんほう (homogeneous self-dual interior point method)】 | 【どうじじこそうついないてんほう (homogeneous self-dual interior point method)】 | ||
| − | + | 線形計画問題の最適性の条件に新たに$2$つのパラメータを導入することによって, 定数ベクトルが$0$ (同次), 主問題と双対問題が同形(自己双対), かつ最適解をもつ 人工的な線形計画問題を生成し, これに主双対内点法を適用する多項式時間解法である. 人工問題の最適解から, 元の問題の最適解の有無や最適解が得られる. 大きな値の初期点を必要としない点で, 非許容初期点内点法 より数値的に安定しているといわれている. | |
2007年7月12日 (木) 22:54時点における版
【どうじじこそうついないてんほう (homogeneous self-dual interior point method)】
線形計画問題の最適性の条件に新たに$2$つのパラメータを導入することによって, 定数ベクトルが$0$ (同次), 主問題と双対問題が同形(自己双対), かつ最適解をもつ 人工的な線形計画問題を生成し, これに主双対内点法を適用する多項式時間解法である. 人工問題の最適解から, 元の問題の最適解の有無や最適解が得られる. 大きな値の初期点を必要としない点で, 非許容初期点内点法 より数値的に安定しているといわれている.