注 : [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 |