| 注：[L♯]、[M♯]は、現物の表記と異なります |
| |
| 第1章 離散最適化を楽しむ 1 |
| 1.1 アメリカの都市を結ぶ 1 |
| 1.2 最短経路の証拠 3 |
| 1.3 巡回セールスマン問題 5 |
| 1.4 離散凸の視点 7 |
| ノート 8 |
| 第2章 凸閏数と凸集合 9 |
| 2.1 極小と最小 9 |
| 2.2 凸関数 10 |
| 2.2.1 1変数の場合 10 |
| 2.2.2 極小と最小の一致 12 |
| 2.2.3 多変数の場合 13 |
| 2.3 凸集合 15 |
| 2.4 まとめ 18 |
| ノート 18 |
| 第3章 連続から離散へ 19 |
| 3.1 1変数の関数 19 |
| 3.2 多変数の関数 21 |
| 3.3 L凸関数 22 |
| 3.4 M凸関数 24 |
| 3.5 離散凸集合 27 |
| 3.6 まとめ 29 |
| ノート 31 |
| 第4章 L凸関数 32 |
| 4.1 [L♯]凸関数 32 |
| 4.2 L凸関数 34 |
| 4.3 [L♯]凸集合とL凸集合 35 |
| 4.4 2次関数 40 |
| 4.5 離散へッセ行列 42 |
| 4.6 L凸関数の例 44 |
| 4.7 L凸関数の演算 46 |
| 4.8 劣モジュラ集合関数 49 |
| 4.9 凸拡張 52 |
| 4.9.1 劣モジュラ集合関数 53 |
| 4.9.2 [L♯]凸関数 54 |
| 4.10 まとめ 56 |
| ノート 57 |
| 第5章 M凸関数 58 |
| 5.1 [M♯]凸関数 58 |
| 5.2 M凸関数 59 |
| 5.3 [M♯]凸集合とM凸集合 60 |
| 5.4 2次関数 65 |
| 5.5 離散ヘッセ行列 69 |
| 5.6 M凸関数の例 70 |
| 5.7 M凸関数の演算 72 |
| 5.8 最小木問題 74 |
| 5.9 まとめ 78 |
| ノート 78 |
| 第6章 連続変数の離散凸関数 79 |
| 6.1 離散から連続へ 79 |
| 6.1.1 連続変数のL凸関数とM凸関数 79 |
| 6.1.2 方向の離散性と値の離散性 82 |
| 6.2 L凸関数 86 |
| 6.2.1 [L♯]凸関数とL凸関数 86 |
| 6.2.2 [L♯]凸集合とL凸集合 88 |
| 6.2.3 2次関数とヘッセ行列 94 |
| 6.2.4 L凸関数の例 96 |
| 6.2.5 L凸関数の演算 97 |
| 6.3 M凸関数 99 |
| 6.3.1 [M♯]凸関数とM凸関数 99 |
| 6.3.2 [M♯]凸集合とM凸集合 101 |
| 6.3.3 2次関数とヘッセ行列 104 |
| 6.3.4 M凸関数の例 106 |
| 6.3.5 M凸関数の演算 108 |
| 6.4 まとめ 109 |
| ノート 110 |
| 第7章 離散化・連続化・粗視化 111 |
| 7.1 離散化と連続化 111 |
| 7.1.1 一般的考察 111 |
| 7.1.2 L凸関数 113 |
| 7.1.3 M凸関数 114 |
| 7.2 離散関数の粗視化 115 |
| 7.2.1 スケーリングと近接定理 115 |
| 7.2.2 L凸関数 117 |
| 7.2.3 M凸関数 119 |
| 7.3 まとめ 120 |
| ノート 121 |
| 第8章 共役性定理 122 |
| 8.1 ルシャンドル変換 122 |
| 8.2 連続版の共役性定理 127 |
| 8.2.1 共役性定理 127 |
| 8.2.2 諸演算と共役性 129 |
| 8.3 離散版の共役性定理 130 |
| 8.3.1 共役性定理 130 |
| 8.3.2 諸演算と共役性 131 |
| 8.4 線形代数における共役性 133 |
| 8.5 劣モジュラ関数と多面体 134 |
| 8.6 まとめ 136 |
| ノート 136 |
| 第9章 和の最小化 137 |
| 9.1 連続変数の関数の和 137 |
| 9.2 離散変数の関数の和 140 |
| 9.2.1 定理の形 140 |
| 9.2.2 離散の困難 141 |
| 9.2.3 定理とその意義 143 |
| 9.3 まとめ 145 |
| ノート 146 |
| 第10章 分離定理 147 |
| 10.1 連続版の分離定理 147 |
| 10.2 離散版の分離定理 148 |
| 10.2.1 定理の形 148 |
| 10.2.2 離散の困難 150 |
| 10.2.3 L分離定理とM分離定理 152 |
| 10.3 劣モジュラ集合関数の分離定理 153 |
| 10.3.1 離散分離定理 154 |
| 10.3.2 L分離定理からの導出 154 |
| 10.3.3 連続世界との関係 155 |
| 10.4 まとめ 157 |
| ノート 157 |
| 第11章 最大・最小定理 158 |
| 11.1 連続版のフェンシェル双対定理 158 |
| 11.2 離散版のフェンシェル双対定理 160 |
| 11.3 エドモンズの交わり定理 163 |
| 11.3.1 交わり定理 164 |
| 11.3.2 離散フェンシェル双対定理からの導出 164 |
| 11.3.3 連続世界との関係 165 |
| 11.4 まとめ 166 |
| ノート 167 |
| 第12章 不動点定理 168 |
| 12.1 連続版の不動点定理 168 |
| 12.2 離散版の不動点定理 170 |
| 12.2.1 整凸集合 170 |
| 12.2.2 方向保存写像 171 |
| 12.2.3 離散不動点定理 173 |
| 12.2.4 証明の概略 174 |
| 12.3 まとめ 176 |
| ノート 176 |
| 第13章 ゲーム理論への応用 177 |
| 13.1 離散凹関数によるモデル 177 |
| 13.2 安定結婚モデル 183 |
| 13.3 割当モデル 185 |
| 13.4 まとめ 186 |
| ノート 186 |
| 第14章 離散凸関数の諸例 188 |
| 14.1 行列とマトロイド 188 |
| 14.2 多項式行列と付値マトロイド 192 |
| 14.3 有限距離空間 195 |
| 14.3.1 距離関数 195 |
| 14.3.2 L凸集合と正斉次M凸関数 196 |
| 14.3.3 木距離 198 |
| 14.3.4 系統樹の構成法 200 |
| 14.3.5 スプリット分解 203 |
| 14.3.6 離散凸アプローチ 206 |
| 14.4 行列和の固有値 211 |
| 14.4.1 固有値の満たす不等式 211 |
| 14.4.2 パズル不等式と離散凹関数 214 |
| 14.5 グラフとネットワーク 218 |
| 14.5.1 マッチング 218 |
| 14.5.2 最小費用流 219 |
| 14.6 マルチモジュラ関数 222 |
| 14.7 在庫管理 226 |
| 14.8 確率過程 229 |
| 14.8.1 キュムラント母関数とレート関数 229 |
| 14.8.2 ブラウン運動 232 |
| 14.8.3 ガウス過程 234 |
| 14.8.4 加法過程 236 |
| 参考文献 238 |
| 記号表 245 |
| 索引 247 |
| 注 : [L♯]、[M♯]は、現物の表記と異なります |
| |
| 第1章 離散最適化を楽しむ 1 |
| 1.1 アメリカの都市を結ぶ 1 |
| 1.2 最短経路の証拠 3 |
| 1.3 巡回セールスマン問題 5 |
