第二章无约束优化问题的算法.doc

《第二章无约束优化问题的算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、授课章节第二章无约束优化问题的算法目的要求常用的线性搜索法；无约束最优化方法重点难点常用的线性搜索法；无约束最优化方法第一节　常用线性搜索法在算法的迭代格式中，在假设迭代点和下降搜索方向为已知的情况下，求步长，使成立。下面介绍几种求步长的算法。一、直接法（0.618法）（求步长）单谷函数（下单峰函数）：设为一元函数的极小点，若，当时，必有；当时，必有，则称为单谷函数（一个谷）。１搜索区间的确定：搜索区间的选取采取如下算法—进-退算法：给定初始点，初始步长。(1)计算；(2)若，搜索成功，歩长加倍，若，则，否则步长继续加倍；(3)若，搜索失败，后退步长，若，则，否则继续加倍后退步长。２0.61

2、8算法的原理规定解得。由此可得３0.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、由线性搜索法得，且满足，由于，可得，即故，即是最优解。以下讨论的是个变量的二次型问题的最优化的问题一、共轭方向的概念与性质１概念：共轭向量组：（１）为阶正定矩阵；（２）为中个非零向量。若则称为共轭向量组（或为正交向量组）。注：当时，共轭性即为通常的正交性。２性质：定理２.２设为为阶正定矩阵，为中个非零向量，且关于两两共轭向量组，则线性无关。证明：设存在一组数，使得成立，用左乘，得，由于是正定的，，即，所以，故线性无关。引理２.１（维直交定理）设为线性无关的维向量，若，且，则。定理２.３设，为任意一组关于两两共轭向量组，则从任意初始点出发，依次沿执行线性搜索，到达至多步迭代得到极小最优解。证明

7、思路：（１）设迭代公式设为；（２）证明。＝…这里。是由于在搜索步长时满足，即；是由于为关于两两共轭的向量组。由于，所以，由定理２.２得线性无关，再由引理２.１可得，所以是最优解。三、产生共轭方向的方法利用点的梯度来构造共轭方向。思路：给出，及迭代公式（由）由要求关于两两共轭由迭代公式求出，得出共轭向量。用右乘的转置，得由的正定性，得，所以四、共轭梯度法算法用不同的方法构造出不同的共轭向量组，得到不同的算法，这