资源描述：
《运筹学与最优化方法第4章ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第四章最优化搜索算法的结构与一维搜索4.1常用的搜索算法结构一、收敛性概念：考虑（fs）设迭代算法产生点列{x(k)}S.1.理想的收敛性：设x∈S是g.opt.当x∈{x(k)}或x(k)≠x，k，满足时，称算法收敛到最优解x。4.1常用的搜索算法结构由于非线性规划问题的复杂性，实用中建立下列收敛性概念：2.实用收敛性：定义解集S={xx具有某种性质}例：S={xx---g.opt}S={xx---l.opt}S={xf(x)=0}S={xf(x)≤β}(β为给定的实数，称为阈值)4.1常用的搜索算法结构一、收敛性概念：考虑（fs）2.实
2、用收敛性（续）▲收敛性：设解集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，
3、k，那么证明只需注意x(k+1)–x-x(k)–x≤x(k+1)–x(k)≤x(k+1)–x+x(k)–x，除以x(k)–x并令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均非零，
4、满足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常用的搜索算法结构四、下降算法模型考虑
5、（fs）常用一种线性搜索的方式来求解：迭代中从一点出发沿下降可行方向找一个新的、性质有改善的点。△下降方向：设∈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一维搜索一元函数求极小及线
6、性搜索均为一维搜索。常用于求：minf(x(k)+d(k))=φ(λ)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)<φ(λ
7、2).则称φ(λ)在[α,β]上强单峰。若只有当φ(λ1)≠φ(λ)，φ(λ2)≠φ(λ)时，上述1º,2º式才成立，则称φ(λ)在[α,β]上单峰。4.2一维搜索一、缩小区间的精确一维搜索（续）若对任意λ1,λ2,α≤λ1<λ2≤β满足：1º若λ2≤λ，则φ(λ1)>φ(λ2);2º若λ1≥λ，则φ(λ1)<φ(λ2).则称φ(λ)在[α,β]上强单峰。若只有当φ(λ1)≠φ(λ)，φ(λ2)≠φ(λ)时，上述1º,2º式才成立，则称φ(λ)在[α,β]上单峰。αλλ1λ2β强单峰αλβ单峰4.2一维搜索一、缩小区间的精确一维搜索（续）定理：设
8、Ф：R→R在[α，β]上单峰，α≤λ＜μ≤β。那么1°若Ф(λ)≥Ф(μ)，则Ф(ρ)≥Ф(μ)，ρ∈[α，λ]；如左下图2°若Ф(λ
