欢迎来到天天文库
浏览记录
ID:58650783
大小:2.52 MB
页数:18页
时间:2020-10-16
《第二章无约束优化问题的算法.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、授课章节第二章无约束优化问题的算法目的要求常用的线性搜索法;无约束最优化方法重点难点常用的线性搜索法;无约束最优化方法第一节 常用线性搜索法在算法的迭代格式中,在假设迭代点和下降搜索方向为已知的情况下,求步长,使成立。下面介绍几种求步长的算法。一、直接法(0.618法)(求步长)单谷函数(下单峰函数):设为一元函数的极小点,若,当时,必有;当时,必有,则称为单谷函数(一个谷)。1搜索区间的确定:搜索区间的选取采取如下算法—进-退算法:给定初始点,初始步长。(1)计算;(2)若,搜索成功,歩长加倍,若,则,否则步长继续加倍;(3)若,搜索失败,后退步长,若,则,否则继续加倍后退步长。20.61
2、8算法的原理规定解得。由此可得30.618算法Step1确定的初始搜索区间(进-退搜索法)、精度;Step2计算,;Step3计算,;Step4若,则令如果,取,停止计算。否则令,,转Step3,(此时,在新的区间计算);Step5若,则令,如果,取,停止计算。否则令,,计算,,转Step4。注意:与在计算机语言中不是一回事,是一个赋值的过程。一、精确线性搜索法(解析法)求步长,满足。令,设包含的极小值点的搜索区间为,即,在搜索区间内给定三点,且满足,不妨取。令是三点的拟合抛物线,且设是抛物线的极小点,即(如图)结束条件:(1)(2)(3)若较大,上述三条中的任意一条都可以作为终止准则。如果
3、不满足终止条件,取三点,或,继续搜索。一、不精确线性搜索法618法或解析法都可以取到精确近似极小点,每次迭代都可以保证使目标函数是下降的,但计算量大。不精确线性搜索法不够精确但计算量较小。为确保目标函数下降,步长不能太大,同时步长又不能太小,所以给一个限定范围。1Goldstein准则取步长满足下式上式等价于下述两个不等式(2.6)(2.7)等价于等价于注:对上式的理解,可以当是一元函数时的特殊情况去理解。夹在两直线和与曲线相交两点之间的满足条件式(2.6)和(2.7),称其为可接受区间。2Wolfe准则在Goldstein准则中,的极小点在可接受区间以外,为克服这一缺点,Wolfe准则提出
4、一个式(2.7)的替补条件,即(2.9)可接受区间是切线的切点、直线与曲线的交点之间的的取值区间。说明:越小,线性搜索越精确,但计算量大。第二节最速下降法对下降方向的确定。条件:目标函数连续可微,。分析:在点处的一阶泰勒展开为由函数梯度反方向是函数下降最快的方向(由二元函数可以看出),所以令则当满足一定条件时可以保证。说明:(1)这是由于,求步长,使。令,即即。(2)最速下降法收敛速度慢。这是由于,所以相邻两下降方向是相互垂直的,即下降是锯齿形状,越接近极小点,锯齿现象越严重,影响收敛速度。(3)该方法易实现,简单,适用于一次逼近的算法,适用于距离极小点较远时使用,在接近极小点时使用其它有效
5、算法。第三节共轭梯度法利用梯度设为下降方向,建立迭代公式,求最优解的方法。说明:该方法易实现,且储存需求小,适用于大规模优化问题的算法。一、两变量正定二次函数的极小化问题设,且其中为正定矩阵。下面讨论从任意初值点出发,最多经过两步迭代可达到其极小点(最优解)。思路:选取与线性无关的向量,且保证和(这里),推出。分析:任意初值点,令下降方向为,迭代公式,有线性搜索法确定,且满足。假若(最优解),则必有左乘这里要求。由于,得与是线性无关的,所以向量可由和线性表示(因为是二维空间),设左乘得由于是正定矩阵,所以,即得则。可以证明是线性无关的,因为如果线性相关,可由线性表示,,,得和线性相关,矛盾。
6、由线性搜索法得,且满足,由于,可得,即故,即是最优解。以下讨论的是个变量的二次型问题的最优化的问题一、共轭方向的概念与性质1概念:共轭向量组:(1)为阶正定矩阵;(2)为中个非零向量。若则称为共轭向量组(或为正交向量组)。注:当时,共轭性即为通常的正交性。2性质:定理2.2设为为阶正定矩阵,为中个非零向量,且关于两两共轭向量组,则线性无关。证明:设存在一组数,使得成立,用左乘,得,由于是正定的,,即,所以,故线性无关。引理2.1(维直交定理)设为线性无关的维向量,若,且,则。定理2.3设,为任意一组关于两两共轭向量组,则从任意初始点出发,依次沿执行线性搜索,到达至多步迭代得到极小最优解。证明
7、思路:(1)设迭代公式设为;(2)证明。=…这里。是由于在搜索步长时满足,即;是由于为关于两两共轭的向量组。由于,所以,由定理2.2得线性无关,再由引理2.1可得,所以是最优解。三、产生共轭方向的方法利用点的梯度来构造共轭方向。思路:给出,及迭代公式(由)由要求关于两两共轭由迭代公式求出,得出共轭向量。用右乘的转置,得由的正定性,得,所以四、共轭梯度法算法用不同的方法构造出不同的共轭向量组,得到不同的算法,这
此文档下载收益归作者所有