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