无约束最优化方法直接搜索法课件.ppt

1、 无约束最优化方法无约束最优化方法无约束最优化方法o 求解无约束最优化问题求解无约束最优化问题 min f(x)的数值的数值迭代解法。迭代解法。o 构成约束最优化方法的基础解法。构成约束最优化方法的基础解法。o 求解无约束最优化问题的下降迭代解法具有求解无约束最优化问题的下降迭代解法具有统一的迭代格式，其基本问题是选择搜索方统一的迭代格式，其基本问题是选择搜索方向和在这些搜索方向上进行一维搜索。向和在这些搜索方向上进行一维搜索。o 由于构成搜索方向的方式可以不同，从而形由于构成搜索方向的方式可以不同，从而形成了各种不同的无约束最优化方法。成了各种不同的无约束最优化方法。无约束优化的直接搜索法无

2、约束优化的直接搜索法 各种无约束优化方法的区别就在于确定其搜索方向各种无约束优化方法的区别就在于确定其搜索方向S(k)的方法不同，所以搜索方向的构成问题是无约束优化方法的关的方法不同，所以搜索方向的构成问题是无约束优化方法的关键。根据构造搜索方向所使用的信息性质的不同，无约束优化键。根据构造搜索方向所使用的信息性质的不同，无约束优化方法可以分为两类：方法可以分为两类：X(k+1)=X(k)+(k)S(k)(k=0,1,2,)一类是只利用目标函数值信息的无约束优化方法，如坐标一类是只利用目标函数值信息的无约束优化方法，如坐标轮换法、鲍威尔法，称为直接搜索法；另一类是利用目标函数的轮换法、鲍威尔法

3、，称为直接搜索法；另一类是利用目标函数的一阶或二阶导数信息的无约束优化方法，如梯度法、牛顿法、共一阶或二阶导数信息的无约束优化方法，如梯度法、牛顿法、共轭梯度法、变尺度法，称为间接搜索法。轭梯度法、变尺度法，称为间接搜索法。基本思想基本思想 坐标轮换法（变量轮换法、交替法、降维法）坐标轮换法（变量轮换法、交替法、降维法）将将n维无约束优化问题转化为维无约束优化问题转化为n个沿坐标轴方向个沿坐标轴方向ei(i=1,2,n)的一维优化问题来求解，并记完成的一维优化问题来求解，并记完成n次一次一维搜索为一轮。若一轮搜索后未得到满足精度要求的最优点，维搜索为一轮。若一轮搜索后未得到满足精度要求的最优点

4、，则继续下一轮迭代搜索。如此反复，直至得到满足精度要求则继续下一轮迭代搜索。如此反复，直至得到满足精度要求的最优点为止。在每一轮搜索中，每次迭代仅对的最优点为止。在每一轮搜索中，每次迭代仅对n元函数的元函数的一个变量沿其坐标轴方向进行一维搜索，其余一个变量沿其坐标轴方向进行一维搜索，其余n-1个变量均个变量均保持不变，再依次轮换进行一维搜索的坐标轴，直至完成沿保持不变，再依次轮换进行一维搜索的坐标轴，直至完成沿n个坐标轴方向的个坐标轴方向的n次一维搜索。次一维搜索。x1x2X0(1)X1(1)X2(1)取初始点取初始点X(0)=X0(1)，x1坐标轴方向的单位向量坐标轴方向的单位向量S1(1)

5、=e1=1 0T，x2坐标轴方向的单位向量坐标轴方向的单位向量S2(1)=e2=0 1T。X1(1)=X0(1)+1(1)S1(1)，X2(1)=X1(1)+2(1)S2(1)判断是否满足迭代收敛准则：判断是否满足迭代收敛准则：|X2(1)X0(1)|？X1(1)=X0(1)+1(1)e1(1)=x1(0)x2(0)T +1(1)1 0T X2(1)=X1(1)+2(1)e2(1)=x1(1)x2(1)T +2(1)0 1T第一轮迭代搜索：第一轮迭代搜索：若满足，则输出最优解，否则，继续下一轮迭代搜索。若满足，则输出最优解，否则，继续下一轮迭代搜索。Xi(k)=Xi-1(k)+i(k)ei(k

6、)(k迭代轮次，迭代轮次，i k轮迭代的第轮迭代的第i次一维搜索次一维搜索 i(k)一维搜索求得的最优步长）一维搜索求得的最优步长）|Xn(k)X0(k)|？计算步骤与算法框图计算步骤与算法框图 1）任选初始点）任选初始点X(0)=X0(1)=x1(0)x2(0)xn(0)T，给定迭代收敛精度给定迭代收敛精度，i=1，k=1。2）置）置n个坐标轴方向向量为单位向量，即个坐标轴方向向量为单位向量，即e1=1 0 0 T，e2=0 1 0 0 T，en=0 0 1T。3）按如下迭代计算公式进行迭代计算）按如下迭代计算公式进行迭代计算 Xi(k)=Xi-1(k)+i(k)ei(k)(k迭代轮次，迭代

7、轮次，i k轮迭代的第轮迭代的第i次一维搜索次一维搜索 i=1，2，n）4）判断是否满足迭代收敛准则）判断是否满足迭代收敛准则|Xn(k)X0(k)|？若满足，则输出最优解若满足，则输出最优解:X*=Xn(k)，f*=f(X*)否则，令否则，令X0(k+1)=Xn(k)，k k+1，返回，返回3）。）。单纯形替换法单纯形替换法 基本思想基本思想 通过计算出若干点处的函数值，对其大小进行比较，可通过计算出若干点处的函数值，对其大小进行比较，可以看出函数值变化的大致趋势，从而可以寻求使函数值下降的以看出函数值变化的大致趋势，从而可以寻求使函数值下降的搜索方向。在搜索方向。在n维空间中，由维空间中，

8、由n+1个不同点顺序相连，就可以个不同点顺序相连，就可以构成一个具有构成一个具有n+1个顶点的多面体个顶点的多面体称之为单纯形。计算函称之为单纯形。计算函数在这数在这n+1个顶点的函数值，并进行比较，据此来确定有利的个顶点的函数值，并进行比较，据此来确定有利的搜索方向和步长，找到一个比较好的点来取代单纯形中较差的搜索方向和步长，找到一个比较好的点来取代单纯形中较差的那个顶点，从而组成了一个新的单纯形，并用之取代原来的单那个顶点，从而组成了一个新的单纯形，并用之取代原来的单纯形。如此下去，新单纯形不断地向目标函数的极小点靠近，纯形。如此下去，新单纯形不断地向目标函数的极小点靠近，直到搜索到极小点

9、为止。直到搜索到极小点为止。计算步骤计算步骤 1）构造初始单纯形）构造初始单纯形 选初始点选初始点X0，和步长，和步长h。从。从X0出发沿各坐标轴方向分别出发沿各坐标轴方向分别走步长走步长h，得到，得到n个顶点个顶点Xi(i=1,2,n)，与，与X0构成初始构成初始单纯形。单纯形。X0 x2x1X1X2 2）计算各顶点的函数值）计算各顶点的函数值 fi=f(Xi)(i=0,1,2,n)3）比较函数值大小，确定最好点）比较函数值大小，确定最好点XL、最差点、最差点 XH 和次差点和次差点 XG，即，即:fL=f(XL)=min fi:i=0,1,2,n fH=f(XH)=max fi:i=0,1

10、,2,n fG=f(XG)=max fi:i=0,1,2,n;i H 4）检验是否满足迭代收敛条件）检验是否满足迭代收敛条件|(fH fL)/fL|?若满足，则结束迭代计算，并输出若满足，则结束迭代计算，并输出 X*=XL 和和 f*=f L 否则，转下一步。否则，转下一步。5）计算除）计算除XH点外的各点的点外的各点的“重心重心”Xn+1，即，即Xn+1=(Xi XH)/n 计算反射点：计算反射点：Xn+2=2Xn+1 XH 和和 fn+2=f(Xn+2)当当 f L fn+2 fG 时，以时，以Xn+2 代替代替XH，fn+2 代代替替 fH，构造新的单纯形，然后返回到，构造新的单纯形，然

11、后返回到 3）。）。X0 x2x1X1X2XHXLXGXn+1Xn+2 6）扩张：当）扩张：当 fn+2 f L 时，取时，取扩张点扩张点Xn+3，即，即Xn+3=Xn+1+(Xn+2 Xn+1)(=1.22.0)并计算并计算 fn+3=f(Xn+3)。若若 fn+3 fn+2，则以，则以Xn+3 代替代替XH，fn+3代替代替fH，构造一个新的单纯形；否则，以，构造一个新的单纯形；否则，以Xn+2 代代替替XH，fn+2 代替代替fH，构造新的单纯形；然后返回到，构造新的单纯形；然后返回到 3）。）。Xn+3 7）收缩：当）收缩：当 fn+2 f G 时，则需收缩。时，则需收缩。若若 fn+

12、2 fH，则取，则取收缩点收缩点Xn+4：Xn+4=Xn+1+(Xn+2 Xn+1)（=0.5）fn+4=f(Xn+4)否则，以否则，以XH代替上式中的代替上式中的Xn+2，计算计算收敛点收敛点Xn+4：Xn+4=Xn+1+(XH Xn+1)fn+4=f(Xn+4)X0 x2x1X1X2XHXLXGXn+1Xn+2Xn+3 若若 fn+4 fH，则以，则以Xn+4 代替代替XH，fn+4代替代替fH，形，形成新的单纯形，然后返回到成新的单纯形，然后返回到 3）；否则转下一步）；否则转下一步8）。）。Xn+4Xn+4 8）缩边：将单纯形向）缩边：将单纯形向XL缩边，可以将各向量缩边，可以将各向量

13、 (Xi XL)(i=0,1,2,n)的长度都缩小一半，即的长度都缩小一半，即 Xi=XL+0.5(Xi XL)=0.5(Xi +XL)(i=0,1,2,n)形成新的单纯形，然后返回到形成新的单纯形，然后返回到 2）。）。鲍威尔（鲍威尔（Powell）法）法 基本思想基本思想 它是直接利用函数值来构造共轭搜索方向的一种共轭它是直接利用函数值来构造共轭搜索方向的一种共轭搜索方向法，又称鲍威尔共轭方向法或方向加速法。由于对搜索方向法，又称鲍威尔共轭方向法或方向加速法。由于对于于n维正定二次函数，共轭搜索方向具有维正定二次函数，共轭搜索方向具有n次收敛的特性，所次收敛的特性，所以鲍威尔法是直接搜索法

14、中十分有效的一种算法，一般认为以鲍威尔法是直接搜索法中十分有效的一种算法，一般认为对于维数对于维数n 20的目标函数它是成功的。鲍威尔法是在研究的目标函数它是成功的。鲍威尔法是在研究具有正定对称矩阵具有正定对称矩阵H的二次函数的极小化问题时形成的，其的二次函数的极小化问题时形成的，其基本思想是在不用函数导数信息的前提下，在迭代过程中逐基本思想是在不用函数导数信息的前提下，在迭代过程中逐次构造关于次构造关于H的共轭方向。的共轭方向。共轭方向的生成共轭方向的生成 设是设是X(k)和和 X(k+1)为从不同点出发，沿同一方向进行为从不同点出发，沿同一方向进行一维搜索一维搜索而得到的两个极小点。而得到

15、的两个极小点。S(j)S(j)S(k)X(k)X(k+1)f(X(k)f(X(k+1)S(j)T f(X(k)=0 S(j)T f(X(k+1)=0 具有正定对称矩阵具有正定对称矩阵H的二次函数的二次函数 f(X)=0.5 XT H X +BT X+C 在在 X(k)和和 X(k+1)两点处的梯度可以表示为两点处的梯度可以表示为 f(X(k)=H X(k)+B （1）f(X(k+1)=H X(k+1）+B （2）（2）（1）得）得f(X(k+1)f(X(k)=H(X(k+1)X(k)（3）（3）式两边同时左乘）式两边同时左乘S(j)T得得S(j)Tf(X(k+1)f(X(k)=S(j)TH(X

16、(k+1)X(k)=0即即 S(j)T H(X(k+1)X(k)=0若取若取 S(k)=X(k+1)X(k)那么，那么，S(k)和和 S(j)关于关于H 共轭，即共轭，即 S(j)T H S(k)=0 这说明：这说明：沿沿S(j)方向分别对函数做两次一维搜索，得到两个方向分别对函数做两次一维搜索，得到两个极小点极小点X(k)和和 X(k+1)，该两点的连线方向，该两点的连线方向S(k)与与S(j)是关是关于于H 共轭的方向。共轭的方向。X(k)x1x2X*S(j)X(k+1)S(k)上述生成共轭方向的方法完全可以推广到上述生成共轭方向的方法完全可以推广到n维优化问题维优化问题中，即在中，即在n

17、维空间中，按上述方法可以生成维空间中，按上述方法可以生成n个相互共轭的搜个相互共轭的搜索方向。索方向。鲍威尔法的基本原理和迭代过程鲍威尔法的基本原理和迭代过程 1）采用坐标轮换法顺次沿）采用坐标轮换法顺次沿n个坐标轴方向进行一维搜个坐标轴方向进行一维搜索，然后以初始点索，然后以初始点X(0)和终点和终点Xn(1)构成一个构成一个新的方向新的方向 S(1)，并以此方向为搜索方向再作一维搜索得到极小点并以此方向为搜索方向再作一维搜索得到极小点Xn+1(1)。2）取始点）取始点X0(2)=Xn+1(1)，并，并去掉去掉原搜索方向组中原搜索方向组中的的第一个方向第一个方向S1(1)=e1，而将第一轮构

18、成的，而将第一轮构成的新搜索方向新搜索方向 S(1)作为作为最末一个方向最末一个方向，以此组成第二轮迭代的，以此组成第二轮迭代的n个方向。个方向。依此进行下去，直到获得满足迭代收敛精度要求的近似极小依此进行下去，直到获得满足迭代收敛精度要求的近似极小点为止。点为止。根据这一原理构造的迭代算法称为根据这一原理构造的迭代算法称为鲍威尔基本算法。鲍威尔基本算法。X1(1)X*S1(1)X0(1)S2(1)S(1)x1x2X2(1)X3(1)X1(2)X2(2)S(2)鲍威尔基本算法的缺点鲍威尔基本算法的缺点 鲍威尔基本算法仅具有理论意义，不要说对于一般的鲍威尔基本算法仅具有理论意义，不要说对于一般的

19、函数，就是对于二次函数，它也可能失效。因为在迭代过程函数，就是对于二次函数，它也可能失效。因为在迭代过程中的中的n个搜索方向有时会变成线性相关，而不能形成共轭方向，个搜索方向有时会变成线性相关，而不能形成共轭方向，从而张不成从而张不成n维空间，导致随后的迭代搜索在降维（维空间，导致随后的迭代搜索在降维（“退化退化”）的空间中进行，可能求不到极小点，故需进行改进。的空间中进行，可能求不到极小点，故需进行改进。那么，为什么会产生这种情况呢？又该如何去改进呢？那么，为什么会产生这种情况呢？又该如何去改进呢？鲍威尔条件及鲍威尔修正算法鲍威尔条件及鲍威尔修正算法 鲍威尔基本算法中，每一轮迭代都是用连接始

20、点和终鲍威尔基本算法中，每一轮迭代都是用连接始点和终点所产生的新搜索方向去机械地替换原方向组中的第一个搜点所产生的新搜索方向去机械地替换原方向组中的第一个搜索方向，而不做任何的索方向，而不做任何的“好坏好坏”判断，这正是产生向量线性判断，这正是产生向量线性相关而发生相关而发生“退化退化”的根本原因所在。为了避免这种的根本原因所在。为了避免这种“退化退化”现象的发生，鲍威尔对这一基本算法进行了修正。即在每一现象的发生，鲍威尔对这一基本算法进行了修正。即在每一轮产生新的搜索方向轮产生新的搜索方向S(k)后，首先判断原搜索方向组是否可后，首先判断原搜索方向组是否可以直接用作下一轮迭代的搜索方向组，若

21、可以，则仍用之，以直接用作下一轮迭代的搜索方向组，若可以，则仍用之，否则，还要进一步判断原搜索方向组中哪个方向上函数值下否则，还要进一步判断原搜索方向组中哪个方向上函数值下降量最大或贡献最大，然后再用新搜索方向替换这个贡献最降量最大或贡献最大，然后再用新搜索方向替换这个贡献最大的搜索方向，以保证逐次生成共轭方向，即每一轮迭代的大的搜索方向，以保证逐次生成共轭方向，即每一轮迭代的搜索方向组线性无关。搜索方向组线性无关。对第对第 k 轮迭代，记轮迭代，记f 1=f(X0(k)f 2=f(Xn(k)f 3=f(2Xn(k)-X0(k)及及 m(k)=max f(Xi-1(k)-f(Xi(k),i=1

22、,2,n，并 记并 记 Sm(k)为 与 为 与 m(k)相 对 应 的 搜 索 方 向，相 对 应 的 搜 索 方 向，S(k)=Xn(k)-X0(k)鲍威尔条件：鲍威尔条件：若若 f 3 f 1,且且(f1-2f2+f3)(f1-f2-m(k)2 0.5 m(k)(f1-f3)2同时成立，则用同时成立，则用S(k)替代替代Sm(k)；否则，仍用原搜索方向组。这；否则，仍用原搜索方向组。这就是就是鲍威尔修正算法鲍威尔修正算法，通常所说的，通常所说的鲍威尔算法鲍威尔算法就是指这一修正算就是指这一修正算法。法。鲍威尔算法的计算步骤及算法框图鲍威尔算法的计算步骤及算法框图 1）任选初始点）任选初始

23、点X(0)=X0(1)，给定迭代收敛精度，给定迭代收敛精度 1,2。取初始基本方向组为取初始基本方向组为单位坐标向量系，即单位坐标向量系，即Si(1)=ei (i=1,2,n),并置迭代轮次并置迭代轮次k=1。2）从）从X0(k)出发，依次沿出发，依次沿Si(k)(i=1,2,n)作一维作一维搜索，得搜索，得n个极小点个极小点Xi(k)(i=1,2,n),构造新的搜索构造新的搜索方向方向 S(k)=Xn(k)-X0(k)，并沿此方向进行一维搜索得极小点，并沿此方向进行一维搜索得极小点Xn+1(k)。3）判断迭代终止条件）判断迭代终止条件|Xn+1(k)X0(k)|1？或或|f(Xn+1(k)f

24、(X0(k)|2|f(Xn+1(k)|？若满足，则终止迭代并输出最优解：若满足，则终止迭代并输出最优解：X*=Xn+1(k)和和 f*=f(X*)否则，则继续下面的迭代计算。否则，则继续下面的迭代计算。4）计算）计算 f(Xi(k)(i=1,2,n)，并求，并求 m(k)=max f(Xi-1(k)-f(Xi(k),i=1,2,n =fm-1-fm及与之对应的两个点及与之对应的两个点Xm-1(k)和和Xm(k)(1m n),则第则第k轮迭轮迭代中贡献最大的方向为代中贡献最大的方向为 Sm(k)=Xm(k)Xm-1(k)5）确定映射点）确定映射点 X(k)=2Xn(k)X0(k)，并计算，并计算

25、f(X(k)，记记f1=f(X0(k),f2=f(Xn(k)及及 f3=f(X(k)检验鲍威尔条件，若满足，则转下一步，否则转第检验鲍威尔条件，若满足，则转下一步，否则转第7）步。）步。6）置第）置第k+1轮迭代的出发点和搜索方向组轮迭代的出发点和搜索方向组 X0(k+1)=Xn+1(k)Si(k+1)(i=1,2,n)即即 S1(k),Sm-1(k),S(k),Sm+1(k),Sn(k)并置并置 k k+1，返回第，返回第2）步。）步。7）置第）置第k+1轮迭代的出发点和搜索方向组轮迭代的出发点和搜索方向组 若若 f2 f3，X0(k+1)=Xn(k)；否则，；否则，X0(k+1)=X(k)。Si(k+1)=Si(k)(i=1,2,n)并置并置 k k+1，返回第，返回第2）步。）步。