函数极值问题求解——C++实现

tech2024-08-16  48

对于一个简单函数来说,例如 ,它的图像存在最大值和最小值,那么给定一个区间我们可以利用以下几种方法进行求解。(0<=x<=100,y的值会给出)

方法1:二分法求解

假定存在极小值在区间内,那么函数一定是先减后增,利用函数fx求解函数值,函数fdx则为fx函数的导数,利用导数我们可以找到该函数fx的极小值。

double fx(double x,double y) { return 7*pow(x,7)+6*pow(x,6)+2*pow(x,3)+8*pow(x,2)-y*x; } double fdx(double x,double y) { return 49*pow(x,6)+36*pow(x,5)+6*pow(x,2)+16*x-y; }

二分法求解,设置left为左边界,right为右边界,则解一定位于left和right之间,当左右边界之间的差值小于某一精确度时,就认为找到了解。具体操作如下,首先判断左右边界差值作为循环条件,接着每次循环找到左右边界的中间值,一旦该点导数值小于0,说明该点的右侧存在正确解,则将左边界设置为该点,反之将右边界缩进,左右边界通过循环不断的向正确解缩进。满足某一精确度后即可输出结果。(注意这里的函数是比较常规简单的单调函数)

double left=0.0,right=100.0; int count=0; double preci=1e-6;//设置精确度 while(right-left>preci) { double mid =(left+right)/2.0; if(fdx(mid,y)<0) { left=mid; } else { right = mid; } }

方法2:牛顿二次迭代

同样是对常规函数求解,只是牛顿二次迭代可以更快的求得结果,即便结果有些许相差,但是在经过100次以上的迭代后,答案已经很精确了。对于二次迭代,需要对函数进行二次求导,得到一次求导后各点的斜率。

double fddx(double x) { return 294*pow(x,5)+180*pow(x,4)+12*x+16; }

首先设置一个边界值,对于该边界值一阶导数的值进行判断,判断是否接近0点,或者在进行两百次循环后退出。接下来,从右边界进行缩进,对于该点进行二阶求导,在该点做一条函数切线,与x轴相交的点相比于原边界值一定更接近正确解。具体写法如下,求一阶导的函数值,该函数值除以斜率(也就是该点二阶导的值)即为缩进的x距离,在原有边界上减去该值,即向正确解缩进。

double preci=1e-8;//设置精确度 double ans=100; int count=0; while(fdx(ans,y)>preci&&count++<200) { ans = ans-(fdx(ans,y)/fddx(ans)); }

方法3:暴力

在已知小范围内设置一个很小的变化量,将所有函数值求出,得到该函数在该区间上的极小值。注意时间复杂度避免超时问题。

double ans=100; double min=fx(ans,y); ans-=0.0005; double stand=fx(ans,y); while(stand<min) { min=stand; ans-=0.0005; stand=fx(ans,y); }

方法4:模拟退火算法

在对于复杂函数进行求解时,以上三种方法,只能求得局部最优的解。利用模拟退火算法才可以得到全局最优解。 具体原理很复杂还不太理解,代码实现如下

#include <cstdio> #include <iostream> #include <cstring> #include <cmath> #include <algorithm> #include <map> #include <vector> #include <set> #include <stack> #include <queue> #include <cstdlib> //srand,rand,RAND_MAX #include <ctime> //time using namespace std; typedef long long ll; int num,mark,m,n,t,maxlen,start,end; #define sc(n) scanf("%d",&n) double fx(double x,double y) { return 7*pow(x,7)+6*pow(x,6)+2*pow(x,3)+8*pow(x,2)-y*x; } double randouble() { return (rand()%10001)/10000.0;//得到小数随机数技巧 } int main() { srand((unsigned int)time(NULL));//初始化伪随机数生成器 double y; scanf("%lf",&y); double preci=1e-8; double t=100;//火的温度 double delta=0.98;//降温系数,降温系数与代码的时间复杂度相关,同时会影响解的精确度 double x=randouble()*100.0; int count=10; double ans=999999999; while(t>preci) { for(int k=1;k<=count;k++) { double nowfx=fx(x,y); double xnew=x+(randouble()*2-1)*t;//从【-1,1】之间得到小数 if(xnew>=0&&xnew<=100) { double newfx=fx(xnew,y); double detay=newfx-nowfx; if(detay<0) { x=xnew; } else { double p=pow(exp(1),-(detay)/t); if(randouble()<p) { x=xnew; } } } } t=t*delta; ans=min(ans,fx(x,y)); } printf("%.4f\n",ans); }
最新回复(0)