5 常用无约束最优化方法

最速下降法Newton法修正Newton法共轭方向法共轭梯度法变尺度法坐标轮换法单纯形法（5.1）成立．点就是问题（5.1）的全局最优点．但是，大多数最优化方法只能求到局部最优点．这个矛盾对于实际问题来讲一般容易解决，因为根据问题的实际意义多半可以直接判定用优化方法求出的局部最优解是否为全局最优解．但在理论上这是个比较复杂的问题，本书不涉及．其中．这个问题的求解是指，在点，使得对于任意的都有（5.2）无约束优化方法是优化技术中极为重要,它不仅可以直接用来求解无约束优化问题，而且很多约束优化问题也常将其转化为无约束优化问题，然后用无约束优化方法来求解．同时，有些无约束优化方法只需略加处理，即可用于求解约束优化问题．无约束优化理论发展较早，比较成熟，方法也很多，新的方法还在陆续出现．把这些方法归纳起来可以分成两大类：一类是仅用计算函数值所得到的信息来确定搜索方向，通常称它为直接搜索法，简称为直接法，另一类需要计算函数的一阶或二阶导数值所得到的信息来确定搜索方向，这一类方法称为间接法（或解析法）．直接法不涉及导数和Hesse矩阵，适应性强，但收敛速度一般较慢；间接法收敛速度一般较快，但需计算梯度，甚至需要计算Hesse矩阵．一般的经验是，在可能求得目标函数导数的情况下还是尽可能使用间接方法；相反，在不可能求得目标函数的导数或根本不存在导数的情况下，当然就应该使用直接法．5.1最速下降法为求问题（5.1）的最优解，按最优化算法的基本思想是从一个给定的初始点出发，通过基本迭代公式，按照特定的算法产生一串点列最速下降法基本原理在基本迭代公式中，每次迭代搜索方向取为目标函数的负梯度方向，即每次迭代的步长取为最优步长，由此所确定的算法称为最速下降法．在第二章中，我们曾经提到，对于函数，其函数值下降最快的方向是该函数的负梯度方向。

对于问题（5.1），假定我们已经迭代了k次，获得了第k个迭代点X出发，可选择的下降方向很多，一个非常自然的想法是沿最速下降方向（即负梯度方向）进行搜索应该是有利的，至少在邻近的范围内是这样．因此，取搜索方向为:进行一维搜索，由此得到第k+1个迭代点，即因子由来确定。，就可以得到一个点列（初始点可任意选择）。当函数满足一定的条件时，数的极小点。为书写方便，记．在不发生混淆时，再记迭代步骤已知目标函数及其梯度，终止限（3）用终止准则检测是否满足：若满足，则打印最优解（5.4）可以推出显式迭代公式．设第k次迭代点为X，我们来求Xk+1的表达式．对式（5.4）关于X求梯度，有（5.5）因此，（5.6）现在从X作直线搜索以确定Xk+1，于是(5.7)其中t是最优步长因子．又因可得由此解出（5.8）例5.1试用最速下降法求函数的极小点．迭代两次，计算各迭代点的函数值，梯度及其模，并验证相邻两个搜索方向是正交的．设初始点有关说明最速下降法的优点是算法简单，每次迭代计算量小，占用内存量小，即使从一个不好的初始点出发，往往也能收敛到局部极小点，但它有一个严重缺点就是收敛速度慢．沿负梯度方向函数值下降很快的说法，容易使人们产生一种错觉，认为这一定是最理想的搜索方向，沿该方向搜索时收敛速度应该很快，然而事实证明，梯度法的收敛速度并不快．特别是对于等值线（面）具有狭长深谷形状的函数，收敛速度更慢．其原因是由于每次迭代后下一次搜索方向总是与前一次搜索方向相互垂直，如此继续下去就产生所谓的锯齿现象．即从直观上看，在远离极小点的地方每次迭代可能使目标函数有较大的下降，但是在接近极小点的地方，由于锯齿现象，从而导致每次迭代行进距离缩短，因而收敛速度不快．5.2Newton法如果目标函数在上具有连续的二阶偏导数，其Hesse矩阵正定并且可以表达成为显式（记，那么可以使用下述的Newton法．这种方法一旦用好，收敛速度是很快的．它是一维搜索Newton切线法的推广．基本原理为寻求收敛速度快的算法,在应用基本迭代公式中一个适当的二次函数来近似该点处的目标函数，由此用点指向近似二次函数极小点的方向来构造搜索方向其中二阶可导，Hesse矩阵正定．不妨设经过次迭代已获点，现将显然是二次函数，并且还是正定二次函数，所以是凸函数且存在唯一全局极小点．为求此极小点，令（5.9）对照基本迭代公式,易知，式（5.9）中的搜索方向方向是直指点处近似二次函数的极小点的方向．此时称此方向为从点出发的Newton方向．从初始点开始，每一轮从当前迭代点出发，沿Newton方向并取步长的算法称为Newton法．迭代步骤已知目标函数及其梯度，Hesse矩阵（1）选定初始点；计算（3）由方程解出例5.2试用Newton法求的极小点，初始点取为由迭代公式（5.9）得第1迭代点为由此，停止迭代得对于目标函数是非二次函数的非约束最优化问题，一般来说，用Newton法通过有限轮迭代并不能保证可求得最优解．但由于目标函数在最优解附近能近似于二次函数，因此当先取接近于最优解的初始点使用Newton法求解时，其收敛速度一般是较快的．从例5.2我们看到，用Newton法求解，只经一轮迭代就得到最优解．这一结果并不是偶然的，因为从Newton方向的构造我们知道，对于正定二次函数，Newon方向就是指向其极小点的方向．因此，用Newton法解目标函数为正定二次函数的无约束最优化问题，只需一次迭代就可得最优解．事实上，可以证明在初始点离最优解不远的条件下，Newton法是二次收敛的．但是当初始点选得离最优解太远时，Newton法并不一定是收敛的方法，甚至连其下降性也很难保证．有关说明Newton法收敛速度非常快具有二次收敛的优点，但它存在下面四个严重的缺点：（1）尽管每次迭代不会使目标函数上升，但仍不能保证下降．当Hesse矩阵非正定时，Newton法的搜索将会失败．（2）对初始点要求严格．一般要求比较接近或有利于接近极值点，而这在实际计算中是比较难办的．（3）在进行某次迭代时可能求不出搜索方向．由于搜索方向为,若目标函数在Hesse矩阵是奇异的，则不存在，因而不能构成newton方向，从而使迭代无法进行．（4）newton方向构造困难，计算相当复杂，除了求梯度以外还需计算Hesse矩阵及其逆矩阵直线搜索方法,无约束优化方法,约束优化方法，占用机器内存相当大．5.3拟Newton法基本原理为了克服Newton法的缺点，人们保留选取Newton方向作为搜索方向，摒弃其步长恒取1，而用一维搜索确定最优步长，由此产生的算法称为修正Newton法（或阻力Newton法）．迭代步骤已知目标函数及其梯度，Hesse矩阵，停止迭代输出，否则转（3）．（4）进行一维搜索．求，使得修正Newton法克服了Newton法的缺点．特别是，当迭代点接近于最优解时，此法具有收敛速度快的优点，对初始点的选择要求不严．但是，修正Newton法仍需要计算目标函数的Hesse矩阵和逆矩阵，所以计大．另外，当目标函数的Hesse矩阵在某点处出 现奇异时，迭代将无法 进行，因此修正Newton 法仍有相当的局限性． 有关说明 5.4共轭方向法 不同最优化方法，取决于基本迭代公式中确定搜索方 向的构造． 最速下降法， ，导致搜索路线出现锯齿状， 收敛速度降低； ，收敛速度虽很快，但计算量很大，特别是还要求Hesse矩阵正定，从而导 致该算法对初始点选择要求过严． 下面介绍共轭方向法，该方法计算量小，收敛速度没 有Newton法快，但比最速下降法快得多。

基本原理首先介绍共轭方向概念及其些性质． 定义5.1 是对称正定矩阵．对于非零向量，若有 （5.10） 相互共轭或 正交的． 对于非零向量组，若有 共轭方向组或正交方向组，也 称它们是一组 的共轭方向． ．由此可知，共轭概念是正交概念的推广，共轭方向是正交方向的推广． 是正定矩阵，是非零 向量．若 是一组 共轭方向，则它们是线性 无关的． 证明：设有一组实数，使得 依次以左乘上式得到 （5.12）因为 是一组 的共轭方向，故有 又由于A是正定矩阵，所以对于， 由此是线性无关． min（5.13） 有如下性质： 定理 5.2设 是对称正定矩阵， 是一组 的共轭方向．对于问题（5.13），若从任意 出发依次沿进行一维搜索，则至 多经过 轮迭代，可得问题（5.13）的最优解． 通常，我们把从任意点出发，依次沿某组共轭 方向进行一维搜索的求解最优化问题的方法，叫做共 轭方向法． 算法形成为了直观起见，考虑形式为（5.13）的二元二次函数． 任选初始点 出发沿某个下降方向 作一维搜索得到 （5.20）且向量 所在的直线必与某条等值线（椭圆）相切于 下一次迭代，若按最速下降法选择负梯度方向作为搜索方向，则将发生锯齿现象，为了克服这种现象，我们设 想，若下一次迭代的搜索方向能直指极小点 ，那么对 于二元二次函数只须顺次进行两次直线搜索就可以求到 极小点了．这样的方向是否存在？若存在，应该满足什 么条件？怎样确定？ 因为直接指极小点 ，所以可写成 （5.21）其中 是最优步长因子，显然，当 （5.22）因为 是极小点，所以有 等式两边同时左乘，并结合式（5.20）和 （5.23）这就是为 使直指极小点所必须满足的条件．显然式 （5.23）中 下面来求的表达式，设 （5.24）式(5.24)两边同时左乘 一般地，在n维空间中可以找出n个互相共轭的方向，对于n元正定二次函数，从任意初始点出发，顺次沿 这n个共轭方向最多作n次直线搜索就可以求得目标函 数的极小点．这就是共轭方向法的算法形成的基本思 对于n元正定二次目标函数，从任意初始点出发，如果经过有限次迭代就能够求得极小点，那末这种算法称 为具有二次终止性．例如Newton法对于二次函数只须 经过一次迭代就可以求得极小点，因此是二次终止的； 而最速下降法不具有二次终止性．共轭方向法（包括 共轭梯度法，变尺度法等）是二次终止的．一般来说， 具有二次终止性的算法，在用于一般函数时，收敛速 度较快． 迭代步骤已知具有正定矩阵 的二次目标 函数 和终止 （1）选定初始点和具有下降 的方向 若满足，则打印，结束；否 （4）提供共轭方向使得 5.5共轭梯度法 如果在共轭方向法中初始的共轭向量 恰好取为初始点 处的负梯度 ，而以下各共轭方向 迭代点处的负梯度 与已经得到的共轭向量 性组合来确定，那么就构成了一种具体的共轭方向法．因为每一个共轭向量都是依赖于迭代点处的负梯度 而构造出来的，所以称为共轭梯度法． 基本原理设从任意点 出发，第一个搜索方向取为 当搜索得到点后，设以下按 为了使选择所产生的 共轭，以右乘上式的两边，于是有 式（5.25）中含有问题（5.13）的目标函数系数矩阵，这对于目标函数是非二次函数的问题是不方便的．通 过简化，一般可以利用目标函数的梯度信息，来产生 n个共轭方向 迭代步骤已知目标函数 ，终止限 （1）选取初始点，给定终止限 ，停止迭代输出 ，否则转（3）． （4）进行一维搜索．求使得 ，停止迭代输出 ．否则转（6）． 例5.3用共轭梯度法求 其中，选初始点为 4.76732 0.0014 72 9.5799 有关说明实际上，可以把共轭梯度法看作是最速下降法的一 种改进．当 时，就变为最速下降法． 共轭梯度法由于不涉及矩阵，仅仅存储向量，因而存储量小，适合于维数较高的优化问题． 另外，共轭梯度法不要求精确的直线搜索．但是， 不精确的直线搜索可能导致迭代出来的向量不再共 轭，从而降低方法的效能．克服的办法是，重设初 始点，即把经过n次迭代得到的X 作为初始点重新迭代． 5.6变尺度法 我们知道Newton法最突出的优点是收敛速度快，在这 一点上其它算法无法比拟的．因此，建议凡是Hesse矩 阵比较容易求出的问题尽可能使用Newton法求解．然 而Newton法还有一个严重缺陷，就是每次迭代都要计 算目标函数的Hesse矩阵和它的逆矩阵，当问题的维数 较大时，计算量迅速增加，从而就抵消了Newton法的 优点．为此，人们开始寻找一种算法既可以保持 Newton法收敛速度快的优点，又可以摆脱关于Hesse矩 阵的计算，这就是本节要给大家介绍的变尺度算法． 变尺度法是一种非常好的方法．其中DFP算法和BFGS 算法，可以说直到目前为止是在不用Hesse矩阵的方法 中最好的算法． 一、变尺度法基本原理Newton法在基本迭代公式 （5.26）为了消除迭代公式(5.26)中的Hesse逆矩阵 ,可用某种 近似矩阵 来替换它，即构造一个矩阵序列 去逼近Hesse逆矩阵序列 ．此时式（5.26）变为 （5.27）式（5.27）是一类更很广泛的迭代公式．例如，当 ，它变为最速下降法的迭代公式． 近似,并且有容易计算的特点，必须对附加某些条件： 理由是，为使搜索方向是下降方向，只要 成立．当对称正定时，此式必然成立，从而保证式 （5.27）具有下降性质． 第二，要求之间的迭代具有简单形式．而 （5.28）是最简单的形式 ．其中 称为校正矩阵，式（5.28） 称为校正公式． 第三，必须满足拟Newton条件．所谓拟Newton 条件 由下面的推导给出． 均已求出，现在推导 所必须满足的条件． 设目标函数具有连续的二阶偏导数．现在 将在 处展成二阶泰勒公式 当用近似 （5.29）式（5.29）就是 所要满足的拟Newton条件． （5.30）变尺度法也称为拟牛顿法。

下面总结变尺度法的迭 代步骤 迭代步骤已知目标函数 及其梯度 ，终止限 （1）选定初始点；计算 ；选定初 始矩阵 ，要求对称正定（例如， （3）作直线搜索，计算 （4）判别终止准则是否满足：若满足，则就是所求 的极小点，打印，结束；否则转（5）． 这里，校正矩阵可由确定的公式来计算．不同的公 式对应不同的拟Newton算法． 不论哪个公式都必须满足拟Newton条件，由式（5.30）和式（5.28）知， 必须满足 （5.31）可见， 满足式（5.31） 的有无穷多个，因此上述拟Newton 算法构成一簇算法．下面分别介绍两个常用的公式． DFP算法BFGS算法 （一）DFP算法DFP算法首先是由Davidon（1959年）提出来的，后来， Fletcher和Powell（1963年）对Davidon的方法作了改 进，最后才形成DFP算法．D、F、P是这三位学者名 字的字头．这种算法是无约束最优化方法最有效的方 法之一． DFP算法基本原理 考虑如下形式的校正公式 （5.32）这里，校正矩阵是 是待定维向量， 根据拟Newton条件，必须满足（5.31），于是有 有无穷多种取法，下面是其中的一种： DFP算法迭代步骤DFP算法的迭代步骤只需用将拟牛顿法中第（5）步具 体化即可。

但是由于计算中舍去误差的影响，特别是直线搜索不 精确的影响，可能要破坏迭代矩阵 的正定性，从而 导致算法失效．为保证 的正定性，采取以下重置措 施：迭代 次后，重置初始点和迭代矩阵，即 ，重新迭代． 已知目标函数及其梯度 ，问题的维数 ，终止 （3）作直线搜索；计算 （4）判别终止准则是否满足：若满足，则打印，结束；否则转（5）． 例5.4用DFP算法求 当我们取时，DFP法与最速下降法具有相同 的第1迭代点，在例5.1中已作了计算 0.738461.4 7692 0.046 16 0.36923 3088.3 7037778 由于，所以 是极小点． （二）BFGS算法BFGS算法是Broyden， Fletcher（1970年），Goldfarb （1969年）和Shanno（1970年）共同研究的结果 ,故名 BFGS算法 BFGS算法基本原理 （5.34）考虑如下形式的校正公式 其中 而参数可取任何实数，每取一个实数就对应一种拟 Newton算法．易证，当 取时就是DFP校正公式．

（编辑：云计算网_宿迁站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!