第三章常用的一维搜索方法 3.1搜索算法结构 一、下降算法模型 minf) 考虑(NP) s.t.xES k+2 常用一种线性搜索的方式来求解：迭代中从 一点出发沿下降可行方向找一个新的、性 Y+ 质有改善的点。迭代计算： xk+1=x+入d,k=0,1,2,… 其中d为第k+1次迭代的搜索方向，2为沿d 搜索的最佳步长因子（通常也称作最佳步 长)
3.1 搜索算法结构 一、下降算法模型 考虑（NP） 常用一种线性搜索的方式来求解：迭代中从 一点出发沿下降可行方向找一个新的、性 质有改善的点。迭代计算： 其中 为第 次迭代的搜索方向， 为沿 搜索的最佳步长因子（通常也称作最佳步 长）。 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",d0,若存在δ>O, 使f(x+2.d)O, 使x+入l∈S,V入∈(O,δ)，称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
模型算法 初始x∈S,k=1 f(X)>f(X)>f(X,) X 对x点选择下降 k=k+1 可行方向 线性搜索求2>0 新点 x*+=x+2d 使xk+1)∈S no yes 是否满足停机条件？ 停
⚫ 模型算法 线性搜索求 ， 新点 使x (k+1)∈S 初始x (1) ∈S, k =1 对x (k)点选择下降 可行方向d (k) k 0 ( ) ( ) ( 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
二、收敛性概念： 考虑(NP) min fx s.t,x∈S 设迭代算法产生点列xcS. 1.理想的收敛性：设x*∈S是g.op(全局最优 解)当x*∈{x或xk)≠x*,k,满足 lim x()=x k>o∞ 时，称算法收敛到最优解x*
二、收敛性概念： 考虑（NP） 设迭代算法产生点列{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*={xx具有某种性质} 例：S*={xx-g.0p S*={xx---L.opty S*=x!x)=) S*=x)s}(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*≠◆，{x为算法产生的点 列。下列情况之一成立时，称算法收敛： 1°3xk)∈S*; ←有限步终止 2°x)图*，Vk,{xk的任意极限点x*∈S*。 ▲全局收敛：对任意初始点x,算法均收敛。 局部收敛：当x山)充分接近解x*时，算法收敛
2.实用收敛性（续） ▲收敛性：设解集S*≠ ，{x (k) }为算法产生的点 列。下列情况之一成立时，称算法收敛： 1°x (k) ∈S*; 2° x (k) S* ， k，{x (k) }的任意极限点x* ∈S* 。 ▲全局收敛：对任意初始点x (1) ,算法均收敛。 局部收敛：当x (1) 充分接近解x*时，算法收敛。 有限步终止
三、收敛速度 设算法产生点列x收敛到解x*,且xkx*,Vk, 关于算法的收敛速度，有 1线性收敛： x+”-x儿0,是使当充分大时有 llD-x*l ≤d llx-x"112
三、收敛速度 设算法产生点列{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超线性收敛于x*,且xx*, Vk,那么 lim 【x+-xⅡ=1 k→ lxk)-x*Ⅱ 证明：只需注意 1+)-x‖-lxW-x*‖1≤x+)-xW‖≤lx+)-x0 +x-x*‖，除财x因-x*‖并令北→oo,利用超线 性收敛定义可得结果。 该结论导出算法的停止条件可用： Ixk+)-xIKε或1f(x+)-f(x)K6
三、收敛速度（续） 定理：设算法点列{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 + 或 −
四、二次终结性 ▲一个算法用于解正定二次函数的无约束极小 时，有限步迭代可达最优解，则称该算法具 有二次终结性
四、二次终结性 ▲一个算法用于解正定二次函数的无约束极小 时，有限步迭代可达最优解，则称该算法具 有二次终结性
例3.3.1.目标函数f(c)=x2,初始点xo)=2,下降方向p()=(-1)+1 步长k=2+2,迭代产生的点列见图33.1(a. 例3.3.2.目标函数f()=2,初始点xo)=2,下降方向p()=-1,步 长=24，迭代产生的点列见图3.3.1(b). f(x)3 f(x)3 2.5 2.5 (x④，fx》 (x,fx®)4 2 2 (xf() 1.5 1.5 (x,fx》 (,f(x) (.f(x) 1(x,fx) x9,f)（,f) 0.5 0.5 01 2 -1.5 1 -0.5 0 0.5 1.5 2 2 1.5 .1 0.5 0 0.5 1.5 2 (a)步长相对于目标值的下降量太长 (b)步长相对于目标值的下降量太短