最適化
Mathematical Optimization
最適化とは
最適化（数理最適化）とは、与えられた制約条件の下で目的関数を最小化（または最大化）する変数の値を求める数学的手法である。工学、経済学、機械学習など幅広い分野で応用される。
図1：最適化問題の一般形式
最適化問題の分類
- 線形計画：目的関数と制約がすべて線形
- 凸最適化：目的関数が凸、実行可能領域が凸集合
- 非線形計画：目的関数または制約が非線形
- 整数計画：変数の一部または全部が整数
- 確率的最適化：不確実性を含む最適化
図2：凸関数と非凸関数
どこで使われるか
- 機械学習：損失関数の最小化、ニューラルネットワークの学習
- オペレーションズリサーチ：生産計画、輸送問題、スケジューリング
- 金融工学：ポートフォリオ最適化、リスク管理
- 制御工学：最適制御、モデル予測制御
- 信号処理：フィルタ設計、圧縮センシング
本シリーズでは、最適化理論の基礎から高度なアルゴリズムまで4段階で体系的に学ぶ。
直感的な例
例1：2次関数の最小化
$$f(x) = x^2 - 4x + 5 = (x - 2)^2 + 1$$
平方完成により、$x = 2$ で最小値 $f(2) = 1$ が直ちに求まる。 これは最も単純な制約なし最適化問題であり、微分を使えば $f'(x) = 2x - 4 = 0$ から同じ結果を得る。
例2：山登り法の直感
霧の中で山頂を目指す登山者を想像しよう。 見える範囲で最も急な上り坂を選んで進む——これが勾配降下法（符号を反転すれば最小化）の直感である。 ただし、目の前の丘が最も高い山とは限らない（局所的最適解の問題）。
例3：制約付き最適化の幾何学
予算制約 $p_1 x_1 + p_2 x_2 \le B$ の下で効用 $u(x_1, x_2)$ を最大化する消費者の問題。 等高線（無差別曲線）と制約領域の接点が最適解であり、 接点では勾配と制約の法線が平行になる——ラグランジュの未定乗数法の幾何学的意味である。
レベル別コンテンツ
入門
最適化の基礎
- 最適化問題の定式化
- 1変数関数の最適化
- 多変数関数の最適化
- 勾配と最適性条件
- ラグランジュの未定乗数法
- 凸集合と凸関数
初級
線形計画と凸最適化
- 線形計画問題
- シンプレックス法
- 双対理論
- 凸最適化の理論
- KKT条件
- 二次計画問題
中級
数値最適化アルゴリズム
- 勾配降下法
- ニュートン法・準ニュートン法
- 共役勾配法
- 内点法
- 確率的勾配降下法
- 制約付き最適化アルゴリズム
上級
発展的トピック
- 整数計画法
- 組合せ最適化
- 大規模・分散最適化
- ロバスト最適化
- 変分法と最適制御
- 半正定値計画 (SDP)
- メタヒューリスティクス
- 不確実性下の最適化
主要アルゴリズムの比較
| アルゴリズム | 収束速度 | 1反復のコスト | メモリ | 適用範囲 |
|---|---|---|---|---|
| 勾配降下法 | 線形 | $O(n)$ | $O(n)$ | 大規模・滑らかな目的関数 |
| 確率的勾配降下法 (SGD) | 準線形 | $O(n)$ | $O(n)$ | 大規模データ・機械学習 |
| 共役勾配法 | 超線形 | $O(n)$ | $O(n)$ | 大規模な2次関数・対称正定値系 |
| ニュートン法 | 2次 | $O(n^3)$ | $O(n^2)$ | 小〜中規模・2回微分可能 |
| 準ニュートン法 (BFGS) | 超線形 | $O(n^2)$ | $O(n^2)$ | 中規模・1階微分のみ |
| L-BFGS | 超線形 | $O(mn)$ | $O(mn)$ | 大規模・メモリ制約あり |
| 信頼領域法 | 2次 | $O(n^3)$ | $O(n^2)$ | 非凸問題・頑健な収束 |
| Nelder-Mead 法 | 準線形 | $O(n)$ | $O(n^2)$ | 微分不可能・低次元 |
| 内点法 | 多項式 | $O(n^3)$ | $O(n^2)$ | 線形計画・凸2次計画 |
| シンプレックス法 | （最悪指数） | $O(mn)$ | $O(mn)$ | 線形計画・実用上高速 |
| 遺伝的アルゴリズム | 確率的 | $O(Nn)$ | $O(Nn)$ | ブラックボックス・組合せ最適化 |
| 焼きなまし法 | 確率的 | $O(n)$ | $O(n)$ | 離散・連続の非凸問題 |
$n$：変数の次元、$m$：制約数またはメモリサイズ、$N$：集団サイズ。 収束速度は十分滑らかな凸問題での典型値。
主要な概念・公式
勾配の定義
$$\nabla f(x) = \left( \frac{\partial f}{\partial x_1}, \ldots, \frac{\partial f}{\partial x_n} \right)^T$$
1次の最適性条件
$$\nabla f(x^*) = 0$$
勾配降下法
$$x_{k+1} = x_k - \alpha_k \nabla f(x_k)$$
ラグランジアン
$$L(x, \lambda, \mu) = f(x) + \sum_i \lambda_i g_i(x) + \sum_j \mu_j h_j(x)$$
KKT条件
$$\nabla f(x^*) + \sum_i \lambda_i^* \nabla g_i(x^*) + \sum_j \mu_j^* \nabla h_j(x^*) = 0$$
$$\lambda_i^* g_i(x^*) = 0, \quad \lambda_i^* \geq 0$$
凸関数の定義
$$f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta) f(y)$$
（$0 \leq \theta \leq 1$）
ヘッセ行列（2次の最適性条件）
$$\nabla^2 f(x^*) = \left[\frac{\partial^2 f}{\partial x_i \partial x_j}\right] \succeq 0$$
停留点 $x^*$ が極小点であるための必要条件
強凸性
$$f(y) \geq f(x) + \nabla f(x)^T(y - x) + \frac{m}{2}\|y - x\|^2$$
（$m > 0$：強凸パラメータ。大域的最小点が一意に存在）
双対ギャップ
$$\eta = f(x) - g(\lambda, \mu) \geq 0$$
（$f$：主問題の値、$g$：双対問題の値。$\eta = 0$ で強双対性）
ニュートン法の更新
$$x_{k+1} = x_k - [\nabla^2 f(x_k)]^{-1} \nabla f(x_k)$$
双対問題
$$\max_{\lambda \geq 0, \mu} \min_{x} L(x, \lambda, \mu)$$
弱双対性は常に成立。凸問題では強双対性（$\eta = 0$）
用語集
最適化理論で頻繁に登場する専門用語をまとめた 用語集を用意している。 エピグラフ、劣勾配、バリア関数、双対ギャップ、相補性スラックネスなど 50語以上を分野別に解説している。
前提知識
- 入門：微分積分（1変数・多変数）、線形代数の基礎
- 初級：入門の内容、行列論
- 中級：初級の内容、数値解析の基礎
- 上級：中級の内容、関数解析、組合せ論