文档介绍：工程优化设计中的数学方法工程优化设计中的数学方法
硕士研究生课程硕士研究生课程
理学院数学系:穆学文
Tel:88207669 E-mail:mxw1334@
第三章常用的一维搜索方法
一元函数求极小及线性搜索均为一维搜索。常用于求:
min f(x(k)+ λd(k))=φ(λ)
. λ∈S
S 有3种情况(-∞,+∞)或(0, +∞)或[a, b]。一般
地, 我们总可以考虑 x ∈(-∞,+∞), 例
对问题 miminn fxfx(( ))
axax≤≤≤≤bb
令: fxfx()(),, aa≤≤ xx≤≤bb
FxFx()()==
+∞+∞,, otothehersrs
则:
miminn fxfx(( )) == mmiinn FF((xx))
axax≤≤≤≤bb −−∞∞≤≤≤≤xx++∞∞
我们主要介绍如下一些搜索方法:
z “成功—失败”法
z (黄金分割法)
z 二分法
z 牛顿法(Newton)和插值法
z 非精确搜索算法
§1 “成功—失败”法
以下方法称为“成功—失败”法(进退法):
步骤1:选取初始点 x∈R , 初始步长 h > 0 及精度ε> 0,
ϕϕ11 == ff ()()xx ..
步骤:计算
2 ϕϕ22 == ff ()()xhxh++ ..
步骤3:若ϕϕ2121<<ϕϕ,, 搜索成功, 转步骤4;否则,搜索失败,
转步骤5。
步骤:令
4 x:= x + h, ϕϕ1212:,:,==ϕϕ hhhh::== 22
步骤5:判断 hh ≤≤εε?? 若 hh ≤≤εε,, 停止迭代,xxxx** == ;否则令
hh 转步骤 2。
hh =−=−,,
44
缺点:效率低。优点:可以求搜索区间
注意:初始步长不能选得太小
例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 (黄金分割法)
峰函数是指只有一个峰值的函数,其严格定义有
定义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
t
0tx* 0 x*
定理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]为最小点,
*
z 若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或 x