黄金分割法（0.618 法）

黄金分割法简介

黄金分割法属于区间缩小法，通过逐步缩小包含极值的区间长度，逼近极值点。在每一次迭代中，使用黄金分割点 0.618 将区间分为两部分，比较这两点处的函数值，舍弃较差区间，从而逐渐逼近最优解。

数学推导

设单峰函数 $f(x)$ 在区间 $[a,b]$ 上有唯一极小值。
根据黄金分割原理，将区间 $[a,b]$ 分成两个子区间，点 $x_1$，$x_2$ 满足
$$\frac{x_2-a}{b-a}=\frac{b-x_1}{b-a}=\varphi \approx 0.618$$
其中
$$\phi =\phi =\frac{\sqrt{5}-1}{2}$$

具体计算

$$\begin{gathered} x_1=b-\phi (b-a) \\ {x}_2=a+\phi (b-a) \end{gathered}$$
然后比较 $f(x_1)$ 和 f(x_2) 的值
如果 $f(x_1)>f(x_2)$ 则舍弃区间 $[a,x_1]$ 极小值在 $[x_1,b]$ 之间
否则，舍弃 区间 $[b,x_2]$ 极小值在 $[a,x_1]$ 之间

算法流程

• [1] 给定区间 $[a,b]$， 计算黄金比例常数 $\phi$
• [2] 计算初始两点
  $$\begin{gathered} x_1=b-\phi (b-a) \\ {x}_2=a+\phi (b-a) \end{gathered}$$
• [3] 计算 $f(x_1)$ 和 $f(x_2)$
• [4] 比较 $f(x_1)$ 和 $f(x_2)$
  若 $f(x_1)>f(x_2)$, 则 $a=x_1$
  否则 $b=x_2$
• [5]更新新的 $x_1$ 和 $x_2$
• [6] 重复计算 4 和 5 直到 $|b-a|<\eta$
• [7] 返回 $\frac{a+b}{2}$ 作为极小值点近似值

算法实现

#include <iostream>
#include <cmath>
#include <functional>class GoldenSectionSearch {
private:double left;        // 区间左端点double right;       // 区间右端点double eps;         // 精度要求std::function<double(double)> func; // 待求极值的函数const double phi = (std::sqrt(5.0) - 1) / 2; // 黄金比例常数 0.618...public:// 构造函数GoldenSectionSearch(double l, double r, double e, std::function<double(double)> f): left(l), right(r), eps(e), func(f) {}// 执行搜索double search() {double x1 = right - phi * (right - left);double x2 = left + phi * (right - left);double f1 = func(x1);double f2 = func(x2);while (std::fabs(right - left) > eps) {if (f1 < f2) { // 若求最大值改成 >right = x2;x2 = x1;f2 = f1;x1 = right - phi * (right - left);f1 = func(x1);} else {left = x1;x1 = x2;f1 = f2;x2 = left + phi * (right - left);f2 = func(x2);}}// 返回极小值点（区间中点）return (left + right) / 2.0;}
};int main() {// 示例：求 f(x) = (x-2)^2 + 1 的最小值点auto func = [](double x) {return (x - 2) * (x - 2) + 1;};GoldenSectionSearch gss(0, 5, 1e-6, func);double min_x = gss.search();std::cout << "极小值点 x ≈ " << min_x << std::endl;std::cout << "对应的 f(x) ≈ " << func(min_x) << std::endl;return 0;
}