| 1.数理計画法概論 内点法を中心にして 1 |
| 1.1 線形計画問題,単体法,楕円体法,双対定理について簡単に 2 |
| 1.1.1 線形計画問題 2 |
| 1.1.2 単体法 3 |
| 1.1.3 計算複雑度の理論の発展と楕円体法 4 |
| 1.1.4 双対定理 6 |
| 1.2 線形計画問題に対する内点法 7 |
| 1.2.1 Karmarkar法 8 |
| 1.2.2 アフインスケーリング法 10 |
| 1.2.3 Renegarによる解析的中心追跡法 11 |
| 1.2.4 主双対内点法 12 |
| 1.3 数理計画問題とは 14 |
| 1.4 連続最適化と離散最適化 17 |
| 1.5 局所最適化と大域的最適化 21 |
| 1.6 凸計画問題と内点法 24 |
| 2.線形計画問題 28 |
| 2.1 線形計画問題とその例 28 |
| 2.2 双対問題 33 |
| 2.3 双対定理と相補性条件 33 |
| 2.4 最適解集合と強相補性条件 36 |
| 2.5 線形計画問題の実行可能領域と最適解集合 39 |
| 2.5.1 等式標準形多面体と主問題の最適解集合 39 |
| 2.5.2 双対等式標準形多面体と双対問題の最適解集合 44 |
| 2.5.3 等式標準形多面体と双対等式標準形多面体の関係 48 |
| 2.6 退化 49 |
| 2.7 単体法 51 |
| 2.8 内点法 55 |
| 2.9 単体法と内点法 57 |
| 2.10 線形計画問題のサイズと計算複雑度の理論 59 |
| 3.線形計画問題に対する主内点法 64 |
| 3.1 線形計画問題に対する主内点法 64 |
| 3.2 アフインスケーリング法 72 |
| 3.2.1 アルゴリズム 72 |
| 3.2.2 双対推定 79 |
| 3.2.3 収束性に関する結果 80 |
| 3.2.4 双対標準形問題に対するアフインスケーリング法 80 |
| 3.2.5 一般問題の解法 82 |
| 3.2.6 関連する話題 82 |
| 3.3 Karmarkar法 84 |
| 3.3.1 アルゴリズム 84 |
| 3.3.2 Karmarkarポテンシャル関数の減少と多項式性 88 |
| 3.3.3 問題の変形 93 |
| 3.3.4 仮定を緩める 95 |
| 3.3.5 Karmarkar法の原論文との等価性 98 |
| 3.4 解析的中心と中心パス,解析的中心追跡法,パス追跡法 100 |
| 3.4.1 解析的中心 100 |
| 3.4.2 解析的中心追跡法 103 |
| 3.4.3 パス追跡法 106 |
| 3.4.4 中心パス 108 |
| 3.4.5 Newton法と主パス追跡法の解析 110 |
| 3.4.6 再び双対推定について 114 |
| 3.5 ポテンシャル減少法 116 |
| 3.6 おわりに 119 |
| 3.7 付録 119 |
| 4.線形計画問題の主双対内点法 122 |
| 4.1 線形計画問題と主双対問題 122 |
| 4.2 主双対内点法 123 |
| 4.2.1 アフインスケーリング法 124 |
| 4.2.2 パス追跡法 127 |
| 4.2.3 さまざまなパス追跡法 131 |
| 4.2.4 ポテンシャル減少法 133 |
| 4.3 非実行可能点列内点法 135 |
| 4.3.1 パス追跡法(その1) 136 |
| 4.3.2 パス追跡法(その2) 139 |
| 4.3.3 Mehrotraの予測子・修正子法 141 |
| 4.4 主双対内点法の大域的収束性と計算量 145 |
| 4.5 局所的超1次収束性 146 |
| 4.6 アルゴリズムの実装とソフトウェアについて 147 |
| 5.2次計画問題と線形相補性問題の内点法 154 |
| 5.1 2次計画問題 154 |
| 5.2 2次計画問題の主内点法 155 |
| 5.3 2次計画問題の主双対内点法 158 |
| 5.4 線形相補性問題 160 |
| 5.5 内点法の収束性 162 |
| 6.半正定値計画問題 164 |
| 6.1 線形計画問題と半正定値計画問題 164 |
| 6.2 線形行列不等式と半正定値計画問題 166 |
| 6.3 半正定値計画問題の例 167 |
| 6.3.1 凸2次最適化問題 167 |
| 6.3.2 固有値に関する条件 169 |
| 6.3.3 行列近似問題 170 |
| 6.3.4 グラフの最大カット問題 171 |
| 6.3.5 非凸型2次最適化問題の半正定値計画緩和 173 |
| 6.4 半正定値計画問題の特徴 175 |
| 6.5 双対定理 177 |
| 6.6 主双対内点法 179 |
| 6.6.1 対数障壁関数と中心パス 179 |
| 6.6.2 基本的な考え方 182 |
| 6.6.3 探索方向 183 |
| 6.6.4 主双対内点法のまとめ 186 |
| 6.7 ソフトウェア 187 |
| 7.凸計画問題に対する多項式内点法 189 |
| 7.1 対称錐上の線形計画問題と2次錐計画問題 190 |
| 7.1.1 対称錐上の線形計画問題とEuclid的Jordan代数,主双対内点法 190 |
| 7.1.2 2次錐計画問題と主双対内点法 193 |
| 7.1.3 問題のスケーリングとスケーリングされたNewton方向 201 |
| 7.1.4 主双対パス追跡法 203 |
| 7.2 自己整合障壁関数を用いた主内点法 204 |
| 7.2.1 凸最適化問題と自己整合障壁関数 204 |
| 7.2.2 パス追跡法 207 |
| 7.2.3 fv(y)最小化に関するNewton法について 212 |
| 7.2.4 線形計画問題,半正定値計画問題の場合 213 |
| 7.2.5 自己整合障壁関数の例 215 |
| 7.2.6 錐に関する自己整合障壁関数,普遍自己整合障壁関数について 215 |
| 8.非線形最適化問題に対する内点法 218 |
| 8.1 非線形最適化問題 218 |
| 8.2 主双対内点法 221 |
| 8.3 ι1型障壁罰金関数を用いた主双対内点法の大域的収束性 232 |
| 8.3.1 直線探索法を用いた場合の大域的収束性 233 |
| 8.3.2 信頼領域法を用いた場合の大域的収束性 237 |
| 8.4 ι2型主双対障壁罰金関数を用いた場合の大域的収束性 243 |
| 8.4.1 微分可能な主双対評価関数 244 |
| 8.4.2 直線探索を用いた場合の大域的収束性 247 |
| 8.5 超1次収束性と2次収束性 249 |
| 8.5.1 前準備 250 |
| 8.5.2 Newton法を用いた場合の局所的2次収束性 253 |
| 8.5.3 準Newton法を用いた場合の局所的超1次収束性 254 |
| 8.5.4 中心パスに沿った場合の超1次収束性 257 |
| 8.6 ソフトウェアと数値実験 259 |
| 文献 263 |
| 索引 279 |
| 1.数理計画法概論 内点法を中心にして 1 |
| 1.1 線形計画問題,単体法,楕円体法,双対定理について簡単に 2 |
| 1.1.1 線形計画問題 2 |
図書
図書
