黄金分割算法原理、实现及函数极小值求解实例

黄金分割算法原理、实现及函数极小值求解实例

引用

CSDN

1.

https://blog.csdn.net/Super_senior1/article/details/144832764

黄金分割算法是一种基于区间收缩的极小点搜索算法，广泛应用于函数极值求解。本文将详细介绍黄金分割算法的基本原理、实现步骤，并通过一个具体的函数极值求解实例，展示其在MATLAB中的应用。

一、算法原理

黄金分割法也称为0.618法，其基本思想是通过不断缩小搜索区间，使搜索区间的端点逼近极小点。具体来说，对于给定的搜索区间[a, b]，算法首先根据黄金比例产生两个内点x1和x2：

x1 = a + 0.382 * (b - a)
x2 = a + 0.618 * (b - a)

然后根据f(x1)和f(x2)的大小关系来重新选择搜索区间：

• 若f(x1) < f(x2)，则搜索区间变为[x1, b]
• 若f(x1) > f(x2)，则搜索区间变为[a, x2]

二、算法步骤

用黄金分割法求解无约束优化问题min f(x), x∈R的基本算法步骤如下：

1. 选定初始区间[a1, b1]及精度ε > 0，计算试探点：
   λ1 = a1 + 0.382 * (b1 - a1)
   μ1 = a1 + 0.618 * (b1 - a1)
   并令k = 1

2. 若bk - ak < ε，则停止计算。否则，根据f(λk)和f(μk)的大小关系进行区间更新：

• 当f(λk) > f(μk)时，更新区间为[λk, bk]，并计算新的试探点
• 当f(λk) ≤ f(μk)时，更新区间为[ak, μk]，并计算新的试探点

3. 重复步骤2，直到满足精度要求或达到最大迭代次数

三、MATLAB实现

以下是黄金分割法的MATLAB程序代码：

function [x, minf] = minHJ(f, a, b, eps)
% 目标函数：f;
% 极值区间左端点：a;
% 极值区间右端点：b;
% 精度：eps;
% 目标函数取最小值时的自变量值：x;
% 目标函数的最小值：minf

format long;
if nargin == 3
    eps = 1.0e-6;
end

l = a + 0.382 * (b - a);
u = a + 0.618 * (b - a);
k = 1;
tol = b - a;

while tol > eps && k < 100000
    fl = subs(f, symvar(f), l);
    fu = subs(f, symvar(f), u);

    if fl > fu
        a = l;
        l = u;
        u = a + 0.618 * (b - a);
    else
        b = u;
        u = l;
        l = a + 0.382 * (b - a);
    end

    k = k + 1;
    tol = abs(b - a);
end

if k == 100000
    disp('找不到最小值！');
    x = NaN;
    minf = NaN;
    return;
end

x = (a + b) / 2;
minf = subs(f, symvar(f), x);
format short;

四、实例演示

使用黄金分割法求解函数f(t) = (t^2 - 1)^2 + (t - 1)^2 + 3在区间[-10, 10]上的最小值：

在MATLAB命令窗口中输入：

syms t
f = t^4 - t^2 - 2*t + 5;
[x, fx] = minHJ(f, -10, 10);

所得结果为：

x =
    1.0000

fx =
18831305206737427346706372180303789976284356552717013960977/6277101735386680763835789423207666416102355444464034512896

进一步计算得到：

>> 18831305206737427346706372180303789976284356552717013960977/6277101735386680763835789423207666416102355444464034512896
ans =
    3.0000

从目标函数的表达式可以看出，t = 1是极小点，黄金分割法求出的结果是正确的。目标函数是单极值点函数，因此极值点(1,3)也是其最小点。其曲线图如图2所示：

绘制上述曲线图的MATLAB代码如下：

% 定义符号变量 t
syms t
% 定义函数 f(t)
f = t^4 - t^2 - 2*t + 5;
% 定义 t 的取值范围，例如从 -3 到 3，步长为 0.01
t_vals = -3:0.01:3;
% 计算 f(t) 在这些 t 值上的取值
f_vals = double(subs(f, t, t_vals));
% 绘制曲线
figure;
plot(t_vals, f_vals, 'LineWidth', 2);
xlabel('t');
ylabel('f(t)');
% 设置 y 轴的区间，例如从 0 到 100
ylim([2.5 6]);
title('Plot of f(t) = t^4 - t^2 - 2t + 5');
grid on;

五、总结

黄金分割算法是一种简单而有效的优化算法，特别适合于一维搜索问题。通过本文的介绍和实例演示，读者可以掌握黄金分割算法的基本原理和实现方法，并能够在MATLAB中进行实际应用。