最適化
Mathematical Optimization
最適化とは
最適化（数理最適化）とは、与えられた制約条件の下で目的関数を最小化（または最大化）する変数の値を求める数学的手法である。工学、経済学、機械学習など幅広い分野で応用される。
図1：最適化問題の一般形式
$$\begin{array}{ll}
\textbf{最小化} & f(\mathbf{x}) \\[6pt]
\textbf{制約条件} & g_i(\mathbf{x}) \le 0, \quad i = 1, \dots, m \\
& h_j(\mathbf{x}) = 0, \quad j = 1, \dots, p \\
& \mathbf{x} \in X
\end{array}$$
最適化問題の分類
- 線形計画：目的関数と制約がすべて線形
- 凸最適化：目的関数が凸、実行可能領域が凸集合
- 非線形計画：目的関数または制約が非線形
- 整数計画：変数の一部または全部が整数
- 確率的最適化：不確実性を含む最適化
図2：凸関数と非凸関数
どこで使われるか
- 機械学習：損失関数の最小化、ニューラルネットワークの学習
- オペレーションズリサーチ：生産計画、輸送問題、スケジューリング
- 金融工学：ポートフォリオ最適化、リスク管理
- 制御工学：最適制御、モデル予測制御
- 信号処理：フィルタ設計、圧縮センシング
本シリーズでは、最適化理論の基礎から高度なアルゴリズムまで4段階で体系的に学ぶ。
レベル別コンテンツ
主要な概念・公式
勾配の定義
$$\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$）
前提知識
- 入門：微分積分（1変数・多変数）、線形代数の基礎
- 初級：入門の内容、行列論
- 中級：初級の内容、数値解析の基礎
- 上級：中級の内容、関数解析、組合せ論