现代设计方法-优化设计.ppt

《现代设计方法-优化设计.ppt》由会员分享，可在线阅读，更多相关《现代设计方法-优化设计.ppt（168页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、现代设计方法优化设计、有限元AdvancedDesignMethodsDesignOptimizationandFiniteElementMethod天津大学机械工程学院1序论第一部分 优化设计 第一章 优化设计的数学基础1.1矢量1.2矩阵1.3多元函数 第二章 优化设计的基本概念 第三章 一维优化3.1单峰函数3.2黄金分割法3.3对分法4.4二次插值法 第四章 多维无约束优化4.1直接法4.2鲍威尔法4.3梯度法（最速下降法）4.4牛顿法 目录ADM2ADM目录 第五章 多维有约束优化5.1概述5.2网格法5.3罚函数法 第六章 优化设计建模 第七章 机械优化设计示例3ADM目录第二部分

2、 有限元引言第一章 弹性力学简介 1.1 求和约定 1.2 应力与应变 1.2.1 应力 1.2.2 应变 1.2.3 小变形弹性理论基本方程 第二章 有限元理论基础 2.1 变分法原理 2.1.1 变分法第一定理 2.1.2 泛函极值的求解欧拉方程 2.1.3 求解变分问题的近似计算法李兹(Ritz)法 2.2 虚功原理（虚功方程）与能量泛函 2.3 插值及单元位移 2.4 弹性力学有限元的矩阵方程4ADM目录第三章第三章平面问题有限元平面问题有限元3.1平面问题基本方程及有限元矩阵方程平面问题基本方程及有限元矩阵方程3.1.1基本方程基本方程3.1.2有限元矩阵方程有限元矩阵方程3.2三角

3、形场应变单元三角形场应变单元3.2.1离散化离散化3.2.2位移模式位移模式3.2.3应变应变3.4刚度矩阵刚度矩阵3.4.1单元刚度矩阵单元刚度矩阵3.4.2总体刚度矩阵的组装总体刚度矩阵的组装3.4.3总体位移向量总体位移向量3.5单元的等效节点力与总体载荷向量单元的等效节点力与总体载荷向量3.5.1单元的等效节点力单元的等效节点力3.5.2总体载荷向量总体载荷向量5ADM目录3.6刚度方程求解刚度方程求解3.6.1边界条件处理边界条件处理3.7有限元分析的实施步骤有限元分析的实施步骤3.8有限元计算收敛性有限元计算收敛性第四章第四章轴对称问题有限元轴对称问题有限元4.1基本方程基本方程4

4、.1.1平衡方程平衡方程4.1.2几何方程几何方程4.1.3物理方程物理方程4.2三角形截面环单元三角形截面环单元4.3轴对称问题的有限元矩阵表达式轴对称问题的有限元矩阵表达式4.3.1单元刚度矩阵单元刚度矩阵4.3.2组装总体刚度矩阵组装总体刚度矩阵4.3.3单元等效节点力单元等效节点力6ADM目录第五章第五章等参数单元等参数单元5.1平面等参元平面等参元5.1.1坐标变换及位移坐标变换及位移5.1.2应变及应变矩阵应变及应变矩阵5.1.3单元刚度矩阵单元刚度矩阵5.1.4单元等效节点力单元等效节点力5.1.5高斯积分高斯积分5.1.6等参元的完备性和协调性等参元的完备性和协调性5.2轴对称

5、等参元轴对称等参元5.2.1坐标变换及位移坐标变换及位移5.2.2应变及应变矩阵应变及应变矩阵5.2.3单元刚度矩阵单元刚度矩阵5.2.4单元等效节点力单元等效节点力5.3等参元的应力、应变计算等参元的应力、应变计算7第六章第六章杆件系统杆件系统第七章第七章薄板弯曲问题薄板弯曲问题第八章第八章结构动力学问题结构动力学问题8.1结构动力学微分方程结构动力学微分方程8.2结构动力学虚功方程结构动力学虚功方程8.3结构动力学有限元矩阵方程结构动力学有限元矩阵方程8.4结构自由振动有限元矩阵方程结构自由振动有限元矩阵方程模态分析模态分析ADM目录8ADM序 论现代设计方法的基本内容：现代设计方法的基本

6、内容：1.CAD2.CAE有限元分析有限元分析*3.优化设计优化设计*4.可靠性设计可靠性设计5.逆向设计逆向设计6.模块化设计模块化设计7.设计专家系统设计专家系统8.价值工程价值工程9.虚拟设计虚拟设计10.9如何评价设计质量?m-1s+1s设计参数设计参数可靠性：性能的波动在允许的设计界限内可靠性：性能的波动在允许的设计界限内稳健性（鲁棒性）：降低在设计点上的敏感性稳健性（鲁棒性）：降低在设计点上的敏感性下限下限上限上限-1s+1s10设计质量，个案研究-SONY电视机有统一的系统设计和公差，任何不合格品都不卖给消费者调查显示，美国消费者一向喜欢日本产的电视机Target下限下限下限下限

7、上限上限上限上限频率SONY JapanSONY JapanSONY U.S.SONY U.S.u日产电视机性能在期望日产电视机性能在期望值附近作小幅波动（方值附近作小幅波动（方差很小），统计上看，差很小），统计上看，大量的产品性能稳定，大量的产品性能稳定，更加趋向设计目标（更加趋向设计目标（TARGET）u美国产的电视机性能美国产的电视机性能呈扁平分布呈扁平分布,多数多数产品产品的质量是刚好落在界限的质量是刚好落在界限内内11DesignSpaceFeasibleDesignSpace例：悬臂梁减重优化确定性优化DesignVariables:10 BeamHeight 80mm10 Fla

8、ngeWidth 50mmConstraint:Stress 16MPaObjective:MinimizeMass(minimizearea)1080105020 30 40 50 60 70203040Beam Height,mmFlange Width,mmStress=16Loads at free endFlangeWidthBeamHeightArea=400Area=300Solution:Beam Height=38.4Flange Width=22.7Stress=16Area=233.412确定性最优点：确定性最优点：应力绝对最小点应力绝对最小点函数最小值几何安装角几何安装

9、角x应力应力f(x)(安装误差 D x)稳健设计D f2D f1 Dx不稳健不稳健 :易受不确定因素影响而造成性能的大幅波动 Dx稳健最优设计点稳健最优设计点牺牲部分性能，牺牲部分性能，更可靠、更稳健的设计更可靠、更稳健的设计不可靠不可靠:应力大于许用应力问题：已知安装角问题：已知安装角x 存在不确定误差，在保证可靠性和稳健性前提下，求使应力存在不确定误差，在保证可靠性和稳健性前提下，求使应力f 最小的最小的x值值最大允许应力最大允许应力危险区危险区安全区安全区概念：质量设计稳健性、可靠性优化13ADM第一章第一章优化设计的数学基础优化设计的数学基础1.1矢量矢量Vector定义：有大小和方向

10、的量1.1.1二维矢量x2x1P(x1,x2)P(x1,x2)O1.1.2n维矢量14ADM第一章第一章优化设计的数学基础优化设计的数学基础1.2矩阵矩阵1.2.1定义由一组数按一定次序排列成的具有m行n列的表15ADM第一章第一章优化设计的数学基础优化设计的数学基础1.2.2逆矩阵逆矩阵Lattice若则B为A的逆矩阵逆矩阵的求法A*为A的伴随矩阵16ADM第一章第一章优化设计的数学基础优化设计的数学基础1.2.3矩阵的正定与负定矩阵的正定与负定二次型对若A为正定；A为半正定；A为负定；A为半负定不定17ADM第一章第一章优化设计的数学基础优化设计的数学基础矩阵正、负定的判定对称矩阵A正定的

11、充要条件：其行列式各阶主子式之值均大于0;对称矩阵A负定的充要条件：各阶主子式的值，应负、正交替地变化符号。1.3多元函数多元函数1.3.1梯度：函数增加最快的方向18ADM第一章第一章优化设计的数学基础优化设计的数学基础1.3.2多元函数的二阶偏导与海赛矩阵多元函数的二阶偏导与海赛矩阵1.3.3函数的泰勒级数展开函数的泰勒级数展开19ADM第一章第一章优化设计的数学基础优化设计的数学基础1.3.4多元函数极值多元函数极值极值定义：在X0点的某邻域内，若X0为严格极大值点；为严格极大值点；X0为严格极小值点；为严格极小值点；极值存在的必要条件：梯度为0T向量极值存在的充分条件：H(X0)正定，

12、正定，F(X0)为极小值；为极小值；H(X0)负定，负定，F(X0)为极大值。为极大值。20ADM第二章第二章优化设计的基本概念优化设计的基本概念参数优化：优化结构的参数参数优化：优化结构的参数拓扑优化：优化拓扑结构拓扑优化：优化拓扑结构1.设计变量设计变量设计过程中，其数值可以改变的能够描述结构特性的独立设计过程中，其数值可以改变的能够描述结构特性的独立变量。传动比，尺寸。变量。传动比，尺寸。2.目标函数目标函数目标函数是比较和选择各种不同设计方案的量化指标，是目标函数是比较和选择各种不同设计方案的量化指标，是设计变量的函数。质量，成本，利润，速度。设计变量的函数。质量，成本，利润，速度。2

13、1ADM第二章第二章优化设计的基本概念优化设计的基本概念3.约束条件约束条件对设计变量取值范围的约束。强度，刚度，固有频率。对设计变量取值范围的约束。强度，刚度，固有频率。4.设计空间和可行域设计空间和可行域设计空间：由设计变量构成的设计空间：由设计变量构成的n维实空间维实空间可行域：设计空间内，满足约束条件的子空间可行域：设计空间内，满足约束条件的子空间5.数学描述数学描述不等式约束不等式约束等式约束等式约束变量取值范围约束变量取值范围约束22ADM第二章第二章优化设计的基本概念优化设计的基本概念6.例例X*X*F(X)等值等值线线g1(X)g2(X)x1x2可行域可行域237.注意事项注意

14、事项设计变量设计变量1）以主要影响因素作为设计变量；）以主要影响因素作为设计变量；2）根据优化问题的特殊性选择设计变量；）根据优化问题的特殊性选择设计变量；3）注意独立变量和相关变量，尽量不包括相关变量；）注意独立变量和相关变量，尽量不包括相关变量；4）变量群转换，减少变量数目，如变量在目标函数中以）变量群转换，减少变量数目，如变量在目标函数中以x1x2形式存形式存在，可令在，可令y=x1x2；5）必须的设计变量不能遗漏；）必须的设计变量不能遗漏；6）冗余变量）冗余变量相关变量，齿轮设计变量为相关变量，齿轮设计变量为i,z,m,b，齿轮孔径为冗齿轮孔径为冗余变量。余变量。ADM第二章第二章优化

15、设计的基本概念优化设计的基本概念24ADM第二章第二章优化设计的基本概念优化设计的基本概念约束函数约束函数1）不能矛盾；）不能矛盾；2）可行域不能无界；）可行域不能无界；3）避免多余约束；）避免多余约束；4）尽量给定设计变量取值上下界，缩小可行域；尽量给定设计变量取值上下界，缩小可行域；5）谨慎对待等式约束；）谨慎对待等式约束；6）近似约束）近似约束不能用精确数学表达式描述的约束的处理；不能用精确数学表达式描述的约束的处理；7）不能遗漏必要的约束，如压簧优化设计忽略了工作状态下，相邻）不能遗漏必要的约束，如压簧优化设计忽略了工作状态下，相邻圈间间隙值约束；圈间间隙值约束；8）全部设计变量必须包

16、含在约束函数集中。）全部设计变量必须包含在约束函数集中。25ADM第二章第二章优化设计的基本概念优化设计的基本概念目标函数目标函数1）目标函数必须包含全部或部分设计变量；）目标函数必须包含全部或部分设计变量；2）当必须采用多目标优化时，可选择其中一个主要的目标作单目标）当必须采用多目标优化时，可选择其中一个主要的目标作单目标优化，其它目标按满足一定值要求的约束处理，优化后在选另一优化，其它目标按满足一定值要求的约束处理，优化后在选另一目标优化；目标优化；3）近似目标函数）近似目标函数借助实验数据处理建立目标函数；借助实验数据处理建立目标函数；4）转移或替代目标函数，如以中心距作为减速器重量的替

17、代目标函）转移或替代目标函数，如以中心距作为减速器重量的替代目标函数；数；5）单体设计对象的多目标评价）单体设计对象的多目标评价设计变量和约束条件不变，建立设计变量和约束条件不变，建立多个不同的目标函数并分别优化，得到一组优化方案，优中择优；多个不同的目标函数并分别优化，得到一组优化方案，优中择优；6）目标函数的规一化）目标函数的规一化minF(X)26ADM第二章第二章优化设计的基本概念优化设计的基本概念8.优化问题求解方法优化问题求解方法搜索法搜索法9.收敛判据收敛判据1）相邻两轮搜索得到的近似极值点相邻两轮搜索得到的近似极值点“相对距离相对距离”小于某一小的正数；小于某一小的正数；2）F

18、(X)可微，则梯度绝对值小于某一小的正数。可微，则梯度绝对值小于某一小的正数。27ADM第三章第三章一维优化一维优化解析法搜索法搜索法直接法（区间缩减法）：黄金分割法、对分法直接法（区间缩减法）：黄金分割法、对分法间接法（插值法）：二次插值、三次插值间接法（插值法）：二次插值、三次插值一维优化在多维优化中作用一维优化在多维优化中作用确定最优步长确定最优步长283.1单峰函数单峰函数3.1.1单峰函数单峰函数在给定区间内仅有一个极小值点的函数在给定区间内仅有一个极小值点的函数多峰与单峰的关系多峰与单峰的关系多峰函数区间分割成数个单峰区间，按单峰函数求极值点多峰函数区间分割成数个单峰区间，按单峰函

19、数求极值点单峰函数极值点求解单峰函数极值点求解单值区间缩小，单值区间缩小，(x1+x2)/2为极值点为极值点ADM第三章第三章一维优化一维优化29ADM第三章第三章一维优化一维优化3.1.2初始单值区间确定算法初始单值区间确定算法进退步法（探索步长加倍）进退步法（探索步长加倍）单峰区间：单峰区间：x2,x4x5,x3h 2h 4h4h2hh hx1x2x3x4x5x4x3x1x230ADM第三章第三章一维优化一维优化一阶导数法（一阶导数法（f(x)连续可微）连续可微）以以h,2h,4h.，h0为步长，为步长，若若f(xk-2)0或或f(xk-2)0,f(xk)=2则则xk-2,xk或或xkxk

20、-2为单峰为单峰区间区间xk-2xk-1xkh2hf031ADM第三章第三章一维优化一维优化3.2黄金分割法黄金分割法3.2.1区间缩小求解极值点的基本思路区间缩小求解极值点的基本思路按一定规则在按一定规则在a,b内取两个点内取两个点x1,x2ax1x2bax1x2bax1x2b(a)(b)(c)f(x1)f(x2)f(x1)=f(x2)a,ba,x2a,bx1,ba,ba,x2或或x1,b32ADM第三章第三章一维优化一维优化3.2.2取点规则取点规则黄金分割法黄金分割法(0.618法，均匀缩短率对称取点法，均匀缩短率对称取点)黄金分割：将一线段分割成两段，使得整段长度黄金分割：将一线段分割

21、成两段，使得整段长度L与较长段与较长段x的比的比值等于较长段值等于较长段x与较短段与较短段L-x的比值的比值Lax1x2b33ADM第三章第三章一维优化一维优化3.2.3区间收缩区间收缩参见参见3.2134ADM第三章第三章一维优化一维优化3.2.4收敛判据收敛判据常用判据常用判据1）2）3）4）判据的使用判据的使用1)、3)或或2)、4)组合使用，并从组合使用，并从a,b,(a+b)/2中选最优者中选最优者abab35ADM第三章第三章一维优化一维优化3.3对分法对分法3.3.1中心对分法（可微中心对分法（可微）比较比较的符号，将区间的符号，将区间a,b缩短一半。缩短一半。3.3.2两点对分

22、法（可不可微两点对分法（可不可微）a(a+b)/2bax1x2bf1f2(a+b)/236ADM第三章第三章一维优化一维优化3.4二次插值法二次插值法二次插值：二次多项式逼近二次插值：二次多项式逼近3.4.1方法原理方法原理二次多项式逼近目标函数，以二次多项式的极小值点作为目标函数的二次多项式逼近目标函数，以二次多项式的极小值点作为目标函数的近似最优点。近似最优点。3.4.2二次多项式构造二次多项式构造单峰区间单峰区间x1,x3内存在极小值点，内存在极小值点，在在x1,x3内取点内取点x2，则则过过x1,x2,x3构造构造其极小值点为其极小值点为x*x1x2x*x*x3f(x)p(x)37AD

23、M第三章第三章一维优化一维优化3.4.3区间缩小原理区间缩小原理比较比较f(x*)和和f(x2)，以其中较小者对应的点为新的以其中较小者对应的点为新的x2点，新点，新x2左右相邻左右相邻的点分别为新的点分别为新x1，新，新x3。3.4.4收敛判据收敛判据见黄金分割法见黄金分割法习题习题初始区间初始区间a,b=-0.5,1.5，绝对精度绝对精度分别用解析法、黄金分割法、中心对分法、两点对分法求解。分别用解析法、黄金分割法、中心对分法、两点对分法求解。38ADM第四章第四章多维无约束优化多维无约束优化分类：分类：1）直接法（不需计算导数）直接法（不需计算导数）2）间接法（需计算导数）间接法（需计算

24、导数）4.1坐标轮换法（坐标方向为搜索方向）坐标轮换法（坐标方向为搜索方向）4.1.1原理原理将将n维问题转化为依次沿维问题转化为依次沿n个坐标方向轮回进行一维搜索。个坐标方向轮回进行一维搜索。39ADM第四章第四章多维无约束优化多维无约束优化40ADM第四章第四章多维无约束优化多维无约束优化4.1.2算法算法1）任选初始点任选初始点设定初始步长设定初始步长置搜索方向置搜索方向2）以）以为初始点，沿为初始点，沿方向作试探，步长方向作试探，步长计算计算，若，若说明试探成功；否则，说明试探成功；否则，若若，置，置，若，若，41ADM第四章第四章多维无约束优化多维无约束优化 则作一维搜索求最优步长和

25、优化点则作一维搜索求最优步长和优化点若沿坐标轴正负方向试探均失败，则迭代点不变若沿坐标轴正负方向试探均失败，则迭代点不变3）以）以为起点，按为起点，按1）沿）沿方向搜索，得方向搜索，得沿沿n个坐标方向进行完一轮一维搜索后，得个坐标方向进行完一轮一维搜索后，得4）以）以作第二轮得起始点作第二轮得起始点，重复，重复2）、）、3）得第二轮搜索）得第二轮搜索终点终点。5）如果从某轮起始点出发，依次沿）如果从某轮起始点出发，依次沿n个坐标轴的正负方向试探均失败，个坐标轴的正负方向试探均失败，则缩短试探步长（如减半），返回则缩短试探步长（如减半），返回2）。当探索步长足够小，满足收敛判）。当探索步长足够小

26、，满足收敛判据据时，终止迭代，所得点即为优化结果时，终止迭代，所得点即为优化结果X*。42ADM第四章第四章多维无约束优化多维无约束优化4.1.3讨论讨论1）计算量小，程序简单，计算效率低，适合变量）计算量小，程序简单，计算效率低，适合变量n10的情况。的情况。2）若目标函数具有脊线，算法将出现病态：沿两个坐标方向均不能使函）若目标函数具有脊线，算法将出现病态：沿两个坐标方向均不能使函数数值下降，误认为最优点。数数值下降，误认为最优点。脊线脊线43ADM第四章第四章多维无约束优化多维无约束优化4.2鲍威尔法（共轭方向为搜索方向）鲍威尔法（共轭方向为搜索方向）4.2.1共轭方向共轭方向1）定义）

27、定义A为为n阶正定矩阵，若两个阶正定矩阵，若两个n维矢量满足维矢量满足则称则称S1和和S2对矩阵对矩阵A共轭，共轭矢量方向为共轭方向。共轭，共轭矢量方向为共轭方向。对于对于n个个n维矢量维矢量Si，i=1,2,n(Si不为不为0)，若满足，若满足则称则称n个个n维矢量维矢量Si，i=1,2,n为对矩阵为对矩阵A共轭。共轭。2）共轭方向与函数的极小值点关系）共轭方向与函数的极小值点关系考察正定二次函数考察正定二次函数其等值线为同心椭圆族其等值线为同心椭圆族44ADM第四章第四章多维无约束优化多维无约束优化S2S1S1X1X2X1(0)X2(0)x1x2从从X1(0)出发沿出发沿S1方向作一维搜索

28、，方向作一维搜索，得最优点得最优点X1（与椭圆相切）；从（与椭圆相切）；从X2(0)出发沿出发沿S1方向作一维搜索，得最优点方向作一维搜索，得最优点X2；连接；连接X1、X2得矢量得矢量S2，S2过椭圆过椭圆族中心，即目标函数极小值点族中心，即目标函数极小值点X*，且且S1、S2对对A正交，正交，沿沿S1的共轭方向的共轭方向S2可搜索到正定二元可搜索到正定二元二次函数极值点二次函数极值点。X*45ADM第四章第四章多维无约束优化多维无约束优化4.2.2原始鲍威尔法原始鲍威尔法S1、S2、S3为共、轭为共、轭方向（方向（参见前页参见前页）搜索方向搜索方向:x1x3x2e1e2e3X0(1)S1e

29、2e3S1X1(1)X2(1)X3(1)X0(2)X1(2)X2(2)X3(2)X0(3)S2e3S1S2S3X1(3)X2(3)X3(3)X0(4)第第1轮轮第第2轮轮第第3轮轮46ADM第四章第四章多维无约束优化多维无约束优化原始鲍威尔法的严重缺陷：当某一轮方向组中的矢量系出现线性相关时原始鲍威尔法的严重缺陷：当某一轮方向组中的矢量系出现线性相关时（特别是接近（特别是接近X*时），会出现退化，无法获得极小值点。时），会出现退化，无法获得极小值点。4.2.3改进鲍威尔法改进鲍威尔法与原始鲍威尔法的区别：每构造一个新方向，根据判别条件决定是否替与原始鲍威尔法的区别：每构造一个新方向，根据判别条

30、件决定是否替换原来的某个方向。构造换原来的某个方向。构造k+1轮方向组时，是否淘汰前一轮的某一个方向轮方向组时，是否淘汰前一轮的某一个方向Sm(k)，根据下面二个条件判断：根据下面二个条件判断：第第k轮初始点函数值；轮初始点函数值；第第k轮最后一个方向搜索终点函数值；轮最后一个方向搜索终点函数值；X0(k)对对Xn(k)映射点映射点Xn1(k)的函数值；的函数值；一维搜索中函数值下降最大者，其方一维搜索中函数值下降最大者，其方向为向为Sm(k)47ADM第四章第四章多维无约束优化多维无约束优化条件式条件式a)、b)同时或两者之同时或两者之一成立：第一成立：第k+1轮仍沿用第轮仍沿用第k轮的轮的

31、方向组，取方向组，取Xn(k)（F2F3）或映）或映射点射点Xn1(k)（F3F(X(k)。不是严格的下降算法。原因：不是严格的下降算法。原因：X(k+1)是近似二次式在牛顿方向上的是近似二次式在牛顿方向上的极小点，而非极小点，而非F(X)在牛顿方向上的极小点。在牛顿方向上的极小点。2）对牛顿法的修正）对牛顿法的修正阻尼牛顿法阻尼牛顿法修正方法：在牛顿方向上作一维搜索求最优步长。修正方法：在牛顿方向上作一维搜索求最优步长。当当F(X)的海赛矩阵的海赛矩阵Hk在迭代点处在迭代点处正定正定情况下，阻尼牛顿法可以保证每次迭情况下，阻尼牛顿法可以保证每次迭代，迭代点的函数值都代，迭代点的函数值都下降；

32、下降；Hk在迭代点处在迭代点处不定不定情况下，函数值不会上升，但不情况下，函数值不会上升，但不一定下降；一定下降；Hk在迭代点处在迭代点处奇异奇异情况下，不能求逆，无法构造牛顿方向；要求情况下，不能求逆，无法构造牛顿方向；要求F(X)二阶可微，需计算梯度、海赛矩阵及其逆矩阵，计算量大二阶可微，需计算梯度、海赛矩阵及其逆矩阵，计算量大。4.4.3收敛判据收敛判据同梯度法。同梯度法。52ADM第四章第四章多维无约束优化多维无约束优化53ADM第四章第四章多维无约束优化多维无约束优化4.5DFP变尺度法变尺度法拟牛顿法，基于牛顿法的思想进行了重要改进。拟牛顿法，基于牛顿法的思想进行了重要改进。4.5

33、.1基本思想基本思想综合梯度法和牛顿法的优有点，克服梯度法收敛速度慢和牛顿法收敛综合梯度法和牛顿法的优有点，克服梯度法收敛速度慢和牛顿法收敛快但稳定性差且计算量大的缺点。快但稳定性差且计算量大的缺点。比较梯度法和牛顿法，比较梯度法和牛顿法，54ADM第四章第四章多维无约束优化多维无约束优化Ak为为nn对称矩阵，对称矩阵，Ak为单位矩阵时，上式为梯度法；为单位矩阵时，上式为梯度法；AkHk-1时，时，上式为阻尼牛顿法。上式为阻尼牛顿法。拟牛顿法的基本思想：用某种方法，人为构造一拟牛顿法的基本思想：用某种方法，人为构造一n阶对称矩阵阶对称矩阵AkA(X(k)，近似替代牛顿法的近似替代牛顿法的Hk-

34、1。通过迭代不断修正。通过迭代不断修正Ak，使使AkHk-1。由于是不断变化的，它使搜索方向不断向牛顿方向逼近，故可把看由于是不断变化的，它使搜索方向不断向牛顿方向逼近，故可把看作是变化的尺度矩阵，这就是变尺度法叫法的由来。梯度法和牛顿作是变化的尺度矩阵，这就是变尺度法叫法的由来。梯度法和牛顿法也属于变尺度法的范畴。法也属于变尺度法的范畴。Ak应满足的条件应满足的条件：1.正定正定保证迭代过程中函数值始终下降，要求保证迭代过程中函数值始终下降，要求S(k)与与gk夹角为锐角，即夹角为锐角，即552.拟牛顿条件拟牛顿条件使使AkHk-1，Ak1可以由第可以由第k步的信息递推构造步的信息递推构造由

35、由得得即即ADM第四章第四章多维无约束优化多维无约束优化56ADM第四章第四章多维无约束优化多维无约束优化4.5.2Ak序列的生成（序列的生成（DFP递推公式）递推公式）57ADM第四章第四章多维无约束优化多维无约束优化4.5.3算法算法1）任选初始点）任选初始点X(0)，收敛精度收敛精度2）置置k=0，Ak=E（单位矩阵）；单位矩阵）；3）沿）沿4）5）用）用DFP公式求公式求Ak+1；6）置置。若。若kn（变量数目），转到变量数目），转到3），否则返回到），否则返回到2）开始）开始下一轮（从负梯度法重开始，有利于收敛）；下一轮（从负梯度法重开始，有利于收敛）；7）输出结果）输出结果X*，F

36、(X*)，结束。结束。58ADM第四章第四章多维无约束优化多维无约束优化4.6共轭梯度法共轭梯度法将将梯梯度度法法和和共共轭轭方方向向法法结结合合起起来来，每每一一轮轮搜搜索索的的第第一一步步沿沿负负梯梯度度方方向向搜搜索索，后后续续各各步步沿沿上上一一步步的的共共轭轭方方向向搜搜索索，具具有有二二次次收收敛敛速速度度，每每一一轮搜索轮搜索n步。步。第一步的搜索方向第一步的搜索方向负梯度方向负梯度方向以后各步的搜索方向以后各步的搜索方向共轭方向共轭方向的确定的确定应使应使n n维实空间中的两个非维实空间中的两个非0 0向量向量S(k)和和S(k1)关于矩阵关于矩阵A共轭，共轭，即应使即应使对于

37、正定二次函数对于正定二次函数有有59ADM第四章第四章多维无约束优化多维无约束优化二式相减二式相减而而则则可得可得即即因因 为一正交系，为一正交系，故有故有则则60ADM第四章第四章多维无约束优化多维无约束优化61ADM第四章第四章多维无约束优化多维无约束优化算法算法l任选初始点任选初始点X(0)，给定收敛精度给定收敛精度和维数和维数n n；2令令，求迭代初始点，求迭代初始点X(0)的梯度的梯度g0取第一次搜索的方向取第一次搜索的方向S(0)为初始点的负梯度为初始点的负梯度3 3进行一维搜索，求最优步长进行一维搜索，求最优步长(k k)并求出新点并求出新点 4 4计算计算X(k+1)点的梯度点

38、的梯度5收敛检查。满足条件收敛检查。满足条件则，计算结束；否则继续下一步；则，计算结束；否则继续下一步；6判判断断k+1是是否否等等于于n，若若k+1n，则则令令X(0)=X(k+1)转转步步骤骤2；若若k+1 n，则继续下一步；则继续下一步；7 7计算计算 62ADM第四章第四章多维无约束优化多维无约束优化8确定下一步的搜索方向确定下一步的搜索方向令令 ，返回步骤，返回步骤3。讨论讨论共轭梯度法具有超线性收敛速度（共轭梯度法具有超线性收敛速度（11收敛速度阶数收敛速度阶数22）。计算效率高于）。计算效率高于梯度法，低于牛顿法，但对初始点没有特殊要求。不需计算二阶偏导数梯度法，低于牛顿法，但对

39、初始点没有特殊要求。不需计算二阶偏导数矩阵及其逆矩阵，计算量与梯度法相当，小于牛顿法。适用于各种规模矩阵及其逆矩阵，计算量与梯度法相当，小于牛顿法。适用于各种规模的问题。的问题。63ADM第四章第四章多维无约束优化多维无约束优化4.7 4.7 单纯形法单纯形法原理原理函数的导数是函数性态的反映，它对选择搜索方向提供了有用的信息。函数的导数是函数性态的反映，它对选择搜索方向提供了有用的信息。在不计算导数的情况下，先算出若干点处的函数值，从它们之间的大在不计算导数的情况下，先算出若干点处的函数值，从它们之间的大小关系中也可以看出函数变化的大概趋势，为寻求函数的下降方向提小关系中也可以看出函数变化的

40、大概趋势，为寻求函数的下降方向提供依据。这里所说的若干点，一般取在单纯形的顶点上。所谓单纯形供依据。这里所说的若干点，一般取在单纯形的顶点上。所谓单纯形是指在是指在n n维空间中具有维空间中具有n n+1+1个顶点的简单图形或凸多面体。利用单纯形个顶点的简单图形或凸多面体。利用单纯形的顶点，计算其函数值并加以比较，从中确定有利的搜索方向和步长，的顶点，计算其函数值并加以比较，从中确定有利的搜索方向和步长，找出具有最大值的顶点并构造目标函数的下降方向，求出最小值点，找出具有最大值的顶点并构造目标函数的下降方向，求出最小值点，以该点取代单纯形的最大值的顶点，重新构造单纯形。随着这种取代以该点取代单

41、纯形的最大值的顶点，重新构造单纯形。随着这种取代过程的不断进行，新的单纯形不断向极小点收缩。这样经过若干次迭过程的不断进行，新的单纯形不断向极小点收缩。这样经过若干次迭代，即可得到满足精度要求的近似解。这就是单纯形法的基本思想。代，即可得到满足精度要求的近似解。这就是单纯形法的基本思想。64ADM第四章第四章多维无约束优化多维无约束优化65ADM第四章第四章多维无约束优化多维无约束优化算法算法选选择择新新的的比比较较好好的的点点替替代代最最差差点点的的算算法法有有4种种：反反射射、扩扩张张、压压缩缩和和收缩收缩。现以二元函数。现以二元函数F(X)=F(x1,x2)为例，说明单纯形法的算法。为例

42、，说明单纯形法的算法。在在x1-x2平平面面上上取取不不在在同同一一直直线线上上的的三三点点XH、XG、XL，以以它它们们为为顶顶点点组成一单纯形（即三角形）组成一单纯形（即三角形）XHXGXL。计算各顶点函数值，设计算各顶点函数值，设F(XH)F(XG)F(XL)说说明明XL点点最最好好，XH点点最最差差。为为了了寻寻找找极极小小点点，一一般般说说来来，应应向向最最差差点点的的反反对对称称方方向向进进行行搜搜索索，即即通通过过XH并并穿穿过过XGXL的的中中点点XC的的方方向向进进行行搜搜索。在此方向上取作索。在此方向上取作XH点相对于点相对于XC点的点的反射反射点点XRXRXC(XCXH)

43、2XCXH计算反射点的函数值计算反射点的函数值F(XR)，可能出现以下几种情形：可能出现以下几种情形：l.F(XR)F(XL)即即反反射射点点比比最最好好点点还还好好，说说明明搜搜索索方方向向正正确确，还还可可以以往前迈进一步，也就是可以往前迈进一步，也就是可以扩张扩张。这时取扩张点。这时取扩张点XEXCk(XCXH)k扩张因子，一般取扩张因子，一般取kl.2-2.0。如果如果F(XE)F(XR)说明扩张有利，就以说明扩张有利，就以XE代替代替XH构成新单纯形构成新单纯形XEXGXL。否则说明扩张不利，舍弃否则说明扩张不利，舍弃XE，仍以仍以XR代替代替XH构成新单纯形构成新单纯形XRXGXL

44、。66ADM第四章第四章多维无约束优化多维无约束优化2.F(XL)F(XR)F(XG)即即反反射射点点比比最最好好点点差差，但但比比次次差差点点好好，说说明明反反射可行，则以反射点代替最差点，仍构成新单纯形射可行，则以反射点代替最差点，仍构成新单纯形XRXGXL。3.F(XG)F(XR)F(XH)即即反反射射点点比比次次差差点点差差，但但比比最最差差点点好好，说说明明XR走得太远，应缩回一些，即走得太远，应缩回一些，即压缩压缩。这时取压缩点。这时取压缩点XKXCm(XRXC)m收缩因子，常取成收缩因子，常取成m0.5。如果如果F(XK)F(XH)，则用则用XK代替代替XH构成新单纯形构成新单纯

45、形XKXGXL。4.F(XR)F(XH)即即反反射射点点比比最最差差点点还还差差，这这时时应应压压缩缩得得更更多多一一些些，即即将新点收缩在将新点收缩在XHXC之间，取压缩点之间，取压缩点XKXCm(XCXH)如果如果F(XK)F(XH)则用则用XK代替代替XH构成新单纯形构成新单纯形XKXGXL。5.F(X)F(XH)即即若若XHXC方方向向上上的的所所有有点点都都比比最最差差点点差差，则则表表明明不不能能沿沿此此方方向向搜搜索索，这这时时应应以以XL为为中中心心收收缩缩，使使顶顶点点XH、XG向向XL移移近近一一半半距距离，得新单纯形离，得新单纯形XHXGXL，如图所示。如图所示。67AD

46、M第四章第四章多维无约束优化多维无约束优化从从以以上上各各步步得得到到新新的的单单纯纯形形后后，再再重重复复开开始始新新一一轮轮构构造造单单纯纯形形，逐逐渐渐缩缩小小单单纯形直至满足精度要求。纯形直至满足精度要求。68ADM第四章第四章多维无约束优化多维无约束优化计算步骤计算步骤1.构构造造初初始始单单纯纯形形。选选初初始始点点X0，从从X0出出发发沿沿各各坐坐标标轴轴方方向向走走步步长长h，得得n个个顶顶点点Xi（i1，2，n）与与X0构构成成初初始始单单纯纯形形。这这样样可可以以保保证证此此单单纯纯形形各各棱棱是是n个个线线性性无无关关的的向向量量，否否则则就就会会使使搜搜索索范范围围局局

47、限限在某个较低维的空间内，有可能找不到极小点；在某个较低维的空间内，有可能找不到极小点；2.计算各顶点函数值。计算各顶点函数值。FiF(Xi)；3.比较函数值的大小，确定最好点比较函数值的大小，确定最好点XL，最差点最差点XH和次差点和次差点XG。FLF(XL)minF(Xi)（i1，2，n）FHF(XH)maxF(Xi)（i1，2，n）FGF(XG)maxF(Xi)（i1，2，n；iH）4.检验是否满足精度要求检验是否满足精度要求满足要求，则满足要求，则X*XL，计算结束。否则，继续步骤计算结束。否则，继续步骤5；5.计算除计算除XH点之外各点的点之外各点的“重心重心”Xn+169和反射点和

48、反射点当当时时，以以Xn+2代代替替XH，Fn+2代代替替FH，构构成成一一新新单单纯纯形形，然然后返回步骤后返回步骤2；6.扩张。当扩张。当Fn+2 FL时，取扩张点时，取扩张点并并计计算算其其函函数数值值Fn+3。若若Fn+3 F n+2，则则以以Xn+3代代替替XH，Fn+3代代替替FH，构构成成新新单单纯纯形形；否否则则，以以Xn+2代代替替XH，Fn+2代代替替FH，构构成成新新单单纯纯形形，然然后返回步骤后返回步骤2；7.压缩。当压缩。当Fn+2 F G时则需收缩，如果时则需收缩，如果Fn+2 F H，则取收缩点则取收缩点否否则则，若若F(XR)F(XH)，在在上上式式中中以以XH

49、代代替替Xn+2，计计算算其其函函数数值值Fn+4。若若Fn+4 F H，则则以以Xn+4代代替替XH，Fn+4代代替替FH，构构成成新新单单纯纯形形，然然后后返返回回步骤步骤3；否则接步骤；否则接步骤8ADM第四章第四章多维无约束优化多维无约束优化70ADM第四章第四章多维无约束优化多维无约束优化8.收缩单纯形。收缩单纯形。最好点不动，其它点向最好点移近为原距离的一半最好点不动，其它点向最好点移近为原距离的一半，即，即（i1，2，n）构成新单纯形，然后返回步骤构成新单纯形，然后返回步骤2继续计算。继续计算。习题习题分别用鲍威尔法、改进鲍威尔法、梯度法、阻尼牛顿法、分别用鲍威尔法、改进鲍威尔法

50、、梯度法、阻尼牛顿法、DFP变尺度法、变尺度法、单纯形法、共轭梯度法求解，迭代单纯形法、共轭梯度法求解，迭代2次。次。71坐标轮换法坐标轮换法将将n n维问题转化为依次沿维问题转化为依次沿n n个坐标方向轮回进行一维搜索。收敛速度较慢，个坐标方向轮回进行一维搜索。收敛速度较慢，适合适合n n1010的小型无约束优化问题，若目标函数具有的小型无约束优化问题，若目标函数具有“脊线脊线”，算法将出，算法将出现病态：沿两个坐标方向均不能使函数数现病态：沿两个坐标方向均不能使函数数 鲍威尔鲍威尔(Powell)法法属于模式搜索法。搜索方向不一定是共轭方向组，而是共轭程度越来越属于模式搜索法。搜索方向不一