無制約最適化 — 勾配法と準ニュートン法
概要
無制約最適化は $\min_{x \in \mathbb{R}^n} f(x)$ を扱う問題で、機械学習・信号処理・物理シミュレーション・統計推定の中核に位置する。
sangi は 1 次元から大規模 ($n \gtrsim 10^4$) までスケールするアルゴリズム群を optimization_1d.hpp / optimization_nd.hpp に揃えており、本記事ではそれぞれの理論的背景と実装上の選択を解説する。
制約付き最適化と非線形最小二乗、線形・凸計画は Optimization-constrained-lp、 微分不要 / メタヒューリスティクスは Optimization-derivative-free を参照。
1 次元最小化 (Brent と黄金分割)
区間 $[a, b]$ 上で $f: \mathbb{R} \to \mathbb{R}$ の最小化は、微分不要の基本問題である。
黄金分割法
区間内の 2 点 $x_1 < x_2$ を比較し、悪い方の端点を捨てて区間を黄金比 $\varphi = (1 + \sqrt{5})/2$ で縮小する。 収束は線形 (区間長が毎回 $1/\varphi \approx 0.618$ 倍)、関数評価 1 回あたり情報量は最大となる。 単峰性 (unimodal) を前提とし、$O(\log(1/\varepsilon))$ 回で収束する。
放物線補間
3 点 $(x_1, f_1), (x_2, f_2), (x_3, f_3)$ を通る放物線の頂点を計算し、その頂点を次の試行点とする。 $f$ が滑らかなら超線形収束 (収束次数 $\approx 1.324$) を達成するが、補間が破綻 (頂点が区間外、3 点が共線) すると失敗する。
Brent 法
Brent (1973) は放物線補間と黄金分割をハイブリッドで組み合わせた。
- 補間が次の条件をすべて満たすときは放物線補間を採用: 頂点が区間内、ステップが直前の区間幅の半分以下、補間が単調収束。
- 条件不成立なら黄金分割で 1 ステップ進む。
滑らかな関数では Brent 法が黄金分割より 5–10 倍少ない関数評価で収束し、関数が非滑らかでも最悪線形収束を保証する。
sangi の brent_minimize が標準的選択である。
ライン探索 (Armijo, Wolfe)
多次元最適化では現在の点 $x_k$ から下降方向 $p_k$ に沿って 1 次元最小化を行う: $\alpha_k = \arg\min_{\alpha > 0} \phi(\alpha)$, $\phi(\alpha) = f(x_k + \alpha p_k)$。 厳密な最小化はコスト高なので、十分に「良い」 $\alpha$ で打ち切る不完全ライン探索が標準となる。
Armijo 条件 (十分減少)
$$f(x_k + \alpha p_k) \leq f(x_k) + c_1 \alpha \, \nabla f(x_k)^T p_k, \qquad c_1 \in (0, 1)$$
関数値が線形モデルから一定割合以上減少することを要求する。典型値 $c_1 = 10^{-4}$。 バックトラッキングは $\alpha$ を初期値から $\rho \in (0, 1)$ で縮小しつつ Armijo を満たす最初の $\alpha$ を採用する素朴な実装。
Wolfe 条件
Armijo に加え、曲率条件を要求する:
$$\nabla f(x_k + \alpha p_k)^T p_k \geq c_2 \, \nabla f(x_k)^T p_k, \qquad c_2 \in (c_1, 1)$$
典型値 $c_2 = 0.9$ (Newton/BFGS), $c_2 = 0.1$ (CG)。 ステップが小さすぎない (曲率が十分減少した) ことを保証する。BFGS の正定性証明には Wolfe (より厳密には強 Wolfe) が必要。
sangi は LineSearchParams で Armijo バックトラッキングを基本としており、勾配ベース手法のステップ選択に共通利用される。
関連記事: ライン探索
最急降下法
方向 $p_k = -\nabla f(x_k)$ で進む単純な手法。 $x_{k+1} = x_k - \alpha_k \nabla f(x_k)$、ステップ $\alpha_k$ はライン探索で決定する。
収束は線形で、条件数 $\kappa$ の二次形式に対して収束速度 $\bigl(\frac{\kappa - 1}{\kappa + 1}\bigr)^2$。 $\kappa$ が大きいと「ジグザグ」が発生し非常に遅い。深層学習で言う SGD/Momentum とは異なり、本来の最急降下はバッチ全勾配を使う決定論的手法である。
sangi の steepest_descent はベースラインとして提供される。実問題では BFGS / L-BFGS / CG のいずれかを使うべきである。
関連記事: 最急降下法
共役勾配法 (FR, PR+)
線形 CG (Hestenes-Stiefel 1952) は対称正定値系 $Ax = b$ を $n$ ステップ以内で解くアルゴリズム。 この発想を非線形最小化に拡張したのが Fletcher-Reeves (1964) と Polak-Ribière (1969) である。
探索方向は前回の方向との共役性を保つように更新する:
$$p_{k+1} = -g_{k+1} + \beta_{k+1} \, p_k, \qquad g_k = \nabla f(x_k)$$
| 変種 | $\beta_{k+1}$ |
|---|---|
| Fletcher-Reeves | $\beta_{k+1}^{FR} = \dfrac{g_{k+1}^T g_{k+1}}{g_k^T g_k}$ |
| Polak-Ribière | $\beta_{k+1}^{PR} = \dfrac{g_{k+1}^T (g_{k+1} - g_k)}{g_k^T g_k}$ |
| Polak-Ribière+ | $\beta_{k+1}^{PR+} = \max(0, \beta_{k+1}^{PR})$ |
PR+ は実用上 FR より速いことが多いが、PR+ が常に下降方向であることを保証するために強 Wolfe 条件のライン探索が必要となる。
sangi の conjugateGradientMinimize は PR+ をデフォルトとし、$n$ ステップごとに $p \leftarrow -g$ で自動リスタートする。
$O(n)$ メモリのみで大規模問題に適用可能だが、悪条件問題では L-BFGS に劣る。
Newton 法と修正 Newton
2 次のテイラー展開を陽に最小化する手法:
$$f(x_k + p) \approx f(x_k) + g_k^T p + \tfrac{1}{2} p^T H_k p \;\Longrightarrow\; p_k^{\text{Newton}} = -H_k^{-1} g_k$$
$H_k = \nabla^2 f(x_k)$ がヘッセ行列。$H_k$ が正定値 (SPD) ならば $p_k^{\text{Newton}}$ は下降方向であり、収束は 2 次 (収束次数 2)。
Hessian が SPD でない場合
非凸関数や鞍点近傍では $H_k$ が不定または特異となり、$p_k^{\text{Newton}}$ が下降方向にならない。対策:
- 修正 Cholesky (Gill-Murray): 分解中に対角を増やして SPD 化。
- Levenberg-Marquardt: $(H + \lambda I) p = -g$ と damping を加える。
- 信頼領域: 二次モデルを信頼半径内でのみ信用する (後述)。
- Truncated Newton (Newton-CG): $H p = -g$ を CG で近似的に解き、負曲率検出で停止。
Newton-CG
sangi の newton_cg_minimize は Newton 方程式 $H p = -g$ を内部 CG で近似的に解く Truncated Newton。
ヘッセ行列を陽に保持せず、ユーザ提供の Hessian-vector product $H(x) v$ のみを使う。
$n$ が大きく Hessian が疎・構造化されているとき有効。
関連記事: Newton 法
BFGS と SR1
準ニュートン法は Hessian を陽に計算せず、勾配差分 $y_k = g_{k+1} - g_k$ とステップ $s_k = x_{k+1} - x_k$ から擬似 Hessian (またはその逆行列) を逐次更新する。
BFGS 公式 (Broyden-Fletcher-Goldfarb-Shanno, 1970)
逆 Hessian $B_k \approx H_k^{-1}$ を rank-2 更新:
$$B_{k+1} = \Bigl(I - \frac{s_k y_k^T}{y_k^T s_k}\Bigr) B_k \Bigl(I - \frac{y_k s_k^T}{y_k^T s_k}\Bigr) + \frac{s_k s_k^T}{y_k^T s_k}$$
性質:
- $B_0$ が SPD かつ Wolfe 条件下で $B_{k+1}$ も SPD (正定性保存)。
- 収束は超線形 (Powell 1976)。
- $O(n^2)$ メモリと $O(n^2)$ 更新コスト。
中規模問題 (~数百次元) の事実上の標準。sangi の bfgs_minimize がこれに該当する。
SR1 (Symmetric Rank-1)
$B_{k+1} = B_k + \frac{(y_k - B_k s_k)(y_k - B_k s_k)^T}{(y_k - B_k s_k)^T s_k}$ の rank-1 更新。 正定性は保証されないが、非凸問題で真の Hessian により近い近似を構築できることがある。信頼領域法と組み合わせて使う。
関連記事: 準ニュートン法
L-BFGS — 限定メモリ
Nocedal (1980) による BFGS の $O(mn)$ メモリ版。 過去 $m$ ステップの $(s_i, y_i)$ ペアのみを保持し、$B_0$ (典型 $\gamma_k I$) から二重ループ再帰で $B_k g_k$ を計算する。
two-loop recursion
q = g_k
for i = k-1 .. k-m:
α_i = (s_i^T q) / (y_i^T s_i)
q -= α_i * y_i
r = γ_k * q # γ_k = (s_{k-1}^T y_{k-1}) / (y_{k-1}^T y_{k-1})
for i = k-m .. k-1:
β = (y_i^T r) / (y_i^T s_i)
r += (α_i - β) * s_i
return r # = -B_k g_k$m$ は典型 $5 \leq m \leq 20$。 $O(mn)$ メモリ・$O(mn)$ 計算で 1 反復が済むため、$n = 10^6$ クラスの問題でも扱える。 大規模機械学習・物理シミュレーション・トモグラフィ等で広く使われる。
sangi の lbfgsMinimize はこの実装で、memory_size (デフォルト 10) で $m$ を設定できる。
信頼領域法 (LM, dogleg, Steihaug-CG)
ライン探索が「方向を決めてから距離を決める」のに対し、信頼領域法は「距離 (半径) を決めてからその中で最良点を探す」。 各反復で次のサブ問題を解く:
$$\min_{p} \;m_k(p) = f_k + g_k^T p + \tfrac{1}{2} p^T B_k p \quad \text{subject to} \quad \|p\| \leq \Delta_k$$
近似モデル $m_k$ と真の関数 $f$ の比 $\rho_k = \dfrac{f(x_k) - f(x_k + p_k)}{m_k(0) - m_k(p_k)}$ で信頼半径 $\Delta_k$ を更新する:
- $\rho_k > 0.75$ なら $\Delta_{k+1} \leftarrow 2 \Delta_k$ (拡大)
- $\rho_k < 0.25$ なら $\Delta_{k+1} \leftarrow \Delta_k / 4$ (縮小)
- $\rho_k > 0.1$ なら $x_{k+1} \leftarrow x_k + p_k$ (採用)、それ以外は拒否
サブ問題の近似解法
- Cauchy point: 最急降下方向で信頼半径まで進む点。常に解けるが収束が遅い。
- dogleg: Cauchy point と Newton step を折れ線で繋ぎ、信頼境界との交点を取る。Powell (1970)。$B_k$ が SPD であることが前提。
- Steihaug-CG: $B_k p = -g_k$ を CG で解き、信頼境界に当たるか負曲率を検出したら停止。$B_k$ が SPD でなくても動く。大規模・疎 Hessian 向け。
- Levenberg-Marquardt: $(B_k + \lambda I) p = -g$ で damping 付き、非線形最小二乗で標準。詳細は Optimization-constrained-lp。
信頼領域法は不定 Hessian でも安定動作し、非凸最適化や悪条件問題で好まれる。
sangi は gaussNewtonMinimize と leastSquaresFit で Levenberg-Marquardt 流の信頼領域を採用している。
関連記事: 信頼領域法
アルゴリズム選択指針
| 状況 | 推奨 |
|---|---|
| 1 次元、滑らか | brent_minimize |
| 1 次元、非滑らか | golden_section_search |
| $n \leq 100$、勾配あり | bfgs_minimize |
| $n \leq 10^3$、Hessian-vector あり | newton_cg_minimize |
| $n \geq 10^3$、勾配のみ、悪条件 | lbfgsMinimize |
| $n \geq 10^3$、メモリ厳しい | conjugateGradientMinimize |
| 非線形最小二乗 $\sum r_i(x)^2$ | gaussNewtonMinimize / leastSquaresFit |
| 勾配が高コスト・ノイジー | nelderMeadMinimize 等 (derivative-free) |
参考文献
- Nocedal, J. and Wright, S. J. (2006). Numerical Optimization, 2nd ed. Springer.
- Fletcher, R. (1987). Practical Methods of Optimization, 2nd ed. Wiley.
- Brent, R. P. (1973). Algorithms for Minimization without Derivatives. Prentice-Hall.
- Liu, D. C. and Nocedal, J. (1989). "On the limited memory BFGS method for large scale optimization". Math. Programming, 45, 503–528.
- Steihaug, T. (1983). "The Conjugate Gradient Method and Trust Regions in Large Scale Optimization". SIAM J. Numer. Anal., 20, 626–637.