《现代设计方法-优化设计优秀PPT.ppt》由会员分享，可在线阅读，更多相关《现代设计方法-优化设计优秀PPT.ppt（168页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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罚函数法 第六章 优化设计建模 第
2、七章 机械优化设计示例3ADM目录其次部分 有限元引言第一章 弹性力学简介 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
3、.2有限元矩阵方程有限元矩阵方程3.2三角形场应变单元三角形场应变单元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、元轴对称问题有限元4.1基本方程基本方程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、和协调性等参元的完备性和协调性5.2轴对称等参元轴对称等参元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、现代设计方法的基本内容：现代设计方法的基本内容：CADCAE有限元分析有限元分析*优化设计优化设计*牢靠性设计牢靠性设计逆向设计逆向设计模块化设计模块化设计设计专家系统设计专家系统价值工程价值工程虚拟设计虚拟设计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、的量二维矢量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第一章第一章优化设计的数学基础优化设计的数学基础矩
11、阵正、负定的判定对称矩阵A正定的充要条件：其行列式各阶主子式之值均大于0;对称矩阵A负定的充要条件：各阶主子式的值，应负、正交替地变更符号。1.3多元函数1.3.1梯度：函数增加最快的方向18ADM第一章第一章优化设计的数学基础优化设计的数学基础1.3.2多元函数的二阶偏导与海赛矩阵多元函数的二阶偏导与海赛矩阵1.3.3函数的泰勒级数绽开函数的泰勒级数绽开19ADM第一章第一章优化设计的数学基础优化设计的数学基础1.3.4多元函数极值多元函数极值极值定义：在X0点的某邻域内，若X0为严格极大值点；为严格极大值点；X0为严格微小值点；为严格微小值点；极值存在的必要条件：梯度为0T向量极值存在的充
12、分条件：H(X0)正定，正定，F(X0)为微小值；为微小值；H(X0)负定，负定，F(X0)为极大值。为极大值。20ADM其次章其次章优化设计的基本概念优化设计的基本概念参数优化：优化结构的参数参数优化：优化结构的参数拓扑优化：优化拓扑结构拓扑优化：优化拓扑结构1.设计变量设计变量设计过程中，其数值可以变更的能够描述结构特性的独立变设计过程中，其数值可以变更的能够描述结构特性的独立变量。传动比，尺寸。量。传动比，尺寸。2.目标函数目标函数目标函数是比较和选择各种不同设计方案的量化指标，是设目标函数是比较和选择各种不同设计方案的量化指标，是设计变量的函数。质量，成本，利润，速度。计变量的函数。质
13、量，成本，利润，速度。21ADM其次章其次章优化设计的基本概念优化设计的基本概念3.约束条件约束条件对设计变量取值范围的约束。强度，刚度，固有频率。对设计变量取值范围的约束。强度，刚度，固有频率。4.设计空间和可行域设计空间和可行域设计空间：由设计变量构成的设计空间：由设计变量构成的n维实空间维实空间可行域：设计空间内，满足约束条件的子空间可行域：设计空间内，满足约束条件的子空间5.数学描述数学描述不等式约束不等式约束等式约束等式约束变量取值范围约束变量取值范围约束22ADM其次章其次章优化设计的基本概念优化设计的基本概念6.例例X*X*F(X)等值等值线线g1(X)g2(X)x1x2可行域可
14、行域237.留意事项留意事项设计变量设计变量1）以主要影响因素作为设计变量；）以主要影响因素作为设计变量；2）依据优化问题的特殊性选择设计变量；）依据优化问题的特殊性选择设计变量；3）留意独立变量和相关变量，尽量不包括相关变量；）留意独立变量和相关变量，尽量不包括相关变量；4）变量群转换，削减变量数目，如变量在目标函数中以）变量群转换，削减变量数目，如变量在目标函数中以x1x2形式存形式存在，可令在，可令y=x1x2；5）必需的设计变量不能遗漏；）必需的设计变量不能遗漏；6）冗余变量）冗余变量相关变量，齿轮设计变量为相关变量，齿轮设计变量为i,z,m,b，齿轮孔径为冗，齿轮孔径为冗余变量。余变
15、量。ADM第二章第二章优化设计的基本概念优化设计的基本概念24ADM第二章第二章优化设计的基本概念优化设计的基本概念约束函数约束函数1）不能冲突；）不能冲突；2）可行域不能无界；）可行域不能无界；3）避开多余约束；）避开多余约束；4）尽量给定设计变量取值上下界，缩小可行域；尽量给定设计变量取值上下界，缩小可行域；5）谨慎对待等式约束；）谨慎对待等式约束；6）近似约束）近似约束不能用精确数学表达式描述的约束的处理；不能用精确数学表达式描述的约束的处理；7）不能遗漏必要的约束，如压簧优化设计忽视了工作状态下，相邻）不能遗漏必要的约束，如压簧优化设计忽视了工作状态下，相邻圈间间隙值约束；圈间间隙值约
16、束；8）全部设计变量必需包含在约束函数集中。）全部设计变量必需包含在约束函数集中。25ADM第二章第二章优化设计的基本概念优化设计的基本概念目标函数目标函数1）目标函数必需包含全部或部分设计变量；）目标函数必需包含全部或部分设计变量；2）当必需接受多目标优化时，可选择其中一个主要的目标作单目标）当必需接受多目标优化时，可选择其中一个主要的目标作单目标优化，其它目标按满足确定值要求的约束处理，优化后在选另一优化，其它目标按满足确定值要求的约束处理，优化后在选另一目标优化；目标优化；3）近似目标函数）近似目标函数借助试验数据处理建立目标函数；借助试验数据处理建立目标函数；4）转移或替代目标函数，如
17、以中心距作为减速器重量的替代目标函）转移或替代目标函数，如以中心距作为减速器重量的替代目标函数；数；5）单体设计对象的多目标评价）单体设计对象的多目标评价设计变量和约束条件不变，建立设计变量和约束条件不变，建立多个不同的目标函数并分别优化，得到一组优化方案，优中择优；多个不同的目标函数并分别优化，得到一组优化方案，优中择优；6）目标函数的规一化）目标函数的规一化minF(X)26ADM第二章第二章优化设计的基本概念优化设计的基本概念8.优化问题求解方法优化问题求解方法搜寻法搜寻法9.收敛判据收敛判据1）相邻两轮搜寻得到的近似极值点）相邻两轮搜寻得到的近似极值点“相对距离相对距离”小于某一小的正
18、数；小于某一小的正数；2）F(X)可微，则梯度确定值小于某一小的正数。可微，则梯度确定值小于某一小的正数。27ADM第三章第三章一维优化一维优化解析法搜寻法干脆法（区间缩减法）：黄金分割法、对分法间接法（插值法）：二次插值、三次插值一维优化在多维优化中作用确定最优步长283.1单峰函数单峰函数3.1.1单峰函数单峰函数在给定区间内仅有一个微小值点的函数在给定区间内仅有一个微小值点的函数多峰与单峰的关系多峰与单峰的关系多峰函数区间分割成数个单峰区间，按单峰函数求极值点多峰函数区间分割成数个单峰区间，按单峰函数求极值点单峰函数极值点求解单峰函数极值点求解单值区间缩小，单值区间缩小，(x1+x2)/
19、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-2为单峰为单峰区间区间xk-2xk-1xkh2hf031ADM第三章第三章一维优化一维优
20、化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法，匀整缩短率对称取点法，匀整缩短率对称取点)黄金分割：将一线段分割成两段，使得整段长度黄金分割：将一线段分割成两段，使得整段长度L与较长段与较长段x的比的比值等于较长段值等于较长段x与较短段与较短段
21、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两点对分法（可不行微）两点对分法（可不行微）a(a+b)/2bax1x2bf1f2(a+b)/2
22、36ADM第三章第三章一维优化一维优化3.4二次插值法二次插值法二次插值：二次多项式靠近二次插值：二次多项式靠近3.4.1方法原理方法原理二次多项式靠近目标函数，以二次多项式的微小值点作为目标函数的近二次多项式靠近目标函数，以二次多项式的微小值点作为目标函数的近似最优点。似最优点。3.4.2二次多项式构造二次多项式构造单峰区间单峰区间x1,x3内存在微小值点，内存在微小值点，在在x1,x3内取点内取点x2，则，则过过x1,x2,x3构造构造其微小值点为其微小值点为x*x1x2x*x*x3f(x)p(x)37ADM第三章第三章一维优化一维优化3.4.3区间缩小原理区间缩小原理比较比较f(x*)和
23、和f(x2)，以其中较小者对应的点为新的，以其中较小者对应的点为新的x2点，新点，新x2左右相左右相邻的点分别为新邻的点分别为新x1，新，新x3。3.4.4收敛判据收敛判据见黄金分割法见黄金分割法习题习题初始区间初始区间a,b=-0.5,1.5，确定精度，确定精度分别用解析法、黄金分割法、中心对分法、两点对分法求解。分别用解析法、黄金分割法、中心对分法、两点对分法求解。38ADM第四章第四章多维无约束优化多维无约束优化分类：分类：1）干脆法（不需计算导数）干脆法（不需计算导数）2）间接法（需计算导数）间接法（需计算导数）4.1坐标轮换法（坐标方向为搜寻方向）坐标轮换法（坐标方向为搜寻方向）4.
24、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）定义）定义A为为n阶正定矩阵，若两个阶正定矩阵，若两个n维矢量满足维矢量满足则称则称S
27、1和和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方向作一维搜寻，方向作一维搜寻，得最优点得最优点X1（与椭圆相切）；从（与椭圆相切）；从X2(
28、0)动身沿动身沿S1方向作一维搜寻，得最方向作一维搜寻，得最优点优点X2；连接；连接X1、X2得矢量得矢量S2，S2过椭圆族中心，即目标函数微小值过椭圆族中心，即目标函数微小值点点X*，且，且S1、S2对对A正交，正交，沿沿S1的共轭方向的共轭方向S2可搜寻到正定二元可搜寻到正定二元二次函数极值点。二次函数极值点。X*45ADM第四章第四章多维无约束优化多维无约束优化4.2.2原始鲍威尔法原始鲍威尔法S1、S2、S3为共、为共、轭方向（参见前页）轭方向（参见前页）搜寻方向搜寻方向:x1x3x2e1e2e3X0(1)S1e2e3S1X1(1)X2(1)X3(1)X0(2)X1(2)X2(2)X3
29、(2)X0(3)S2e3S1S2S3X1(3)X2(3)X3(3)X0(4)第第1轮轮第第2轮轮第第3轮轮46ADM第四章第四章多维无约束优化多维无约束优化原始鲍威尔法的严峻缺陷：当某一轮方向组中的矢量系出现线性相关时原始鲍威尔法的严峻缺陷：当某一轮方向组中的矢量系出现线性相关时（特殊是接近（特殊是接近X*时），会出现退化，无法获得微小值点。时），会出现退化，无法获得微小值点。4.2.3改进鲍威尔法改进鲍威尔法与原始鲍威尔法的区分：每构造一个新方向，依据判别条件确定是否替与原始鲍威尔法的区分：每构造一个新方向，依据判别条件确定是否替换原来的某个方向。构造换原来的某个方向。构造k+1轮方向组时，
30、是否淘汰前一轮的某一个方向轮方向组时，是否淘汰前一轮的某一个方向Sm(k)，依据下面二个条件推断：，依据下面二个条件推断：第第k轮初始点函数值；轮初始点函数值；第第k轮最终一个方向搜寻终点函数值；轮最终一个方向搜寻终点函数值；X0(k)对对Xn(k)映射点映射点Xn1(k)的函数的函数值；值；一维搜寻中函数值下降最大者，其方向一维搜寻中函数值下降最大者，其方向为为Sm(k)47ADM第四章第四章多维无约束优化多维无约束优化条件式条件式a)、b)同时或两者之同时或两者之一成立：第一成立：第k+1轮仍沿用第轮仍沿用第k轮的轮的方向组，取方向组，取Xn(k)（F2F3）或）或映射点映射点Xn1(k)
31、（F3F(X(k)。不是严格的下降算法。缘由：。不是严格的下降算法。缘由：X(k+1)是近似二次式是近似二次式在牛顿方向上的微小点，而非在牛顿方向上的微小点，而非F(X)在牛顿方向上的微小点。在牛顿方向上的微小点。2）对牛顿法的修正）对牛顿法的修正阻尼牛顿法阻尼牛顿法修正方法：在牛顿方向上作一维搜寻求最优步长。修正方法：在牛顿方向上作一维搜寻求最优步长。当当F(X)的海赛矩阵的海赛矩阵Hk在迭代点处正定状况下，阻尼牛顿法可以保证在迭代点处正定状况下，阻尼牛顿法可以保证每次迭代，迭代点的函数值都下降；每次迭代，迭代点的函数值都下降；Hk在迭代点处不定状况下，函数值在迭代点处不定状况下，函数值不会
32、上升，但不确定下降；不会上升，但不确定下降；Hk在迭代点处奇异状况下，不能求逆，无法在迭代点处奇异状况下，不能求逆，无法构造牛顿方向；要求构造牛顿方向；要求F(X)二阶可微，需计算梯度、海赛矩阵及其逆矩阵，二阶可微，需计算梯度、海赛矩阵及其逆矩阵，计算量大。计算量大。4.4.3收敛判据收敛判据同梯度法。同梯度法。52ADM第四章第四章多维无约束优化多维无约束优化53ADM第四章第四章多维无约束优化多维无约束优化4.5DFP变尺度法变尺度法拟牛顿法，基于牛顿法的思想进行了重要改进。拟牛顿法，基于牛顿法的思想进行了重要改进。4.5.1基本思想基本思想综合梯度法和牛顿法的优有点，克服梯度法收敛速度慢
33、和牛顿法收敛综合梯度法和牛顿法的优有点，克服梯度法收敛速度慢和牛顿法收敛快但稳定性差且计算量大的缺点。快但稳定性差且计算量大的缺点。比较梯度法和牛顿法，比较梯度法和牛顿法，54ADM第四章第四章多维无约束优化多维无约束优化Ak为为nn对称矩阵，对称矩阵，Ak为单位矩阵时，上式为梯度法；为单位矩阵时，上式为梯度法；AkHk-1时，上式为阻尼牛顿法。时，上式为阻尼牛顿法。拟牛顿法的基本思想：用某种方法，人为构造一拟牛顿法的基本思想：用某种方法，人为构造一n阶对称矩阵阶对称矩阵AkA(X(k)，近似替代牛顿法的，近似替代牛顿法的Hk-1。通过迭代不断修正。通过迭代不断修正Ak，使使AkHk-1。由于
34、是不断变更的，它使搜寻方向不断向牛顿方向靠近，故可把看作由于是不断变更的，它使搜寻方向不断向牛顿方向靠近，故可把看作是变更的尺度矩阵，这就是变尺度法叫法的由来。梯度法和牛顿法是变更的尺度矩阵，这就是变尺度法叫法的由来。梯度法和牛顿法也属于变尺度法的范畴。也属于变尺度法的范畴。Ak应满足的条件：应满足的条件：1.正定正定保证迭代过程中函数值始终下降，要求保证迭代过程中函数值始终下降，要求S(k)与与gk夹角为锐角，即夹角为锐角，即552.拟牛顿条件拟牛顿条件使使AkHk-1，Ak1可以由第可以由第k步的信息递推构造步的信息递推构造由由得得即即ADM第四章第四章多维无约束优化多维无约束优化56AD
35、M第四章第四章多维无约束优化多维无约束优化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(X*)，结束。，结束。58ADM第四章第四章多维无约
36、束优化多维无约束优化4.6共轭梯度法共轭梯度法将梯度法和共轭方向法结合起来，每一轮搜寻的第一步沿负梯度方向将梯度法和共轭方向法结合起来，每一轮搜寻的第一步沿负梯度方向搜寻，后续各步沿上一步的共轭方向搜寻，具有二次收敛速度，每一搜寻，后续各步沿上一步的共轭方向搜寻，具有二次收敛速度，每一轮搜寻轮搜寻n步。步。第一步的搜寻方向第一步的搜寻方向负梯度方向负梯度方向以后各步的搜寻方向以后各步的搜寻方向共轭方向的确定共轭方向的确定应使应使n维实空间中的两个非维实空间中的两个非0向量向量S(k)和和S(k1)关于矩阵关于矩阵A共轭，共轭，即应使即应使对于正定二次函数对于正定二次函数有有59ADM第四章第四
37、章多维无约束优化多维无约束优化二式相减二式相减而而则则可得可得即即因因 为一正交系，为一正交系，故有故有则则60ADM第四章第四章多维无约束优化多维无约束优化61ADM第四章第四章多维无约束优化多维无约束优化算法算法l任选初始点任选初始点X(0)，给定收敛精度，给定收敛精度和维数和维数n；2令令，求迭代初始点，求迭代初始点X(0)的梯度的梯度g0取第一次搜寻的方向取第一次搜寻的方向S(0)为初始点的负梯度为初始点的负梯度3进行一维搜寻，求最优步长进行一维搜寻，求最优步长(k)并求出新点并求出新点4计算计算X(k+1)点的梯度点的梯度5收敛检查。满足条件收敛检查。满足条件则，计算结束；否则接着下
38、一步；则，计算结束；否则接着下一步；6推断推断k+1是否等于是否等于n，若，若k+1n，则令，则令X(0)=X(k+1)转步骤转步骤2；若；若k+1n，则接着下一步；，则接着下一步；7计算计算62ADM第四章第四章多维无约束优化多维无约束优化8确定下一步的搜寻方向确定下一步的搜寻方向令令，返回步骤，返回步骤3。探讨探讨共轭梯度法具有超线性收敛速度（共轭梯度法具有超线性收敛速度（1收敛速度阶数收敛速度阶数2）。计算效率高于）。计算效率高于梯度法，低于牛顿法，但对初始点没有特殊要求。不需计算二阶偏导数梯度法，低于牛顿法，但对初始点没有特殊要求。不需计算二阶偏导数矩阵及其逆矩阵，计算量与梯度法相当，
39、小于牛顿法。适用于各种规模矩阵及其逆矩阵，计算量与梯度法相当，小于牛顿法。适用于各种规模的问题。的问题。63ADM第四章第四章多维无约束优化多维无约束优化4.7 4.7 单纯形法单纯形法原理原理函数的导数是函数性态的反映，它对选择搜寻方向供应了有用的信息。函数的导数是函数性态的反映，它对选择搜寻方向供应了有用的信息。在不计算导数的状况下，先算出若干点处的函数值，从它们之间的大在不计算导数的状况下，先算出若干点处的函数值，从它们之间的大小关系中也可以看出函数变更的或许趋势，为寻求函数的下降方向供小关系中也可以看出函数变更的或许趋势，为寻求函数的下降方向供应依据。这里所说的若干点，一般取在单纯形的
40、顶点上。所谓单纯形应依据。这里所说的若干点，一般取在单纯形的顶点上。所谓单纯形是指在是指在n n维空间中具有维空间中具有n+1n+1个顶点的简洁图形或凸多面体。利用单纯形个顶点的简洁图形或凸多面体。利用单纯形的顶点，计算其函数值并加以比较，从中确定有利的搜寻方向和步长，的顶点，计算其函数值并加以比较，从中确定有利的搜寻方向和步长，找出具有最大值的顶点并构造目标函数的下降方向，求出最小值点，找出具有最大值的顶点并构造目标函数的下降方向，求出最小值点，以该点取代单纯形的最大值的顶点，重新构造单纯形。随着这种取代以该点取代单纯形的最大值的顶点，重新构造单纯形。随着这种取代过程的不断进行，新的单纯形不
41、断向微小点收缩。这样经过若干次迭过程的不断进行，新的单纯形不断向微小点收缩。这样经过若干次迭代，即可得到满足精度要求的近似解。这就是单纯形法的基本思想。代，即可得到满足精度要求的近似解。这就是单纯形法的基本思想。64ADM第四章第四章多维无约束优化多维无约束优化65ADM第四章第四章多维无约束优化多维无约束优化算法算法选选择择新新的的比比较较好好的的点点替替代代最最差差点点的的算算法法有有4种种：反反射射、扩扩张张、压压缩缩和和收缩。现以二元函数收缩。现以二元函数F(X)=F(x1,x2)为例，说明单纯形法的算法。为例，说明单纯形法的算法。在在x1-x2平平面面上上取取不不在在同同始始终终线线
42、上上的的三三点点XH、XG、XL，以以它它们们为为顶顶点组成一单纯形（即三角形）点组成一单纯形（即三角形）XHXGXL。计算各顶点函数值，设。计算各顶点函数值，设F(XH)F(XG)F(XL)说说明明XL点点最最好好，XH点点最最差差。为为了了找找寻寻微微小小点点，一一般般说说来来，应应向向最最差差点点的的反反对对称称方方向向进进行行搜搜寻寻，即即通通过过XH并并穿穿过过XGXL的的中中点点XC的的方方向向进进行搜寻。在此方向上取作行搜寻。在此方向上取作XH点相对于点相对于XC点的反射点点的反射点XRXRXC(XCXH)2XCXH计算反射点的函数值计算反射点的函数值F(XR)，可能出现以下几种
43、情形：，可能出现以下几种情形：l.F(XR)F(XL)即即反反射射点点比比最最好好点点还还好好，说说明明搜搜寻寻方方向向正正确确，还还可可以往前迈进一步，也就是可以扩张。这时取扩张点以往前迈进一步，也就是可以扩张。这时取扩张点XEXCk(XCXH)k扩张因子，一般取扩张因子，一般取kl.2-2.0。假假如如F(XE)F(XR)说说明明扩扩张张有有利利，就就以以XE代代替替XH构构成成新新单单纯纯形形XEXGXL。否否则则说说明明扩扩张张不不利利，舍舍弃弃XE，仍仍以以XR代代替替XH构构成成新新单单纯纯形形XRXGXL。66ADM第四章第四章多维无约束优化多维无约束优化2.F(XL)F(XR)
44、F(XG)即即反反射射点点比比最最好好点点差差，但但比比次次差差点点好好，说说明明反射可行，则以反射点代替最差点，仍构成新单纯形反射可行，则以反射点代替最差点，仍构成新单纯形XRXGXL。3.F(XG)F(XR)F(XH)即即反反射射点点比比次次差差点点差差，但但比比最最差差点点好好，说说明明XR走得太远，应缩回一些，即压缩。这时取压缩点走得太远，应缩回一些，即压缩。这时取压缩点XKXCm(XRXC)m收缩因子，常取成收缩因子，常取成m0.5。假如假如F(XK)F(XH)，则用，则用XK代替代替XH构成新单纯形构成新单纯形XKXGXL。4.F(XR)F(XH)即即反反射射点点比比最最差差点点还
45、还差差，这这时时应应压压缩缩得得更更多多一一些些，即即将新点收缩在将新点收缩在XHXC之间，取压缩点之间，取压缩点XKXCm(XCXH)假如假如F(XK)F(XH)则用则用XK代替代替XH构成新单纯形构成新单纯形XKXGXL。5.F(X)F(XH)即即若若XHXC方方向向上上的的全全部部点点都都比比最最差差点点差差，则则表表明明不不能能沿沿此此方方向向搜搜寻寻，这这时时应应以以XL为为中中心心收收缩缩，使使顶顶点点XH、XG向向XL移移近近一一半距离，得新单纯形半距离，得新单纯形XHXGXL，如图所示。，如图所示。67ADM第四章第四章多维无约束优化多维无约束优化从从以以上上各各步步得得到到新
46、新的的单单纯纯形形后后，再再重重复复起起先先新新一一轮轮构构造造单单纯纯形形，渐渐渐渐缩缩小小单单纯形直至满足精度要求。纯形直至满足精度要求。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和反射点和反射点当当时时，以以Xn+2代代替替XH，Fn+2代代替替FH，构构
48、成成一一新新单单纯纯形形，然后返回步骤然后返回步骤2；6.扩张。当扩张。当Fn+2FL时，取扩张点时，取扩张点并并计计算算其其函函数数值值Fn+3。若若Fn+3Fn+2，则则以以Xn+3代代替替XH，Fn+3代代替替FH，构构成成新新单单纯纯形形；否否则则，以以Xn+2代代替替XH，Fn+2代代替替FH，构构成成新新单纯形，然后返回步骤单纯形，然后返回步骤2；7.压缩。当压缩。当Fn+2FG时则需收缩，假如时则需收缩，假如Fn+2FH，则取收缩点，则取收缩点否否则则，若若F(XR)F(XH)，在在上上式式中中以以XH代代替替Xn+2，计计算算其其函函数数值值Fn+4。若若Fn+4FH，则则以以
49、Xn+4代代替替XH，Fn+4代代替替FH，构构成成新新单单纯纯形形，然后返回步骤然后返回步骤3；否则接步骤；否则接步骤8ADM第四章第四章多维无约束优化多维无约束优化70ADM第四章第四章多维无约束优化多维无约束优化8.收缩单纯形。最好点不动，其它点向最好点移近为原距离的一半收缩单纯形。最好点不动，其它点向最好点移近为原距离的一半，即，即（i1，2，n）构成新单纯形，然后返回步骤构成新单纯形，然后返回步骤2接着计算。接着计算。习题习题分分别别用用鲍鲍威威尔尔法法、改改进进鲍鲍威威尔尔法法、梯梯度度法法、阻阻尼尼牛牛顿顿法法、DFP变变尺尺度度法法、单纯形法、共轭梯度法求解，迭代单纯形法、共轭
50、梯度法求解，迭代2次。次。71坐标轮换法坐标轮换法将将n n维问题转化为依次沿维问题转化为依次沿n n个坐标方向轮回进行一维搜寻。收敛速度较慢，个坐标方向轮回进行一维搜寻。收敛速度较慢，适合适合n10n10的小型无约束优化问题，若目标函数具有的小型无约束优化问题，若目标函数具有“脊线脊线”，算法将出，算法将出现病态：沿两个坐标方向均不能使函数数现病态：沿两个坐标方向均不能使函数数 鲍威尔鲍威尔(Powell)(Powell)法法 属于模式搜寻法。搜寻方向不确定是共轭方向组，而是共轭程度越来越属于模式搜寻法。搜寻方向不确定是共轭方向组，而是共轭程度越来越高的方向组（改进共轭方向），避开原始鲍威尔