第四章 最优化搜索算法的结构 与 维搜索
第 四 章 最优化搜索算法的结构 与 一维搜索
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∞ 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
41常用的搜索算法结构 、收敛速度(续) 定理:设算法点列{x的超线性收敛于x2,且 xx,k,那么 (k+1)-x ( lim k→ (k) 证明只需注意 +0=x21-1x0-x=x+0-x1≤ x12x10-x1,除x(6-x=并k 利用超线性收的定义可得结果
4.1 常用的搜索算法结构 二、收敛速度（续） 定理：设算法点列{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
41常用的搜索算法结构 二次终结性 个算法用于解正定二次函数的无约束极 小时,有限步选代可达最优解,则称该算 法具有二次终结性。 二次终结性=共轭方向+精确一维搜索。 ▲共轭方向 定义:设Anxn对称正定,d(O, ∈R",d()0,02≠0,满足Ad2称 d),d2关于矩阵A共轭。 共轭向量组:d1)42,…,dm∈Rn均 满足 doTado=0,(i≠)
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 均非零， 满足d (i)TAd(j)=0,(i≠j)
41常用的搜索算法结构 三、二次终结性(续) 当A=1(单位矩阵时,DA2=D2=0,即正 交关系。 当d1),2,…,dm)关于正定矩阵A两两共轭时 1),d2,…,dm)线性无关。 pr00F:设=a1+a2)+…+anmy=0, Vj=1, 2, ., m, doTAd= a dOTAdo=0 d0TAd0>0,故a;=0,即线性无关 超线性收敛和二次终结性常用来讨论算法的优点
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= 1 d (1)+ 2 d (2)+…+ m d (m) =0， j=1,2, …,m， d (j)TAd= jd (j)TAd(j)=0 ∵ d (j)TAd(j) >0，故j =0，即线性无关。 超线性收敛和二次终结性常用来讨论算法的优点。 正定
41常用的搜索算法结构 四、下降算法模型 考虑() in f(r) s.t.x∈s 常用一种线性搜索的方式来求解:选 点出发沿下降可行方向找一个新的、 改善的点。 △下降方向: 设∈S,d∈R",l≠0,若存在δ>0 使f(x+ad)<f(x),∈(0,。),称d为 在、点的下降方向
4.1 常用的搜索算法结构 四、下降算法模型 考虑（fs） 常用一种线性搜索的方式来求解：迭代中从一 点出发沿下降可行方向找一个新的、性质有 改善的点。 △下降方向 ： 设 ∈S，d ∈Rn ,d≠0,若存在 ， 使 ，称d 为 在 点的下降方向。 min f(x) s.t. x∈S _ x 0 ( ) ( ), (0, ) _ _ _ f x+ d f x x
41常用的搜索算法结构 四、下降算法模型(续) △可行方向:设X∈S,d∈Rnd+0,若存 在δ>9 使x+l∈S,V∈(O,),称d 为x点的可行方向 同时满足上述两个性质的方向称 下降可行方向
4.1 常用的搜索算法结构 四、下降算法模型（续） △可行方向：设 ∈S，d∈Rn ,d≠0,若存 在 ， 使 ，称d 为 点的可行方向。 同时满足上述两个性质的方向称 下降可行方向。 _ x _ x 0 , (0, ) _ x+ d S