5-常用无约束最优化方法

第五章常用无约束优化方法★最速下降法★Newton法★修正Newton法★共轭方向法★共轭梯度法★变尺度法★坐标轮换法★单纯形法第五章常用无约束优化方法对于多维无约束最优化问题)(minXf（5.1）成立．点就是问题（5.1）的全局最优点．但是，大多数最优化方法只能求到局部最优点．这个矛盾对于实际问题来讲一般容易解决，因为根据问题的实际意义多半可以直接判定用优化方法求出的局部最优解是否为全局最优解．但在理论上这是个比较复杂的问题，本书不涉及．*X其中．这个问题的求解是指，在中找一点，使得对于任意的都有1RRfn：nRnRX)()(*XfXf（5.2）无约束优化方法是优化技术中极为重要,它不仅可以直接用来求解无约束优化问题，而且很多约束优化问题也常将其转化为无约束优化问题，然后用无约束优化方法来求解．同时，有些无约束优化方法只需略加处理，即可用于求解约束优化问题．第五章常用无约束优化方法无约束优化理论发展较早，比较成熟，方法也很多，新的方法还在陆续出现．把这些方法归纳起来可以分成两大类：一类是仅用计算函数值所得到的信息来确定搜索方向，通常称它为直接搜索法，简称为直接法，另一类需要计算函数的一阶或二阶导数值所得到的信息来确定搜索方向，这一类方法称为间接法（或解析法）．直接法不涉及导数和Hesse矩阵，适应性强，但收敛速度一般较慢；间接法收敛速度一般较快，但需计算梯度，甚至需要计算Hesse矩阵．一般的经验是，在可能求得目标函数导数的情况下还是尽可能使用间接方法；相反，在不可能求得目标函数的导数或根本不存在导数的情况下，当然就应该使用直接法．第五章常用无约束优化方法5.1最速下降法为求问题（5.1）的最优解，按最优化算法的基本思想是从一个给定的初始点出发，通过基本迭代公式，按照特定的算法产生一串点列，如果点列收敛，则该点列的极限点为问题（5.1）的最优解．0XkkkkPtXX1}{kX最速下降法基本原理在基本迭代公式中，每次迭代搜索方向取为目标函数的负梯度方向，即，而每次迭代的步长取为最优步长，由此所确定的算法称为最速下降法．kkkkPtXX1kP)(Xf)(kkXfPkt在第二章中，我们曾经提到，对于函数，其函数值下降最快的方向是该函数的负梯度方向。第五章常用无约束优化方法对于问题（5.1），假定我们已经迭代了k次，获得了第k个迭代点Xk．现在从Xk出发，可选择的下降方向很多，一个非常自然的想法是沿最速下降方向（即负梯度方向）进行搜索应该是有利的，至少在邻近的范围内是这样．因此，取搜索方向为:)(kkXfP为了使目标函数在搜索方向上下降最多，沿Pk进行一维搜索，由此得到第k+1个迭代点，即)(1kkkkXftXX其中步长tk因子由来确定。))((min))((kktkkkXftXfXftXf记为))(,(1kkkXfXlsX令k=0,1,2,...，就可以得到一个点列（初始点可任意选择）。当函数满足一定的条件时，该点列必收敛于函数的极小点。为书写方便，记．故．在不发生混淆时，再记．)()(XfXg)()(kkXfXg)()(kkkXfXgg第五章常用无约束优化方法迭代步骤已知目标函数及其梯度，终止限、和．)(Xf)(Xg123（1）选定初始点，计算，；置0X)(00Xff)(00Xgg0k（2）作直线搜索：),(1kkkgXlsX计算)(11kkXff)(11kkXgg（3）用终止准则检测是否满足：若满足，则打印最优解,,结束；否则，置，转（2）．1kX)(1kXf1kk第五章常用无约束优化方法将最速下降法应用于正定二次函数cXbAXXXfTT21)(（5.4）可以推出显式迭代公式．设第k次迭代点为Xk，我们来求Xk+1的表达式．对式（5.4）关于X求梯度，有bAXXg)(（5.5）因此，bAXXggkkk)(（5.6）现在从Xk出发沿-gk作直线搜索以确定Xk+1，于是kkkkgtXX1(5.7)其中tk是最优步长因子．又因0)(1kTkgXg，再结合式（5.5）、（5.6）、（5.7）0])([kTkkkgbgtXA0][kTkkkgAgtg或可得由此解出kTkkTkkAggggt第五章常用无约束优化方法代入式（5.7）中得到kkTkkTkkkgAggggXX1（5.8）例5.1试用最速下降法求函数的极小点．迭代两次，计算各迭代点的函数值，梯度及其模，并验证相邻两个搜索方向是正交的．设初始点为．2221214),(xxxxfTX]1,1[0解与式（5.4）比较，得8002A梯度表达式是212182),()(xxxxfXf由，计算出TX]11[0，5141)(220xf82)(00Xfg24621.8||||0g第五章常用无约束优化方法因为目标函数是二次的，可以使用式（5.8），所以有04616.073846.08213077.0110000001gAggggXXTT计算，55385.004616.0473846.0)(221Xf，，52237.136923.047692.1)(111gXfg11076.011076.036923.047692.142500.004616.073846.01111112gAggggXXTT．，，91335.088008.022152.0)(06134.0)(2221gXfgXf因为10210.00000.0000TTgggg，，说明相邻两个搜索方向是正交的．第五章常用无约束优化方法有关说明最速下降法的优点是算法简单，每次迭代计算量小，占用内存量小，即使从一个不好的初始点出发，往往也能收敛到局部极小点，但它有一个严重缺点就是收敛速度慢．沿负梯度方向函数值下降很快的说法，容易使人们产生一种错觉，认为这一定是最理想的搜索方向，沿该方向搜索时收敛速度应该很快，然而事实证明，梯度法的收敛速度并不快．特别是对于等值线（面）具有狭长深谷形状的函数，收敛速度更慢．其原因是由于每次迭代后下一次搜索方向总是与前一次搜索方向相互垂直，如此继续下去就产生所谓的锯齿现象．即从直观上看，在远离极小点的地方每次迭代可能使目标函数有较大的下降，但是在接近极小点的地方，由于锯齿现象，从而导致每次迭代行进距离缩短，因而收敛速度不快．第五章常用无约束优化方法5.2Newton法如果目标函数在上具有连续的二阶偏导数，其Hesse矩阵正定并且可以表达成为显式（记，那么可以使用下述的Newton法．这种方法一旦用好，收敛速度是很快的．它是一维搜索Newton切线法的推广．))()(2XfXG基本原理为寻求收敛速度快的算法,在应用基本迭代公式中，每轮迭代在迭代的起始点处用一个适当的二次函数来近似该点处的目标函数，由此用点指向近似二次函数极小点的方向来构造搜索方向.kkkkPtXX1kXkXkP第五章常用无约束优化方法1RRfn：设最优化问题为)(minXf其中二阶可导，Hesse矩阵)(2Xf正定．不妨设经过次迭代已获点，现将在处展成二阶泰勒公式，于是有kkXkXX)(Xf．))(()(21)()()()()(2kkTkkTkkXXXfXXXXXfXfXQXf显然是二次函数，并且还是正定二次函数，所以是凸函数且存在唯一全局极小点．为求此极小点，令)(XQ)(XQ0))(()()(2kkkXXXfXfXQ即可解得)()]([12kkkXfXfXX即)()]([121kkkkXfXfXX（5.9）对照基本迭代公式,易知，式（5.9）中的搜索方向)()]([12kkkXfXfP步长因子1kt第五章常用无约束优化方法方向是直指点处近似二次函数的极小点的方向．此时称此方向为从点出发的Newton方向．从初始点开始，每一轮从当前迭代点出发，沿Newton方向并取步长的算法称为Newton法．)()]([12kkkXfXfPkX)(XQkX1kt迭代步骤已知目标函数及其梯度，Hesse矩阵，终止限．)(Xf)(Xg)(XG（1）选定初始点；计算；置．0X)(),(0000XggXff0k（2）计算.)(2kkXfG（3）由方程解出．kkkgPGkP（4）计算.，，)(111kkkkkXffPXX)(11kkXgg（5）判别终止准则是否满足：若满足，则打印最优解，结束；否则，置，转（2）．1kX1kf1kk第五章常用无约束优化方法第五章常用无约束优化方法例5.2试用Newton法求的极小点，初始点取为．2221214)(xxxxf，TX]1,1[0解梯度为TxxXfXg]82[)()(21，Hesse矩阵为8002)(XG其逆矩阵为125.0005.0)(1XG由迭代公式（5.9）得第1迭代点为11000()()10.502000.125180XXGXgX．由此，停止迭代得61100||)(||XfTXX]00[1*，第五章常用无约束优化方法对于目标函数是非二次函数的非约束最优化问题，一般来说，用Newton法通过有限轮迭代并不能保证可求得最优解．但由于目标函数在最优解附近能近似于二次函数，因此当先取接近于最优解的初始点使用Newton法求解时，其收敛速度一般是较快的．从例5.2我们看到，用Newton法求解，只经一轮迭代就得到最优解．这一结果并不是偶然的，因为从Newton方向的构造我们知道，对于正定二次函数，Newon方向就是指向其极小点的方向．因此，用Newton法解目标函数为正定二次函数的无约束最优化问题，只需一次迭代就可得最优解．事实上，可以证明在初始点离最优解不远的条件下，Newton法是二次收敛的．但是当初始点选得离最优解太远时，Newton法并不一定是收敛的方法，甚至连其下降性也很难保证．第五章常用无约束优化方法有关说明Newton法收敛速度非常快具有二次收敛的优点，但它存在下面四个严重的缺点：（1）尽管每次迭代不会使目标函数上升，但仍不能保证下降．当Hesse矩阵非正定时，Newton法的搜索将会失败．（2）对初始点要求严格．一般要求比较接近或有利于接近极值点，而这在实际计算中是比较难办的．（3）在进行某次迭代时可能求不出搜索方向．由于搜索方向为,若目标函数在点Hesse矩阵是奇异的，则不存在，因而不能构成newton方向，从而使迭代无法进行．)()]([12kkkXfXfPkX12)]([kXf（4）newton方向构造困难，计算相当复杂，除了求梯度以外还需计算Hesse矩阵及其逆矩阵，占用机器内存相当大．第五章常用无约束优化方法5.3拟Newton法基本原理为了克服Newton法的缺点，人们保留选取Newton方向作为搜索方向，摒弃其步长恒取1，而用一维搜索确定最优步长，由此产生的算法称为修正Newton法（或阻力Newton法）．迭代步骤已知目标函数及其梯度，Hesse矩阵，终止限．)(Xf)(Xg)(XG（1）选取初始点，令．0X0k（2）计算．若，停止迭代输出，否则转（3）．)()(kkXfXg||)(||kXf（3）构造Newton方向．计算，取121)]([)(kkXfXG)()]([12kkkXfXfP（4）进行一维搜索．求，使得．令，转（2）．kt)(min)(0kktkkktPXfPtXf1,1kkPtXXkkkk第五章常用无约束优化方法修正Newton法克服了Newton法的缺点．特别是，当迭代点接近于最优解时，此法具有收