4 无约束最优化方法-直接搜索法

的数值迭代解法。求解无约束最优化问题的下降迭代解法具有统一的迭代格式，其基本问题是选择搜索方向和在这些搜索方向上进行一维搜索。由于构成搜索方向的方式可以不同，从而形成了各种不同的无约束最优化方法。无约束优化的直接搜索法各种无约束优化方法的区别就在于确定其搜索方向S的方法不同，所以搜索方向的构成问题是无约束优化方法的关键。根据构造搜索方向所使用的信息性质的不同，无约束优化方法可以分为两类：一类是只利用目标函数值信息的无约束优化方法，如坐标轮换法、鲍威尔法，称为直接搜索法；另一类是利用目标函数的一阶或二阶导数信息的无约束优化方法，如梯度法、牛顿法、共轭梯度法、变尺度法，称为间接搜索法。基本思想坐标轮换法（变量轮换法、交替法、降维法）将n维无约束优化问题转化为n个沿坐标轴方向en)的一维优化问题来求解，并记完成n次一维搜索为一轮。若一轮搜索后未得到满足精度要求的最优点，则继续下一轮迭代搜索。如此反复，直至得到满足精度要求的最优点为止。在每一轮搜索中，每次迭代仅对n元函数的一个变量沿其坐标轴方向进行一维搜索，其余n-1个变量均保持不变，再依次轮换进行一维搜索的坐标轴，直至完成沿n个坐标轴方向的n次一维搜索。

第一轮迭代搜索：若满足，则输出最优解，否则，继续下一轮迭代搜索。计算步骤与算法框图1）任选初始点Xk+1，返回3）。单纯形替换法基本思想通过计算出若干点处的函数值，对其大小进行比较，可以看出函数值变化的大致趋势，从而可以寻求使函数值下降的搜索方向。在n维空间中，由n+1个不同点顺序相连，就可以构成一个具有n+1个顶点的多面体——称之为单纯形。计算函数在这n+1个顶点的函数值，并进行比较，据此来确定有利的搜索方向和步长，找到一个比较好的点来取代单纯形中较差的那个顶点，从而组成了一个新的单纯形，并用之取代原来的单纯形。如此下去，新单纯形不断地向目标函数的极小点靠近，直到搜索到极小点为止。计算步骤1）构造初始单纯形选初始点X出发沿各坐标轴方向分别走步长h，得到n个顶点X构成初始单纯形。否则，转下一步。5）计算除X计算反射点：Xn+22Xn+1n+2代替Xn+26）扩张：当fn+2n+2，则以Xn+3代替n+3代替f，构造一个新的单纯形；否则，以Xn+2n+2代替fn+37）收缩：当fn+2，则取收缩点Xn+4代替上式中的Xn+2计算收敛点Xn+4，则以Xn+4代替Xn+4代替fn+48）缩边：将单纯形向X形成新的单纯形，然后返回到2）。

鲍威尔（Powell）法基本思想它是直接利用函数值来构造共轭搜索方向的一种共轭搜索方向法，又称鲍威尔共轭方向法或方向加速法。由于对于n维正定二次函数，共轭搜索方向具有n次收敛的特性，所以鲍威尔法是直接搜索法中十分有效的一种算法，一般认为对于维数n20的目标函数它是成功的。鲍威尔法是在研究具有正定对称矩阵H的二次函数的极小化问题时形成的，其基本思想是在不用函数导数信息的前提下，在迭代过程中逐次构造关于H的共轭方向。(k+1)为从不同点出发，沿同一方向进行一维搜索而得到的两个极小点。(k+1)两点处的梯度可以表示为HX(k+1）关于H共轭，即方向分别对函数做两次一维搜索，得到两个极小点X(k+1)，该两点的连线方向S上述生成共轭方向的方法完全可以推广到n维优化问题中，即在n维空间中，按上述方法可以生成n个相互共轭的搜索方向。鲍威尔法的基本原理和迭代过程1）采用坐标轮换法顺次沿n个坐标轴方向进行一维搜索，然后以初始点X并以此方向为搜索方向再作一维搜索得到极小点Xn+1，并去掉原搜索方向组中的第一个方向S作为最末一个方向，以此组成第二轮迭代的n个方向。依此进行下去，直到获得满足迭代收敛精度要求的近似极小点为止。

根据这一原理构造的迭代算法称为鲍威尔基本算法。鲍威尔基本算法的缺点鲍威尔基本算法仅具有理论意义，不要说对于一般的函数，就是对于二次函数，它也可能失效。因为在迭代过程中的n个搜索方向有时会变成线性相关，而不能形成共轭方向，从而张不成n维空间，导致随后的迭代搜索在降维（“退化”）的空间中进行，可能求不到极小点直线搜索方法,无约束优化方法,约束优化方法，故需进行改进。那么，为什么会产生这种情况呢？又该如何去改进呢？鲍威尔条件及鲍威尔修正算法鲍威尔基本算法中，每一轮迭代都是用连接始点和终点所产生的新搜索方向去机械地替换原方向组中的第一个搜索方向，而不做任何的“好坏”判断，这正是产生向量线性相关而发生“退化”的根本原因所在。为了避免这种“退化”现象的发生，鲍威尔对这一基本算法进行了修正。即在每一轮产生新的搜索方向S后，首先判断原搜索方向组是否可以直接用作下一轮迭代的搜索方向组，若可以，则仍用之，否则，还要进一步判断原搜索方向组中哪个方向上函数值下降量最大或贡献最大，然后再用新搜索方向替换这个贡献最大的搜索方向，以保证逐次生成共轭方向，即每一轮迭代的搜索方向组线性无关。；否则，仍用原搜索方向组。这就是鲍威尔修正算法，通常所说的鲍威尔算法就是指这一修正算鲍威尔算法的计算步骤及算法框图1）任选初始点X),构造新的搜索方向S否则，则继续下面的迭代计算。4）计算f及与之对应的两个点Xm-1检验鲍威尔条件，若满足，则转下一步，否则转第7）步。6）置第k+1轮迭代的出发点和搜索方向组k+1，返回第2）步。7）置第k+1轮迭代的出发点和搜索方向组k+1，返回第2）步。

（编辑：海南站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!