第四章 最优化搜索算法的结构 与 维搜索
第 四 章 最优化搜索算法的结构 与 一维搜索
41常用的搜索算法结构 收敛性概念:考虑() 设选代算法产生点列}sS 1.理想的收敛性:设κ*∈S是g,op:当 x∈{x}或x≠x,Vk,满足 lim xk=x 时,称算法收敛到最优解x
4.1 常用的搜索算法结构 一、收敛性概念： 考虑（fs） 设迭代算法产生点列{x (k)} S. 1. 理想的收敛性：设x*∈S是g.opt.当 x*∈ {x (k)} 或 x (k) ≠ x* ， k，满足 时，称算法收敛到最优解 x* 。 ( ) * lim x x k k = →
41常用的搜索算法结构 由于非线性规划问题的复杂性,实用中建立下 列收敛性概念 2.实用收敛性:定义解集 S*={x|x具有某种性质} 例:s*={xx--g.op} S*=xlx---Lopty S={x(x)=0} Sw={xf(x)≤f (B为给定的实数,称为值
4.1 常用的搜索算法结构 由于非线性规划问题的复杂性，实用中建立下 列收敛性概念 ： 2. 实用收敛性：定义解集 S* = { x | x 具有某种性质 } 例：S*={x|x---g.opt} S*={x|x---l.opt} S*={x| f(x)=0} S*={x|f(x)≤β } (β为给定的实数，称为阈值)
41常用的搜索算法结构 收敛性概念:考虑()2实用收敛性(续) ▲收敛性:设解集*≠如,{为算法产生 的点列。下列情况之一成立时,称算法收 敛 1°3x)∈S; 2°x(),Vk,{X任王意极限点∈S。 ▲全局收敛:对任意初始点x,算法均收敛。 局部收敛:当地①充分接近解x时,算法 才收敛
4.1 常用的搜索算法结构 一、收敛性概念： 考虑（fs）2.实用收敛性（续） ▲收敛性：设解集S*≠ ，{x (k)}为算法产生 的点列。下列情况之一成立时，称算法收 敛： 1°x (k) ∈S*; 2° x (k) S* ， k，{X(k)}任意极限点∈S* 。 ▲全局收敛：对任意初始点x (1) ,算法均收敛。 局部收敛：当x (1) 充分接近解x*时，算法 才收敛。
41常用的搜索算法结构 收敛速度 设算法产生点列{),收敛到解x,且xx*, Vk 1线性收敛:x-x<1当k充分大时成立。 2超线性收敛 lin∥x( 0 k→>∞ X X 3二阶收敛:彐a>0,是使当k充分大时有 x (k+1) (k) 水 X
4.1 常用的搜索算法结构 二、收敛速度 设算法产生点列{x (k) },收敛到解x*,且x (k)≠x* ， k， 1.线性收敛： 当k充分大时成立。 2.超线性收敛： 3.二阶收敛： ﹥0，是 使当k充分大时有 0 || || || || lim ( ) * ( 1) * = − − + → x x x x k k k − − + ( ) * 2 ( 1) * || || || || x x x x k k 1 || || || || ( ) * ( 1) * − − + x x x x k k