无约束优化方法

关于无约束优化方法第1页，共42页，2023年，2月20日，星期四4.1概述，数值解法：是利用已有的信息，通过计算点一步一步地直接移动，逐步逼近最后达到最优点。1）选择迭代方向即探索方向；2）在确定的方向上选择适当步长迈步进行探索第2页，共42页，2023年，2月20日，星期四，无约束优化方法可以分成两类：一类是利用目标函数的一阶或二阶导数的无约束优化方法（如最速下降法、共轭梯度法、牛顿法及变尺度法）；另一类只利用目标函数的无约束优化方法（如坐标轮换法、单形替换法及鲍威尔法等）。4.1概述第3页，共42页，2023年，2月20日，星期四，定义：最速下降法就是采用使目标函数值下降得最快的负梯度方向作为探索方向，来求目标函数的极小值的方法，又称为梯度法。最速下降法的迭代公式4.2梯度法（最速下降法）第4页，共42页，2023年，2月20日，星期四，最速下降法的迭代步骤：4.2梯度法（最速下降法）第5页，共42页，2023年，2月20日，星期四，4.2梯度法（最速下降法）第6页，共42页，2023年，2月20日，星期四，梯度法的特点：

1）对初始搜索点无严格要求；

2）收敛速度不快；

3）相邻两次迭代搜索方向互相垂直，在远离极值点处收敛快，在靠近极值点处收敛慢；

4）收敛速度与目标函数值的性质有关，对等值线是同心圆的目标函数来说，经过一次迭代就可以达到极值点。4.2梯度法（最速下降法）第7页，共42页，2023年，2月20日，星期四4.3牛顿型法，牛顿型法的基本思想：利用二次曲线来逐点近似原目标函数，以二次曲线的极小点来近似原目标函数的极小点并逐渐逼近该点。

基本牛顿法的迭代公式：第8页，共42页，2023年，2月20日，星期四，基本牛顿法的迭代公式：4.3牛顿型法第9页，共42页，2023年，2月20日，星期四，基本牛顿法的迭代公式：阻尼牛顿法的迭代公式：4.3牛顿型法第10页，共42页，2023年，2月20日，星期四，阻尼牛顿法的迭代步骤：4.3牛顿型法第11页，共42页，2023年，2月20日，星期四，阻尼牛顿法的迭代公式：4.3牛顿型法第12页，共42页，2023年，2月20日，星期四

设法构造出一个对称正定矩阵来代替，并在迭代过程中使逐渐逼近

,那么就简化了牛顿法的计算，并且保持了牛顿法收敛快的优点。4.4变尺度法（拟牛顿法），变尺度法的基本思想：牛顿方向：变尺度法的迭代公式：尺度矩阵第13页，共42页，2023年，2月20日，星期四，尺度矩阵G正定牛顿迭代公式：目的：目标函数的偏心率减小到零。4.4变尺度法（拟牛顿法）第14页，共42页，2023年，2月20日，星期四，变尺度矩阵的建立：变尺度法的迭代公式：搜索方向：尺度矩阵应具备的条件：1）为正定对称矩阵；2）具有简单的迭代形式:3）满足拟牛顿条件：令则4.4变尺度法（拟牛顿法）第15页，共42页，2023年，2月20日，星期四，变尺度法的一般步骤：4.4变尺度法（拟牛顿法）第16页，共42页，2023年，2月20日，星期四，变尺度法的流程图：4.4变尺度法第17页，共42页，2023年，2月20日，星期四，DFP算法：DFP算法的校正公式4.4变尺度法（拟牛顿法）第18页，共42页，2023年，2月20日，星期四，DFP算法：4.4变尺度法（拟牛顿法）第19页，共42页，2023年，2月20日，星期四4.5共轭方向及共轭方向法，

在下一次迭代时，选择搜索方d1指向极小点x*，共轭方向以二元函数为例：我们任意选择一个初始点x0点，沿着某个下降方向d0作一维搜索第20页，共42页，2023年，2月20日，星期四，共轭方向正交4.5共轭方向及共轭方向法第21页，共42页，2023年，2月20日，星期四，共轭方向的性质4.5共轭方向及共轭方向法第22页，共42页，2023年，2月20日，星期四，共轭方向法的步骤4.5共轭方向及共轭方向法第23页，共42页，2023年，2月20日，星期四，共轭方向的形成格拉姆-斯密特向量系共轭化的方法

n个线性无关的向量系vi（i=0,1，…，n-1）一组独立向量dr（r=0,1，…，n-1）

4.5共轭方向及共轭方向法第24页，共42页，2023年，2月20日，星期四，4.5共轭方向及共轭方向法第25页，共42页，2023年，2月20日，星期四，共轭梯度法：先沿最速下降方向(负梯度方向)探索第一步，然后沿与该负梯度方向相共轭的方向进行探索。4.5共轭梯度法第26页，共42页，2023年，2月20日，星期四，共轭方向与梯度之间的关系：

它表示沿着方向dk做一维搜索，它的终点xk+1与始点xk的梯度之差与dk的共轭方向dj正交。4.5共轭梯度法第27页，共42页，2023年，2月20日，星期四，共轭梯度法递推公式：4.5共轭梯度法第28页，共42页，2023年，2月20日，星期四，共轭梯度法步骤：4.5共轭梯度法第29页，共42页，2023年，2月20日，星期四，共轭梯度法步骤：4.5共轭梯度法第30页，共42页，2023年，2月20日，星期四，共轭梯度法4.5共轭梯度法第31页，共42页，2023年，2月20日，星期四4.6鲍威尔法，鲍威尔法的基本思想：

直接利用迭代点的目标函数值来构造共轭方向，然后再从任一初始点出发，逐次的共轭方向作一维搜索求极值点。第32页，共42页，2023年，2月20日，星期四，共轭方向的生成：结论：从不同的两点出发，沿同一方向进行两次一维搜索，所得两个极小点的连线方向便是原方向共轭的另一方向。第八节鲍威尔法第33页，共42页，2023年，2月20日，星期四，共轭方向的生成：二维情况：任意点出发沿着x1轴方向和AB方向搜索，即可得到极小点。第八节鲍威尔法第34页，共42页，2023年，2月20日，星期四，基本POWELL法（二维）：第八节鲍威尔法第35页，共42页，2023年，2月20日，星期四基本POWELL法（n维）：1）从初始点出发，首先沿着n个坐标轴方向进行一维搜索，得到一个终点；2）由初始点和终点连线形成一个新方向，该方向排在原方向组的最后，去掉原方向组的的第一个方向，形成新的方向组；3）从上一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭代的始点。4）从新的始点出发，沿着新的方向组做一维搜索。如此反复进行n轮搜索后，可找到n个共轭方向，若目标函数是正定二次型函数，则经过n轮后就可以找到极小点。第八节鲍威尔法第36页，共42页，2023年，2月20日，星期四改进POWELL法：

获得新方向构成新方向组时,不是轮换地去掉原来的方向,而是经判别后,在n+1个方向中留下最接近共轭的n个方向。第八节鲍威尔法第37页，共42页，2023年，2月20日，星期四1）给定初始点，选取初始方向组，它由n个线性无关的向量组成置k=02）从出发顺次沿作一维搜索得接着以为起点，沿方向移动一个距离得到并分别求出

改进POWELL算法的步骤:一轮迭代的始点一轮迭代的终点一轮迭代的反射点第38页，共42页，2023年，2月20日，星期四同时计算各中间点函数值计算n个函数值之差并找出其中最大的一个（3）根据是否满足判别条件来确定是否对原方向组进行替换。因此有第39页，共42页，2023年，2月20日，星期四，

不满足判别条件，下轮迭代仍用原方向组