最急降下法（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）

完全直線探索（Exact Line Search）

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

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

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

不完全直線探索（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}$）

Wolfe条件

Armijo条件に加えて：

$$\nabla f(x_k + \alpha d_k)^T d_k \geq c_2 \nabla f(x_k)^T d_k$$

ここで $c_1 < c_2 < 1$（通常 $c_2 = 0.9$）

実装例

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 wolfe_line_search(f, grad_f, x, d, alpha_init=1.0, c1=1e-4, c2=0.9, max_iter=50):
    """Wolfe条件による直線探索"""
    alpha_lo, alpha_hi = 0, None
    alpha = alpha_init
    
    f_x = f(x)
    grad_x = grad_f(x)
    phi_0 = f_x
    dphi_0 = np.dot(grad_x, d)
    
    for i in range(max_iter):
        phi_alpha = f(x + alpha * d)
        
        # Armijo条件をチェック
        if phi_alpha > phi_0 + c1 * alpha * dphi_0:
            alpha_hi = alpha
            alpha = (alpha_lo + alpha_hi) / 2
            continue
        
        # Wolfe条件をチェック
        dphi_alpha = np.dot(grad_f(x + alpha * d), d)
        if dphi_alpha >= c2 * dphi_0:
            return alpha
        
        if dphi_alpha > 0:
            alpha_hi = alpha
        else:
            alpha_lo = alpha
            
        if alpha_hi is not None:
            alpha = (alpha_lo + alpha_hi) / 2
        else:
            alpha *= 2
    
    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)}")

# 収束過程の可視化
plt.figure(figsize=(10, 5))

plt.subplot(1, 2, 1)
plt.plot(history[:, 0], history[:, 1], 'o-')
plt.xlabel('x₁')
plt.ylabel('x₂')
plt.title('収束経路')
plt.grid(True)

plt.subplot(1, 2, 2)
f_values = [quadratic_function(x) for x in history]
plt.plot(f_values, 'o-')
plt.xlabel('反復回数')
plt.ylabel('目的関数値')
plt.title('目的関数の減少')
plt.grid(True)
plt.yscale('log')

plt.tight_layout()
plt.show()

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

function val = getfield_default(s, field, default)
    if isfield(s, field)
        val = s.(field);
    else
        val = default;
    end
end

理論的性質

収束性

最急降下法の収束性は目的関数の性質に依存します：

凸関数の場合

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

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

適切なステップサイズを選ぶと収束が保証され、収束率は $O(1/k)$ です。

強凸関数の場合

$f(x)$ が強凸関数の場合、線形収束率 $O(\rho^k)$ が得られます。

最急降下法の幾何学的解釈

• 勾配方向: $\nabla f(x_k)$ は関数の等高線に垂直で、関数値が最も急激に増加する方向
• 最急降下方向: $-\nabla f(x_k)$ はその反対方向、つまり最も急激に減少する方向
• ジグザグ現象: 楕円型の等高線では、最急降下方向が必ずしも最適解への最短経路とならない

コメントと補足

利点

1. 実装の簡単さ: アルゴリズムが直感的で実装が容易
2. メモリ効率: 勾配情報のみを使用するため、メモリ使用量が少ない
3. 大域収束性: 適切な直線探索と組み合わせれば大域収束が保証される

欠点

1. 収束速度: 高次の手法（ニュートン法など）と比較して収束が遅い
2. 条件数依存性: 目的関数の条件数が悪いと収束が非常に遅くなる
3. 局所最適性の確認: ヘッセ行列 $H(x_k) = \nabla^2 f(x_k)$ の正定性をチェックする必要

実用的な考慮事項

1. 直線探索の重要性: ステップ幅 $\alpha_k$ を最適化することで、無駄な反復を避けられる
2. スケーリング: 変数のスケールが大きく異なる場合、事前正規化が効果的
3. 初期点の選択: 非凸問題では、複数の初期点からの実行を推奨

発展的手法との関係

最急降下法は以下の高度な手法の基礎となります：

1. 共役勾配法: 二次関数に対してより効率的な探索方向を生成
2. 準ニュートン法: ヘッセ行列の近似により収束速度を向上
3. 信頼領域法: 直線探索の代わりに信頼領域内での最適化

まとめ

最急降下法の要点：

1. 基本原理: 負の勾配方向への移動による関数値の減少
2. 直線探索: 効率的なステップサイズの決定が重要
3. 収束性: 凸関数に対して理論的な収束保証
4. 実装の容易さ: シンプルで理解しやすいアルゴリズム
5. 発展への基礎: より高度な最適化手法への出発点

実装のポイント

最急降下法を実装する際は、適切な直線探索手法（Armijo条件やWolfe条件）の選択が重要です。また、収束判定には勾配のノルムを使用し、数値的安定性に注意してください。

参考文献

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

演習問題

1. 二次関数 $f(x) = \frac{1}{2}x^T Q x - b^T x$ に対して最急降下法の収束条件を導出せよ。

2. Armijo条件の意味を幾何学的に説明し、パラメータ $c_1$ の影響を考察せよ。

3. 楕円型等高線を持つ二次関数において、最急降下法がジグザグ運動する理由を説明せよ。

4. 条件数の異なる二次関数に対して、最急降下法の収束速度を比較実装せよ。