现代设计方法之无约束设计的最优化方法

现代设计方法之无约束设计的最优化方法第1页，课件共104页，创作于2023年2月主要内容1、Powell法的应用计算2、梯度法的应用计算3、共轭梯度法的应用计算4、变尺度法的应用计算第2页，课件共104页，创作于2023年2月重点难点共轭与共轭方向的概念共轭方向的形成常用的无约束优化设计方法的基本步骤与几何解释第3页，课件共104页，创作于2023年2月第2章第一节所列举的机械优化设计问题，都是在一定的限制条件下追求某一指标为最小，它们都属于多维约束优化问题。工程问题大都如此。

为什么要研究多维无约束优化问题???

引入

第4页，课件共104页，创作于2023年2月(1)有些实际问题，其数学模型本身就是一个多维无约束优化问题。

(2)通过熟悉它的解法可以为研究多维约束优化问题打下良好的基础。

(3)多维约束优化问题的求解可以通过一系列多维无约束优化方法来达到。所以多维无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。第5页，课件共104页，创作于2023年2月多维无约束优化问题是：求n维设计变量使目标函数：

各种多维无约束优化解法的区别：搜索方向的不同第6页，课件共104页，创作于2023年2月◆分类：（1）直接解法---不使用导数信息，如坐标轮换法、Powell法、随机搜索法、单纯形法等（2）间接解法(解析法)---要使用导数，二阶有梯度法、共轭梯度法、二阶以上用牛顿法搜索方向的构成问题是多维无约束优化方法的关键第7页，课件共104页，创作于2023年2月多维无约束优化方法算法的基本过程:

从选定的某初始点x(k)出发，沿着以一定规律产生的搜索方向S(k)，取适当的步长a(k),逐次搜寻函数值下降的新迭代点x(k+1),使之逐步通近最优点x*。第8页，课件共104页，创作于2023年2月

可以把初始点x(k)、搜索方向S(k)、迭代步长a(k)称为优化方法算法的三要素。其中以搜索方向S(k)更为突出和重要，它从根本上决定一个算法的成败、收敛速率的快慢等。一个算法的搜索方向成为该优化方法的基本标志，分析、确定搜索方向S(k)是研究优化方法的最根本的任务之一。第9页，课件共104页，创作于2023年2月

函数的负梯度方向是函数值下降最快的方向搜索方向S取该点的负梯度方向(最速下降方向)，使函数值在该点附近的范围内下降最快。2.4.1最速下降(梯度)法第10页，课件共104页，创作于2023年2月为了使目标函数值沿搜索方向能够获得最大的下降值，其步长因子应取一维搜索的最佳步长。即有第11页，课件共104页，创作于2023年2月根据一元函数极值的必要条件和多元复合函数求导公式，得

第12页，课件共104页，创作于2023年2月

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

第13页，课件共104页，创作于2023年2月第14页，课件共104页，创作于2023年2月例2.4-1求目标函数的极小点。初始点解：初始点处函数值及梯度分别为第15页，课件共104页，创作于2023年2月沿负梯度方向进行一维搜索，有为一维搜索最佳步长，应满足极值必要条件

第16页，课件共104页，创作于2023年2月算出一维搜索最佳步长

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

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

第17页，课件共104页，创作于2023年2月这一问题的目标函数f(x)的等值线为一簇椭圆。将上例中目标函数引入变换y1=x1,y2=5x2则函数f(x)变为：其等值线由椭圆变成一簇同心圆。第18页，课件共104页，创作于2023年2月

仍从

即

出发进行最速下降法寻优。此时：沿负梯度方向进行一维搜索：第19页，课件共104页，创作于2023年2月β为一维搜索最佳步长，可由极值条件：由从而算得一步计算后设计点的位置及其目标函数：第20页，课件共104页，创作于2023年2月经变换后，只需一次迭代，就可找到最优解。这是因为经过尺度变换：等值线由椭圆变成圆。11第21页，课件共104页，创作于2023年2月梯度法的特点:（1）理论明确，程序简单，对初始点要求不严格。（2）对一般函数而言，收敛速度并不快，因为最速下降方向仅是指某点的一个局部性质。第22页，课件共104页，创作于2023年2月（4）梯度法的收敛速度与目标函数的性质密切相关。对于等值线(面)为同心圆（球）的目标函数，一次搜索即可达到极小点。（3）相邻两次搜索方向的正交性决定了迭代过程的路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。第23页，课件共104页，创作于2023年2月2.4.2共轭方向法

1.共轭方向

设G为n×n阶实对称正定矩阵，如果有两个n维向量S0和S1满足，则称向量S0与S1

关于矩阵G共轭。第24页，课件共104页，创作于2023年2月当G为单位矩阵时，假设目标函数f(x)在极值点附近的二次近似函数为对二维情况任选取初始点x0沿某个下降方向S0作一维搜索，得x1第25页，课件共104页，创作于2023年2月

因为是沿S0方向搜索的最佳步长，即在点x1处函数f（x）沿方向S0的方向导数为零。考虑到点x1处方向导数与梯度之间的关系，故有如果按最速下降法，选择负梯度方向为搜索方向，则将发生锯齿现象。第26页，课件共104页，创作于2023年2月第27页，课件共104页，创作于2023年2月α0S0x0x1x*11α1S1取下一次的迭代搜索方向S1直指极小点x*

S1第28页，课件共104页，创作于2023年2月如果能够选定这样的搜索方向，那么对于二元二次函数只需顺次进行S0、S1两次直线搜索就可以求到极小点x*，即有那么这样的S1方向应该满足什么条件呢?第29页，课件共104页，创作于2023年2月对于前述的二次函数:有当

时。x*是f(x)极小点，应满足极值必要条件，故有将等式两边同时左乘得：第30页，课件共104页，创作于2023年2月就是使S1直指极小点x*，S1所必须满足的条件。两个向量S0和S1称为G的共轭向量，或称SO和S1对G是共轭方向。

第31页，课件共104页，创作于2023年2月2.共轭方向的性质性质1

若非零向量系S0,S1,S2,…,Sm-1是对G共轭，则这m个向量是线性无关的。性质2

在n维空间中互相共轭的非零向量的个数不超过n。

性质3

从任意初始点出发，顺次沿n个G的共轭方向S0,S1,S2,…,进行一维搜索，最多经过n次迭代就可以找到的二次函数f(x)极小点。

第32页，课件共104页，创作于2023年2月关键：新的共轭方向确定第33页，课件共104页，创作于2023年2月3.共轭梯度法共轭梯度法是共轭方向法中的一种，该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来。从xk出发，沿负梯度方向作一维搜索:第34页，课件共104页，创作于2023年2月设与Sk共轭的下一个方向Sk+1由Sk和点xk+1的负梯度的线形组合构成，即：共轭条件：第35页，课件共104页，创作于2023年2月

则：解得：第36页，课件共104页，创作于2023年2月则上两式相减，并代入令为函数的泰勒二次展开式第37页，课件共104页，创作于2023年2月将式与式两边相乘，并应用共轭条件得：第38页，课件共104页，创作于2023年2月因此第39页，课件共104页，创作于2023年2月第40页，课件共104页，创作于2023年2月迭代精度。

，已知初始点[1,1]T例题2.4-2求下列问题的极值解：1）第一次沿负梯度方向搜寻计算初始点处的梯度第41页，课件共104页，创作于2023年2月为一维搜索最佳步长，应满足第42页，课件共104页，创作于2023年2月得:2）第二次迭代：第43页，课件共104页，创作于2023年2月得:代入目标函数第44页，课件共104页，创作于2023年2月得因收敛。由从而有：第45页，课件共104页，创作于2023年2月共轭梯度法特点1）每步迭代只需存储若干向量（适用于大规模问题）；2）有二次终结性（对于正定二次函数，至多n次迭代可达opt.）

第46页，课件共104页，创作于2023年2月比较梯度法与共轭梯度法1、梯度法：搜索方向为目标函数负梯度方向，计算速度开始搜索下降快，愈接近极值点下降愈慢。对初始点的选择要求不高，适合与其它方法结合使用。2、共轭梯度法：第一步搜索沿负梯度方向，然后沿负梯度的共轭方向搜索。计算效率优于梯度法。对初始点没有特殊的要求，不需要计算二阶偏导数矩阵及其逆矩阵，计算量与梯度法相当。适用于各种大规模的问题。第47页，课件共104页，创作于2023年2月2.4.3鲍威尔方法鲍威尔（Powell）法是直接利用函数值来构造共轭方向的一种方法对函数：基本思想：在不用导数的前提下，在迭代中逐次构造G的共轭方向第48页，课件共104页，创作于2023年2月1.共轭方向的生成jjkkkSdggk+1xxk+1设xk,xk+1为从不同点出发，沿同一方向Sj进行一维搜索而得到的两个极小点。jS第49页，课件共104页，创作于2023年2月根据梯度和等值面相垂直的性质，Sj和xk,xk+1两点处的梯度gk，gk+1之间存在关系:另一方面，对于上述二次函数，其xk，xk+1两点处的梯度可表示为:第50页，课件共104页，创作于2023年2月因而有取这说明只要沿Sj方向分别对函作两次一维搜索，得到两个极小点xk和xk+1，那么这两点的连线所给出的方向Sk就是与Sj一起对G共轭的方向。第51页，课件共104页，创作于2023年2月2.基本算法1）任选一初始点x0，再选两个线性无关的向量，如坐标轴单位向量e1=[1,0]T和e2=[0,1]T作为初始搜索方向。2）从x0出发，顺次沿e1，e2作一维搜索，得点，两点连线得一新方向S1x1x2x0oe1e2d1d2x*1第52页，课件共104页，创作于2023年2月用S1代替e1形成两个线性无关向量S1,e2

，作为下一轮迭代的搜索方向。再从出发，沿S1作一维搜索得点，作为下一轮迭代的初始点。x1x2x0oe1e2d1d2x*1第53页，课件共104页，创作于2023年2月x1x2x0oe1e2d1d2x*13）从出发，顺次沿e2,S1作一维搜索，得到点，两点连线得一新方向:第54页，课件共104页，创作于2023年2月沿S2作一维搜索得点x2

即是二维问题的极小点x*

方法的基本迭代格式包括共轭方向产生和方向替换两主要步骤。x1x2x0oe1e2d1d2x*1第55页，课件共104页，创作于2023年2月

把二维情况的基本算法扩展到n维，则鲍威尔基本算法的要点是：在每一轮迭代中总有一个始点（第一轮的始点是任选的初始点）和n个线性独立的搜索方向。从始点出发顺次沿n个方向作一维搜索得一终点，由始点和终点决定了一个新的搜索方向。第56页，课件共104页，创作于2023年2月用这个方向替换原来n个方向中的一个，于是形成新的搜索方向组。替换的原则是去掉原方向组的第一个方向而将新方向排在原方向的最后。此外规定，从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭代的始点。这样就形成算法的循环。

上述基本算法仅具有理论意义。第57页，课件共104页，创作于2023年2月

因为在迭代中的n个搜索方向有时会变成线性相关而不能形成共轭方向的情况。从而导致可能求不到极小点，所以上述基本算法有待改进。第58页，课件共104页，创作于2023年2月3.改进的算法在鲍威尔基本算法中，每一轮迭代都用连结始点和终点所产生出的搜索方向去替换原向量组中的第一个向量，而不管它的“好坏”，这是产生向量组线性相关的原因所在。第59页，课件共104页，创作于2023年2月在改进的算法中首先判断原向量组是否需要替换。如果需要替换，还要进一步判断原向量组中哪个向量最坏，然后再用新产生的向量替换这个最坏的向量，以保证逐次生成共轭方向。第60页，课件共104页，创作于2023年2月为此，要解决两个关键问题：（1）Sk＋1是否较好？是否应该进入新的方向组？即方向组是否进行更新？

（2）如果应该更新方向组，

Sk＋1不一定替换方向，而是有选择地替换某一方向。第61页，课件共104页，创作于2023年2月令在k次循环中（）分别称为一轮迭代的始点、终点和反射点。第62页，课件共104页，创作于2023年2月则在循环中函数下降最多的第m次迭代是记：相应的方向为。因此第63页，课件共104页，创作于2023年2月为了构成共轭性好的方向组，须遵循下列准则：在k次循环中，若满足条件：则选用新方向Sk，并在第k+1迭代中用Sk替换对应于

的方向。否则，仍然用原方向组进行第k+1迭代。第64页，课件共104页，创作于2023年2月这样重复迭代的结果，后面加进去的向量都彼此对G共轭，经n轮迭代即可得到一个由n个共轭方向所组成的方向组。对于n次函次，最多n次就可找到极小点，而对一般函数，往往要超过n次才能找到极小点（这里“n”表示设计空间的维数）。第65页，课件共104页，创作于2023年2月例2.4-5用改进的鲍威尔法求目标函数的最优解。已知初始点[1,1]T，迭代精度解：（1）第1轮迭代计算第66页，课件共104页，创作于2023年2月沿e1方向进行一维搜索得第67页，课件共104页，创作于2023年2月以为起点，沿第二坐标轴方向e2进行一维搜索得第68页，课件共104页，创作于2023年2月确定此轮中的最大下降量及其相应方向第69页，课件共104页，创作于2023年2月反射点及其函数值检验Powell条件第70页，课件共104页，创作于2023年2月由于满足Powell条件，则淘汰函数值下降量最大的方向e1，下一轮的基本方向组为e2，。构成新的方向第71页，课件共104页，创作于2023年2月沿方向一维搜索得极小点和极小值此点为下轮迭代初始点。

按点距准则检验终止条件

需进行第二轮迭代计算。第72页，课件共104页，创作于2023年2月（2）第2轮迭代计算此轮基本方向组为e2，，分别相当于，，起始点为

=沿e2方向进行一维搜索得

第73页，课件共104页，创作于2023年2月以为起点沿方向一维搜索得确定此轮中函数值最大下降量及其相应方向第74页，课件共104页，创作于2023年2月反射点及其函数值检验Powell条件，淘汰函数值下降量最大的方向e2，下一轮的基本方向组应为，。

第75页，课件共104页，创作于2023年2月构成新的方向沿方向进行一维搜索得第76页，课件共104页，创作于2023年2月检验终止条件（3）第3轮迭代计算此轮基本方向组为

，，起始点为＝，先后沿，方向，进行一维搜索，得第77页，课件共104页，创作于2023年2月

检验终止条件

故最优解

第78页，课件共104页，创作于2023年2月实际上，前两轮迭代的，为共轭方向，由于本例目标函数是二次函数，按共轭方向的二次收敛性，故前两轮的结果就是问题的最优解，但每一轮迭代都需要进行n+1次迭代。第79页，课件共104页，创作于2023年2月

补充知识：牛顿法在xk邻域内用一个二次函数来近似代替原目标函数，并将的极小点作为对目标函数求优的下一个迭代点。经多次迭代，使之逼近目标函数的极小点。

设

为

的极小点

第80页，课件共104页，创作于2023年2月这就是多元函数求极值的牛顿法迭代公式。

对于二次函数，海赛矩阵是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。第81页，课件共104页，创作于2023年2月例2－4

求目标函数

的极小点。初始点经过一次迭代即求得极小点，函数极小值。第82页，课件共104页，创作于2023年2月第83页，课件共104页，创作于2023年2月

牛顿法的主要缺点是每次迭代都要计算函数的二阶导数矩阵，并对该矩阵求逆。这样工作量很大。特别是矩阵求逆，当维数高时工作量更大。第84页，课件共104页，创作于2023年2月2.4.4变尺度法

变尺度法是在牛顿法的思想上进行了重大改进的一类方法。基本思想变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降到最低限度。

第85页，课件共104页，创作于2023年2月把的尺度放大5倍，则目标函数等值线由一簇椭圆变成一簇同心圆。例如在用最速下降法求的极小值时,需要进行10次迭代才能达到极小点如作变换

y1=x1,y2=5x2x2消除了函数的偏心，用最速下降法只需一次迭代即可求得极小点。第86页，课件共104页，创作于2023年2月Ak

是需要构造n×n的一个对称方阵，称为变尺度矩阵如Ak=I,则得到梯度法；

则得到阻尼牛顿法；如迭代方向：迭代公式：变尺度法的关键在于尺度矩阵Ak的产生。第87页，课件共104页，创作于2023年2月2、构造尺度矩阵Ak从初始矩阵A0=I(单位矩阵)开始，通过对公式

中修正矩阵的不断修正，在迭代中逐步逼近于因此，一旦达到最优点附近，就可望达到牛顿法的收敛速度。。第88页，课件共104页，创作于2023年2月1）DFP法（Davidon-Fletcher-Powell)式中第89页，课件共104页，创作于2023年2月2）BFGS算法(Broyden-Fletcher-Goldfrob-Shanno)DFP算法由于舍入误差和一维搜索不精确，有可能导致构造矩阵的正定性遭