最优化方法:四、一维搜索法
程序员文章站
2022-07-15 22:30:53
...
主要参考书目:
- 最优化方法及其应用/郭科,陈聆,魏友华.-北京:高等教育出版社,2007.7(2013.7重印)
迭代的基本公式是
当我们确定了搜索方向,我们要做的就是确定一个步长,使得,从而也就确定了,记为。寻找的过程即称是一维搜索。
对于一个确定的目标函数,一维搜索等价于以下两式:
可以证明,在处满足如下图:
1、一些概念
- 搜索区间
即是包含问题最优解的一个区间。 - 单谷区间与单谷函数
定义:
有性质:
根据此性质,我们可以将一个已知的单谷区间缩短为一个更小的单谷区间,从而无限接近于最优解。
2、进退法(加步搜索法)
该方法主要用于确定初始搜索区间。
- 基本原理:
我们即是要寻找如图c的情况。 - 计算步骤
该流程图中初始点赋的值为0,实际上可以是任意值。 - matlab实现
function [a,b] = JinTui(f,xk0,d,th)
%进退法求搜索区间
%输入:
% f:目标函数的句柄
% xk0:初始值
% d:搜索方向
% th:初始步长
%输出:
% [a b]得到的搜索区间
%——开始
t=th;
x1=xk0;y1=feval(f,x1);
x2=x1+t.*d;y2=feval(f,x2);
while y1==y2
t=1.1*t;
x2=x1+t.*d;
y2=feval(f,x2);
end
if y2<y1
t=2*t;
x3=x2+t.*d;
y3=feval(f,x3);
elseif y2>y1
t=-t;
%交换x1,x2
x3=x1;y3=y1;
x1=x2;y1=y2;
x2=x3;y2=y3;
x3=x2+t.*d;
y3=feval(f,x3);
end
while 1
while y2==y3
t=1.1*t;
x3=x2+t.*d;
y3=feval(f,x3);
end
if y3>y2
break;
else
x1=x2;y1=y2;
x2=x3;y2=y3;
t=2*t;
x3=x2+t.*d;
y3=feval(f,x3);
end
end
a=min(x1,x3);
b=max(x1,x3);
end
2、对分法
- 基本思路
在一个单谷区间内,求函数的极小值即是求的点。此对分法即是求函数零点的对分法,不再赘述。 - 特点
此方法要求“单谷”,也要求原函数导数存在。
3、牛顿切线法
- 基本思路
与对分法类似,同样是把求函数的极小值转化为求的点。此时的牛顿切线法也就是求函数零点的牛顿切线法,亦不赘述。 - 特点
此方法同样要求“单谷”,也要求原函数二阶导数存在。
该方法若使用恰当收敛很快,但同时也容易出现不能收敛的问题。
4、黄金分割法
- 基本思路
利用单谷区间的性质,缩短区间,点选为区间的两个黄金分割点。 - 特点
只要求“单谷”。
5、抛物线插值法
- 基本思路
通过用抛物线拟合目标函数的方法求取近似极小值。
不妨设单谷搜索区间为,再任取,根据此三点确定一个抛物线,求出其最小值点,若精度不满足要求,再利用单谷区间的性质缩短区间进一步迭代。 - 具体内容
流程如下:
上一篇: BigDecima做除法时遇到的问题
下一篇: Vue常见异常处理技巧