- 数理最適化の原理とアルゴリズム全般を体系的に扱う教科書で、連続・離散問題の両方を網羅
- 導関数ベースの手法から確率的・進化的手法まで、多様なアプローチを段階的に説明
- 制約条件、双対性、線形・二次計画法など、実応用に必要な数学的構造を収録
- 各章に要約と演習問題を用意し、学習と実践を並行できる構成
- MIT Pressのオープンライセンス(CC BY-NC-ND) で配布
序文と概要
- 本書は最適化問題を解くためのアルゴリズムの理論と実装を扱う教科書で、第2版として刊行
- 著者は Mykel J. Kochenderfer と Tim A. Wheeler
- MIT Press から刊行され、Creative Commons の非商用・改変禁止ライセンスで公開
- 序文と謝辞の後、13章構成となっている
- 各章は中核概念、要約、演習問題で構成され、学習中心の構造を維持
第1章. 序論
- 最適化の歴史、プロセス、数学的定式化、応用分野を紹介
- 極値(minima) と 最適性条件(optimality conditions) を説明
- 本書全体の概要と要約、演習問題を含む
第2章. 導関数と勾配
- 単変数および多変数の導関数の定義と計算方法を説明
- 数値微分(numerical differentiation) と 自動微分(automatic differentiation) の手法を収録
- 回帰勾配と確率的近似手法(SPSA) を扱う
第3章. ブラケティング(Bracketing)
- 単峰性(unimodality) の概念と 初期区間探索の手順を説明
- フィボナッチ探索、黄金分割探索、二次近似探索などの区間ベースのアルゴリズムを収録
- Shubert-Piyavskii および 二分法(bisection) を含む
第4章. 局所降下(Local Descent)
- 降下方向反復(descent direction iteration) と ステップサイズ(step factor) の概念を説明
- 線探索(line search) および 近似線探索の手法を収録
- 信頼領域(trust region) アプローチと 終了条件を扱う
第5章. 一次手法(First-Order Methods)
- 勾配降下法、共役勾配法、モメンタム、Nesterovモメンタム などの主要手法を収録
- AdaGrad, RMSProp, Adadelta, Adam, Hypergradient Descent など現代的な最適化アルゴリズムを掲載
- 各手法の特徴と比較要約を提供
第6章. 二次手法(Second-Order Methods)
- ニュートン法(Newton’s Method) と 割線法(Secant Method) を説明
- Levenberg-Marquardtアルゴリズム および 準ニュートン(Quasi-Newton) 手法を収録
- 要約と演習問題で締めくくる
第7章. 直接法(Direct Methods)
- 座標探索、Powell、Hooke-Jeeves、パターン探索、Nelder-Mead単体法 などを紹介
- 分割矩形法(Divided Rectangles) を収録
- 非導関数ベース最適化アプローチが中心
第8章. 確率的手法(Stochastic Methods)
- ノイズ付き降下、メッシュ適応探索、導関数不要最適化などの確率的アプローチを扱う
- 焼きなまし法、クロスエントロピー、自然進化戦略、共分散行列適応(CMA) を収録
- 確率ベース探索の効率性を強調
第9章. 集団ベース手法(Population Methods)
- 遺伝的アルゴリズム、差分進化、粒子群最適化(PSO) などの集団探索手法を説明
- Firefly、Cuckoo Search、ハイブリッド手法を収録
- 集団反復(population iteration) 構造で問題を解決
第10章. 制約条件(Constraints)
- 制約付き最適化(constrained optimization) の基本概念と制約の種類を説明
- ラグランジュ乗数法、スラック変数、ペナルティ法および内点(interior point)法を収録
- 制約除去変換(transformations) と 乗数法(method of multipliers) を扱う
第11章. 双対性(Duality)
- 双対問題(dual problem) と 原始-双対(primal-dual)法を説明
- 双対上昇(dual ascent) および ADMM(Alternating Direction Method of Multipliers) を収録
- 分散最適化(distributed methods) の応用を扱う
第12章. 線形計画法(Linear Programming)
- 問題定式化、単体法(Simplex Algorithm)、双対証明(dual certificates) を説明
- 線形制約条件下での最適化構造を体系的に提示
第13章. 二次計画法(Quadratic Programming)
- 二次目的関数と線形制約条件を含む問題定式化
- 最小二乗(least squares) 問題と 線形不等式制約を扱う
- 最短距離計画法(least distance programming) を収録
付録およびその他の情報
- 各章末に要約と演習問題を収録
- MIT Press が2025年版として刊行、非商用での共有を許可(CC BY-NC-ND)
- LaTeXベースの組版で、問い合わせ先は bugs@algorithmsbook.com
4件のコメント
今はアクセスできませんね…
https://algorithmsbook.com/optimization/#download
今はリンクが少し変わったのか、ここでPDFを見たりダウンロードしたりできるようですね。
ありがとうございます!!
Hacker Newsのコメント
HNのトップに**最適化（optimization）**の話題が上がってきてうれしい。
自分が作ったLP可視化サイトを紹介したい。線形計画法（Linear Programming）のアルゴリズムが、制約条件や目的関数が変わったときにどう反応するかを視覚的に見ることができる。
デモページに入ると多角形が自動で描画され、頂点や制約線をドラッグしながらアルゴリズムの反復（iteration）を観察できる。
まだ完成度は高くないが、視覚的な学習が好きな人なら面白く使えると思う。フィードバック歓迎。
**メタヒューリスティクス（metaheuristics）**関連の資料を共有したい。
私が働いているTimefoldでは、これらの本に出てくる Tabu Search や Simulated Annealing のようなアルゴリズムを活用して、近似最適解を素早く見つけている。
Timefoldのドキュメントにあるローカルサーチアルゴリズムのダイアグラムも参考になる。
521ページのCCライセンスの最適化教科書で、本当にすばらしそうだ。
前半では自動微分ベースの最新のgradient-basedアルゴリズム（例: Adam）を扱い、後半（第12章）では線形最適化（simplex など）を扱っている。
演習問題も多く、長いこと待っていたまさにそういう本だった。
最適化アルゴリズムは単に問題を解くだけでなく、汎用問題解決器に向けた試みだと思う。プログラムが答えを直接探すのではなく、「答えがどのような形か」を定義し、その上に最適化を適用するやり方だ。
現在のAIもこうしたアプローチに基づいている。
Kochenderferのこの本と以前の著書 Decision Making Under Uncertainty（PDF）は、私が最も好きな技術書の一つだ。
説明が明快で可視化もすばらしく、gradient descent以外のさまざまな最適化の考え方を扱っている。
コードはJuliaで書かれているが、他の言語に移すのは難しくない。言語に縛られず、概念に集中すべきだ。
最適化は単なるテクニックではなく、難しい問題を解くための思考法そのものだ。
この本は CMA-ES, surrogate model, Gaussian process などを一冊で扱っている珍しい資料だ。
学部時代にこんな本があれば本当に助かったと思う。以前は関連内容が複数の論文や本に散らばっていた。
博士課程のときにこの本を何度も通読した。ニューラルネットワークと数値解析を研究していたが、深さと広さのバランスがとてもよい。
今でも参考書としてよく使っている。
本に Firefly, Cuckoo Search のようなメタヒューリスティクスが含まれているのを見て驚いた。
これらのアルゴリズムは学界で信頼されておらず、ITOR論文でも批判されていた。
こうした手法だけを研究する小規模コミュニティが相互引用しながらバブルを形成している。学会でもしばしば論争になる。
**多目的最適化（multiobjective optimization）**の章がすばらしかった。
このテーマに集中した他の本や資料があるなら知りたい。
この本とNocedal & Wrightの Numerical Optimizationを比較してもらえるとうれしい。