[最优化技术] 3-1 黄金分割法

3-1 黄金分割法

黄金分割法

简述

黄金分割法是常用的一维搜索试探方法，又称“0.618”法。
黄金分割法的基本思想是：每次缩小后的 新区间长度 与 原区间长度 的比值始终是一个常数，此常数为0.618。也就是说每次的区间缩短率都等于0.618。

• 每次迭代只需计算一个新点的函数值（因为另一个点可复用上一轮的结果），大大减少了函数评估次数。
  
• 黄金分割比例具有自相似性：每次缩小区间后，新的两点仍保持黄金比例分布。
  
• 这种对称性和比例不变性避免了数值误差累积，提高了算法的数值稳定性。
  

证明

由上图所示，为使每次迭代时有一个分割点可以复用，即：上一次的左分割点作为这一次的右分割点；或者上一次的右分割点作为这一次的左分割点，需要满足以下比例成立：

\[1:\lambda = \lambda1-\lambda)\]
故：

\[\begin{align*}1-\lambda &= \lambda^2 \\\lambda^2 + \lambda - 1 &= 0\end{align*}\]
取正数解：

\[\lambda = \frac{\sqrt{5}-1}{2} \approx 0.618\]
此数也就是大名鼎鼎的黄金分割比。
计算公式


\[\begin{align*}a_1 &= b - 0.618(b - a) \\b_1 &= a + 0.618(b - a)\end{align*}\]
程序框图

提供如下基于黄金分割法进行一维函数搜索的程序框图，注意 图中字母与下文的代码变量并非严格一一对应，仅供参考。

代码示例

对于黄金分割法，给出以下C++函数仅供参考。

1. // 黄金分割法 求最小值点（横坐标）
2. double golden_section(function<double(double)> func, double l, double r, double eps) {
3.         const double ratio = 0.618;
4.         double a = l, b = r;
5.         double aa = b - ratio * (b-a);
6.         double bb = a + ratio * (b-a);
7.         double y1 = func(aa);
8.         double y2 = func(bb);
9.        
10.         int step = 0;
11.         printf("[debug] step %d: (%.5lf, %.5lf)\n", step, a, b);
12.         while (b - a > eps) {                         // 点距准则
13.                 if (y1 >= y2) {
14.                         a = aa;
15.                         aa = bb;                 // 复用上次分割点横坐标
16.                         y1 = y2;                 // 复用上次分割点纵坐标
17.                         bb = a + ratio * (b-a);  // 计算新的分割点
18.                         y2 = func(bb);
19.                 } else {
20.                         b = bb;
21.                         bb = aa;                 // 复用上次分割点横坐标
22.                         y2 = y1;                 // 复用上次分割点纵坐标
23.                         aa = b - ratio * (b-a);  // 计算新的分割点
24.                         y1 = func(aa);
25.                 }
26.                 step++;
27.                 printf("[debug] step %d: (%.5lf, %.5lf)\n", step, a, b);
28.         }
29.         return (a + b) / 2;
30. }

复制代码

结合上一篇文章所讲的进退法确定初始区间，我们可以轻松求解出任何一维单谷函数的 极小值点 和 极小值。给出如下完整C++代码仅供参考。
C++代码实现：[code]#include #include #include #include using namespace std;// 进退法求初始区间pair bracket_minimum(function func, double a0, double h) {        // 进退法最大搜索次数        const int MAX_ITER = 1e4;        if (h  MAX_ITER)                                throw runtime_error("Max iterations exceeded in right expansion");                        printf("[debug] step %d: (%.2lf, %.2lf, %.2lf)\n", iter, x0, x1, x2);                        x0 = x1;                        x1 = x2;                        h *= 2;                        x2 = x1 + h; // 步长加倍                }                printf("[debug] step %d: (%.2lf, %.2lf, %.2lf)\n", iter + 1, x0, x1, x2);                return make_pair(x0, x2);        }}// 黄金分割法 求最小值点（横坐标）double golden_section(function func, double l, double r, double eps) {        const double ratio = 0.618;        double a = l, b = r;        double aa = b - ratio * (b-a);        double bb = a + ratio * (b-a);        double y1 = func(aa);        double y2 = func(bb);                int step = 0;        printf("[debug] step %d: (%.5lf, %.5lf)\n", step, a, b);        while (b - a > eps) {                        // 点距准则                if (y1 >= y2) {                        a = aa;                        aa = bb;                        y1 = y2;                        bb = a + ratio * (b-a);                        y2 = func(bb);                } else {                        b = bb;                        bb = aa;                        y2 = y1;                        aa = b - ratio * (b-a);                        y1 = func(aa);                }                step++;                printf("[debug] step %d: (%.5lf, %.5lf)\n", step, a, b);        }        return (a + b) / 2;}int main() {        // 定义一个一元凸函数        auto f = [](double x) {                return x * x - 2 * x - 5;        };        double a0, h, eps;        cout > a0;        cout > h;        cout > eps;        pair range;        try {                range = bracket_minimum(f, a0, h);                cout