最优化考试之黄金分割法

大家好，欢迎来到IT知识分享网。

前言

最近要考最优化了，感觉时间有点赶，所以就直接学了解题方法，没去学习具体的原理了。

一、黄金分割法

1.解题条件

一般来说，题目会给出以下初始条件

1. 条件函数f(x)
2. 起始区间 [a0,b0]
3. 精度要求L

2.解题形式

先看下表格形式，我们解题就是在下列表格内不断迭代直至|a-b|<=L

1. a、b代表每次迭代时的左右区间;
2. x1、x2分别代表每次迭代的左右试点（这部分计算就会用到黄金分割）;
3. f(x1)、f(x2)分别代表左右试点的函数值，根据二者大小决定下一次迭代更新左端点a还是右端点b;
4. |a-b|代表达到的结果精度，当它小于等于L时迭代结束。

3.解题过程

1. 第一次迭代将初始点a0、a0作为a、b值；
2. 计算当前a、b绝对值之差，如果小于等于精度范围L，停止迭代；
3. 计算左试点x1，公式如下 $x_1=a+0.382\ast (b-a)$
4. 计算右试点x2，公式如下 $x_2=a+0.618\ast (b-a)$
5. 分别计算f(x1)、f(x2)值，比较二者大小；
   若f(x1)大于f(x2)，则更新下一次迭代的a为x1;
   若f(x2)大于f(x1)，则更新下一次迭代的b为x2;
   总而言之，就是哪边试点的函数值大下一次就更新哪边的端点。
6. 迭代次数加一，回到第2步。

4.案例

这是网上找的一道题目，字写的丑就不丢人了，这道题没有具体说明它的精度范围，我就自行定义了精度范围为0.05，大家可以根据第三节的过程来跟着运算一下，最终写在纸张上的形式应该和下面代码结果截图的形式基本一样。

//黄金分割法：0.618法求极小值；  //黄金分割法：0.618法求极小值；  #include<iostream> #include<iomanip> #include <math.h> #include<stdio.h> #include<cmath> using namespace std; double func(double x){ 
    //此处需要按实际情况修改函数表达式 double s=x*x-x+2; return s; } int main(){ 
    cout<<"函数:f(x)=x^2-x+2"<<endl; double L,a1,b1; cout<<"请输入初始区间："; cin>>a1>>b1; cout<<"请输入精度范围："; cin>>L; int k; double a[20]; double b[20]; double r[20]; double u[20]; a[1]=a1; b[1]=b1; k=1; double fr,fu; cout<<"------------------------------------------------------------------------------------"<<endl; printf("\t%s \t%s \t%s \t%s \t%s \t%s \t%s \t%s\n", "迭代次数", "a", "b","x1","x2","f(x1)","f(x2)","|a-b|"); cout<<"------------------------------------------------------------------------------------"<<endl; r[k]=a[k]+0.382*(b[k]-a[k]); u[k]=a[k]+0.618*(b[k]-a[k]); while(b[k]-a[k] >=L){ 
    fr=func(r[k]); fu=func(u[k]); printf("\t%d\t %8.3f %8.3f %8.3f %8.3f %8.4f %8.4f %8.4f\n", k, a[k], b[k],r[k],u[k],fr,fu,fabs(a[k]-b[k])); cout<<"------------------------------------------------------------------------------------"<<endl; if(fr<fu){ 
    b[k+1]=u[k]; a[k+1]=a[k]; r[k+1]=a[k+1]+0.382*(b[k+1]-a[k+1]); u[k+1]=r[k]; } else if(fr>fu){ 
    a[k+1]=r[k]; b[k+1]=b[k]; r[k+1]=u[k]; u[k+1]=a[k+1]+0.618*(b[k+1]-a[k+1]); } k++; } printf("\t%d\t %8.3f %8.3f \n", k, a[k], b[k]); cout<<"------------------------------------------------------------------------------------"<<endl; cout<<"\t迭代"<<k-1<<"次，达到要求！"<<endl; printf("\tb[%d]-a[%d]=%4.3f \n", k,k,b[k]-a[k]); printf("\t最优值在区间 [%4.3f, %4.3f]\n",a[k],b[k]); }