第四章-无约束优化方法

第四章无约束优化方法坐标轮换法鲍威尔法梯度法牛顿法DFP变尺度法BFGS变尺度法无约束优化方法的评价准则及选用无约束优化方法是优化技术中基本的也是非常重要的内容。无约束优化问题的数学模型求上述问题最优解（x*,F*）的方法，称为无约束优化方法无约束优化方法，不仅可以直接求无约束优化设计问题的最优解，而且通过对无约束优化方法的研究给约束优化方法建立明确的概念、提供良好的基础·某些优化设计方法就是先把约束优化设计问题转化为无约束问题后，再直接用无约束优化方法求解。无约束优化理论研究开展得较早，构成的优化方法巳很多，也比较成熟，新的方法仍在陆续出现。本章的内容与目的是讨论几个常用无约束优化方法的基本思想、方法构成、迭代步骤以及终止准则等方面问题。在n维无约束优化方法的算法中，用函数的一阶、二价导数进行求解的算法，称为解析法;无约束优化方法总体分成两大类型:解析法或称间接法、直接搜索法或简称直接法；对于n维优化问题，如果只利用函数值求最优值的解法，称为直接搜索法；解析法的收敛速率较高，直接法的可靠性较高。本章介绍的坐标轮换法和鲍威尔法属于直接法；梯度法、共轭梯度法、牛顿法和变尺度法属于解析法无约束优化方法算法的基本过程是:从选定的某初始点x(k)出发，沿着以一定规律产生的搜索方向S(k),取适当的步长a(k),逐次搜寻函数值下降的新迭代点x(k+1),使之逐步逼近最优点x*。可以把初始点x(k)、搜索方向S(k)、迭代步长a(k)称为优化方法算法的三要素。其中以搜索方向S(k)更为突出和重要，它从根本上决定着一个算法的成败、收敛速率的快慢等。所以，一个算法的搜索方向成为该优化方法的基本标志，分析、确定搜索方向S(k)是研究优化方法的最根本的任务之一。坐标轮换法坐标轮换法属于直接法，既可以用于无约束优化问题的求解，又可以经过适当处理用于约束优化问题求解。坐标轮换法是每次搜索只允许一个变量变化，其余变量保持不变，即沿坐标方向轮流进行搜索的寻优方法。它把多变量的优化问题轮流地转化成单变量（其余变量视为常量）的优化问题，因此又称这种方法为变量轮换法。此种方法只需目标函数的数值信息而不需要目标函数的导数。一、坐标轮换法的迭代过程如图，以二次函数为例。任取一初始点x(0)作为第一轮的始点x0(1),先沿第一坐标轴的方向e1作一维搜索，用一维优化方法确定最优步长1(1)，得第一轮的第一个迭代点x1(1)=x0(1)+1(1)e1，然后以x1(1)为新起点，沿第二坐标轴的方向e2作一维搜索，确定步长2(1)，得第一轮的第二个迭代点x2(1)=x1(1)+1(1)e2第二轮迭代，需要x0(2)x2(1)x1(2)=x0(2)+1(2)e1x2(2)=x1(2)+2(2)e2依次类推，不断迭代，目标函数值不断下降，最后逼近该目标函数的最优点。二、终止准则可以采用点距准则注意：若采用点距准则或函数值准则，其中采用的点应该是一轮迭代的始点和终点，而不是某搜索方向的前后迭代点。坐标轮换法的计算步骤⑴任选初始点作为第一轮的起点，置n个坐标轴方向矢量为单位坐标矢量：⑵按照下面迭代公式进行迭代计算k为迭代轮数的序号，取k=1，2，……；i为该轮中一维搜索的序号，取i=1，2，……n步长α一般通过一维优化方法求出其最优步长。⑶按下式判断是否中止迭代如满足，迭代中止，并输出最优解最优解否则，令k←k+1返回步骤（2）例题4.1用坐标轮换法求目标函数的无约束最优解。给定初始点，精度要求ε=0.1解：做第一轮迭代计算沿e1方向进行一维搜索式中，为第一轮的起始点，取按最优步长原则确定最优步长α1，即极小化此问题可由某种一维优化方法求出α1。这里，我们暂且用微分学求导解出，令其一阶导数为零以为新起点，沿e2方向一维搜索以最优步长原则确定α2，即为极小化对于第一轮按终止条件检验继续进行第2轮迭代计算，各轮计算结果见课本表4.1。计算5轮后，有故近似优化解为坐标轮换法的流程图入口出口给定,εk←1i←1i=n?xx**)(*xFFi←i+1)0()(xxki?)(0)(kknxx)0(xk←k+1(k)nx(0)x沿ei方向一维搜索αiiekikixkix)()(1)(F←F(x))(kixx--++小结坐标轮换法程序简单，易于掌握。但是计算效率比较低，尤其是当优化问题的维数较高时更为严重。一般把此种方法应用于维数小于10的低维优化问题。对于目标函数存在“脊线”的情况，在脊线的尖点处没有一个坐标方向可以使函数值下降，只有在锐角所包含的范围搜索才可以达到函数值下降的目的，故坐标轮换法对此类函数会失效。x2x1脊线鲍威尔方法鲍威尔方法是直接搜索法中一个十分有效的算法。该算法是沿着逐步产生的共轭方向进行搜索的，因此本质上是一种共轭方向法。一、鲍威尔基本算法如图所示，以三维二次目标函数的无约束优化问题为例。鲍威尔基本算法的搜索过程鲍威尔基本算法的步骤：第一环基本方向组取单位坐标矢量系e1、e2、e3、…、en，沿这些方向依次作一维搜索，然后将始末两点相连作为新生方向，Sk=xnk-x0k再沿新生方向作一维搜索，完成第一环的迭代。以后每环的基本方向组是将上环的第一个方向淘汰，上环的新生方向补入本环的最后而构成。S2kS3k……SnSkn维目标函数完成n环的迭代过程称为一轮。从这一轮的终点出发沿新生方向搜索所得到的极小点，作为下一轮迭代的始点。这样就形成了算法的循环。鲍威尔基本算法的缺陷：可能在某一环迭代中出现基本方向组为线性相关的矢量系的情况。如第k环中，产生新的方向：Sk=xnk-x0k=1(k)S1(k)+2(k)S2(k)+•••+n(k)Sn(k)式中，S1(k)、S2(k)、•••、Sn(k)为第k环基本方向组矢量，1(k)、2(k)、•••、n(k)为个方向的最优步长。若在第k环的优化搜索过程中出现1(k)=0，则方向Sk表示为S2(k)、S3(k)、•••、Sn(k)的线性组合，以后的各次搜索将在降维的空间进行，无法得到n维空间的函数极小值，计算将失败。如图所示为一个三维优化问题的示例，设第一环中1=0，则新生方向与e2、e3共面，随后的各环方向组中，各矢量必在该平面内，使搜索局限于二维空间，不能得到最优解。鲍威尔基本算法的退化x1x2x31=02e23e3S1二、鲍威尔修正算法在某环已经取得的n+1各方向中，选取n个线性无关的并且共轭程度尽可能高的方向作为下一环的基本方向组鲍威尔修正算法的搜索方向的构造：在第k环的搜索中，x0k为初始点，搜索方向为S1(k)、S2(k)、•••、Sn(k)，产生的新方向为Sk，此方向的极小点为x(k)。点xn+1(k)=2xn(k)-x0(k)，为x0(k)对xn(k)的映射点。计算x0(k)、x1(k)、•••、xn(k)、x(k)、xn+1(k)各点的函数值，记作：F1=F(x0(k))F2=F(xn(k))F3=F(xn+1(k))=F(xm(k))-F(xm-1(k))是第k环方向组中，依次沿各方向搜索函数值下降最大值，即Sm(k)方向函数下降最大。(F3)(F2)(F1)影射点函数下降量△鲍威尔算法的方向淘汰为了构造第k+1环基本方向组，采用如下判别式：按照以下两种情况处理：1、上式中至少一个不等式成立，则第k+1环的基本方向仍用老方向组S1(k)、S2(k)、•••、Sn(k)。k+1环的初始点取x0(k+1)=xn(k)F2F3x0(k+1)=xn+1(k)F2F32、两式均不成立，则淘汰函数值下降最大的方向，并用第k环的新生方向补入k+1环基本方向组的最后，即k+1环的方向组为S1(k)、S2(k)、•••、Sm-1(k)、Sm+1(k)•••、Sn(k)、Sn+1(k)。k+1环的初始点取x0(k+1)=x(k)x(K)是第k环沿Sn+1(K)方向搜索的极小点。鲍威尔算法的终止条件：||x(K)-x0(k)||三修正算法的迭代步骤及流程图Powell算法的步骤如下：⑴任选初始迭代点，选定迭代精度ε，取初始基本方向组为单位坐标矢量系其中，i=1，2……n（下同）。然后令k=1（环数）开始下面的迭代⑵沿诸方向依次进行n次一微搜索，确定各步长使得到点阵i=1，2……n构成新生方向沿方向进行一维搜索求得优化步长，得⑶判断是否满足迭代终止条件。如满足则可结束迭代，最优解为停止计算。否则，继续进行下步。⑷计算各迭代点的函数值，并找出相邻点函数值差最大者（1≤m≤n）及与之相对应的两个点和，并以表示两点的连线方向。⑸确定映射点并计算函数值检验鲍威尔条件若至少其中之一成立转下步，否则转步骤⑺⑹置k+1环的基本方向组和起始点为（即取老方向组）当F2＜F3当F2≥F3令k←k+1，返回步骤⑵⑺置k+1环的方向组和起始点为令k←k+1，返回步骤⑵例题4.2试用鲍威尔修正算法求目标函数的最优解。已知初始点，迭代精度ε=0.001解：第一环迭代计算沿第一坐标方向e1进行一维搜索α1=2以为起点，改沿第二坐标轴方向e2进行一维搜索α2=0.5构成新方向沿S1方向进行以为搜索得极小点与极小值计算点距需进行第二环迭代计算第二环迭代计算首先确定上环中的最大函数下降量及其相应方向映射点及其函数值检查鲍威尔条件于是可知鲍威尔条件两式均不成立。第二环取基本方向组和起始点为沿e2方向作一维搜索得以为起点沿S1方向一维搜索得构成新生方向沿S2方向一维搜索得检查迭代终止条件需再作第三环迭代计算。根据具体情况来分析，S1，S2实际上为共轭方向，见下图。本题又是二次函数，有共轭方向的二次收敛性，上面结果就是问题的最优解。可以预料，如果做第三环迭代，则一定各一维搜索的步长为零，必有故得最优解梯度法优化设计是追求目标函数值最小，因此，自然可以设想从某点出发，其搜索方向取该点的负梯度方向，使函数值在该点附近下降最快。这种方法也称为最速下降法。一、基本原理梯度法的迭代公式为：x(k+1)=x(k)-(k)g(k)其中g(k)是函数F(x)在迭代点x(k)处的梯度f(x(k))，(k)一般采用一维搜索的最优步长，即f(x(k+1))=f(x(k)-(k)g(k))=minf(x(k)-(k)g(k))=min()据一元函数极值条件和多元复合函数求导公式，得’()=-(f(x(k)-(k)g(k)))Tg(k)=0即(f(x(k+1)))Tg(k)=0或(g(k+1))Tg(k)=0此式表明，相邻的两个迭代点的梯度是彼此正交的。也即在梯度的迭代过程中，相邻的搜索方向相互垂直。梯度法向极小点的逼近路径是锯齿形路线，越接近极小点，锯齿越细，前进速度越慢。这是因为梯度是函数的局部性质，从局部上看，在该点附近函数的下降最快，但从总体上看则走了许多弯路，因此函数值的下降并不快。二、迭代终止条件采用梯度准则：||g(k)||三、迭代步骤（1）任选初始迭代点x(0)，选收敛精度。（2）确定x(k)点的梯度（开始k=0)（3）判断是否满足终止条件||g(k)||？若满足输出最优解，结束计算。否则转下步。（4）从x(k)点出发，沿-g(k)方向作一维搜索求最优步长(k)。得下一迭代点x(k+1)=x(k)-(k)g(k),令k=k+1返回步骤(2)。四、梯度法流程图入口给定：x(0)，k=0||g(k)||？x*=x(k)f*=f(x(k))出口x(k)=x(0)计算：g(k)k=k+1沿g(k)方向一维搜索，求最优步长(k)。x(k+1)=x(k)-(k)g(k)/||g(k)||NY例题4.3用梯度法求目标函数的最优解。已知初始点迭代精度ε=0.005解：函数的梯度第一次迭代：以为起点沿一方向作一维搜索得第一个迭代点继续第二次迭代到第五次迭代结束时，有故迭代可终止，最优解为迭代数据表见课本表4.2共轭梯度法共轭梯度法是共轭方向法的一种，因为该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来的，所以称作共轭梯度法。一、共轭梯度法