Python Nelder-Mead算法详解|极客笔记

Python Nelder-Mead算法详解

1. 介绍

Nelder-Mead算法是一种经典的优化算法，用于寻找多元函数的最小值。它是一种基于直接搜索的无导数优化方法，通常适用于目标函数的梯度难以求解的情况。

Nelder-Mead算法的基本思想是通过不断地调整一个多维空间中的一组顶点，以尝试找到目标函数的最小值。这种方法不要求目标函数是凸的，也不需要计算目标函数的梯度信息，因此具有较好的适用性。

在Nelder-Mead算法中，一组顶点可以表示为一个简单形状，如线段、三角形或多面体。通过不断地调整这些顶点的位置，算法试图找到一个能够使目标函数值最小化的局部最优解。

2. 算法步骤

Nelder-Mead算法的基本步骤如下：
1. 初始化：选择一组初始顶点，并计算每个顶点对应的目标函数值。
2. 排序：将所有顶点按照目标函数值的大小排序，确定最优顶点（最小值）、次优顶点和最差顶点。
3. 中心点计算：计算中心点，即剔除最差顶点后，其余顶点的几何中心。
4. 反射：通过反射操作得到反射点，即过中心点的延长线与最差顶点的交点。
5. 扩展或收缩：如果反射点比次优点更好，则进行扩展操作；否则进行收缩操作。
6. 压缩：将所有顶点向中心点靠拢，缩小搜索空间。
7. 结束条件：判断是否满足结束条件，如目标函数值已经收敛或迭代次数达到上限。

3. Nelder-Mead算法的Python实现

下面给出Nelder-Mead算法的Python实现代码：

import numpy as np

def nelder_mead(f, x_start, tol=1e-6, max_iter=1000):
    n = len(x_start)
    alpha = 1
    beta = 0.5
    gamma = 2
    sigma = 0.5

    x = np.array(x_start)
    f_val = f(x)

    for i in range(max_iter):
        # Calculate function values at each vertex
        points = [x]
        for j in range(n):
            point = x + sigma * (np.random.rand(n) - 0.5)
            points.append(point)

        f_vals = np.array([f(point) for point in points])
        best_idx = np.argmin(f_vals)
        worst_idx = np.argmax(f_vals)

        x_best, x_worst = points[best_idx], points[worst_idx]
        x_avg = np.mean([point for k, point in enumerate(points) if k != worst_idx], axis=0)

        # Reflection
        x_reflect = (1 + alpha) * x_avg - alpha * x_worst
        if f(x_reflect) < f_vals[best_idx]:
            # Expansion
            x_expand = (1 - gamma) * x_avg + gamma * x_reflect
            if f(x_expand) < f_vals[best_idx]:
                x[worst_idx] = x_expand
            else:
                x[worst_idx] = x_reflect
        else:
            if f(x_reflect) < f_vals[worst_idx]:
                x[worst_idx] = x_reflect
            # Contraction
            x_contract = beta * x_worst + (1 - beta) * x_avg
            if f(x_contract) < f_vals[worst_idx]:
                x[worst_idx] = x_contract
            else:
                for j, point in enumerate(points):
                    if j != best_idx:
                        x[j] = (point + x_best) / 2

        f_val = f(x)

        if np.sqrt(np.mean((f_vals - f_val) ** 2)) < tol:
            break

    return x

# Example usage
def quadratic(x):
    return np.sum(x ** 2)

x_start = [1, 1]
result = nelder_mead(quadratic, x_start)
print(result)