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