第4章 无约束优化方法

第四章无约束优化方法§4-1最速下降法（梯度法）§4-2牛顿类方法§4-3共轭方向法§4-4共轭梯度法§4-5变尺度法§4-6坐标轮换法§4-7鲍威尔方法§4-8单形替换法第1章所列举的机械优化设计问题，都是在一定的限制条件下追求某一指标为最小，它们都属于约束优化问题。工程问题大都如此。为什么要研究无约束优化问题?（1）有些实际问题，其数学模型本身就是一个无约束优化问题。（2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。（3）约束优化问题的求解可以通过一系列无约束优化方法来达到。所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。无约束优化问题是：12[]Tnxxxx求n维设计变量()minfx使目标函数min()nfRxx目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。（1）间接法——要使用目标函数的一阶或二阶导数构造搜索方向，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度法等。（2）直接法——不使用导数信息，只利用目标函数值构造搜索方向，如坐标轮换法、鲍威尔法、单纯形法等。4-1梯度法基本思想：函数的负梯度方向是函数值在该点下降最快的方向。将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最速下降法或梯度法。()fx搜索方向s取该点的负梯度方向(最速下降方向)，使函数值在该点附近的范围内下降最快。1(0,1,2,)kkkkskxx1()(0,1,2,)kkkkafkxxx为了使目标函数值沿搜索方向能够获得最大的下降值，其步长因子应取一维搜索的最佳步长。即有()kfxk1()[()]min[()]min()kkkkkkaafffffxxxxx根据一元函数极值的必要条件和多元复合函数求导公式，得'()[()]()0Tkkkkfffxxx1[()]()0kTkffxx1()0kTkss图4-2最速下降法的搜索路径在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。这就是说在迭代点向函数极小点靠近的过程，走的是曲折的路线。形成“之”字形的锯齿现象，而且越接近极小点锯齿越细。011*10();3minmin4||;1,kkkkkkkkkkkkkxkdfxfxadaxxadxxxxkk1）给定初始点和收敛精度，置；2）计算梯度，并构造搜索方向）用一维搜索的方法求解得最佳步长，代入得到新的迭代点；）若，则停止迭代，得最优解否则，转到第二步。梯度法计算步骤例4－1求目标函数的极小点。解取初始点则初始点处函数值及梯度分别为0[2,2]Tx2212()25fxxx00102()10424()50100xfxfxxx沿负梯度方向进行一维搜索，有01000024()2100fxxx为一维搜索最佳步长，应满足极值必要条件0122()min(24)25(2100)min()fx00'()8(24)5000(2100)0算出一维搜索最佳步长06260.0200307231252第一次迭代设计点位置和函数值0120241.91987721000.307178510x1()3.686164fx继续作下去，经10次迭代后，得到最优解00Tx()0fx这个问题的目标函数的等值线为一簇椭圆,迭代点从走的是一段锯齿形路线，见图4-3。0x图4-3等值线为椭圆的迭代过程将上例中目标函数引入变换2212()25fxxxy1=x1,y2=5x2则函数f(X)变为：221212(,)yyyy其等值线由椭圆变成一簇同心圆。仍从即出发进行最速下降法寻优。此时：0[2,2]Tx0[2,10]Ty00102()10424()220yyyyy沿负梯度方向进行一维搜索：1000000()242410201020yyyβ为一维搜索最佳步长，可由极值条件：10022()min[()]min()()(24)(1020)yyy0()0由0260.552从而算得一步计算后设计点的位置及其目标函数：010124010200()0yy经变换后，只需一次迭代，就可找到最优解。这是因为经过尺度变换：11225yxyx等值线由椭圆变成圆。等值线为圆的迭代过程比较以上两种函数形式12212121221221212122201(,)250502201(,)022xfxxxxxxxyyyyyyyy二次型函数的对角形矩阵刻画了椭圆的长短轴，它们是表示度量的矩阵或者是表示尺度的矩阵。最速下降法的收敛速度和变量的尺度关系很大，在适当条件下，最速下降法的收敛速度估计式为21**2(1)kkmxxxxMM——f（x）海塞矩阵最大特征值上界m——f（x）海塞矩阵最小特征值下界梯度法的特点（1）理论明确，程序简单，对初始点要求不严格。每迭代一次除需进行一维搜索外，只需计算函数的一阶导数，计算量小。（2）梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。（3）按负梯度方向搜索并不等同于以最短时间到达最优点，对一般函数而言，梯度法的收敛速度并不快，因为最速下降方向仅仅是指迭代点的一个局部性质，从局部上看，在一点附近函数下降是最快的，但从整体看则走了许多弯路，下降的并不算快。（4）梯度法的收敛速度与目标函数的性质和初始点的位置选择密切有关。对于等值线(面)为同心圆（球）的目标函数，一次搜索即可达到极小点。最速下降法采用了函数的负梯度方向作为下一步的搜索方向，整个搜索过程收敛速度较慢，这是它的主要缺点。但是，应用最速下降法可以使目标函数在开头几步下降很快，所以它可与其它无约束优化方法配合使用，特别是一些更有效的方法都是在对它进行改进后，或在它的启发下获得的，因此最速下降法仍是有约速和无约束优化方法的基础。4-2牛顿类方法基本思想：在xk邻域内用一个二次函数来近似代替原目标函数，并将的极小点作为对目标函数求优的下一个迭代点。经多次迭代，使之逼近目标函数的极小点。()x()x()fx1kx()fx2()()()()()1()()()2kkTkkTkkffffxxxxxxxxxxx设为的极小点1kx()x1()0kx21()()()0kkkkffxxxx一维情况的牛顿迭代公式k+1=kf(k)/f(k)k=0,1,2,对于多元函数f(x),设xk为f(x)极小点x*的一个近似点，在xk处将f(x)进行泰勒展开，保留到二次项，得到海塞矩阵121[()]()(0,1,2,)kkkkffkxxxx这就是多元函数求极值的牛顿法迭代公式。对于二次函数，海赛矩阵H是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。例4－2求目标函数的极小点。解取初始点2212()25fxxx0[2,2]Tx则初始点处的函数梯度、海赛矩阵及其逆阵分别为010224()50100xxfxx牛顿方向102010102402()()121000050ffxxxx2020()050fx201102()1050fx经过一次迭代即求得极小点00x函数极小值()0fx从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念。因此对于非二次函数，如果采用上述牛顿迭代公式，有时会使函数值上升。阻尼牛顿法121[()]()(0,1,2,)kkkkkkkksffkxxxxxk阻尼因子，沿牛顿方向进行一维搜索的最佳步长，由下式求得：1()()min()kkkkkkkffsfsxxx阻尼牛顿法每次迭代都在牛顿方向上进行一维搜索，避免了迭代后函数值上升的现象，从而保持了牛顿法的二次收敛性，而对初始点的选择没有要求。阻尼牛顿法的迭代步骤：01111*1,0;()()()()34||;1,kkkkkkkkkkkkkkkxkfxGxGxdGxfxxxddxxxxkk1）给定初始点收敛精度，置2）计算、和，得到；）求，其中，是沿着进行一维搜索的最佳步长；）检查收敛精度。若，则停止迭代，得最优解否则，转到第二步继续进行搜索。例用牛顿法求解下列方法：2221212122)(minxxxxxxxf给定初始点Tx)0,0()1(解目标函数f(x)的梯度和海塞矩阵是2224)()(221,241)(22121xfxHxxxxxf在x(1)处，目标函数f(x)的梯度和海塞矩阵是2224)()(1,1)()1(2)1()1(xfxHxfT牛顿方向231111212121112224)(.))(()1(1)1()1(xfxHd从x(1)出发，沿d(1)作一维搜索，令步长变量为λ，最优步长为λ1，则有23,232310021)1()1(xxdx2545493223)(2222)1()1(dxf令102525)(1)1()1(dxf故23123100)1()1()2(dxx上述想x（2）即极小点。牛顿法方法特点（1）初始点应选在极小值X*附近，有一定难度；（2）尽管每次迭代都不会使函数值上升，但不能保证每次下降；（3）若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向；（4）不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。此外，对于二阶不可微的F(X)也不适用。虽然阻尼牛顿法有上述缺点，但在特定条件下它具有收敛最快的优点，并为其他的算法提供了思路和理论依据。梯度法与牛顿法：一般迭代式：1(0,1,2,)kkkkskxx梯度法：1()(0,1,2,)kkkkafkxxx牛顿法：121[()]()(0,1,2,)kkkkffkxxxx阻尼牛顿法：121[()]()(0,1,2,)kkkkkffkxxxx4-3共轭方向及共轭方向法为了克服最速下降法的锯齿现象以提高其收敛速度，发展了一类共轭方向法。一、共轭方向的基本概念首先以二元二次函数为例予以说明共轭方向概念，设函数2*2阶对称正定矩阵式中二元二次函数的等值线为一组椭圆，任选初始点x0沿某个下降方向d0作一维搜索，得x1=x0+0d0。0是沿d0方向搜索的最佳步长，即在x1点处函数f(x)沿d0方向的方向导数为零。故有00101dxfdfTxd0与某一等值线相切于x1点。为了避免按最速下降法出现的锯齿现象，可取下一次的迭代搜索方向d1直指极小点x*，如图所示。既有x*=x1+1d11为d1方向上的最佳步长。二次函数f(x)在x1点的梯度为