最適化

科目の概要

工場で何をどれだけ作るか（生産計画）、トラックでどの倉庫からどの店へ運ぶか（配送）、資金をどの資産にどれだけ配分するか（ポートフォリオ）、データに合うようにモデルのパラメータをどう決めるか（機械学習の学習）。見かけはまったく違うが、これらはすべて「決定変数 $x$ を制約 $x \in X$ のもとで選び、目的関数 $f(x)$ を最小（または最大）にする」という同じ枠組みで書ける。最適化（数理最適化）は、この形の問題を数学として扱い、解き、得られた答えが本当に最良であることを確かめる分野である。

この科目では次の三つの問いを軸にする。最良の選択は存在するか。ある候補が最良であることをどう確かめるか（最適性条件と、双対性による最適性の「証明書」）。最良の選択をどう計算するか（アルゴリズムと、その収束の速さ）。

三つの問いのすべてで鍵になるのが凸性である。凸な問題では、局所的に最良な点が全体でも最良になり、勾配が $0$ という 1 次の条件だけで最適性が判定できる。線形計画・最小二乗法・ロジスティック回帰・平均分散ポートフォリオはどれも凸であり、規模が大きくても信頼できる解法がある。一方、整数変数を含む問題（配送経路、スケジューリング）やニューラルネットワークの学習は凸でなく、大域的に最良な解を求めることは一般に難しい（0-1 整数計画は NP 困難な問題を含む）。おおまかには凸性が「解ける問題」と「難しい問題」を分けるので、実務では、問題を凸に定式化できるか、凸な問題で近似できるかが最も重要な判断の一つになる（最短路問題のように、凸でなくても特別な構造のおかげで効率よく解ける問題もある）。

この科目で学ぶことは次のとおりである。

定式化、最小値の存在（コンパクト性と強圧性）、制約なし問題の最適性条件
凸集合と凸関数：射影定理・分離定理、凸性の判定、強凸性と $L$ -平滑性、劣勾配
線形計画：単体法、ファルカスの補題、双対定理とシャドウプライス
制約付き最適化：KKT 条件、ラグランジュ双対、スレーター条件と強双対性
アルゴリズム：勾配法・加速法・近接勾配法、ニュートン法・準ニュートン法とその収束解析
確率的勾配降下法と、整数計画・組合せ最適化

最適化は、微分積分（01）と線形代数（02）の上に立つ応用数学であり、統計学（最尤推定・回帰）、機械学習（学習とは損失関数の最小化である）、オペレーションズ・リサーチ、制御、金融工学の共通言語である。関数を変数とする無限次元の最適化は、変分法や関数解析につながる。

前提知識

多変数の微分：01-calculus 第7章（勾配・ヘッセ行列・多変数のテイラーの定理、 $\mathbb{R}^n$ のコンパクト集合と最大値・最小値の定理）。全章で使う。
陰関数定理とラグランジュの未定乗数法：01-calculus 第8章。第4章で使う。
1 変数の凸関数（01-calculus 第4章 4.7 節）と微分積分学の基本定理（第5章）。第2章で使う。
線形代数：固有値（02-linear-algebra 第5章）、内積・直交射影・最小二乗法・実対称行列の直交対角化（第7章）、正定値性・特異値分解・レイリー商（第8章）。全章で使う。
コンパクト性：03-topology 第5章。第1章の最小値の存在で少し使うが、 $\mathbb{R}^n$ の中の話なので 01-calculus 第7章の範囲で足りる。
確率：第7章の確率的勾配降下法で、期待値と分散の基本的な性質を使う（22 統計学第1章程度。測度論は使わない）。

この科目の記法

NOTATION.md に加えて、次の記法を使う。

記号	意味
$x \in \mathbb{R}^n$	縦ベクトル（太字にしない）
$A^{\top}$	転置（02-linear-algebra の ${}^tA$ と同じもの）
$\langle x, y \rangle = x^{\top}y$ , $\lVert x \rVert$	標準内積とユークリッドノルム（特に断らなければ $\ell^2$ ）
$x \geq 0$	各成分が $0$ 以上であること
$\nabla f(x)$ , $\nabla^2 f(x)$	勾配（縦ベクトル）とヘッセ行列
$A \succeq B$ , $A \succ B$	対称行列 $A - B$ が半正定値、正定値であること
$p^{\ast}$ , $x^{\ast}$	最適値と最適解
$\operatorname{argmin}_{x \in X} f(x)$	最適解の全体
$P_C(x)$	閉凸集合 $C$ への射影
$\partial f(x)$	劣微分（劣勾配の全体）
$f^{\ast}$	共役関数（最適値 $p^{\ast}$ と区別する）
$\mathbf{1}$	すべての成分が $1$ のベクトル（定義関数 $\mathbf{1}_A$ とは添字の有無で区別する）

到達目標

学習時間の目安と進め方

全体で 60〜80 時間（1 章あたり演習を含めて 8〜12 時間）が目安である。学部 2〜4 年の講義 1〜2 科目分に相当する。
第1章と第2章が土台である。第3章（線形計画）と第4章（KKT 条件と双対性）は第2章の分離定理を、第5章（勾配法）と第6章（ニュートン法）は第2章の強凸性と $L$ -平滑性を使う。第7章の前半は第5章を、後半は第1章と第3章を使う。
目的に応じて読む順を変えてよい。機械学習のためなら「第1章 → 第2章 → 第5章 → 第4章 → 第7章 → 第6章」、生産・物流などのオペレーションズ・リサーチのためなら「第1章 → 第2章（2.1〜2.5 節）→ 第3章 → 第4章 → 第7章」が一つの目安である。
理論と計算を往復すること。各章の小さな数値例は、NumPy で実装して確かめられる。収束率や条件数の影響のような理論の予言を、実際の反復の様子と比べてみるとよい。
「得られた答えが本当に最良か」を確かめる習慣をつけること。最適性条件・双対問題による証明書（第1章例 1.2、第3章・第4章）は、そのための道具である。
仮定を外すと何が起こるかを反例で確かめること。本科目の主な反例：最適値が達成されない $e^x$ や完全分離のロジスティック回帰（第1章）、ヘッセ行列が半正定値でも局所最小でない $x^3$ （第1章）、コンパクト性がないと強分離できない 2 つの閉凸集合（第2章）、定義域が開でないと 2 次条件が成り立たない例（第2章）、劣勾配の逆向きに進んでも値が下がらない例（第2章）。

参考文献

日本語

福島雅夫『非線形最適化の基礎』（朝倉書店）— 非線形最適化の理論（凸解析、最適性条件、双対性）と基本的なアルゴリズムを、証明つきで体系的に述べた教科書。第1・2・4章の参照先。
久野誉人・繁野麻衣子・後藤順哉『数理最適化』（オーム社）— 線形計画・非線形計画・組合せ最適化を一冊で学べる教科書。科目全体の副読本に向く。
金森敬文・鈴木大慈・竹内一郎・佐藤一誠『機械学習のための連続最適化』（講談社）— 機械学習で使われる連続最適化（凸解析、勾配法、近接勾配法、確率的最適化など）を扱う。第2・5・7章の先を学ぶために。

英語

S. Boyd, L. Vandenberghe, Convex Optimization (Cambridge University Press) — 凸集合・凸関数・双対性の理論から、近似・統計的推定・幾何の応用、ニュートン法・内点法のアルゴリズムまでを扱う凸最適化の標準的な教科書。第2・4・6章の主な参照先。
J. Nocedal, S. J. Wright, Numerical Optimization (Springer) — 直線探索・信頼領域法・準ニュートン法・非線形最小二乗・制約付き最適化のアルゴリズムを、実用上の工夫を含めて詳しく扱う。第5・6章の参照先。
Y. Nesterov, Lectures on Convex Optimization (Springer) — $L$ -平滑性・強凸性のもとでの勾配法の収束率、加速法、計算量の下界などを厳密に扱う。第2章 2.7 節と第5章の参照先。
D. P. Bertsekas, Nonlinear Programming (Athena Scientific) — 最適性条件・ラグランジュ乗数・双対性・アルゴリズムを厳密に論じた教科書。
V. Chvátal, Linear Programming (W. H. Freeman) — 単体法と双対定理を中心に線形計画を丁寧に解説した古典。第3章の参照先。
A. Schrijver, Theory of Linear and Integer Programming (Wiley) — 多面体・線形計画・整数計画の理論を網羅した専門書。
B. Korte, J. Vygen, Combinatorial Optimization: Theory and Algorithms (Springer) — 最短路・最小全域木・ネットワークフロー・マッチング・NP 完全性などを扱う組合せ最適化の標準的な教科書。第7章の参照先。

次に学ぶもの

24 機械学習の数理 — サポートベクターマシンの双対問題（第4章）、正則化と勾配法・確率的勾配法（第5章・第7章）が直接使われる。
22 統計学 — 最尤推定・線形回帰・一般化線形モデルは最適化問題であり、一般化線形モデルの計算に使う IRLS（反復重み付き最小二乗法）は、正準リンクの場合はニュートン法（第6章）そのものである（22-statistics 第6章定理 6.7）。
10 関数解析 — 無限次元の最適化の基礎。ヒルベルト空間の最近点定理（第2章定理 2.6）とハーン–バナッハの定理の幾何形（第4章）は、本科目第2章の射影定理と分離定理の無限次元版である。
18 偏微分方程式論第6章 — 変分法の直接法。強圧性と下半連続性による最小点の存在（本科目第1章）の無限次元版である。
11 確率論第5章 — 確率的勾配降下法のほとんど確実な収束などの精密な解析には、マルチンゲールの理論が使われる。