第4章 最优化搜索算法的结构与一维搜索.ppt

第4章 最优化搜索算法的结构与一维搜索
*
第1页，本讲稿共31页
常用的搜索算法结构
一、收敛性概念： 考虑（fs）
设迭代算法产生点列{x(k)} S.
1. 理想的收敛性：设x*本讲稿共31页
常用的搜索算法结构
四、下降算法模型（续）
△可行方向：设 ∈S，d∈Rn,d≠0,若存在 ，使 ，称d 为 点的可行方向。
同时满足上述两个性质的方向称下降可行方向。
*
第10页，本讲稿共31页
常用的搜索算法结构
模型算法
线性搜索求 ，
新点
使x(k+1)∈S
初始x(1) ∈S, k =1
对x(k)点选择下降
可行方向d(k)
是否满足停机条件？
停
k=k+1
yes
no
*
第11页，本讲稿共31页
一维搜索
一元函数求极小及线性搜索均为一维搜索。常用于求：
min f(x(k)+ d(k))=φ(λ)
. λ∈S
S有3种情况（-∞，+∞）或（0， +∞ ）或[a,b]
一、缩小区间的精确一维搜索：考虑问题(P)
min φ(λ)
. λ ∈[α, β]
φ (λ):R→R
1、不确定区间及单峰函数
△不确定区间： [α, β]含φ(λ)的最小点，但不知其位置
*
第12页，本讲稿共31页
一维搜索
一、缩小区间的精确一维搜索（续）
定义：设φ： [α, β] →R， λ* ∈[α, β] 是φ在[α, β] 上的最小点 ，若对任意λ1 ,λ2, α≤ λ1 < λ2 ≤β满足：
1º 若λ2 ≤ λ* ，则φ(λ1) > φ(λ2);
2º 若λ1 ≥λ* ，则φ(λ1) <φ(λ2).
则称φ(λ)在[α, β] 上强单峰。
若只有当φ(λ1) ≠φ(λ* )， φ(λ2) ≠φ(λ* )时，上述1º, 2º 式才成立，则称φ(λ)在[α, β] 上单峰。
*
第13页，本讲稿共31页
一维搜索
一、缩小区间的精确一维搜索（续）
若对任意λ1 ,λ2, α≤ λ1 < λ2 ≤β满足：
1º 若λ2 ≤ λ* ，则φ(λ1) > φ(λ2);
2º 若λ1 ≥λ* ，则φ(λ1) <φ(λ2).
则称φ(λ)在[α, β] 上强单峰。
若只有当φ(λ1) ≠φ(λ* )， φ(λ2) ≠φ(λ* )时，上述1º, 2º 式才成立，则称φ(λ)在[α, β] 上单峰。
α λ* λ1λ2 β
强单峰
α λ* β
单峰
*
第14页，本讲稿共31页
一维搜索
一、缩小区间的精确一维搜索（续）
定理：设Ф：R→R 在[α，β ]上单峰，α≤λ＜μ≤ β 。那么
1°若Ф(λ)≥ Ф(μ)，则Ф(ρ) ≥Ф(μ)，  ρ ∈[α，λ]；如左下图
2°若Ф(λ)＜ Ф(μ)，则Ф(ρ)≥Ф(λ)，  ρ ∈[μ ， β]；如右下图
α λ μ β
α λ μ β
*
第15页，本讲稿共31页
一维搜索
一、缩小区间的精确一维搜索（续）
Proof. 1°反证：设
λ* ∈[α,β]为最小点，γ∈[α,λ]及γ﹤λ﹤λ*，使ф (γ)<ф (μ )<ф (λ)，
若λ* ∈[λ ,β]，由定义ф (γ)>ф (λ)，矛盾（假设）；
若λ* ∈[α ,λ），由定义及μ >λ ≥λ*， ф(μ )>ф (λ), 矛盾（条件）；
于是结论成立。
2 °的证明类似（略）。
注：上述定理为缩短区间的算法提供了理论根据。
*
第16页，本讲稿共31页
一维搜索
一、缩小区间的精确一维搜索（续）
2、黄金分割法（ 法）
通过上述定理，选二点λ<μ ,比较ф (λ) 与ф (μ ),可去掉[α ,λ]或者[μ ,β].考虑条件：
1°对称： λ- α= β