第六节无约束优化方法鲍威尔

第六节无约束优化方法鲍威尔第1页，共44页，2023年，2月20日，星期一§4.5坐标轮换法一.坐标轮换法：1.基本思想：每次搜索只允许一个变量变化，其余变量保持不变，即沿坐标方向轮流进行搜索的寻优方法。它把多变量的优化问题轮流地转化成单变量（其余变量视为常量）的优化问题，因此又称这种方法为变量轮换法。此种方法只需目标函数的数值信息而不需要目标函数的导数。第2页，共44页，2023年，2月20日，星期一计算步骤:⑴任选初始点,确定搜索方向第一轮的起点，置n个坐标轴方向矢量为单位坐标矢量§4.5坐标轮换法第3页，共44页，2023年，2月20日，星期一⑵迭代计算k为迭代轮数的序号，取k=1，2，……；i为该轮中一维搜索的序号，取i=1，2，……n步长α一般通过一维优化方法求出其最优步长。⑶判断是否中止迭代如满足，迭代中止，并输出最优解最优解否则，令k←k+1返回步骤（2）§4.5坐标轮换法

应该是一轮迭代的始点和终点，不是某搜索方向的前后迭代点。第4页，共44页，2023年，2月20日，星期一坐标轮换法的流程图第5页，共44页，2023年，2月20日，星期一例:用坐标轮换法求下列目标函数的无约束最优解。

给定初始点，精度要求ε=0.1解：做第一轮迭代计算沿e1方向进行一维搜索式中，为第一轮的起始点，取第6页，共44页，2023年，2月20日，星期一按最优步长原则确定最优步长α1，即极小化此问题可由某种一维优化方法求出α1:

以为新起点，沿e2方向一维搜索以最优步长原则确定α2，即为极小化第7页，共44页，2023年，2月20日，星期一对于第一轮按终止条件检验计算5轮后，有故近似优化解为第8页，共44页，2023年，2月20日，星期一§4.5

坐标轮换法

3.方法评价：

方法简单，容易实现。当维数增加时，效率明显下降。收敛慢，以振荡方式逼近最优点。

受目标函数的性态影响很大。如图a)所示，二次就收敛到极值点；如图b)所示，多次迭代后逼近极值点；如图c)所示，目标函数等值线出现山脊（或称陡谷），若搜索到A点，再沿两个坐标轴以±t0步长测试，目标函数值均上升，计算机判断A点为最优点。事实上发生错误。第9页，共44页，2023年，2月20日，星期一

鲍威尔方法是直接搜索法中一个十分有效的算法。该算法是沿着逐步产生的共轭方向进行搜索的，因此本质上是一种共轭方向法。§4.6

鲍威尔方法

第10页，共44页，2023年，2月20日，星期一一、共轭方向的生成§4.6

鲍威尔方法

为两个极小点根据梯度与等值面之间关系可知第11页，共44页，2023年，2月20日，星期一一、共轭方向的生成§4.6

鲍威尔方法

对于二次函数，两点处的梯度可表示为代入到公式：第12页，共44页，2023年，2月20日，星期一一、共轭方向的生成§4.6

鲍威尔方法

结论：从不同的点出发沿某一方向分别对函数作两次一维搜索，得到两个极小点，那么这两个极小点的连线方向与该方向对G共轭第13页，共44页，2023年，2月20日，星期一二、鲍威尔基本算法

鲍威尔基本算法的搜索过程（二维）第14页，共44页，2023年，2月20日，星期一二、鲍威尔基本算法

鲍威尔基本算法的搜索过程（三维）第15页，共44页，2023年，2月20日，星期一

鲍威尔基本算法的步骤：

1）第一轮基本方向组取单位坐标矢量系e1、e2、

e3

、…、en，沿这些方向依次作一维搜索，然后将始末两点相连作为新生方向。

2）再沿新生方向作一维搜索，完成第一轮的迭代。以后每轮的基本方向组是将上轮的第一个方向淘汰，上轮的新生方向补入本轮的最后而构成：

d2k

,

d3k,……dnk

,

dk第16页，共44页，2023年，2月20日，星期一

鲍威尔基本算法的缺陷：

可能在某一轮迭代中出现基本方向组为线性相关的矢量系的情况。如第k轮中，产生新的方向：

dk=xnk-x0k=1kd1k+2kd2k+•••+nkdnk

式中，d1k、d2k、

•••、

dnk为第k轮基本方向组矢量，1k

、2k、•••、nk为各方向的最优步长。

若在第k轮的优化搜索过程中出现1k=0，则方向dk表示为d2k、

d3k

、•••、

dnk的线性组合，以后的各次搜索将在降维的空间进行，无法得到n维空间的函数极小值，计算将失败。

第17页，共44页，2023年，2月20日，星期一鲍威尔基本算法的退化x1x2x31=02e23e3S1如图所示为一个三维优化问题的示例，设第一轮中1=0

，则新生方向与e2、e3共面，随后的各环方向组中，各矢量必在该平面内，使搜索局限于二维空间，不能得到最优解。e2e3S1第18页，共44页，2023年，2月20日，星期一三、鲍威尔修正算法

在某轮已经取得的n+1个方向中，选取n个线性无关的并且共轭程度尽可能高的方向作为下一轮的基本方向组

鲍威尔修正算法的搜索方向的构造：在第k轮的搜索中，x0k

为初始点，搜索方向为d1k、d2k

、

•••、

dnk，产生的新方向为dk

，此方向的极小点为xk。沿dk方向移动得到点

xn+1k=2xnk-x0k

，称之为x0k对xnk的映射点。

计算x0k

、

x1k、•••、xnk、xk、xn+1k

各点的函数值，记作：

F1=F(x0k)

F2=F(xnk)

F3=F(xn+1k)=F(xm-1k)-F(xmk)

是第k轮方向组中，依次沿各方向搜索函数下降值第19页，共44页，2023年，2月20日，星期一鲍威尔算法的方向淘汰(F3)(F2)(F1)反射点函数最大下降量△m始点终点第20页，共44页，2023年，2月20日，星期一为了构造第k+1轮基本方向组，采用如下判别式：

按照以下两种情况处理：

1)

上式中至少一个不等式成立，则第k+1轮的基本方向仍用老方向组d1k、d2k、

•••、

dnk。k+1轮的初始点取

x0k+1=xnkF2<F3

x0k+1=xn+1kF2F3

第21页，共44页，2023年，2月20日，星期一2）两式均不成立，则淘汰函数值下降最大的方向，并用第k轮的新生方向补入k+1轮基本方向组的最后，即k+1轮的方向组为d1k、d2k

、•••、dm-1k、dm+1k、•••、dnk、

dk

。(F3)(F2)(F1)反射点始点终点函数最大下降量△m第22页，共44页，2023年，2月20日，星期一k+1轮的初始点取:

x0k+1=xk

xk是第k轮沿dk方向搜索的极小点。

(F3)(F2)(F1)反射点函数下降量△始点终点dk方向极小点第23页，共44页，2023年，2月20日，星期一四、修正算法的迭代步骤及流程图Powell算法的步骤如下：⑴

任选初始迭代点，选定迭代精度ε，取初始基本方向组为单位坐标矢量系其中，i=1，2……n

然后令k=1（轮数）开始迭代⑵

沿诸方向依次进行n次一维搜索，确定各步长第24页，共44页，2023年，2月20日，星期一得到点阵i=1，2……n构成新生方向沿方向进行一维搜索求得优化步长(3)计算各迭代点的函数值，找出相邻点函数值差最大者（1≤m≤n）及与之相对应的两个点和，并以表示两点的连线方向。第25页，共44页，2023年，2月20日，星期一（4）关键点函数值（5）判断是否满足迭代终止条件。则可结束迭代，最优解为停止计算。否则，继续进行下步。第26页，共44页，2023年，2月20日，星期一检验鲍威尔判别条件是否成立若至少其中之一成立转下步，否则转步骤⑺⑹

确定k+1轮的基本方向组和起始点（即取老方向组）当F2＜F3当F2≥F3令k←k+1，返回步骤⑵第27页，共44页，2023年，2月20日，星期一⑺

确定k+1轮的方向组和起始点令k←k+1，返回步骤⑵第28页，共44页，2023年，2月20日，星期一例试用鲍威尔修正算法求目标函数的最优解。已知初始点，迭代精度ε=0.001解：第一轮迭代计算沿第一坐标方向e1进行一维搜索α1=2第29页，共44页，2023年，2月20日，星期一以为起点，改沿第二坐标轴方向e2进行一维搜索α2=0.5构成新方向第30页，共44页，2023年，2月20日，星期一沿d1方向进行一维搜索得极小点与极小值计算点距需进行第二轮迭代计算第31页，共44页，2023年，2月20日，星期一第二轮迭代计算首先确定上轮中的最大函数下降量及其相应方向映射点及其函数值第32页，共44页，2023年，2月20日，星期一检查鲍威尔条件于是可知鲍威尔条件两式均不成立。第二轮取基本方向组和起始点为第33页，共44页，2023年，2月20日，星期一沿e2方向作一维搜索得以为起点沿d1方向一维搜索得第34页，共44页，2023年，2月20日，星期一构成新生方向沿d2方向一维搜索得检查迭代终止条件需再作第三轮迭代计算。第35页，共44页，2023年，2月20日，星期一根据具体情况来分析，d1，d2实际上为共轭方向，见下图。本题又是二次函数，有共轭方向的二次收敛性，上面结果就是问题的最优解。可以预料，如果做第三轮迭代，则一定各一维搜索的步长为零，必有故得最优解第36页，共44页，2023年，2月20日，星期一在不计算导数的情况下，先算出若干点处的函数值，从它们之间的大小关系中也可以看出函数变化的大概趋势，为寻求函数的下降方向提供依据。原理：利用单纯形的顶点，计算其函数值并加以比较，从中确定有利的搜索方向和步长，找到一个较好的点取代单纯形中较差的点，组成新的单纯形来代替原来的单纯形。使新单纯形不断的向目标函数的极小点靠近，直到搜索到极小点位置§4.7

单形替换法方法

第37页，共44页，2023年，2月20日，星期一§4.7

单形替换法方法

设x5称为x1点相对于x4点的反射点x4为x2点、x3点连线的中点取第38页，共44页，2023年，2月20日，星期一§4.7

单形替换法方法

五种情况：1）如果构成新的单纯形x2x3x6如果构成新的单纯形x2x3x5第39页，共44页，2023年，2月20日，星期一§4.7

单形替换法方法

五种情况：2）构成新的单纯形x2x3x5第40页，共44页，2023年