常用的一维搜索方法
更新时间:2023-05-23 03:41:01 阅读量: 实用文档 文档下载
线性规划,工程优化
工程优化设计中的数学方法硕士研究生课程
理学院数学系:穆学文 Tel:88207669 E-mail:mxw1334@
线性规划,工程优化
第三章常用的一维搜索方法一元函数求极小及线性搜索均为一维搜索。常用于求: min f(x(k)+λd(k))=φ(λ) s.t.λ∈S S有3种情况(-∞,+∞)或(0,+∞ )或[a, b]。一般地,我们总可以考虑 x∈ (-∞,+∞),例对问题 min f ( x)a≤ x≤b a≤ x≤b
令:则:
f ( x), a≤ x≤ b F ( x)= +∞, othersa≤ x≤b a≤ x≤b
min f ( x)= min F ( x) ∞≤ x≤+∞ ∞≤ x≤+∞
线性规划,工程优化
我们主要介绍如下一些搜索方法:“成功—失败”法 0.618法(黄金分割法)二分法牛顿法(Newton)和插值法非精确搜索算法
线性规划,工程优化
§1
“成功—失败”法
以下方法称为“成功—失败”法(进退法):步骤1:选取初始点 x∈R,初始步长 h> 0及精度ε> 0, 11= f ( x).步骤2:计算 22= f ( x+ h).步骤3:若 22< 11,搜索成功,转步骤4;否则,搜索失败,转步骤5。步骤4:令 x:= x+ h, 11:= 22, h:= 2h步骤5:判断 h≤ε?若 h≤ε,停止迭代, x**= x;否则令 h转步骤 2。 h= ,h= , 4
缺点:效率低。优点:可以求搜索区间注意:初始步长不能选得太小
线性规划,工程优化
例1:设给定初始点为 a及初始步长为 h,求搜索区间[c, d] 1)前进运算首先计算 f (a), f (a+h),如果 f (a)> f (a+h),则步长加倍,计算f (a+3h).若 f (a+h)<= f (a+3h),则c=a, d=a+3h;否则将步长再加倍,并重复上面运算. 2)后退运算如果 f (a)< f (a+h),则将步长缩为原来的1/4并改变符号,即将步长改为-h/4,如果 f (a)< f (a-h/4),则c=a-h/4,d=a+h;否则将步长加倍,并继续后退。注意: 1. h选择要适当.(太大含多个单峰区间,太小迭代次数多); 2. f (x)单调时无结果, (加迭代次数限制); 3.可与中点法结合寻找单调区间(思考)。
线性规划,工程优化
§2
0.618法(黄金分割法)
0.618法是求单峰函数极值的一种试探法.所谓的单峰函数是指只有一个峰值的函数,其严格定义有定义1:设 f(x)是定义在[a, b]上的函数,如果 1) x*∈[a, b]是φ在[a, b]上的最小点, 2)若对任意x1,x2, a≤ x1< x2≤b,满足: 1º若x2≤ x*,则 f (x1)> f (x2); 2º若x1≥x*,则 f (x1)<f (x2).则称 f(x)为[a, b]上的单峰函数。
线性规划,工程优化
f
f
0
x*
t
0
x*
t
线性规划,工程优化
定理1:设 f:R→R在[a, b]上是单峰函数, a≤ x1< x2≤b。那么 1°若 f (x1)≥ f (x2),则 x*∈[x1, b],如左下图 2°若 f (x1)< f (x2),则 x*∈[a, x2],如右下图
α
x1
x2
b
α
x1
x2
b
线性规划,工程优化
Proof. 1°反证法:设 x*∈[a, b]为最小点,若x*∈[a, x1],由定义知 f (x1)< f (x2 ),矛盾 (假设); 2°若x*∈[x2, b],由定义知 f (x1 )> f (x2 ),矛盾(条件);结论成立。注:上述定理为缩短区间的算法提供了
理论根据。
线性规划,工程优化
通过上述定理,选二点 x1< x2,比较 f (x1 )与 f (x2 ),可去掉[a, x1]或者[x2, b].考虑条件: 1°对称: x1– a= b- x2……① (使“坏”的情况去掉,区间长度不小于“好”的情况) 2°保持缩减比 t=(保留的区间长度/原区间长度)不变。 (使每次保留下来的节点, x1或 x2,在下一次的比较中成为一个相应比例位置的节点 )。推导缩减比 t:如图设第一次保留[a, x2] (去掉[x2, b]),那么第二次保留的长度为[α, x1],则
α
x1
x2
b
x2 α x1 α= t= b α x2 α
(2)
线性规划,工程优化
整理②:
x2= a+ t ( b -α ) x1= a+ t ( x2 -α )
1± 5结合①式:t 2+ t– 1= 0 t= (舍去负值) 2故 t≈0.618注意:上式有 t 2= 1- t,故有 x1= a+ (1- t )( b -α ) x2= a+ t ( b -α)
(算法框图见下页)
线性规划,工程优化
黄金分割法(0.618法)(算法)初始[a, b],ε>0t= ( 5 1)/ 2
x1=α+ (1- t)(b -α ) x2
=α+t (b -α )b -α<ε?
yes
α
x1 x2 x2
b
Nof( x1 )-f( x2 )>0?
STOP; x*=(α+b)/2
b= x2, x2= x1 x1=α+ (1-t)( b -α ) No
b
yes
αα= x1, x1= x2 x2=α+t ( b–α)
x1
x2 x1
b
α
线性规划,工程优化
黄金分割法(0.618法)的优缺点优点:不要求函数可微,且每次迭代只需计算一个函数值,计算量小,程序简单缺点:收敛速度慢。
线性规划,工程优化
§3
二分法
设 f (x)在[a,b]上可微,且当导数为零时是解。取 x=(a+b)/ 2,那么 f′(x)= 0时, x为最小点, x= x*; f′(x)> 0时, x在上升段, x*< x,去掉[x,b]; f′ (x)< 0时, x在下降段, x*> x,去掉[a, x] . (自己画算法框图)tgα>0 tgα<0
ααx
f′ ( x )
αb
f′ ( x )
α
x
b
线性规划,工程优化
x*处,f ' ( x* )= 0,且 x< x*时,我们知道,在极小点 * f ( x )递减,即 f ' ( x )< 0,而当 x> x*,函数递增,即 f '( x)> 0。若找到一个区间[a, b],满足性质 f ' ( a)< 0, f ' ( b)> 0 * f ' ( x* )= 0,为找此 x*则[a,b]内必有 f ( x)的极小点 x,且a+b取 x0=,若 f ' ( x0 )< 0则在 2
用[ a, x0]作新的区间[a,b],继续这个过程,逐步将区间[a,b]缩小,当区间[a,b]的长度充分小时,或者当 f ' ( x0 )充分小时,即可将[a,b]的中点取做极小点的近似点,这时有估计: a+b b a< x* 2 2
[ a, x0]中有极小点,这时
线性规划,工程优化
至于区间[a, b]的确定,一般可采用下述方法:首先取初始点 x0,若 f ' ( x0 )< 0,则在 x0右方取点 x1= x0+ x, ( x也是事先给定的步长);若 f ' ( x1 )> 0,则令 a= x0, b= x1;若仍然有 f ' ( x0 )< 0,则取 x2= x1+ x (或将 x放大一倍,再取 x2= x+ x ),若 f '( x2 )> 0,则以[ x 1, x 2]作区间[a,b];否则继续下去。对于 f '( x0 )> 0的情况,可类似于上面在 x0左侧取点,此时 x< 0 .优点:计算量较少,而且总能收敛到一个局部极小点。缺点:收
敛速度较慢
线性规划,工程优化
§4
牛顿法(Newton)和插值法
§4 .1、Newton法:对 f (x)在 x k点展开: f (x )= f (xk )+ f′(xk )( x-xk )+(1/2) f″(xk )(x-xk )2+ o||(x- xk) 2||取二次式(略去高阶项) g(x)= f (xk)+f′(xk)(x-xk)+ (1/2)f″(xk)(x-xk)2用 g(x)作为f (x)的近似,当 f″(xk)> 0时,其驻点为极小点: g′ (x)= f′(xk)+f″(xk)(x - xk )=0得 xk+1= xk–f′(xk)/f″(xk).取 xk+1为新的迭代点。以上过程即Newton法。特点:收敛速度快,二阶收敛。缺点:须计算二次导数,对初始点要求高、局部收敛。
线性规划,工程优化
Newton法算法框图:初始 x1,ε1,ε2>0 k=1
— f '(xk )—<ε1?
y
停;解 xk
N停,失败
N
f″(xk )>0?
k=k+1
Yxk+1= xk - f′ (xk )/ f″(xk )
Y| xk+1 - xk|<ε2
N
线性规划,工程优化
例1:求 min f (x)=
∫ arctan t d t0
x
解: f′ (x)=arctan x, f″(x)=1/(1+ x2)迭代公式: xk+1= xk - (1+ xk 2) arctan xk取 x1= 1,计算结果: f′ (xk) 1/f″(xk ) k xk 1 1 0.7854 2 2 -0.5708 -0.5187 1.3258 3 0.1169 -0.1164 1.0137 4 -0.001095 -0.001095 x4≈ x*=0取 x1=2,计算结果如下:
线性规划,工程优化
k 1 2 3
xk 2 -3.5357 13.95
f′ (xk) 1.1071 -1.2952不收敛。
1/f″( xk ) 5 13.50
§4 .2、插值法用 f (x)在2或3个点的函数值或导数值,构造2次或3次多项式作为f (x)的近似值,以这多项式的极小点为新的迭代点。 3点2次,2点2次,4点3次,3点3次,2点3次等以 3点2次为例:取 x 1,x 2,x3,求出f (x1 ), f (x2 ), f (x3 )(利用“成功-失败”法)
线性规划,工程优化
设二次插值多项式:a x2+b x+c= g(x) a x12+bx1+c= g (x1 ) a x22+bx2+c= g (x2 ) ax32+bx3+ c= g (x3 )解得: a, b( x1 x2 ) g ( x3 )+ ( x2 x3 ) g ( x1 )+ ( x3 x1 ) g ( x2 ) a= ( x1 x2 )( x2 x3 )( x3 x1 )
( x12 x22 ) g ( x3 )+ ( x22 x32 ) g ( x1 )+ ( x32 x12 ) g ( x2 ) b= ( x1 x2 )( x2 x3 )( x3 x1 )x=
b 2a
正在阅读:
常用的一维搜索方法05-23
成都经开区汽车产业集群演进实证研究10-04
中年人美文网02-18
五年级传统文化教案01-19
2012年二级建造师考试《建筑实务》精选练习题及答案3503-03
三年级下册《书法练习指导》教案04-24
2016-2017年甘肃省定西市陇西县初三上学期期末数学试卷含答案解析03-16
2014年广东广雅中学高中招生热点问答07-03
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- 一维
- 常用
- 方法
- 搜索