搜索算法结构ppt课件.ppt

搜索算法结构
一、下降算法模型
考虑(NP)
常用一种线性搜索的方式来求解:迭代中从一点出发沿下降可行方向找一个新的、性质有改善的点。迭代计算:
其中为第次迭代的搜索方向, 为沿搜索的最佳步长因子(通常也称作最佳步长)。
min f(x)
. x∈S
第三章常用的一维搜索方法
△可行方向:设∈S,d∈Rn,d≠0,若存在,使,称d 为点的可行方向。
同时满足上述两个性质的方向称下降可行方向。
△下降方向:
设∈S,d ∈Rn,d≠0,若存在,使,称d 为在点的下降方向。
模型算法
线性搜索求,
新点
使x(k+1)∈S
初始x(1) ∈S, k =1
对x(k)点选择下降
可行方向d(k)
是否满足停机条件?
停
k=k+1
yes
no
5
3
1
二、收敛性概念:
考虑(NP)
设迭代算法产生点列{x(k)} S.
1. 理想的收敛性:设x*∈(全局最优解).当x*∈{x(k)} 或 x(k) ≠ x*, k,满足
时,称算法收敛到最优解 x*。
min f(x)
. x∈S
由于非线性规划问题的复杂性,实用中建立下列收敛性概念:
2. 实用收敛性:定义解集
S* = { x | x 具有某种性质}
例:S*={x|x---}
S*={x|x---}
S*={x| f(x)=0}
S*={x|f(x)≤β} (β为给定的实数阈值)
三、收敛速度(续)
定理:设算法点列{x(k)}超线性收敛于x*,且x(k)≠x*, k,那么
证明:只需注意
| ||x(k+1) –x* || -|| x(k) –x* || |≤||x(k+1) –x(k) || ≤||x(k+1) –x* || +|| x(k) –x* || ,除以|| x(k) –x* || 并令k→∞,利用超线性收敛定义可得结果。
该结论导出算法的停止条件可用:
四、二次终结性
▲一个算法用于解正定二次函数的无约束极小时,有限步迭代可达最优解,则称该算法具有二次终结性。