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

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

2、继续加倍后退步长。0.618算法的原理规定解得。由此可得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准则中，的极小点在可接受区间以外，为克

4、服这一缺点，Wolfe准则提出一个式 (2.7)的替补条件，即 (2.9)可接受区间是切线的切点、直线与曲线的交点之间的的取值区间。说明：越小，线性搜索越精确，但计算量大。第二节 最速下降法 对下降方向的确定。条件：目标函数连续可微，。分析：在点处的一阶泰勒展开为由函数梯度反方向是函数下降最快的方向（由二元函数可以看出），所以令则当满足一定条件时可以保证。说明：（1）这是由于，求步长，使。令，即即。（2）最速下降法收敛速度慢。这是由于，所以相邻两下降方向是相互垂直的，即下降是锯齿形状，越接近极小点，锯齿现象越严重，影响收敛速度。（3）该方法易实现，简单，适用于一次逼近的算法，适用于距离极小点较

5、远时使用，在接近极小点时使用其它有效算法。第三节 共轭梯度法利用梯度设为下降方向，建立迭代公式，求最优解的方法。说明：该方法易实现，且储存需求小，适用于大规模优化问题的算法。一、 两变量正定二次函数的极小化问题设，且其中为正定矩阵。下面讨论从任意初值点出发，最多经过两步迭代可达到其极小点（最优解）。思路：选取与线性无关的向量，且保证和（这里），推出。 分析：任意初值点，令下降方向为，迭代公式，有线性搜索法确定，且满足。假若（最优解），则必有左乘这里要求。由于，得与是线性无关的，所以向量可由和线性表示（因为是二维空间），设左乘得由于是正定矩阵，所以，即得则。可以证明是线性无关的，因为如果线性相关

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

7、小最优解。证明思路：（）设迭代公式设为；（）证明。这里。是由于在搜索步长时满足，即；是由于为关于两两共轭的向量组。由于，所以，由定理.得线性无关，再由引理.可得，所以是最优解。三、产生共轭方向的方法利用点的梯度来构造共轭方向。思路：给出，及迭代公式（由）由要求关于两两共轭由迭代公式求出，得出共轭向量。用右乘的转置，得由的正定性，得，所以四、共轭梯度法算法用不同的方法构造出不同的共轭向量组，得到不同的算法，这些算法都是利用点的梯度来构造共轭方向，因而称这种算法为共轭梯度法算法（简称共轭梯度算法）。（） 对于正定二次函数的共轭梯度法若令，由上述分析可得正定二次函数的共轭梯度算法公式为其中终止条件.

8、例用共轭梯度算法求解，取初始点为（） 对于非正定二次函数的共轭梯度法略。第四节Newton法及其改进一、 Newton法基本原理Newton法是以二次近似作为基础而提出的非二次函数的优化算法。设是二阶连续可微函数，是无约束极小解，在初值点进行Taylor二阶展开，求出展开的二次函数极小点，在进行二阶Taylor展开，求出展开的二次函数极小点，得出一系列极小点去逼近的极小解。设在处的二阶Taylor展开，得近似二次函数，即其中，若令，则，若正定（对称），则有由极值必要条件知，即。称Newton迭代公式，的解为Newton方向。当初始点与最优解很近且正定时迭代公式以二次收敛速度收敛于最优解，但很难

9、检验是否接近，所以很难保证方向是下降方向。二、 改进Newton法算法1对强迫正定分解设是对称正定矩阵，则可唯一分解为其中是对角矩阵，对角线元素恰是的特征根，矩阵是单位下三角矩阵。在实际计算中，由于误差积累，可能出现计算结果，为此Gill-Murray提出了一种强迫正定分解法，即对一般对称矩阵，存在单位下三角矩阵和正定对角矩阵，使得,其中是对角矩阵。当对角矩阵充分正定时，。所谓充分正定是指的特征根的绝对值足够大，避免出现由于误差积累。（强迫正定分解法我们不讲，计算公式参看教材P58）2改进Newton法算法设，对进行强迫正定分解，得，令下降方向为的解，得，得到迭代公式为（这里称为阻尼因子，即步

10、长），由线性搜索法得到步长。当时，终止迭代。3负曲率方向算法 负曲率方向：若在处的梯度，而Hesse矩阵至少有一个负根，即存在一个向量（方向）满足，称方向为负曲率方向。设在处的梯度，Hesse矩阵即不正定也不负定（鞍点），由二阶Taylor展开（）设的负曲率方向，满足，且当足够小时有。由此可见：（1）对于负曲率方向，满足,与都是下降方向（如图）；（2）对于方向，满足，则是下降方向；（3）对于方向，满足，则是下降方向.三、Newton法的主要特征（1）Newton法应用于具有正定Hesse矩阵的二次函数时，只需一次迭代即可达到无约束优化问题的全局极小解，计算法具有二次收敛；（2）当初始点接近极小

11、解时，Newton法产生的迭代序列以二阶收敛的速度趋于问题的平稳点，但当初始点远离极小解时，Hesse矩阵可能是奇异的，Newton方向不存在，或者Hesse矩阵不正定，不是下降方向，此时需要使用改进的Newton法，其收敛速度大大降低。（3）Newton法对于目标函数要求高（二阶连续可微），且需较多的存储单元，每次迭代均要进行矩阵求逆的运算。（4）当Hesse矩阵不定时，可采取强迫矩阵正定分解策略，利用负曲率方向作为搜索方向。由此可见，改进Newton法保留了Newton法的一些优点，也克服了Newton法及其阻尼Newton法的一些不足，因此改进Newton法数值稳定，具有较快的收敛速度。

12、第五节 拟Newton法（变尺度法）（简述）拟Newton法的优势是吸收了Newton法的收敛速度快的特点，仅仅利用目标函数以及一阶可导的信息，由近似Newton方向建立迭代公式，该方法被认为是无约束优化问题（中小规模）问题中最有效的算法。一、 拟Newton法的迭代格式迭代格式：Step1：输入初始点，初始对称正定矩阵；Step2：确立搜索方向；Step3：线性搜索步长，满足；Step：修正；Step：迭代公式注：拟Newton法是一族算法，每一种构造的算法都是一种特殊的拟Newton法。二、 构造的原则1拟Newton条件令，且有中值定理有得令，则(由于是对称的，所以要求也是对称的，同理也

13、是对称的)。方程称为拟Newton方程或拟Newton条件。注：用该方法求出的近似解较少运算过程中的储存，而保留了Newton法的收敛速度快的优点。三、 构造的具体过程（1）DFP变尺度算法迭代公式由及可得，即令，其中,得由于，是数值，则所以令与则得迭代校正矩阵公式为（2）BFGS变尺度算法迭代公式 若令，完全类似可以推出（实际上就是中与互换一下位置），从而拟Newton方程变为，由该方程计算出，再导出得其中，或写成注：1理论上公式BFGS法和DFP法的迭代公式是相同的，由和应该产生相同的序列，但由于我们进行的都是线性搜索近似计算得出的结果，所以实际上是不同的，经验显示BFGS法明显优于DFP法，这也是我们经常遇到的现象，看是完全相同的计算法，只是计算顺序或计算公式稍加改变，得到的算法（结果）却不同。2通常设,令，线性搜索得到步长，得，得和，求的,作调整，令作为新的初始值，使满足条件，得， 。例1考虑无约束优化问题取初始点,精度，试用拟Newton法（BFGS法和DFP法）求该解问题。解：梯度采取精确线性搜索，由得步长公式为这里。1 DFP法求。得，修正矩阵, 赋值（让初值更接近）,由DFP法的迭代公式得，,由于，至此已满足终止准则，终止计算，得到问题