第三章常用的一维搜索方法 31搜索算法结构 下降算法模型 min fox 考虑() s.t.x∈S d 常用一种线性搜索的方式来求解:迭代中从 点出发沿下降可行方向找一个新的、性 质有改善的点。迭代计算: =x2+2d6,k=0,1,2, 其中d为第k+1次迭代的搜索方向,为沿d k+1 搜索的最佳步长因子(通常也称作最佳步 长) X k
3.1 搜索算法结构 一、下降算法模型 考虑（fs） 常用一种线性搜索的方式来求解：迭代中从 一点出发沿下降可行方向找一个新的、性 质有改善的点。迭代计算： 其中 为第 次迭代的搜索方向， 为沿 搜索的最佳步长因子（通常也称作最佳步 长）。 min f(x) s.t. x∈S 第三章 常用的一维搜索方法 k d k +1 k k d 1 , 0,1,2, k k k k x x d k + = + = k X k+1 X k+2 X k 1 d + k d k 2 d + k k d
△下降方向 设x∈s,d∈R,l+0,若存在δ>0, 使f(x+Ad)O, 使x+Ad∈S,vλ∈(0,),称d为x点的可 行方向 同时满足上述两个性质的方向称下降可行方向
△可行方向：设 ∈S，d∈Rn ,d≠0,若存在 ， 使 ，称d 为 点的可 行方向。 同时满足上述两个性质的方向称下降可行方向。 _ x _ x _ x 0 , (0, ) _ x+ d S △下降方向 ： 设 ∈S，d ∈Rn ,d≠0,若存在 ， 使 ，称d 为 在 点的下 降方向。 0 ( ) ( ), (0, ) _ _ f x+ d f x _ x
●模型算法初始∈Sk=1fx)>f(x)>fx 对x点选择下降 可行方向小 X k=k+1 线性搜索求 新点,k+ 1 使x+)∈S no yes 是否满足停机条件? 停
⚫ 模型算法 线性搜索求 ， 新点 使x (k+1)∈S 初始x (1) ∈S, k =1 对x (k)点选择下降 可行方向d (k) k ( ) ( ) ( 1) ( ) k k k k x = x + d + 是否满足停机条件？ 停 k=k+1 no yes x1 x2 5 3 1 X0 X1 X2 ( ) X0 f ( ) X1 f ( ) X2 f
二、收敛性概念: 考虑(/) min f() s.t.x∈s 设送代算法产生点列{x6}cS 1.理想的收敛性:设x*∈S是g0p(全局最优 解当x∈{或x)≠x,k,满足 lim x(k)=x k一 时,称算法收敛到最优解x
二、收敛性概念： 考虑（fs） 设迭代算法产生点列{x (k) } S. 1. 理想的收敛性：设x*∈S是g.opt(全局最优 解).当x*∈ {x (k) } 或 x (k) ≠ x* ， k，满足 时，称算法收敛到最优解 x* 。 ( ) * lim x x k k = → min f(x) s.t. x∈S
由于非线性规划问题的复杂性,实用中建立下列 收敛性概念: 2.实用收敛性:定义解集 S={x|x具有某种性质} 例:s*={xx-g.0p Sx=lxlr---lopty S*={xWx)=0 Ss=Exlf(x)sB) (B为给定的实数,称为值
由于非线性规划问题的复杂性，实用中建立下列 收敛性概念 ： 2. 实用收敛性：定义解集 S* = { x | x 具有某种性质 } 例：S*={x|x---g.opt} S*={x|x---l.opt} S*={x| f(x)=0} S*={x|f(x)≤β } (β为给定的实数，称为阈值)
2实用收敛性(续) ▲收敛性:设解集S*≠{(}为算法产生的点 列。下列情况之一成立时,称算法收敛 1°x)∈S;←有限步终止 2°)的,Vk,{x的任意极限点eS。 ▲全局收敛:对任意初始点①,算法均收敛。 局部收敛:当x()充分接近解κ时,算法收敛
2.实用收敛性（续） ▲收敛性：设解集S*≠ ，{x (k) }为算法产生的点 列。下列情况之一成立时，称算法收敛： 1°x (k) ∈S*; 2° x (k) S* ， k，{x (k) }的任意极限点∈S* 。 ▲全局收敛：对任意初始点x (1) ,算法均收敛。 局部收敛：当x (1) 充分接近解x*时，算法收敛。 有限步终止
三、收敛速度 设算法产生点列{),收敛到解x,且xx, Vk,关于算法的收敛速度,有 1线性收敛:x=x0,是使当k充分大时有 (k+1) C (k)
三、收敛速度 设算法产生点列{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
、收敛速度(续) 定理:设算法点列{的超线性收敛于x*,且x6)x*, k,那么 (k+ 1)X ( k→>o (k)=X 证明:只需注意 lk+)-x211x()-x|≤|x+)-x(≤|x(+)x2 +x)-x28,除x()-x*1并会x→0,利用超线 性收敛定义可得结果。 该结论导出算法的停止条件可用: x(+)-x6|k公或f(x()-f(x)E
三、收敛速度（续） 定理：设算法点列{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→∞，利用超线 性收敛定义可得结果。 1 || || || || lim ( ) * ( 1) = − − + → x x x x k k (k) k 该结论导出算法的停止条件可用： ( ) 1 ( ) || || k k x x + − ( ) 1 ( ) | ( ) ( ) | k k f x f x + 或 −
四、二次终结性 ▲一个算法用于解正定二次函数的无约束极小 时,有限步迭代可达最优解,则称该算法具 有二次终结性
四、二次终结性 ▲一个算法用于解正定二次函数的无约束极小 时，有限步迭代可达最优解，则称该算法具 有二次终结性
常用的一维搜索算法 问题描述: 已知xk,并且求出了x处的可行下降方向Pk, 从x出发,沿方向酽求如下目标函数的最优解, minf(=+ad")=mind(a) >0 >0 或者选取a>0使得 k=mina>ovi
问题描述： 已知 , k x 并且求出了 k x 处的可行下降方向 , k p 从 k x 出发，沿方向 k d 求如下目标函数的最优解， 或者选取 min min ( ) ( ) k k 0 0 f x d + = 0 k 使得： min 0 0 ( ) T k k k k = + = f x d d 常用的一维搜索算法