第三章 无约束最优化方法.doc

第三章 无约束最优化方法本章内容及教学安排第一节 概述第二节 迭代终止原则第三节 常用的一维搜索方法第四节 梯度法第五节 牛顿法第六节 共轭方向法第七节 变尺度法第八节 坐标轮换法第九节 鲍威尔方法第一节 概述优化问题可分为无约束优化问题有约束优化问题无约束最优化问题求解基于古典极值理论的一种数值迭代方法，主要用来求解非线性规划问题迭代法的基本思想：所以迭代法要解决三个问题1、如何选择搜索方向2、如何确定步长3、如何确定最优点（终止迭代）第二节 迭代终止准则1）2） 3）第三节 常用的一维搜索方法本节主要解决的是如何确定最优步长的问题。从初始点出发，以一定的步长沿某一个方向，可以找到一个新的迭代点，其公式如下：现在假设已经确定，需要确定的是步长，就把求多维目标函数的极小值这个多维算过程中，当起步点和方向问题，变成求一个变量即步长的最优值的一维问题了。即由此可见，最佳步长由一维搜索方法来确定求，使得一、一维搜索区间的确定区间应满足 进退法确定搜索区间区间的特点：两边翘。方法的思想；1）先明确函数在某一初始点的走势，是上升还是下降，若是下降，则最小点在该点的右边，若是上升，则最小点在函数的左边。2）根据最小点在该初始点的位置，确定搜索的方向：上升则后退，下降则前进3）只到函数的走势出现逆转，将最小值包含在区间中。具体算法1)给定初始点和初始步长2）从任意点出发，以，计算和3）比较，若（F1F2），函数下降，转（4）(5)做前进算法；若（F1F2），转（6）(7)做后退算法；（4）当时（前进），极小点在点的右方，应加大步长作前进运算。取，计算和； (5)比较F2和F3。当F3F2时，则满足F1F2F3，即x1，x2，x3三点函数值形成“高一低一高”的情况，函数极小点必在区间x1，x3内。令ax1，bx3，初始搜索区间a,b确定；当F3F2时，则极小点还在F3的右方，应继续作前进运算：放弃F1点，作置换x1=x2，x2x3，F1F2，F2F3及。再取新点，并求F3F(x3)转(5).反复上述过程，直到函数值出现“高一低一高”时，取左右两端点为初始搜索区间的两端点。（注意：（4），（5）为（前进算法）（6）当（后退），由图34(b)知极小点在F1的左方，应作后退运算。取，作符号置换，Zx1，x1x2，x2=x3及WF1、F1F2，F1W。取；计算。(7) 比较F2和F3。当F3F2时，函数极值点在区间x3，x1内。令ax3，bx1，输出初始搜索区间a,b；当F3F2时，则极小点还在F3的左方，应继续作后退运算。作置换x1x2，x2=x3，及F1F2，F2F3及。取新点，并求，转(7)。反复上述过程直到函数值出现“高一低一高”时，取左、右两端点为初始单峰区间的两端点。（注意：（6），（7）为（后退算法）进退算法确定单峰区间的计算框图进退算法确定单峰区间的计算框图如图35所示。确定搜索区间的其他算法：导数法：在极小点两侧二、黄金分割法（0.618法）一）基本原理在搜索区间a,b适当插入内两点x1和x2 ，它们把a,b分为三段。计算并比较x1和x2两点的函数值，因为a,b是单峰区间，故当时，极小点必在x1,b中；当时，极小点必在a，x2中，。无论发生哪一种情况，都将包含极小点的区间缩小，然后在保留下来的区间上作同样的处理，如此迭代下去，将使搜索区间逐步缩小，直到满足预先给定的精度时，即获得维优化问题的近似最优解；因为x1和x2仍包含在缩小的区间内，它的函数值已计算过，所以以后的每次迭代只需插入一个新点，并计算这个新点的函数值就可进行比较。黄金比例：要求：二）黄金分割法算法步骤与框图算法要点：两点比较，大作端点，小为内点。a,b= -1.111,-0.940，其长度为0.171三、分数法（斐波那契法）一）斐波那契数列：如果设F(n)为该数列的第n项(nN+)。那么可以写成如下形式： F(0) = 0，F(1)=F(2)=1，F(n)=F(n-1)+F(n-2) (n3)斐波那契数列：算法要点：两点比较，大作端点，小为内点。斐波那契数法每次缩短所取的比例是变化的端点的取舍与黄金分割法是相同的。特点：1）两点是对称的，保留的区间长度都是原来长度的Fn-1/Fn,即缩短比例是Fn-1/Fn2）保留的内点刚好是下一轮区间的一个点，故下一轮只需添加一个新点。其他一维搜索方法：牛顿法、二次插值法、三次插值法。机械结构的最优化设计大都为多维问题，一维问题的情况很少。但是一维问题的最优化方法是优化方法中最基本的方法，在数值方法迭代计算过程中，都要进行一维探索。也可以把多维问题化为一些一维问题来处理。作业：第四节、梯度法（最速下降法）一、基本思想函数在某一点的梯度方向是函数值在此点的上升最快的方向，那么负梯度方向是函数下降最快的方向。利用函数的负梯度作为函数的搜索方向。设函数在点的梯度为则在点的搜索方向为：故迭代公式可以写为：或因此优化问题就变成为一维搜索问题求，使得二、算法框图：三、算例：四、关于梯度法的几点说明(1)梯度法理论明确，方法简单，概念清楚。每迭代一次除需进行一维搜索外，只需计算函数的一阶偏导数，计算量小，且对初始点没有严格要求；(2)相邻两次迭代的梯度方向是互相正交的，即。以后迭代中也总是前后两次迭代方向互为正交，因此，梯度法搜索路线呈直角锯齿形，靠近极小点时，搜索点的密度越来越大，这说明收敛速度越来越慢。(3)迭代次数与目标函数等值线的形状有关。目标函数的等值线形成的椭圆族愈扁，迭代次数愈多，搜索难于到达最优点，如例42。但当等值线族为圆族时，则一次选代就能达到极小点，如例41，这是因为圆周上任一点的负梯度方向总是指向圆心的。(4)按负梯度方向搜索并不等同于以最短时间到达最优点。因为“负梯度方向是函数值最速下降方向”仅是迭代点邻域内的一种局部性质，从整个迭代过程来看，并不带有最速下降的性质。五、提高梯度法搜索速度的解决办法1）选择好点：不容易2）变量代换（改变函数的性态）：3）避免前后两次迭代方向正交： 或降低一维搜索时最优步长的精度。4）平行切线法5）与其他方法联合使用。梯度法作业：第五节、牛顿法一、基本思想由于梯度法相邻两次搜索方向总是互相正交，前进路线呈锯齿形，使得其在极小点附近，收敛速度越来越慢。人们试图找到这样一种方向：它直接指向最优点，从任意选定的初始点出发，沿此方向迭代一次就达到极小点牛顿法。牛顿法亦称切线法，其基本思想来源于牛顿法求解方程的根。求一个一元函数的根，可在函数上任取一点，作切线，交x轴与，在过作的切线，得到点，如此反复，最终可趋近于方程的根。其迭代公式为：求函数的极小点可视为求方程的根。设有连续的一阶和二阶导数则牛顿法求极值的迭代公式为若，则就是近似极小点对于正定二次函数其梯度为由极值理论知是极小点的必要条件，故极小点若任取初始点，其梯度为S=X*-X0若取为搜索方向则：当步长为1时， 为极小点比较阴影部分的值，对二次函数沿方向搜索，取适当步长，只要一次迭代就可达到极值点。对于非二次函数，算法就没有那么简单，但由于函数在极小点附近往往具有非常强的正定二次函数性态，所以我们可以利用二次函数的这种性质，来加快搜索速度。牛顿法就是利用了这种性质。二、原始牛顿法对于多元函数，可以将函数在附近用泰勒公式展开其梯度若为极小点，必有，所以牛顿法的方向， 并且，其步长为1，这是原始牛顿法。例题：用原始牛顿法解得最优解三、修正的牛顿法-阻尼牛顿法原始牛顿法的优点：收敛速度快从原始牛顿法的推导过程可知，对任何正定二次函数，因其近似函数由与原目标函数f(x)完全相同，二阶偏导数矩阵又为一常数正定方阵，因此可以从任一初始点出发，按迭代公式迭代一次就可达到目标函数的极小点X*。对于非二次函数虽然不能一步就求出极小点，但由于在X*附近二次函数由与原目标函数f(x)是近似的，所以牛顿方向可以作为近似方向，按公式进行迭代一般也将很快收敛于函数的最优点X*。原始牛顿法的缺点： 1，计算较复杂。在每次迭代确定牛顿方向时，都要计算目标函数的一阶导数和二阶偏导数矩阵及其逆矩阵。这就使计算较为复杂，增加了每次迭代的计算工作量。2，对海赛矩阵要求高。为了保证牛顿方向是目标函数的下降方向，必须满足 ，要求可逆（非奇异）、正定。3，对于非二次函数，要求初始点的选取要靠近极值点，否则可能导致不收敛。原始牛顿法并不是对所有函数都会很好地收敛，有时会出现函数值上升的情况，甚至会收敛到鞍点或不收敛，原因是步长为1，不经过一维搜索，方法的效果依赖于初始点的选取。不收敛的例子：一阶导数二阶导数：定义域的三个区域：由于原始牛顿法不能保证函数值稳定地下降，于是使出现了修正牛顿或称阻尼牛顿法。其修正方法是：由求时，不是直接利用原来的迭代公式计算，而是沿着点处的牛顿方向进行一维搜索，将该方向上的目标函数最优点作为。这样就会避免收敛到鞍点或不收敛。迭代格式改为：式中为沿牛顿方向作一维搜索求得的最优步长，即：式中是牛顿方向，这种修正牛顿法虽然汁算工作量多了一些，但在目标函数的海森矩阵处处正定的情况下，它能保证每次迭代都能使函数值有所下降，即使初始点选得不好，用这种搜索方法也会成功。同时，它还保持了牛顿法收敛快的优点。四、迭代步骤及计算框图五）关于牛顿法的讨论 (1)牛顿法对正定二次函数的寻优特别有效，迭代一次即达到极小点，。对于一般目标函数，在极小点附近，它的收敛速度也是很快的，即牛顿法具有二次收敛性。 (2)牛顿法对函数的性态有较严格的要求。除了函数需具有一、二阶偏导数外，为了保证函数的稳定下降，海森矩阵必须处处正定，否则牛顿法将失败。为了能使迭代计算顺利进行，海森矩阵必须为非奇异，否则无法求其逆短阵，不能构成牛顿方向。 (3)计算复杂。因为除了求梯度外还需计算海森矩阵及其逆矩阵，所以计算困难且占用较大的计算机贮存量。牛顿法作业：第六节 共轭方向法一、共扼方向的基本概念(一)共轭方向与正交方向 设A为n阶实对称正定矩阵，若有两个n维向量和：能满足 则称向量和对矩阵A共扼，共扼向量的方向称为共轭方向。 如果非零向量组、中任意两个向量关于n阶对称正定矩阵A共轭，即满足 则称向量组、，关于矩阵A共轭，即对于同一实对称矩阵A可根据需要取不同的对A共扼的方向组。若有两个向量和关于单位矩阵I共轭，则由共轭定义知即 和正交。正交是共轭方向的特例。共轭方向的理解：两个不相关的向量经过A变换后变成互相正交的向量。矩阵的作用变换向量的方向。高等数学中的坐标变换(二) 共扼方向的几何意义设有二元二次正定函数它在坐标平面上的等值线是一族同心的椭圆，如图。在图上两点沿方向作根两平行线，它与等值线的切点（即该方向上的极小点）为和，那么连接这两点的方向为，它与是共轭的。证明如下：因为函数在和处的梯度分别为将上述两式相减又由梯度的性质可知，和是函数等值线在和处的法向量，故 所以和对矩阵A共扼。二、共扼向量的重要性质(1)设A为nn阶实对称正定矩阵，、。为对A共轭的n个非零向量，则可证明这一组向量线性无关。线性无关的定义对向量组 ，如果存在一组不全为零的数 , 使得 那么, 称向量组 线性相关. 如果这样的 个数不存在, 即上述向量等式仅当 时才能成立, 就称向量组 线性无关。用通俗的话说就是：线性相关，就是在一组数据中有一个或者多个向量可以被其余向量表示。线性无关，就是在一组数据中没有一个向量可以被其余向量表示。向量线性无关的证明用反证法：设存在一组数不全为零的数，、，使得在上式分别左乘，当时的项为零，故得到，由于i为任选，故、=0得证。(2) 设一组向量、是线性无关的向量组，则可以构造出n个向量、，使其满足 对于n维优化问题而言，线性无关向量系中向量的个数不可能超过问题的维数，因此共扼向量的个数最多等于n。单位坐标向量系是一组线性元关的共扼向量的最简单的例子，且它们也是正交向量系。(3)设A为nn阶实对称正定矩阵，、。为对A共轭的n个非零向量，对于正定二次函数f(X)的极小化寻优问题，从任何初始点X0出发，依次沿方向经n次一维搜索即可收敛到极小点X*=Xn。这与同心椭圆簇的几何性质有关：两条平行的任意方向的切线，其切点的连线必通过椭圆簇的共同中心。（证明略说明：教材中的只是一个说明性的结论）三、以n个单位向量构造共轭方向共轭方向的构造方法以n维空间的n个单位向量构造共轭方向。单位向量（1）（2）和对矩阵A共扼，即（3）令其中 令其中 注意：每一步中的是不同的。（4）通式：这样共构造了n个共轭向量。四、以函数梯度信息的构造共轭方向-共轭梯度法一）共轭梯度法的基本原理利用极小点的负梯度方向来构成共轭方向，使它形成具有二次收敛的共轭梯度法。设有二次函数：二）共轭梯度法共轭向量的构造方法：给定，令取沿一维搜索（注意！）得到，令令 并使、共轭，（注意：和是正交的）即，则有沿一维搜索得到，令令，并使与、共轭即，则有 （注意：、共轭，故）通式 其中 注意：K表示第K步，每一步迭代均有K个值，不同的迭代轮次中， 的值是不同的，都要重新计算。这样可以构造一组共轭向量。说明：每个梯度是通过迭代一步一步获得的，同样，每获得一个梯度，旋即通过梯度和前面的方向向量构造一个新的与前面得到的方向向量共轭的向量，这样迭代n次即可获得n个互相共轭的向量。三）公式的简化采用这种方法构造共轭方向，要用到海赛矩阵A，对A的要求比较高，对上述方法作改进和简化。首先，了解根据以上方法构造的共轭方向以及各迭代点梯度的关系和特点，主要有三个特点：特点一： 前后两次迭代点的梯度之差与其他任一共轭方向是正交的特点二：某迭代点的梯度与此前各点的搜索方向是正交的。特点三：迭代点处的梯度与前面各点处的梯度正交，亦即通过此方式得到各点的梯度是一个正交系。1、 前后两次迭代点的梯度之差与其他任一共轭方向是正交的在第K次迭代中因 若令 和 二式相减得 式中第K次迭代的最优步长因子 为前后两个点的梯度方向的差如果、是按照共轭梯度法构造的关于A的n个共轭向量则 （ j,k=1,2,n）即结论一： （为前后两个点的梯度方向的差，上式说明前后两次迭代点的梯度之差与其他任一共轭方向是正交的）2、某迭代点的梯度与此前各点的搜索方向是正交的。设kj，则：由于是迭代点处的梯度，而是沿方向搜索得到的最优点，故与正交，所以有因此：， j=1,2，,k-1结论二：某迭代点的梯度与此前各点的搜索方向是正交的。当K=n时，即有（n是函数的维数）即 上式等式两边左乘以，得 *由于沿方向求极小点，即与正交于是有：如果、是关于A的n个共轭向量，式（*）为 因而，必有 或 （因为K的取值范围）所以为函数的极小点。（间接证明了共轭梯度法的二次收敛性）这说明，若能在迭代过程中，能利用梯度信息，来构造一个、的共轭方向序列，对于一个n维函数，在第n次迭代中，即可取得最优点。3、迭代点处的梯度与前面各点处的梯度正交，即通过此方式得到各点的梯度是一个正交系。在第r次迭代中（rk），有：统一写成 （此处）上式两边同时左乘 （注意：rk），得：由结论二（某迭代点的梯度与此前各点的搜索方向是正交的）可知 （rk）结论三：迭代点处的梯度与前面各点处的梯度正交，并可得到结论：通过此