《第4章 最优化搜索算法的结构与一维搜索》由会员分享，可在线阅读，更多相关《第4章 最优化搜索算法的结构与一维搜索（31页珍藏版）》请在金锄头文库上搜索。
1、1,第 四 章,最优化搜索算法的结构与一维搜索,2,4.1 常用的搜索算法结构,一、收敛性概念： 考虑（fs） 设迭代算法产生点列x(k) S.1. 理想的收敛性：设x*S是g.opt.当x* x(k) 或 x(k) x*， k，满足 时，称算法收敛到最优解 x*。,3,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) (为给定的实数，称为阈值),4,4.1 常用的搜索算法结构,一、收敛性概念：
2、考虑（fs）2.实用收敛性（续）收敛性：设解集S* ，x(k)为算法产生的点列。下列情况之一成立时，称算法收敛： 1x(k) S*; 2x(k) S*， k，X(k)任意极限点S* 。 全局收敛：对任意初始点x(1),算法均收敛。 局部收敛：当x(1) 充分接近解x*时，算法才收敛。,5,4.1 常用的搜索算法结构,二、收敛速度 设算法产生点列x(k),收敛到解x*,且x(k)x*， k，1.线性收敛： 当k充分大时成立。2.超线性收敛： 3.二阶收敛： 0，是 使当k充分大时有,6,4.1 常用的搜索算法结构,二、收敛速度（续）定理：设算法点列x(k)超线性收敛于x*,且x(k)x*， k，
3、那么证明只需注意| |x(k+1) x* | -| x(k) x* | | |x(k+1) x(k) | |x(k+1) x* | +| x(k) x* | ，除以| x(k) x* | 并令k，利用超线性收敛定义可得结果。,7,4.1 常用的搜索算法结构,三、二次终结性一个算法用于解正定二次函数的无约束极小时，有限步迭代可达最优解，则称该算法具有二次终结性。二次终结性=共轭方向+精确一维搜索。共轭方向 定义： 设 Ann 对称正定，d (1),d (2) Rn , d (1) 0，d(2) 0，满足d(1)TAd(2)=0, 称d(1),d(2) 关于矩阵A共轭。 共轭向量组：d(1),d(
4、2), ,d(m) Rn 均非零，满足d(i)TAd(j)=0,(ij) .,8,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)+ 2d(2)+ md(m) =0， j=1,2, ,m， d(j)TAd= jd(j)TAd(j)=0 d(j)TAd(j) 0，故j =0，即线性无关。 超线性收敛和二次终结性常用来讨论算法的优点。,9,4.1 常用的搜索算法结构,
5、四、下降算法模型 考虑（fs） 常用一种线性搜索的方式来求解：迭代中从一点出发沿下降可行方向找一个新的、性质有改善的点。下降方向 ： 设 S，d Rn,d0,若存在 ，使 ，称d 为 在 点的下降方向。,10,4.1 常用的搜索算法结构,四、下降算法模型（续）可行方向：设 S，dRn,d0,若存在 ，使 ，称d 为 点的可行方向。同时满足上述两个性质的方向称下降可行方向。,11,4.1 常用的搜索算法结构,模型算法,线性搜索求 ，新点使x(k+1)S,yes,no,12,4.2 一维搜索,一元函数求极小及线性搜索均为一维搜索。常用于求： min f(x(k)+ d(k)=() s.t. S S
6、有3种情况（-，+）或（0， + ）或a,b一、缩小区间的精确一维搜索：考虑问题(P) min () s.t. , ():RR1、不确定区间及单峰函数 不确定区间： , 含()的最小点，但不知其位置,13,4.2 一维搜索,一、缩小区间的精确一维搜索（续）定义：设： , R， * , 是在, 上的最小点 ，若对任意1 ,2, 1 (2); 2 若1 * ，则(1) (2).则称()在, 上强单峰。 若只有当(1) (* )， (2) (* )时，上述1, 2 式才成立，则称()在, 上单峰。,14,4.2 一维搜索,一、缩小区间的精确一维搜索（续）若对任意1 ,2, 1 (2); 2 若1 *
7、 ，则(1) (2).则称()在, 上强单峰。 若只有当(1) (* )， (2) (* )时，上述1, 2 式才成立，则称()在, 上单峰。,15,4.2 一维搜索,一、缩小区间的精确一维搜索（续）定理：设：RR 在， 上单峰， 。那么 1若() ()，则() ()， ，；如左下图 2若() ()，则()()， ， ；如右下图,16,4.2 一维搜索,一、缩小区间的精确一维搜索（续）Proof. 1反证：设* ,为最小点，,及*，使 () ( ) ()，矛盾（假设）； 若* ,），由定义及 *， ( ) (), 矛盾（条件）； 于是结论成立。 2 的证明类似（略）。注：上述定理为缩短区间的算
8、法提供了理论根据。,17,4.2 一维搜索,一、缩小区间的精确一维搜索（续）2、黄金分割法（0.618 法）通过上述定理，选二点0 时， 在上升段， * ，去掉, ； () ，去掉 , ；(自己画算法框图),21,4.2 一维搜索,4、进退法求初始不确定区间 找三点使两端点的函数值大于中间点的函数值。 思路：任取0，步长 0，取1=0 + ， 1若(0 ) (1), 令=2 （步长加倍），2=0 - ， 若(2 )(0),则停，= 2，= 1 (图1) 2若(0 )(1), 令=2 , 2=1 + ， 若(2 )(1),则停，= 0 ，= 2 (图2),22,4.2 一维搜索,4、进退法求初始
9、不确定区间（续）（自己画算法框图）注意：1 选择要适当。（太大含多个单峰区间，太小迭代次数增加）； 2（ ）单调时无结果，（加迭代次数限制）； 3可与中点法结合寻找单调区间（思考）。,23,4.2 一维搜索,二、牛顿法（Newton）和插值法1、Newton法： 对 在 k 点展开： ( )= (k )+ (k )(- k ) + (1/2) (k )(- k )2 + o (- k )2 取二次式（略去高阶项）： qk() = (k) +(k)(-k) + (1/2)(k)(-k)2,24,4.2 一维搜索,二、牛顿法（Newton）和插值法1、Newton法：（续） 用qk()作为()的近似，当(k) 0时，其驻点为极小点： qk()= (k) +(k)(- k )=0 得 k +1=k (k) /(k) 取k +1为新的迭代点。以上过程即Newton法。特点：二阶、局部收敛。 （算法框图见下页）,
