无约束优化方法

无约束优化方法第1页，共57页，2023年，2月20日，星期五第四章无约束优化方法，

（4）对于多维无约束问题来说，古典极值理论中令一阶导数为零，但要求二阶可微，且要判断海赛矩阵为正定才能求得极小点，这种方法有理论意义，但无实用价值。和一维问题一样，若多元函数F(X)不可微，亦无法求解。但古典极值理论是无约束优化方法发展的基础。第2页，共57页，2023年，2月20日，星期五第四章无约束优化方法第一节概述，

对于无约束优化问题的求解，可以直接应用第二章的极值条件来确定极值点位置。这就是把求函数极值的问题变成求解方程无约束优化问题是：求n维设计变量使目标函数

这是一个含有n个未知量，n个方程的方程组，并且一般是非线性的。对于非线性方程组，一般是很难用解析方法求解的，需要采用数值计算方法逐步求出非线性联立方程组的解。第3页，共57页，2023年，2月20日，星期五第四章无约束优化方法第一节概述，数值解法：是从给定的初始点x0出发，沿某一搜索方向d0进行搜索。确定最佳步长α，使函数值沿d0方向下降最大。依此方式按下述公式不断进行，形成迭代的下降算法。1）选择迭代方向即探索方向；2）在确定的方向上选择适当步长迈步进行探索。

各种无约束优化方法的区别就在于确定其搜索方向dk的方法不同。所以搜索方向的构成问题是无约束优化方法的关键。第4页，共57页，2023年，2月20日，星期五第四章无约束优化方法第一节概述，第5页，共57页，2023年，2月20日，星期五第四章无约束优化方法第一节概述，无约束优化方法可以分成两类：一类是利用目标函数的一阶或二阶导数的无约束优化方法（如最速下降法、共轭梯度法、牛顿法及变尺度法）；另一类只利用目标函数的无约束优化方法（如坐标轮换法、单形替换法及鲍威尔法等）。第6页，共57页，2023年，2月20日，星期五第四章无约束优化方法第二节最速下降法，最速下降法的迭代公式定义：最速下降法就是采用使目标函数值下降得最快的负梯度方向作为探索方向，来求目标函数的极小值的方法，又称为梯度法。第7页，共57页，2023年，2月20日，星期五第四章无约束优化方法第二节最速下降法，

为了使目标函数值沿搜索方向能够获得最大的下降值，其步长因子应取一维搜索的最佳步长。即有

根据一元函数极值的必要条件和多元复合函数求导公式，得

第8页，共57页，2023年，2月20日，星期五第四章无约束优化方法第二节最速下降法，

在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。这就是说在迭代点向函数极小点靠近的过程，走的是曲折的路线。形成“之”字形的锯齿现象，而且越接近极小点锯齿越细。

图4-2最速下降法的搜索路径第9页，共57页，2023年，2月20日，星期五第四章无约束优化方法第二节最速下降法，最速下降法的迭代步骤：第10页，共57页，2023年，2月20日，星期五第四章无约束优化方法第二节最速下降法，第11页，共57页，2023年，2月20日，星期五第四章无约束优化方法，沿负梯度方向进行一维搜索，有为一维搜索最佳步长，应满足极值必要条件

解取初始点则初始点处函数值及梯度分别为第12页，共57页，2023年，2月20日，星期五第四章无约束优化方法，算出一维搜索最佳步长

第一次迭代设计点位置和函数值

继续作下去，经10次迭代后，得到最优解

第13页，共57页，2023年，2月20日，星期五第四章无约束优化方法，

这个问题的目标函数的等值线为一簇椭圆,迭代点从走的是一段锯齿形路线，见图4-3。第14页，共57页，2023年，2月20日，星期五第四章无约束优化方法，将上例中目标函数引入变换其等值线由椭圆变成一簇同心圆。

仍从即出发进行最速下降法寻优。此时：沿负梯度方向进行一维搜索：则函数f(X)变为：y1=x1,y2=5x2第15页，共57页，2023年，2月20日，星期五第四章无约束优化方法，β为一维搜索最佳步长，可由极值条件：由从而算得第一次走步后设计点的位置及其相应的目标函数：第16页，共57页，2023年，2月20日，星期五第四章无约束优化方法，经变换后，只需一次迭代，就可找到最优解。这是因为经过尺度变换：等值线由椭圆变成圆。第17页，共57页，2023年，2月20日，星期五第四章无约束优化方法第二节最速下降法，最速下降法的特点：

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

2）收敛速度不快；

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

4）收敛速度与目标函数值的性质有关，对等值线是同心圆的目标函数来说，经过一次迭代就可以达到极值点。第18页，共57页，2023年，2月20日，星期五第四章无约束优化方法第三节牛顿型法，牛顿型法的基本思想：利用二次曲线来逐点近似原目标函数，以二次曲线的极小点来近似原目标函数的极小点并逐渐逼近该点。

基本牛顿法的迭代公式：第19页，共57页，2023年，2月20日，星期五第四章无约束优化方法第三节牛顿型法，基本牛顿法的迭代公式：第20页，共57页，2023年，2月20日，星期五第四章无约束优化方法第三节牛顿型法，基本牛顿法的迭代公式：阻尼牛顿法的迭代公式：第21页，共57页，2023年，2月20日，星期五第四章无约束优化方法

第三节牛顿型法，阻尼牛顿法的迭代步骤：第22页，共57页，2023年，2月20日，星期五第四章无约束优化方法第三节牛顿型法，阻尼牛顿法的迭代公式：第23页，共57页，2023年，2月20日，星期五第四章无约束优化方法第四节共轭方向及共轭方向法，

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

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

第28页，共57页，2023年，2月20日，星期五第四章无约束优化方法第四节共轭方向及共轭方向法，第29页，共57页，2023年，2月20日，星期五第四章无约束优化方法第五节共轭梯度法，共轭梯度法：先沿最速下降方向(负梯度方向)探索第一步，然后沿与该负梯度方向相共轭的方向进行探索。第30页，共57页，2023年，2月20日，星期五第四章无约束优化方法第五节共轭梯度法，共轭方向与梯度之间的关系：

它表示沿着方向dk做一维搜索，它的终点xk+1与始点xk的梯度之差与dk的共轭方向dj正交。第31页，共57页，2023年，2月20日，星期五第四章无约束优化方法第五节共轭梯度法，共轭梯度法递推公式：第32页，共57页，2023年，2月20日，星期五第四章无约束优化方法第五节共轭梯度法，共轭梯度法步骤：第33页，共57页，2023年，2月20日，星期五第四章无约束优化方法第五节共轭梯度法，共轭梯度法步骤：第34页，共57页，2023年，2月20日，星期五第四章无约束优化方法第五节共轭梯度法，共轭梯度法第35页，共57页，2023年，2月20日，星期五

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

,那么就简化了牛顿法的计算，并且保持了牛顿法收敛快的优点。第四章无约束优化方法第六节变尺度法（拟牛顿法），变尺度法的基本思想：牛顿方向：变尺度法的迭代公式：尺度矩阵第36页，共57页，2023年，2月20日，星期五第四章无约束优化方法第六节变尺度法（拟牛顿法），尺度矩阵G正定牛顿迭代公式：目的：目标函数的偏心率减小到零。第37页，共57页，2023年，2月20日，星期五第四章无约束优化方法第六节变尺度法（拟牛顿法），变尺度矩阵的建立：变尺度法的迭代公式：搜索方向：尺度矩阵应具备的条件：1）为正定对称矩阵；2）具有简单的迭代形式:3）满足拟牛顿条件：令则第38页，共57页，2023年，2月20日，星期五第四章无约束优化方法第六节变尺度法（拟牛顿法），变尺度法的一般步骤：第39页，共57页，2023年，2月20日，星期五第四章无约束优化方法第六节变尺度法（拟牛顿法），变尺度法的流程图：第40页，共57页，2023年，2月20日，星期五第四章无约束优化方法第六节变尺度法（拟牛顿法），DFP算法：DFP算法的校正公式第41页，共57页，2023年，2月20日，星期五第四章无约束优化方法第六节变尺度法（拟牛顿法），DFP算法：第42页，共57页，2023年，2月20日，星期五第四章无约束优化方法第七节坐标轮换法，基本思想：每次仅对多元函数的一个变量沿其坐标轴进行一维探索，其余各变量均固定不动，并依次轮换进行一维探索的坐标轴，完成第一轮探索后再重新进行第二轮探索，直到找到目标函数在全域上的最小点为止。目的：将一个多维的无约束最优化问题，转化为一系列的一维问题来求解。第43页，共57页，2023年，2月20日，星期五第四章无约束优化方法第七节坐标轮换法，二维问题第44页，共57页，2023年，2月20日，星期五第四章无约束优化方法第七节坐标轮换法，第k轮迭代公式：包括正负第45页，共57页，2023年，2月20日，星期五第四章无约束优化方法第七节坐标轮换法，步长α的几种取法：随机选择方法加速步长法最优步长法（一维搜索方法，如：黄金分割法、二次插值法，来确定最优步长）第46页，共57页，2023年，2月20日，星期五第四章无约束优化方法第七节坐标轮换法，加速步长法：第47页，共57页，2023年，2月20日，星期五第四章无约束优化方法第七节坐标轮换法，坐标轮换法的流程图第48页，共57页，2023年，2月20日，星期五第四章无约束优化方法第七节坐标轮换法，坐标轮换法的特点：

计算简单、概念清楚、易于掌握；但搜索路线较长（需要经过多次曲折迂回的路径才能达到极值点），计算率较低，特别是当维数很高时很费时，所以坐标轮换法只能用于低维（n<10）的优化问题求解。此外，坐标轮换法的效率在很大程度上取决于目标函数的性态，也就是等值线的形态与坐标轴的关系。第49页，共57页，2023年，2月20日，星期五第四章无约束优化方法第八节鲍威尔法，鲍威尔法的基本思想：

直接利用迭代点的目标函数值来构造共轭方向，然后再从任一初始点出发，逐次的共轭方向作一维搜索求极值点。第50页，共57页，2023年，2月20日，星期五第四章无约束优化方法第八节鲍威尔法，共轭方向的生成：结论：从不同的两点出发，沿同一方向进行两次一维搜索，所得两个极小点的连线方向便是原方向共轭的另一方向。第51页，共57页，2023年，2月20日，星期五第四章无约束优化方法第八节鲍威尔法，共轭方向的生成：二维情况：任意点出发沿着x1轴方向和AB方向搜索，即可得到极小点。第52页，共57页，2023年，2月20日，星期五第四章无约束优化方法第八节鲍威尔法，基本POWELL法（二维）：第53页，共57页，2023年，2月20日，星期五第四章无约束优化方法第八节鲍威尔法基本POWELL法（n维）：1）从初始点出发，首先沿着n个坐标轴方向进行一维搜索，得到一个终点；2）由初始点和终点连线形成一个新方向，该方向排在原方向组的最后，去掉原方向组的的第一个方向，形成新的方向组；3）从上一轮的搜索终