Nelder-Mead法

主な特徴

Nelder-Mead法：関数の最小値を探索するための非線形最適化アルゴリズム

微分不要
目的関数の勾配（微分値）を必要としないため、微分が困難または不可能な関数にも適用できる

シンプレックス使用
n次元空間でn+1個の点からなるシンプレックス（多面体）を用いて探索を行う

アメーバ法
シンプレックスがアメーバのように変形しながら最小値を探索することから、アメーバ法とも呼ばる

アルゴリズムの流れ

1. 初期化: n+1個の点からなる初期シンプレックスを生成
2. 評価: 各点での関数値を計算し、最悪点（最大値）、最良点（最小値）を特定
3. 反射: 最悪点を除く重心に対して、最悪点を反射
4. 拡大/収縮: 反射点の評価結果に応じて、シンプレックスを拡大または収縮
5. 縮小: 必要に応じて、全体的にシンプレックスを縮小
6. 繰り返し: 収束条件を満たすまで2-5のステップを繰り返す

より詳細な解説

1. 初期化
n次元の問題に対して、n+1個の点からなる初期シンプレックスを生成

---

反復プロセス
2. 評価
各点でのコスト関数の値を計算し、最良点（最小値）、最悪点（最大値）、次悪点を特定

3. 重心計算
最悪点を除く全ての点の重心を計算

4. 反射
最悪点を重心に対して反射させ、新しい点を生成
反射点のコスト値が最良点と次悪点の間にある場合、反射点を採用し、最悪点と置き換える
その後、ステップ2に戻る

5. 拡大
反射点のコスト値が最良点よりも良い場合、反射方向にさらに拡大した点を生成
拡大点のコスト値が反射点より良ければ拡大点を、そうでなければ反射点を採用し、最悪点と置き換える
その後、ステップ2に戻る

6. 収縮
反射点のコスト値が次悪点より悪い場合、以下の収縮操作を行う
外側収縮: 反射点が最悪点より良い場合、重心と反射点の間に新しい点を生成
内側収縮: それ以外の場合、重心と最悪点の間に新しい点を生成
収縮点のコスト値が最悪点より良ければ、収縮点を採用し最悪点と置き換える
その後、ステップ2に戻る

7. 縮小
収縮が失敗した場合、最良点を除く全ての点を最良点方向に縮小
その後、ステップ2に戻る

8. 終了条件
シンプレックスのサイズが十分小さくなるか、最大反復回数に達した場合、アルゴリズムを終了

---

このプロセスにより、Nelder-Mead法はシンプレックスを変形させながら最小値を探索。アルゴリズムは微分情報を必要としないため、複雑な関数や離散的な関数にも適用可能

ただし、初期値の選択が重要であり、局所的な最小値に陥る可能性があるため、多点探索を併用するなどの工夫が必要な場合もある

Pythonを用いたスクラッチ実装

ライブラリ経由だとscipy.optimize.minimizeなどから簡単に利用可能

import numpy as np


def nelder_mead(f, x0, alpha=1.0, beta=2.0, gamma=0.5, delta=0.5, max_iter=1000, tol=1e-8):
    """Nelder-Mead 最適化アルゴリズム。

    Args:
        f (callable): 最小化したい目的関数。
        x0 (numpy.ndarray): 初期点。
        alpha (float, optional): 反射係数。デフォルトは1.0。
        beta (float, optional): 拡大係数。デフォルトは2.0。
        gamma (float, optional): 収縮係数。デフォルトは0.5。
        delta (float, optional): 縮小係数。デフォルトは0.5。
        max_iter (int, optional): 最大反復回数。デフォルトは1000。
        tol (float, optional): 収束判定の閾値。デフォルトは1e-8。

    Returns:
        tuple: 最適解と最適値のタプル。
    """
    # シンプレックスの初期化
    n = len(x0)
    simplex = [x0]
    for i in range(n):
        point = x0.copy()
        point[i] += 0.05
        simplex.append(point)

    def evaluate(x):
        """評価関数"""
        return f(x)

    # メインループ
    for _ in range(max_iter):
        # シンプレックスの点を評価値でソート
        simplex.sort(key=evaluate)

        # 収束判定
        if np.max([evaluate(s) for s in simplex]) - np.min([evaluate(s) for s in simplex]) < tol:
            break

        # 重心の計算（最悪点を除く）
        centroid = np.mean(simplex[:-1], axis=0)

        # 反射
        reflected = centroid + alpha * (centroid - simplex[-1])
        if evaluate(simplex[0]) <= evaluate(reflected) < evaluate(simplex[-2]):
            simplex[-1] = reflected
            continue

        # 拡大
        if evaluate(reflected) < evaluate(simplex[0]):
            expanded = centroid + beta * (reflected - centroid)
            if evaluate(expanded) < evaluate(reflected):
                simplex[-1] = expanded
            else:
                simplex[-1] = reflected
            continue

        # 収縮
        if evaluate(reflected) >= evaluate(simplex[-2]):
            if evaluate(reflected) < evaluate(simplex[-1]):
                contracted = centroid + gamma * (reflected - centroid)
            else:
                contracted = centroid + gamma * (simplex[-1] - centroid)

            if evaluate(contracted) < evaluate(simplex[-1]):
                simplex[-1] = contracted
                continue

        # 縮小
        for i in range(1, n + 1):
            simplex[i] = simplex[0] + delta * (simplex[i] - simplex[0])

    # 最適解と最適値を返す
    return simplex[0], evaluate(simplex[0])


def rosenbrock(x):
    """Rosenbrock関数"""
    return (1 - x[0])**2 + 100 * (x[1] - x[0]**2)**2


# 使用例
initial_guess = np.array([0, 0])
result, value = nelder_mead(rosenbrock, initial_guess)

print("最適解:", result)
print("最適値:", value)

他に比較される最適化手法

手法	特徴	Nelber-Mead法の優位点
勾配降下法	勾配情報が必要だが収束が速い場合が多い	微分不可能な関数への適用が可能
BFGS法	勾配情報が必要だが収束が速く二次収束性を持つ	上に同じ．比較的実装も簡単
遺伝的アルゴリズム	比較的大域的な探索に強く，他店探索が可能	局所的探索に強くパラメータ調整が比較的容易
粒子群最適化	確率的アプローチ，並列処理に適する，多次元問題に対して効果的	決定論的アプローチ，少ない関数評価回数で収束可能，経験的に低次元で効率的に動作
シミュレーテッドアニーリング	局所界からの脱出能力，大域的最適化を見つけやすい	局所的な探索に効果的で比較的収束が速い