勾配法アルゴリズム

概要

勾配法は最適化問題を解くための最も基本的で重要なアルゴリズム群です。関数の勾配情報を利用して最適解に向かって反復的に改善していく手法で、機械学習、制御工学、信号処理など幅広い分野で応用されています。

勾配降下法（Gradient Descent）

最適化問題の定式化

勾配降下法は、関数 $f(x)$ の最小値を求めるための最適化アルゴリズムです：

$$\min_{x \in \mathbb{R}^n} f(x)$$

ここで、関数 $f(x)$ は通常、微分可能な連続関数と仮定します。

テイラー展開による勾配の解釈

関数 $f(x)$ をある点 $x_k$ の周りで1次のテイラー展開すると：

$$f(x_k + d) \approx f(x_k) + \nabla f(x_k)^T d$$

ここで：

• $\nabla f(x_k)$: 点 $x_k$ における勾配ベクトル
• $d$: 探索方向ベクトル

勾配の幾何学的意味

• $\nabla f(x_k) = 0$ ならば、$x_k$ は極値点の候補
• $\nabla f(x_k) \neq 0$ ならば、関数を最小化する方向に進む必要

関数を減少させるため、負の勾配方向に向かって更新：

$$d_k = -\nabla f(x_k)$$

勾配の方向性

勾配 $\nabla f(x_k)$ は関数値が最も急激に増加する方向を示します。したがって、最小化のためには反対の方向（負の勾配方向）に進むのが効果的です。

勾配降下法の更新式

現在の点 $x_k$ から負の勾配方向に移動し、学習率（ステップサイズ） $\alpha_k > 0$ を導入すると：

$$x_{k+1} = x_k - \alpha_k \nabla f(x_k)$$

これが勾配降下法の基本的な更新則です。

学習率の選択

学習率 $\alpha_k$ は最適化の収束速度と安定性に大きく影響します。

固定ステップサイズ（Fixed Step Size）

一定の値 $\alpha_k = \alpha$ を使用：

利点:

• 実装が簡単
• 計算コストが低い

課題:

• 大きすぎると発散の可能性
• 小さすぎると収束が非常に遅い

適応的ステップサイズ（Line Search）

各ステップで $\alpha_k$ を調整：

$$\alpha_k = \arg\min_{\alpha > 0} f(x_k - \alpha \nabla f(x_k))$$

代表的な手法:

• Armijo条件（十分減少条件）
• バックトラッキング
• 黄金分割法

収束性理論

凸関数の場合

$f(x)$ が凸関数で、勾配がリプシッツ連続の場合：

$$\|\nabla f(x) - \nabla f(y)\| \leq L\|x - y\|$$

適切な学習率 $\alpha_k \leq \frac{2}{L}$ を選ぶと収束が保証され、収束率は $O(1/k)$

強凸関数の場合

$f(x)$ が強凸関数（$\nabla^2 f(x) \succeq \mu I$）の場合、指数的収束 $O(e^{-k})$ が得られます。

非凸問題

一般の非凸問題では、勾配降下法は局所最適解にしか収束しません。大域最適解を求めるには特別な手法が必要です。

最急降下法（Steepest Descent Method）

基本概念

最急降下法は、目的関数 $f(x)$ を最も急激に減少させる方向（勾配方向）に進むことで、局所最小値を求める反復最適化アルゴリズムです。

探索方向の定義

点 $x_k$ における探索方向 $d_k$ を次のように定めます：

$$d_k = -\nabla f(x_k)$$

減少性の確認

$\nabla f(x_k) \neq 0$ のとき、探索方向と勾配方向の内積：

$$\nabla f(x_k)^T d_k = -\|\nabla f(x_k)\|^2 < 0$$

これは $d_k$ が確実に $f$ の値を減少させる方向であることを示します。

最急降下法のアルゴリズム

Algorithm: Steepest Descent Method
1. 初期点 x₀ ∈ ℝⁿ を選択
2. for k = 0, 1, 2, ... do:
   3. 停止条件の確認: ‖∇f(xₖ)‖ ≤ ε ならば停止
   4. 探索方向を計算: dₖ = -∇f(xₖ)
   5. ステップサイズを決定: αₖ = argmin{α>0} f(xₖ + α dₖ)
   6. 探索点を更新: xₖ₊₁ = xₖ + αₖ dₖ
   7. k := k + 1

直線探索（Line Search）

ステップサイズ $\alpha_k$ を求める1次元最適化問題：

$$\min_{\alpha > 0} \phi(\alpha) = f(x_k + \alpha d_k)$$

完全直線探索（Exact Line Search）

解析的または数値的に正確な最適ステップサイズを求める

不完全直線探索（Inexact Line Search）

計算効率を重視し、適当な改善を示すステップサイズを求める

Armijo条件:

$$f(x_k + \alpha d_k) \leq f(x_k) + c_1 \alpha \nabla f(x_k)^T d_k$$

ここで $0 < c_1 < 1$（通常 $c_1 = 10^{-4}$）

実装例

Python実装

import numpy as np
import matplotlib.pyplot as plt

def steepest_descent(f, grad_f, x0, alpha=0.01, max_iter=1000, tol=1e-6):
    """
    最急降下法の実装
    
    Parameters:
    f: 目的関数
    grad_f: 勾配関数
    x0: 初期点
    alpha: 学習率
    max_iter: 最大反復回数
    tol: 許容誤差
    """
    x = x0.copy()
    history = [x.copy()]
    
    for k in range(max_iter):
        grad = grad_f(x)
        
        # 停止条件
        if np.linalg.norm(grad) < tol:
            print(f"収束しました (反復回数: {k})")
            break
            
        # 探索方向
        d = -grad
        
        # Armijo条件によるバックトラッキング
        alpha_k = backtracking_line_search(f, grad_f, x, d, alpha)
        
        # 更新
        x = x + alpha_k * d
        history.append(x.copy())
    
    return x, np.array(history)

def backtracking_line_search(f, grad_f, x, d, alpha_init, c1=1e-4, rho=0.5):
    """Armijo条件によるバックトラッキング直線探索"""
    alpha = alpha_init
    f_x = f(x)
    grad_x = grad_f(x)
    
    while f(x + alpha * d) > f_x + c1 * alpha * np.dot(grad_x, d):
        alpha *= rho
        
    return alpha

# 使用例: 二次関数の最小化
def quadratic_function(x):
    """f(x) = (x₁-1)² + 2(x₂-2)²"""
    return (x[0] - 1)**2 + 2*(x[1] - 2)**2

def quadratic_gradient(x):
    """f(x)の勾配"""
    return np.array([2*(x[0] - 1), 4*(x[1] - 2)])

# 最適化の実行
x0 = np.array([0.0, 0.0])
x_opt, history = steepest_descent(quadratic_function, quadratic_gradient, x0)

print(f"最適解: {x_opt}")
print(f"最適値: {quadratic_function(x_opt)}")

MATLAB実装

function [x, history] = steepest_descent(f, grad_f, x0, options)
    % 最急降下法の実装
    
    if nargin < 4
        options = struct();
    end
    
    % デフォルトパラメータ
    alpha = getfield_default(options, 'alpha', 0.01);
    max_iter = getfield_default(options, 'max_iter', 1000);
    tol = getfield_default(options, 'tol', 1e-6);
    
    x = x0;
    history = x0;
    
    for k = 1:max_iter
        grad = grad_f(x);
        
        % 停止条件
        if norm(grad) < tol
            fprintf('収束しました (反復回数: %d)\n', k);
            break;
        end
        
        % 探索方向
        d = -grad;
        
        % 直線探索
        alpha_k = line_search(f, grad_f, x, d, alpha);
        
        % 更新
        x = x + alpha_k * d;
        history = [history, x];
    end
end

function alpha = line_search(f, grad_f, x, d, alpha_init)
    % Armijo条件によるバックトラッキング
    c1 = 1e-4;
    rho = 0.5;
    
    alpha = alpha_init;
    f_x = f(x);
    grad_x = grad_f(x);
    
    while f(x + alpha * d) > f_x + c1 * alpha * (grad_x' * d)
        alpha = rho * alpha;
    end
end

共役勾配法（Conjugate Gradient Method）

背景と動機

最急降下法では、評価関数が最も急に減る方向（負の勾配方向）を探索方向として使用しますが、この方向が常に最適解に効率的に近づくとは限りません。

最急降下法の問題点

• 勾配方向は等高線に対して垂直
• 最短経路になるとは限らない
• ジグザグ運動による効率の悪化

共役勾配法は、この問題を解決する効率的なアルゴリズムです。

二次関数の場合の理論

以下のような二次形評価関数を考えます：

$$f(x) = \frac{1}{2}(x - x^*)^T Q (x - x^*) + f^*$$

ここで：

• $Q \in \mathbb{R}^{n \times n}$: 正定値対称行列
• $x^*$: 最適解
• $f^*$: 最適値

共役方向の定義

ベクトル $d_i$ と $d_j$ が行列 $Q$ に関して共役（conjugate）であるとは：

$$d_i^T Q d_j = 0, \quad i \neq j$$

が成り立つことです。

共役勾配法の重要な性質

1. 有限収束性: $n$ 次元二次関数の場合、最大 $n$ ステップで正確解に到達
2. メモリ効率: 前のステップの情報のみを保存
3. 行列の保存不要: ヘッセ行列を明示的に計算・保存する必要がない

アルゴリズム

Algorithm: Conjugate Gradient Method
1. 初期点 x₀ を選択
2. r₀ = -∇f(x₀), d₀ = r₀  (初期残差と探索方向)
3. for k = 0, 1, 2, ... do:
   4. 停止条件: ‖rₖ‖ ≤ ε ならば停止
   5. ステップサイズ: αₖ = rₖᵀrₖ / (dₖᵀQdₖ)
   6. 更新: xₖ₊₁ = xₖ + αₖdₖ
   7. 新しい残差: rₖ₊₁ = rₖ - αₖQdₖ
   8. ベータ係数: βₖ₊₁ = rₖ₊₁ᵀrₖ₊₁ / (rₖᵀrₖ)
   9. 新しい探索方向: dₖ₊₁ = rₖ₊₁ + βₖ₊₁dₖ

Fletcher-Reeves公式

一般の非線形関数に対しては、以下の公式を使用：

$$\beta_k^{FR} = \frac{\|\nabla f(x_{k+1})\|^2}{\|\nabla f(x_k)\|^2}$$

Polak-Ribière公式

より実用的な公式：

$$\beta_k^{PR} = \frac{\nabla f(x_{k+1})^T (\nabla f(x_{k+1}) - \nabla f(x_k))}{\|\nabla f(x_k)\|^2}$$

実装例

Python実装

def conjugate_gradient(A, b, x0, max_iter=None, tol=1e-6):
    """
    共役勾配法による線形システム Ax = b の求解
    """
    n = len(b)
    if max_iter is None:
        max_iter = n
    
    x = x0.copy()
    r = b - A @ x  # 初期残差
    d = r.copy()   # 初期探索方向
    
    for k in range(max_iter):
        # 停止条件
        if np.linalg.norm(r) < tol:
            print(f"収束しました (反復回数: {k})")
            break
        
        # ステップサイズ
        Ad = A @ d
        alpha = (r @ r) / (d @ Ad)
        
        # 更新
        x = x + alpha * d
        r_new = r - alpha * Ad
        
        # ベータ係数（Fletcher-Reeves）
        beta = (r_new @ r_new) / (r @ r)
        
        # 新しい探索方向
        d = r_new + beta * d
        r = r_new
    
    return x

def nonlinear_conjugate_gradient(f, grad_f, x0, method='PR', max_iter=1000, tol=1e-6):
    """
    非線形共役勾配法
    method: 'FR' (Fletcher-Reeves) または 'PR' (Polak-Ribière)
    """
    x = x0.copy()
    grad = grad_f(x)
    d = -grad.copy()  # 初期探索方向
    
    for k in range(max_iter):
        # 停止条件
        if np.linalg.norm(grad) < tol:
            print(f"収束しました (反復回数: {k})")
            break
        
        # 直線探索
        alpha = backtracking_line_search(f, grad_f, x, d)
        
        # 更新
        x_new = x + alpha * d
        grad_new = grad_f(x_new)
        
        # ベータ係数の計算
        if method == 'FR':
            beta = np.dot(grad_new, grad_new) / np.dot(grad, grad)
        elif method == 'PR':
            beta = np.dot(grad_new, grad_new - grad) / np.dot(grad, grad)
        else:
            raise ValueError("method must be 'FR' or 'PR'")
        
        # 新しい探索方向
        d = -grad_new + beta * d
        
        # 更新
        x = x_new
        grad = grad_new
    
    return x

勾配法の比較と選択指針

各手法の特徴

手法	収束速度	メモリ使用量	実装複雑度	適用範囲
勾配降下法	線形	$O(n)$	低	一般的
最急降下法	線形	$O(n)$	中	一般的
共役勾配法	超線形	$O(n)$	中	二次関数で最適

選択指針

勾配降下法を選ぶ場合

• 大規模問題
• 確率的設定（SGD）
• 実装の簡単さを重視

最急降下法を選ぶ場合

• 中規模問題
• 高精度な解が必要
• 収束性を重視

共役勾配法を選ぶ場合

• 二次関数または二次関数に近い問題
• メモリ効率を重視
• 少ない反復回数で収束したい

実践的アドバイス

実際の問題では、複数の手法を試して最も効果的なものを選択することが重要です。また、問題の性質（凸性、条件数など）を理解することで適切な手法を選択できます。

高度なトピック

準ニュートン法への発展

勾配法の限界を克服する手法：

• BFGS法（Broyden-Fletcher-Goldfarb-Shanno）
• L-BFGS法（Limited-memory BFGS）
• DFP法（Davidon-Fletcher-Powell）

確率的勾配法

大規模データに対応：

• SGD（Stochastic Gradient Descent）
• Mini-batch SGD
• Adam, AdaGrad, RMSprop

加速勾配法

収束速度の向上：

• Nesterovの加速勾配法
• 重球法（Heavy Ball Method）

まとめ

勾配法アルゴリズムの要点：

1. 勾配降下法: 最も基本的な手法、実装が簡単
2. 最急降下法: 直線探索により効率化
3. 共役勾配法: 二次関数に対して優秀な性能
4. 理論的基礎: テイラー展開と最適性条件
5. 実装上の考慮: 学習率、停止条件、数値安定性
6. 応用範囲: 機械学習から制御工学まで幅広い

参考文献

1. Nocedal, J., & Wright, S. J. (2006). Numerical Optimization. Springer.
2. Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
3. 大塚 敏之, 非線形最適制御入門(Introduction to Nonlinear Optimal Control)，コロナ社, 2011.
4. Bertsekas, D. P. (2016). Nonlinear Programming. Athena Scientific.