ＫＳ情報科学専門書 しっかり学ぶ数理最適化 モデルからアルゴリズムまで

著者名：梅谷俊治【著】

講談社（2021/01発売）

• ISBN：9784065212707

内容説明

最適化問題へのモデル化と、基本的なアルゴリズムを俯瞰し、最適化という考え方の基礎をしっかりと固める。大事なことは、いつの時代も変わらない。イメージしやすい具体的な例や、理解の定着にかかせない演習問題も充実！

【推薦の言葉】
数理最適化は、問題解決のための数学である。今では、その成果を実装したソルバーが簡単に手に入るようになった。直面する問題を解決するには、まずそれをモデル化し、適切な最適化手法を適用するという手順を踏む。
本書は、豊富な実例を通して、モデル化の勘どころを説明し、さらに広範な最適化手法それぞれを、基本から分かりやすく解説している。この分野全般を知るための「最適解」として推薦したい。
――茨木俊秀(京都情報大学院大学学長)

【サポートページ】
https://sites.google.com/view/introduction-to-optimization/main

【主な内容】
第1章 数理最適化入門
1.1 数理最適化とは
1.2 最適化問題
1.3 代表的な最適化問題
1.4 本書の構成

第2章 線形計画
2.1 線形計画問題の定式化
2.2 単体法
2.3 緩和問題と双対定理

第3章 非線形計画
3.1 非線形計画問題の定式化
3.2 制約なし最適化問題
3.3 制約つき最適化問題

第4章 整数計画と組合せ最適化
4.1 整数計画問題の定式化
4.2 アルゴリズムの性能と問題の難しさの評価
4.3 効率的に解ける組合せ最適化問題
4.4 分枝限定法と切除平面法
4.5 近似解法
4.6 局所探索法
4.7 メタヒューリスティクス

目次

第1章 数理最適化入門
1.1 数理最適化とは
1.2 最適化問題
1.3 代表的な最適化問題
1.4 本書の構成
第2章 線形計画
2.1 線形計画問題の定式化
2.2 単体法
2.3 緩和問題と双対定理
第3章 非線形計画
3.1 非線形計画問題の定式化
3.2 制約なし最適化問題
3.2.1 制約なし最適化問題の最適性条件
3.2.2 最急降下法
3.2.3 ニュートン法
3.2.4 準ニュートン法
3.2.5 反復法の収束性
3.3 制約つき最適化問題
3.3.1 等式制約つき最適化問題の最適性条件
3.3.2 不等式制約つき最適化問題の最適性条件
3.3.3 双対問題と双対定理
3.3.4 有効制約法
3.3.5 ペナルティ関数法とバリア関数法
3.3.6 拡張ラグランジュ関数法
3.3.7 内点法
3.3.8 逐次2次計画法
第4章 整数計画と組合せ最適化
4.1 整数計画問題の定式化
4.1.1 整数計画問題の応用例
4.1.2 論理的な制約条件
4.1.3 固定費用付き目的関数
4.1.4 離接した制約条件
4.1.5 非凸な非線形関数の近似
4.1.6 整数性を持つ整数計画問題
4.1.7 グラフの連結性
4.1.8 パターンの列挙
4.2 アルゴリズムの性能と問題の難しさの評価
4.2.1 アルゴリズムの計算量とその評価
4.2.2 問題の難しさとNP困難問題
4.3 効率的に解ける組合せ最適化問題
4.3.1 貪欲法
4.3.2 動的計画法
4.3.3 ネットワークフロー
4.4 分枝限定法と切除平面法
4.4.1 分枝限定法
4.4.2 切除平面法
4.4.3 整数計画ソルバーの利用
4.5 近似解法
4.5.1 近似解法の性能評価
4.5.2 ビンパッキング問題
4.5.3 最大カット問題
4.5.4 巡回セールスマン問題
4.5.5 頂点被覆問題
4.5.6 ナップサック問題
4.6 局所探索法
4.6.1 局所探索法の概略
4.6.2 近傍の定義と解の表現
4.6.3 探索空間と解の評価
4.6.4 移動戦略
4.6.5 局所探索法の効率化
4.7 メタヒューリスティクス
4.7.1 メタヒューリスティクスの概略
4.7.2 多スタート局所探索法
4.7.3 反復局所探索法
4.7.4 遺伝的アルゴリズム
4.7.5 アニーリング法
4.7.6 タブー探索法
4.7.7 誘導局所探索法
4.7.8 ラグランジュヒューリスティクス

感想・レビュー

※以下の感想・レビューは、株式会社ブックウォーカーの提供する「読書メーター」によるものです。

[オザマチ]

内容が盛りだくさんなので、ざっと読んで問題と解法の分類を把握した。

2022/05/01

[kaida6213]

数理最適化の分野を網羅的に扱った本。線形計画、非線形計画のところはなんとかついていけたが、最終章とかは説明が端的すぎて雰囲気のみ把握。一冊にすべてまとめるてのは無理ありますね。

2023/05/12

[shin_ash]

数理最適化に関わりそうだったので、積読から引っ張り出して読んでみた。最適化や数理最適化は統計や機械学習の推定の文脈で断片的な知識があったり、超初心者向けの入門書やある手法の専門職で広大な最適化の話題の一部を読んだりはするが、知識が断片化するばかりでどうにもつかみどころがない。そう言う意味では本書は比較的体系的に数理最適化を説明しており、しかも細かく丁寧に説明はしている。しかしわかりやすくはない。内容よりは日本語の表現がイマイチに思える。細かい故か誤植が非常に多い。内容はよいが読解に強いストレスのかかる本。

2024/09/20

[Taizo]

あくまで個人的実感ではあるんだけど、この分野、いまいち入門書の決定版がなかった。しょうがないからWebに落ちてる解説記事などを拾い読みしていたんだけど、パラ読みした感じ今後はこの本がその決定版として使えそう。あくまで理論的なところに絞れば、線形・非線形計画から組合せ最適化までバッチこい。記述もイメージを呼び込むグラフがふんだんに盛り込まれていてわかりやすい。理論の網羅性と引き換えにコード実装は一切書かれてないので、そちらは他の本やWeb記事で補完すると良さそう。

2021/12/28

[ONE_shoT_]

最適化に関する書籍をきちんと読んだのは初めてかもしれない。様々な問題の定式化の例が載っているので、自分が解こうとしている問題を定式化する際に参考にできそう。

2020/11/29