最適化 上級
Mathematical Optimization - Advanced
大学院レベルこの章の目標
- 整数計画法の理論と解法（分枝限定法、切除平面法）を理解する
- 組合せ最適化問題の計算複雑性とNP困難性を学ぶ
- 大規模最適化のための分解法と効率的アルゴリズムを習得する
- 分散最適化とADMMの理論を理解する
- 不確実性下での最適化（ロバスト最適化）を学ぶ
- 変分法と最適制御の基礎を理解する
前提知識
- 中級の内容（凸最適化、双対理論、KKT条件）
- 関数解析の基礎（ノルム空間、汎関数）
- 組合せ論の基礎（グラフ理論、計算複雑性）
章の構成
第1章: 整数計画法
整数計画問題の定式化、分枝限定法、切除平面法を学ぶ。
第2章: 組合せ最適化
組合せ最適化問題の例、NP困難性、近似アルゴリズムを学ぶ。
第3章: 大規模最適化
疎行列の活用、分解法、座標降下法、近接勾配法を学ぶ。
第4章: 分散最適化
ADMM、合意最適化、フェデレーテッドラーニングを学ぶ。
第5章: ロバスト最適化
不確実性の扱い、ロバスト線形計画、分布ロバスト最適化を学ぶ。
第6章: 変分法と最適制御
汎関数の最適化、オイラー・ラグランジュ方程式、最大原理を学ぶ。
第7章: 数値最適化の収束率と加速法
Lipschitz 滑らかさと強凸性、Nesterov 加速勾配法の $O(1/k^2)$、Nemirovski-Yudin の下界、FISTA、Newton/BFGS の局所収束率。
第8章: 近接作用素
$\text{prox}_{\lambda g}$ の定義と一意性、射影との関係、レゾルベント（陰的勾配ステップ）、軟しきい値などの閉形式、Moreau 包絡線、近接勾配法への橋渡し。
第9章: 近接勾配法とFISTA
前進後退分割による近接勾配法（ISTA）と加速版 FISTA、収束率、backtracking・restart、Lasso・全変動・圧縮センシングへの応用。
第10章: ベイズ最適化
ガウス過程による代理モデル、獲得関数（EI, PI, UCB）、逐次近似最適化。
第11章: 焼きなまし法
メトロポリス基準、冷却スケジュール、大域的最適化の確率的手法。
第12章: 遺伝的アルゴリズム
選択・交叉・突然変異による進化的最適化、スキーマ定理。
第13章: 動的計画法
最適部分構造、部分問題の重複、ナップサック問題、ベルマン方程式。
第14章: 粒子群最適化と群知能
PSO の速度更新式、蟻コロニー最適化、カッコウ探索、ホタルアルゴリズム。
第15章: 多目的最適化
パレート最適性、スカラ化法、NSGA-II、MOEA/D、性能指標。
第16章: 差分進化と進化戦略
DE/rand/1/bin、CMA-ES、自然進化戦略、自然勾配。
第17章: 遺伝的プログラミングと文法進化
木構造の交叉・突然変異、STGP、文脈自由文法に基づく文法進化、節約圧。
第18章: 進化計算の共通概念
探査と知識利用、ミームアルゴリズム、ボールドウィン効果、クロスエントロピー法。
第19章: 不確実性を考慮した最適化
VaR・CVaR、ミニマックス原理、情報ギャップ決定理論、多項式カオス展開。
第20章: 多領域設計最適化（MDO）
協調最適化、SAND、IDF、MDF の各アーキテクチャ、結合変数、感度解析。
第21章: 実験計画法と空間充填
完全実施要因計画、ラテン超方格法、空間充填指標、Morris-Mitchell基準。
練習問題
上級レベルの理解を確認するための演習問題集。
概要
上級では、連続最適化の枠組みを超えて、より広範な最適化問題を扱う。
整数計画法は、変数が整数値に制約される最適化問題を扱う。連続緩和と分枝限定法を組み合わせた体系的な解法や、切除平面法による多面体的アプローチを学ぶ。
組合せ最適化では、巡回セールスマン問題やナップサック問題などの古典的問題を通じて、NP困難性の概念と、それに対処するための近似アルゴリズムやメタヒューリスティクスを学ぶ。
大規模最適化では、現代のデータサイエンスや機械学習で必要とされる、大量のデータや変数を効率的に扱う手法を学ぶ：
- 疎行列構造の活用
- 問題の分解法（Dantzig-Wolfe分解、Benders分解）
- 座標降下法と近接勾配法
分散最適化は、データが複数のノードに分散している場合の最適化手法を扱う。ADMM（交互方向乗数法）は、制約付き最適化問題を分散的に解くための強力なフレームワークである。
ロバスト最適化は、パラメータに不確実性がある場合に、最悪ケースでの性能を保証する解を求める手法である。確率的手法との違いや、計算可能な緩和について学ぶ。
変分法と最適制御は、関数空間上での最適化を扱う。オイラー・ラグランジュ方程式やポントリャーギンの最大原理は、動的システムの最適制御における基本定理である。
よくある質問
最適化上級ではどのようなトピックを扱うか
整数計画法・組合せ最適化（NP困難性と近似アルゴリズム）、大規模最適化（分解法・座標降下法・近接勾配法）、分散最適化（ADMM）、ロバスト最適化、変分法と最適制御に加え、焼きなまし法・遺伝的アルゴリズム・粒子群最適化・進化戦略などのメタヒューリスティクス、そして数値最適化の収束理論（Nesterov 加速・近接作用素）などを扱う。
組合せ最適化のNP困難性にはどう対処するか
厳密解を現実的な時間で求められない問題に対しては、分枝限定法や切除平面法で探索空間を絞り込む、性能保証のある近似アルゴリズムで近似解を得る、焼きなまし法・遺伝的アルゴリズム・粒子群最適化などのメタヒューリスティクスで実用解を探す、といった方針を組合せて用いる。
大規模最適化ではどのような手法を使うか
疎行列構造の活用、問題の分解法（Dantzig–Wolfe 分解・Benders 分解）、座標降下法、近接勾配法（ISTA/FISTA）、分散環境での ADMM（交互方向乗数法）などを用いる。1 反復あたりの計算量を抑えつつ大量の変数やデータを扱えるのが要点である。
読み物
組合せ爆発という壁読み物
「全部試せば最適解が出る」を打ち砕く組合せ爆発。NP困難とどう付き合い、緩和・分枝限定・メタヒューリスティクスで実用解にたどり着くか、最前線の思考法を肩の力を抜いて語る。
不確かな世界に賭ける読み物
現実のデータは揺らぎ、未来は読めない。きれいに解いた最適解が本番で崩れるのはなぜか。最悪に備えるロバスト最適化と、平均で攻める確率的最適化――不確実性と向き合うプロの思考法を肩の力を抜いて語る。