资源描述：
《运筹学与最优化方法 第4章最优化搜索算法的结构》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第四章最优化搜索算法的结构与一维搜索4.1常用的搜索算法结构一、收敛性概念：考虑（fs）设迭代算法产生点列{x(k)}S.1.理想的收敛性：设x*∈S是g.opt.当x*∈{x(k)}或x(k)≠x*，k，满足时，称算法收敛到最优解x*。4.1常用的搜索算法结构由于非线性规划问题的复杂性，实用中建立下列收敛性概念：2.实用收敛性：定义解集S*={x
2、x具有某种性质}例：S*={x
3、x---g.opt}S*={x
4、x---l.opt}S*={x
5、f(x)=0}S*={x
6、f(x)≤β}(β为给定的实数，称为阈值)4.1常用的搜索算法结构一、收敛性概念：考虑（fs）2.实用收敛
7、性（续）▲收敛性：设解集S*≠，{x(k)}为算法产生的点列。下列情况之一成立时，称算法收敛：1°x(k)∈S*;2°x(k)S*，k，{X(k)}任意极限点∈S*。▲全局收敛：对任意初始点x(1),算法均收敛。局部收敛：当x(1)充分接近解x*时，算法才收敛。4.1常用的搜索算法结构二、收敛速度设算法产生点列{x(k)},收敛到解x*,且x(k)≠x*，k，1.线性收敛：当k充分大时成立。2.超线性收敛：3.二阶收敛：﹥0，是使当k充分大时有4.1常用的搜索算法结构二、收敛速度（续）定理：设算法点列{x(k)}超线性收敛于x*,且x(k)≠x*，k，那么证明只需注意
8、
9、
10、
11、x(k+1)–x*
12、
13、-
14、
15、x(k)–x*
16、
17、
18、≤
19、
20、x(k+1)–x(k)
21、
22、≤
23、
24、x(k+1)–x*
25、
26、+
27、
28、x(k)–x*
29、
30、，除以
31、
32、x(k)–x*
33、
34、并令k→∞，利用超线性收敛定义可得结果。4.1常用的搜索算法结构三、二次终结性▲一个算法用于解正定二次函数的无约束极小时，有限步迭代可达最优解，则称该算法具有二次终结性。▲二次终结性=共轭方向+精确一维搜索。▲共轭方向·定义：设An×n对称正定，d(1),d(2)∈Rn,d(1)≠0，d(2)≠0，满足d(1)TAd(2)=0,称d(1),d(2)关于矩阵A共轭。·共轭向量组：d(1),d(2),…,d(m)∈Rn均
35、非零，满足d(i)TAd(j)=0,(i≠j).4.1常用的搜索算法结构三、二次终结性（续）·当A=I(单位矩阵)时，d(1)TAd(2)=d(1)Td(2)=0，即正交关系。·当d(1),d(2),…,d(m)关于正定矩阵A两两共轭时，d(1),d(2),…,d(m)线性无关。proof:设d=1d(1)+2d(2)+…+md(m)=0，j=1,2,…,m，d(j)TAd=jd(j)TAd(j)=0∵d(j)TAd(j)>0，故j=0，即线性无关。超线性收敛和二次终结性常用来讨论算法的优点。正定4.1常用的搜索算法结构四、下降算法模型考虑（fs）常用一种线性搜索的方
36、式来求解：迭代中从一点出发沿下降可行方向找一个新的、性质有改善的点。△下降方向：设∈S，d∈Rn,d≠0,若存在，使，称d为在点的下降方向。minf(x)s.t.x∈S4.1常用的搜索算法结构四、下降算法模型（续）△可行方向：设∈S，d∈Rn,d≠0,若存在，使，称d为点的可行方向。同时满足上述两个性质的方向称下降可行方向。4.1常用的搜索算法结构模型算法线性搜索求，新点使x(k+1)∈S初始x(1)∈S,k=1对x(k)点选择下降可行方向d(k)是否满足停机条件？停k=k+1yesno4.2一维搜索一元函数求极小及线性搜索均为一维搜索。常用于求：minf(x(k)+d(k))
37、=φ(λ)s.t.λ∈SS有3种情况（-∞，+∞）或（0，+∞）或[a,b]一、缩小区间的精确一维搜索：考虑问题(P)minφ(λ)s.t.λ∈[α,β]φ(λ):R→R1、不确定区间及单峰函数△不确定区间：[α,β]含φ(λ)的最小点，但不知其位置4.2一维搜索一、缩小区间的精确一维搜索（续）定义：设φ：[α,β]→R，λ*∈[α,β]是φ在[α,β]上的最小点，若对任意λ1,λ2,α≤λ1<λ2≤β满足：1º若λ2≤λ*，则φ(λ1)>φ(λ2);2º若λ1≥λ*，则φ(λ1)<φ(λ2).则称φ(λ)在[α,β]上强单峰。若只有当φ(λ1)≠φ(λ*)，φ(λ2)≠φ(λ
38、*)时，上述1º,2º式才成立，则称φ(λ)在[α,β]上单峰。4.2一维搜索一、缩小区间的精确一维搜索（续）若对任意λ1,λ2,α≤λ1<λ2≤β满足：1º若λ2≤λ*，则φ(λ1)>φ(λ2);2º若λ1≥λ*，则φ(λ1)<φ(λ2).则称φ(λ)在[α,β]上强单峰。若只有当φ(λ1)≠φ(λ*)，φ(λ2)≠φ(λ*)时，上述1º,2º式才成立，则称φ(λ)在[α,β]上单峰。αλ*λ1λ2β强单峰αλ*β单峰4.2一维搜索一、缩小区间的精确一维搜索（续）定理：设Ф：R
