最適化用語集

Glossary of Mathematical Optimization

最適化理論で頻繁に登場する用語を分野別に整理した。各用語には定義と、関連するページへのリンクを付記している。

基礎概念

目的関数（objective function）
最小化（または最大化）したい関数 $f(\mathbf{x})$。コスト関数、損失関数とも呼ばれる。
実行可能領域（feasible region）
すべての制約条件を満たす点の集合。実行可能集合とも呼ばれる。
大域的最適解（global optimum）
実行可能領域全体で目的関数を最小化する点。
局所的最適解（local optimum）
ある近傍内で目的関数を最小化する点。大域的最適解とは限らない。
勾配（gradient）
多変数関数の各変数に対する偏微分を並べたベクトル：$\nabla f(x) = \left(\frac{\partial f}{\partial x_1}, \ldots, \frac{\partial f}{\partial x_n}\right)^T$。 関数が最も急に増加する方向を示す。→ 入門：勾配
ヘッセ行列（Hessian matrix）
2階偏微分を並べた対称行列：$\nabla^2 f(x) = \left[\frac{\partial^2 f}{\partial x_i \partial x_j}\right]$。 曲率情報を持ち、2次の最適性条件やニュートン法で使用される。→ 中級：ニュートン法
ヤコビ行列（Jacobian matrix）
ベクトル値関数 $\mathbf{F}: \mathbb{R}^n \to \mathbb{R}^m$ の1階偏微分を並べた $m \times n$ 行列。勾配はスカラー関数のヤコビアンの転置である。
停留点（stationary point）
$\nabla f(x^*) = 0$ を満たす点。極小点、極大点、鞍点のいずれかである。
鞍点（saddle point）
ある方向では極小、別の方向では極大となる停留点。ヘッセ行列が不定（正と負の固有値を持つ）の場合に対応する。

凸解析

凸集合（convex set）
任意の2点を結ぶ線分が集合に含まれる集合：$\theta x + (1-\theta)y \in C$ （$0 \le \theta \le 1$）。→ 入門：凸集合と凸関数
凸関数（convex function）
$f(\theta x + (1-\theta)y) \le \theta f(x) + (1-\theta)f(y)$ を満たす関数。局所的最適解が大域的最適解と一致する。
強凸関数（strongly convex function）
パラメータ $m > 0$ に対して $f(y) \ge f(x) + \nabla f(x)^T(y-x) + \frac{m}{2}\|y-x\|^2$ を満たす関数。大域的最小点が一意に存在し、勾配降下法の収束速度が保証される。
凸錐（convex cone）
$x \in C$ ならば $\alpha x \in C$（$\alpha \ge 0$）かつ凸である集合。半正定値行列の集合 $\mathbb{S}^n_+$ が代表例。
エピグラフ（epigraph）
関数 $f$ のグラフの上側の領域：$\text{epi}\,f = \{(x, t) \mid f(x) \le t\}$。$f$ が凸 $\Leftrightarrow$ $\text{epi}\,f$ が凸集合。凸解析の基本的な道具である。
劣勾配（subgradient）
非滑らかな凸関数 $f$ に対して、$f(y) \ge f(x) + g^T(y-x)$（$\forall y$）を満たすベクトル $g$。$f$ が微分可能な点では勾配と一致する。劣微分 $\partial f(x)$ は全劣勾配の集合。
共役関数（conjugate function / Fenchel conjugate）
$f^*(y) = \sup_x \{y^T x - f(x)\}$。凸関数の双対的表現であり、双対理論の基礎となる。
近接作用素（proximal operator）
$\text{prox}_f(x) = \arg\min_u \left\{f(u) + \frac{1}{2}\|u - x\|^2\right\}$。非滑らかな正則化項を持つ最適化問題で使用される（ISTA、ADMM 等）。
リプシッツ連続（Lipschitz continuity）
$\|f(x) - f(y)\| \le L\|x - y\|$ を満たす定数 $L > 0$ が存在するとき、$f$ は $L$-リプシッツ連続であるという。勾配のリプシッツ連続性は収束速度解析で重要。

最適性条件

1次の必要条件（first-order necessary condition）
制約なし問題で $x^*$ が局所的最小点ならば $\nabla f(x^*) = 0$。
2次の十分条件（second-order sufficient condition）
$\nabla f(x^*) = 0$ かつ $\nabla^2 f(x^*) \succ 0$（正定値）ならば $x^*$ は狭義の局所的最小点。
KKT 条件（Karush-Kuhn-Tucker conditions）
制約付き最適化の1次の必要条件。以下の4条件から構成される：
  1. 停留性：$\nabla f + \sum_i \lambda_i \nabla g_i + \sum_j \mu_j \nabla h_j = 0$
  2. 主実行可能性：$g_i(x) \le 0,\; h_j(x) = 0$
  3. 双対実行可能性：$\lambda_i \ge 0$
  4. 相補性スラックネス：$\lambda_i g_i(x) = 0$
凸問題では十分条件にもなる。→ 初級：KKT条件
制約想定（constraint qualification）
KKT条件が必要条件として成立するための制約に対する正則性条件。 線形独立制約想定（LICQ）、Slater 条件などがある。
相補性スラックネス（complementary slackness）
$\lambda_i g_i(x^*) = 0$：最適解において、不等式制約が等号で成立しない（$g_i < 0$）ならばその乗数は $\lambda_i = 0$。逆に $\lambda_i > 0$ なら制約は等号で成立（有効制約）。

双対理論

ラグランジアン（Lagrangian）
$L(x, \lambda, \mu) = f(x) + \sum_i \lambda_i g_i(x) + \sum_j \mu_j h_j(x)$。制約を目的関数に組み込む道具。→ 入門：ラグランジュ法
ラグランジュ乗数（Lagrange multiplier）
制約に対応する双対変数 $\lambda_i, \mu_j$。制約を少し緩めたときの目的関数値の変化率（影の価格）を表す。
双対問題（dual problem）
$\max_{\lambda \ge 0,\, \mu} \min_x L(x, \lambda, \mu)$。主問題の下界を与える。→ 初級：双対理論
弱双対性（weak duality）
双対問題の最適値 $d^*$ は主問題の最適値 $p^*$ 以下：$d^* \le p^*$。常に成立する。
強双対性（strong duality）
$d^* = p^*$（双対ギャップがゼロ）。凸問題で Slater 条件を満たす場合に成立する。
双対ギャップ（duality gap）
$\eta = p^* - d^* \ge 0$。主問題の最適値と双対問題の最適値の差。収束判定や停止基準に使用される。強双対性のもとでは $\eta = 0$。
Slater 条件（Slater's condition）
凸問題において、すべての不等式制約を狭義に満たす内点が存在するとき成立する。強双対性を保証する十分条件として最も広く使われる。
Fenchel 双対（Fenchel duality）
共役関数を用いた双対変換。$\min_x \{f(x) + g(Ax)\}$ の双対は $\max_y \{-f^*(-A^Ty) - g^*(y)\}$。ADMM 等の分離型アルゴリズムの理論的基盤。

アルゴリズム

勾配降下法（gradient descent）
$x_{k+1} = x_k - \alpha_k \nabla f(x_k)$。最も基本的な反復最適化手法。→ 中級：勾配降下法
確率的勾配降下法（SGD: stochastic gradient descent）
ミニバッチからの勾配推定値を使用。大規模データに適する。→ 中級：SGD
ニュートン法（Newton's method）
$x_{k+1} = x_k - [\nabla^2 f(x_k)]^{-1}\nabla f(x_k)$。2次収束するが、ヘッセ行列の計算・逆行列が必要。→ 中級：ニュートン法
準ニュートン法（quasi-Newton method）
ヘッセ行列を直接計算せず、勾配情報から近似する手法。BFGS、L-BFGS が代表的。超線形収束する。
共役勾配法（conjugate gradient method）
前の探索方向と共役な方向を順に選ぶ手法。$n$ 次元の2次関数を最大 $n$ ステップで厳密に解ける。→ 中級：共役勾配法
信頼領域法（trust region method）
現在の点の近傍（信頼領域）で2次モデルを最小化する手法。直線探索法より頑健な収束性を持つ。→ 中級：信頼領域法
Nelder-Mead 法（Nelder-Mead method）
微分を使わないシンプレックスベースの直接探索法。低次元の非滑らか問題に有効。→ 中級：Nelder-Mead
直接探索法（direct search method）
勾配を使わずに関数値のみで最適化する手法の総称。パターンサーチ、MADS 等。→ 中級：直接探索法
内点法（interior point method）
実行可能領域の内部を通る経路をたどる手法。バリア関数を用い、線形計画を多項式時間で解ける。→ 中級：内点法
ステップサイズ（step size / learning rate）
反復法における更新量の大きさ $\alpha_k$。大きすぎると発散、小さすぎると収束が遅い。Armijo 条件や Wolfe 条件で適切な値を選ぶ。
線探索（line search）
探索方向 $d_k$ が定まった後、$\alpha_k = \arg\min_\alpha f(x_k + \alpha d_k)$ を近似的に求める手順。
収束速度（convergence rate）
反復法が最適解に近づく速さ。線形（$\|x_{k+1} - x^*\| \le c\|x_k - x^*\|$）、超線形、2次（$\|x_{k+1} - x^*\| \le c\|x_k - x^*\|^2$）に分類される。

制約付き最適化

有効制約（active constraint）
最適解 $x^*$ において等号で成立する不等式制約：$g_i(x^*) = 0$。有効制約の集合を active set と呼ぶ。
バリア関数（barrier function）
実行可能領域の境界で無限大になる関数。対数バリア $-\sum_i \log(-g_i(x))$ が代表的。内点法で使用される。
ペナルティ法（penalty method）
制約違反にペナルティ $\rho\sum_i \max(0, g_i(x))^2$ を課す手法。$\rho \to \infty$ で制約付き問題の解に収束する。
拡張ラグランジアン法（augmented Lagrangian method）
ラグランジアンにペナルティ項を加えた $L_\rho(x,\lambda) = L(x,\lambda) + \frac{\rho}{2}\sum_i g_i(x)^2$。ペナルティ法より数値的に安定。
ADMM（交互方向乗数法）
拡張ラグランジアン法の変種で、問題を分離可能な部分問題に分割して交互に解く。大規模な分散最適化で広く使用される。
シンプレックス法（simplex method）
線形計画問題を多面体の頂点を渡り歩いて解くアルゴリズム。最悪計算量は指数的だが、実用上は非常に高速。→ 初級：シンプレックス法
スラック変数（slack variable）
不等式制約 $g_i(x) \le 0$ を等式制約 $g_i(x) + s_i = 0,\; s_i \ge 0$ に変換する非負変数。→ 初級：スラック変数

特殊な問題クラス

線形計画問題（LP: linear programming）
目的関数・制約がすべて線形の最適化問題。→ 初級：線形計画
二次計画問題（QP: quadratic programming）
目的関数が2次、制約が線形の問題。→ 初級：二次計画
半正定値計画（SDP: semidefinite programming）
変数が半正定値行列 $X \succeq 0$ である凸最適化問題。組合せ最適化の緩和、制御理論、量子情報などで使用される。
2次錐計画（SOCP: second-order cone programming）
$\|Ax + b\| \le c^Tx + d$ 型の制約を持つ凸問題。LP と SDP の中間に位置する。ロバスト最適化やポートフォリオ最適化で使用。
DC 計画（DC programming）
目的関数が2つの凸関数の差 $f(x) = g(x) - h(x)$ として表される問題。DCA（DC Algorithm）で局所解を求める。非凸問題の広い部分クラスを含む。
整数計画問題（IP: integer programming）
変数の一部または全部が整数に制約される問題。一般に NP 困難。→ 上級：整数計画
組合せ最適化（combinatorial optimization）
離散的な候補の集合から最適解を求める問題。巡回セールスマン問題（TSP）、ナップサック問題が代表例。→ 上級：組合せ最適化
多目的最適化（multi-objective optimization）
複数の目的関数を同時に最適化する問題。パレート最適解の集合を求める。→ 上級：多目的最適化
ロバスト最適化（robust optimization）
パラメータの不確実性に対して最悪ケースでの性能を保証する最適化。→ 上級：ロバスト最適化
確率的最適化（stochastic optimization）
目的関数や制約に確率変数を含む最適化問題。期待値最適化、確率的制約などがある。→ 上級：不確実性下の最適化

メタヒューリスティクス

遺伝的アルゴリズム（GA: genetic algorithm）
生物の進化を模倣した最適化手法。選択・交叉・突然変異を繰り返して解を改善する。→ 上級：遺伝的アルゴリズム
焼きなまし法（SA: simulated annealing）
金属の焼きなまし過程を模倣。温度を下げながら確率的に解を探索し、局所解からの脱出を図る。→ 上級：焼きなまし法
粒子群最適化（PSO: particle swarm optimization）
鳥の群れの行動を模倣。各粒子が個体の最良解と群全体の最良解に引きつけられながら探索する。→ 上級：群知能
差分進化法（DE: differential evolution）
個体間の差分ベクトルを利用して新しい候補解を生成する進化的手法。パラメータ調整が容易で実用性が高い。→ 上級：進化戦略
CMA-ES（共分散行列適応進化戦略）
多変量正規分布のパラメータ（平均と共分散行列）を適応的に更新する進化戦略。ブラックボックス最適化の標準手法。→ 上級：進化戦略
ベイズ最適化（Bayesian optimization）
ガウス過程で目的関数を近似し、獲得関数で次の評価点を選ぶ手法。評価コストの高い関数の最適化に有効。→ 上級：ベイズ最適化
タブー探索（tabu search）
最近訪問した解をタブーリストに記録し、再訪を禁止しながら局所探索を行う手法。組合せ最適化で広く使用される。

参考資料