现代设计方法优化设计学习教案

1、会计学1第一页，共169页。2序论(x ln)第一部分 优化设计 第一章 优化设计的数学基础 1.1 矢量 1.2 矩阵 1.3 多元函数 第二章 优化设计的基本概念 第三章 一维优化 3.1 单峰函数 3.2 黄金分割法 3.3 对分法 4.4 二次插值法 第四章 多维无约束优化 4.1 直接法 4.2 鲍威尔法 4.3 梯度法（最速下降法） 4.4 牛顿法 目 录ADM第1页/共168页第二页，共169页。3ADM目 录 第五章 多维有约束(yush)优化 5.1 概述 5.2 网格法 5.3 罚函数法 第六章 优化设计建模 第七章 机械优化设计示例第2页/共168页第三页，共169页。4

2、ADM目 录第二部分 有限元引言第一章 弹性力学简介 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 插值及单元位移(wiy) 2.4 弹性力学有限元的矩阵方程第3页/共168页第四页，共169页。5ADM目 录第三章 平面问题有限元 3.1 平面问题基本方程及有限元矩阵方程 3.1.1 基本方程 3.1.2 有限元矩阵方程

3、 3.2 三角形场应变单元 3.2.1 离散化 3.2.2 位移(wiy)模式 3.2.3 应变 3.4 刚度矩阵 3.4.1 单元刚度矩阵 3.4.2 总体刚度矩阵的组装 3.4.3 总体位移(wiy)向量 3.5 单元的等效节点力与总体载荷向量 3.5.1 单元的等效节点力 3.5.2 总体载荷向量第4页/共168页第五页，共169页。6ADM目 录 3.6 刚度方程求解 3.6.1 边界条件处理 3.7 有限元分析(fnx)的实施步骤 3.8 有限元计算收敛性第四章 轴对称问题有限元 4.1 基本方程 4.1.1 平衡方程 4.1.2 几何方程 4.1.3 物理方程 4.2 三角形截面环

4、单元 4.3 轴对称问题的有限元矩阵表达式 4.3.1 单元刚度矩阵 4.3.2 组装总体刚度矩阵 4.3.3 单元等效节点力第5页/共168页第六页，共169页。7ADM目 录第五章 等参数单元 5.1 平面等参元 5.1.1 坐标变换及位移 5.1.2 应变及应变矩阵 5.1.3 单元刚度矩阵 5.1.4 单元等效节点(ji din)力 5.1.5 高斯积分 5.1.6 等参元的完备性和协调性 5.2 轴对称等参元 5.2.1 坐标变换及位移 5.2.2 应变及应变矩阵 5.2.3 单元刚度矩阵 5.2.4 单元等效节点(ji din)力 5.3 等参元的应力、应变计算第6页/共168页第

5、七页，共169页。8第六章 杆件系统第七章 薄板弯曲问题第八章 结构动力学问题 8.1 结构动力学微分方程 8.2 结构动力学虚功方程 8.3 结构动力学有限元矩阵方程 8.4 结构自由振动(zhndng)有限元矩阵方程模态分析ADM目 录第7页/共168页第八页，共169页。9ADM序 论现代设计方法的基本内容：CADCAE有限元分析*优化设计*可靠性设计逆向设计模块化设计设计专家系统价值工程(gngchng)虚拟设计第8页/共168页第九页，共169页。10如何评价(pngji)设计质量?m-1s+1s设计参数可靠性：性能的波动在允许的设计(shj)界限内稳健性（鲁棒性）：降低(jingd

6、)在设计点上的敏感性下限上限-1s +1s第9页/共168页第十页，共169页。11设计(shj)质量， 个案研究 - SONY电视机有统一的系统设计和公差，任何不合格品都不卖给消费者调查(dio ch)显示，美国消费者一向喜欢日本产的电视机Target频率u日产电视机性能在期望值附近作小幅波动（方差很小），统计上看，大量的产品性能稳定，更加趋向设计目标（ TARGET ）u美国产的电视机性能呈扁平分布 , 多数产品的质量是刚好落在界限内第10页/共168页第十一页，共169页。12DesignSpaceFeasibleDesignSpace例：悬臂梁减重优化确定性优化Design Varia

7、bles:10 Beam Height 80 mm10 Flange Width 50 mmConstraint:Stress 16 MPaObjective:Minimize Mass(minimize area)1080105020304050 6070203040Beam Height, mmFlange Width, mmStress= 16Loads at free endFlangeWidthBeamHeightArea = 400Area = 300Solution:Beam Height= 38.4Flange Width= 22.7Stress= 16Area= 233.4第

8、11页/共168页第十二页，共169页。13确定性最优点：应力绝对最小点函数最小值几何安装角x应力 f(x)(安装误差 D x) 稳健设计D f2D f1 Dx 不稳健 :易受不确定因素影响而造成性能的大幅波动Dx 稳健最优设计点牺牲部分性能，更可靠、更稳健的设计不可靠:应力大于许用应力问题：已知安装角x 存在不确定误差，在保证(bozhng)可靠性和稳健性前提下，求使应力f 最小的x值最大允许(ynx)应力危险区安全区概念(ginin)：质量设计稳健性、可靠性优化第12页/共168页第十三页，共169页。14ADM第一章 优化设计的数学(shxu)基础1.1 矢量 Vector定义：有大小(

9、dxio)和方向的量1.1.1 二维矢量x2x1P(x1,x2)P(x1,x2)OTxxOPX,21TxxOPX,21TxxxxPP,21211.1. 2 n维矢量(shling) TnxxxOPX,.,21第13页/共168页第十四页，共169页。15ADM第一章 优化设计(shj)的数学基础1.2 矩阵1.2.1 定义 由一组数按一定(ydng)次序排列成的具有m行n列的表mnmmnnaaaaaaaaaA.212222111211第14页/共168页第十五页，共169页。16ADM第一章 优化设计(shj)的数学基础1.2.2 逆矩阵(j zhn) Lattice 若 则B为A的逆矩阵(j

10、 zhn) 逆矩阵(j zhn)的求法EBAAB1 ABAAA*1A*为A的伴随(bn su)矩阵第15页/共168页第十六页，共169页。17ADM第一章 优化设计的数学(shxu)基础1.2.3 矩阵(j zhn)的正定与负定 二次型 对 若133132232112233222211321222),(321xxaxxaxxaxaxaxaxxxFAXXT 0XanyXFXFXFXFXF)(0)(0)(0)(0)(A为正定(zhn dn)；A为半正定(zhn dn)；A为负定；A为半负定不定第16页/共168页第十七页，共169页。18ADM第一章 优化设计的数学(shxu)基础矩阵正、负定的

11、判定 对称矩阵A正定的充要条件：其行列式各阶主子式之值均大于0; 对称矩阵A负定的充要条件：各阶主子式的值，应负、正交替地变化符号 。1.3 多元(du yun)函数1.3.1 梯度：函数增加最快的方向nixFXFTi,.,2, 1,)(第17页/共168页第十八页，共169页。19ADM第一章 优化设计(shj)的数学基础1.3.2 多元函数的二阶偏导与海赛矩阵1.3.3 函数的泰勒(ti l)级数展开 njixxFHji,.,2 , 1,2XXHXXFXXFXFFXXXHXXXFXXXFXFTTTTDDDD)(21)()()()()(21)()()()(000000000第18页/共168

12、页第十九页，共169页。20ADM第一章 优化设计的数学(shxu)基础1.3.4 多元(du yun)函数极值 极值定义：在X0点的某邻域 内，若)(0X)()()()(00XFXFXFXFX0为严格(yng)极大值点；X0为严格(yng)极小值点；极值存在的必要条件：梯度为0T向量 0)(0XF极值存在的充分条件：XXHXXXHXXFXFTTTDDDDDD)(21)(21)(000H(X0)正定， F(X0)为极小值；H(X0)负定， F(X0)为极大值。第19页/共168页第二十页，共169页。21ADM第二章 优化设计(shj)的基本概念参数优化：优化结构的参数拓扑优化：优化拓扑结构1

13、. 设计变量(binling)设计过程中，其数值可以改变的能够描述结构特性的独立变量(binling)。传动比，尺寸。2. 目标函数目标函数是比较和选择各种不同设计方案的量化指标，是设计变量(binling)的函数。质量，成本，利润，速度。,.,21nxxxX )(XF第20页/共168页第二十一页，共169页。22ADM第二章 优化设计(shj)的基本概念3. 约束条件 对设计变量取值范围的约束。强度(qingd)，刚度，固有频率。4. 设计空间和可行域设计空间：由设计变量构成的n维实空间可行域：设计空间内，满足约束条件的子空间5. 数学描述iiiiibxaXhXg0)(0)(不等式约束(y

14、ush)等式约束(yush)变量取值范围约束(yush),.,2, 1, 0)(;,.2 , 1, 0)(|)(minpmmjXhmjXgXDRDXXFjjn第21页/共168页第二十二页，共169页。23ADM第二章 优化设计(shj)的基本概念6. 例0)(0)(01)(02)(44)(min2413221221112221xXgxXgxxXgxxXgxxxXFX*X*F(X)等值线g1(X)g2(X)x1x2可行(kxng)域第22页/共168页第二十三页，共169页。247. 注意事项 设计(shj)变量 1）以主要影响因素作为设计(shj)变量； 2）根据优化问题的特殊性选择设计(s

15、hj)变量； 3）注意独立变量和相关变量，尽量不包括相关变量； 4）变量群转换，减少变量数目，如变量在目标函数中以x1x2形式存 在，可令y= x1x2 ； 5）必须的设计(shj)变量不能遗漏； 6）冗余变量相关变量，齿轮设计(shj)变量为i,z,m,b，齿轮孔径为冗 余变量。ADM第二章 优化设计的基本概念第23页/共168页第二十四页，共169页。25ADM第二章 优化设计的基本概念约束函数 1）不能矛盾； 2）可行域不能无界； 3）避免多余约束； 4） 尽量给定设计变量取值上下界，缩小可行域； 5）谨慎对待等式约束； 6）近似约束不能用精确数学表达式描述的约束的处理； 7）不能遗漏必

16、要的约束，如压簧优化设计忽略了工作状态下，相邻 圈间间隙值约束； 8）全部设计变量必须(bx)包含在约束函数集中。第24页/共168页第二十五页，共169页。26ADM第二章 优化设计的基本概念目标函数 1）目标函数必须包含全部或部分设计变量； 2）当必须采用多目标优化时，可选择其中一个主要的目标作单目标 优化，其它目标按满足一定值要求的约束处理，优化后在选另一 目标优化； 3）近似目标函数借助实验数据处理建立目标函数； 4）转移或替代目标函数，如以中心距作为减速器重量的替代目标函 数； 5）单体设计对象(duxing)的多目标评价设计变量和约束条件不变，建立 多个不同的目标函数并分别优化，得

17、到一组优化方案，优中择优； 6）目标函数的规一化minF(X)第25页/共168页第二十六页，共169页。27ADM第二章 优化设计的基本概念8. 优化问题求解方法 搜索法9. 收敛判据 1）相邻两轮搜索得到的近似极值点“相对距离”小于某一小的正数(zhngsh)； 2）F(X)可微，则梯度绝对值小于某一小的正数(zhngsh)。)()2()1()0(,.,nXXXX第26页/共168页第二十七页，共169页。28ADM第三章 一维优化解析法搜索法 直接法（区间缩减法）：黄金分割法、对分法 间接法（插值法）：二次插值、三次(sn c)插值 一维优化在多维优化中作用确定最优步长1)(minRxx

18、f)()()()1()()()()(minkkkkkkkSXXSXF第27页/共168页第二十八页，共169页。293.1 单峰函数3.1.1 单峰函数在给定区间内仅有一个极小值点的函数多峰与单峰的关系 多峰函数区间分割(fng)成数个单峰区间，按单峰函数求极值点单峰函数极值点求解 单值区间缩小， (x1+x2)/2为极值点ADM第三章 一维优化0,212, 1 xxxx第28页/共168页第二十九页，共169页。30ADM第三章 一维优化3.1.2 初始单值区间确定算法进退(jntu)步法（探索步长加倍）单峰区间(q jin)：x2 , x4 x5 , x3 h 2h 4h 4h 2h h

19、hx1 x2 x3 x4x5 x4 x3 x1 x2第29页/共168页第三十页，共169页。31ADM第三章 一维优化 一阶导数(do sh)法（f(x)连续可微） 以h,2h,4h.，h0为步长， 若 f(xk-2 )0 或 f(xk-2 )0, f(xk)=2 则 xk-2 , xk或xk xk-2 为单峰区间xk-2 xk-1 xk h 2hf0第30页/共168页第三十一页，共169页。32ADM第三章 一维优化3.2 黄金分割(hungjnfng)法3.2.1 区间缩小求解极值点的基本思路 按一定规则在a,b内取两个点x1,x2a x1 x2 b a x1 x2 b a x1 x2

20、 b (a) (b) (c) f(x1)f(x2) f(x1)=f(x2)a,b a,x2 a,b x1,b a,b a,x2 或x1,b 第31页/共168页第三十二页，共169页。33ADM第三章 一维优化3.2.2 取点规则黄金分割法(0.618法，均匀缩短率对称取点) 黄金分割：将一线(yxin)段分割成两段，使得整段长度L与较长段x 的比值等于较长段x与较短段L-x 的比值L a x1 x2 b LLxLxLLxL)1 (LL)1 (LL)1 (618. 0215012LL)1 ()(618. 0),(382. 021abaxabax第32页/共168页第三十三页，共169页。34A

21、DM第三章 一维优化3.2.3 区间收缩(shu su) 参见 3.2 1618. 0lnlnlnln)(ababNabN第33页/共168页第三十四页，共169页。35ADM第三章 一维优化3.2.4 收敛判据 常用判据 1） 2） 3） 4） 判据的使用 1)、3)或2)、4)组合(zh)使用，并从a, b, (a+b)/2中选最优者4321)(/)()()()(/bfbfafbfafbbabafDfD a b a b第34页/共168页第三十五页，共169页。36ADM第三章 一维优化3.3 对分法3.3.1 中心对分法（可微） 比较的符号(fho)，将区间a,b缩短一半。3.3.2 两

22、点对分法（可不可微） 2),( ),( bafbfaf a (a+b)/2 b0)( af0)2( baf0)( bf2,baabaa x1 x2 b f1 f2 有明显的差异。的选取应使21221,)(ffxabaxfxf(a+b)/222第35页/共168页第三十六页，共169页。37ADM第三章 一维优化3.4 二次插值法 二次插值：二次多项式逼近3.4.1 方法原理 二次多项式逼近目标函数，以二次多项式的极小值点作为目标函数的近似最优点。3.4.2 二次多项式构造(guzo) 单峰区间x1,x3内存在极小值点，在x1,x3内取点x2，则过x1,x2,x3构造(guzo)其极小值点为x*

23、 321xfxfxf2)(cxbxaxp x1 x2 x* x* x3 32132,*,*,xxxxxxf(x)p(x)第36页/共168页第三十七页，共169页。38ADM第三章 一维优化3.4.3 区间缩小原理 比较f(x*)和f(x2)，以其中(qzhng)较小者对应的点为新的x2点，新 x2左右相邻的点分别为新x1 ，新 x3 。3.4.4 收敛判据见黄金分割法习题初始区间 a,b = -0.5,1.5，绝对精度分别用解析法、黄金分割法、中心对分法、两点对分法求解。) 1(5)(min1xexfx15. 0第37页/共168页第三十八页，共169页。39ADM第四章 多维无约束优化nR

24、XXF)(min分类：1）直接法（不需计算导数） 2）间接法（需计算导数）4.1 坐标轮换法（坐标方向为搜索方向）4.1.1 原理 将n维问题(wnt)转化为依次沿n个坐标方向轮回进行一维搜索。)()()()1()()()()(minkkkkkkkSXXSXF第38页/共168页第三十九页，共169页。40ADM第四章 多维无约束优化第39页/共168页第四十页，共169页。41ADM第四章 多维无约束优化4.1.2 算法 1）任选初始点 设定初始步长 置搜索方向(fngxing) 2）以 为初始点，沿 方向(fngxing)作试探，步长 计算 ，若 说明试探成功；否则， 若 ，置 ，若 ，T

25、nxxxX,.,)0()0(2)0(1)0(0)01. 0(0TnTTieeeS 1,.,0 , 0 , 0.0,.,0 , 1 , 00,.,0 , 0 , 1 21)0(X1e01)0(eXX)()()0(XFXF和)()()0(XFXF)()()0(XFXF0)()()0(XFXF第40页/共168页第四十一页，共169页。42ADM第四章 多维无约束优化 则作一维搜索求最优步长和优化点 若沿坐标轴正负方向试探均失败，则迭代点不变 3）以 为起点，按1）沿 方向搜索，得 沿n个坐标方向进行完一轮一维搜索后，得 4）以 作第二轮得起始点 ，重复2）、3）得第二轮搜索终点 。 5）如果从某轮

26、起始点出发，依次沿n个坐标轴的正负方向试探均失败，则缩短试探步长（如减半），返回2）。当探索(tn su)步长足够小，满足收敛判据 时，终止迭代，所得点即为优化结果X*。SXXSXF)0()1()0(1)(min)0()1(1XX)1(1X2e)1(2X)1(nX)1(nX)1()2(0nXX)2(nXmin第41页/共168页第四十二页，共169页。43ADM第四章 多维无约束优化4.1.3 讨论 1）计算量小，程序简单，计算效率低，适合变量n10的情况。 2）若目标函数具有脊线，算法将出现病态：沿两个坐标方向(fngxing)均不能使函数数值下降，误认为最优点。脊线(j xin)第42页/

27、共168页第四十三页，共169页。44ADM第四章 多维无约束优化4.2 鲍威尔法（共轭方向为搜索方向）4.2.1 共轭方向 1）定义 A为n阶正定矩阵，若两个n维矢量满足 则称S1和S2对矩阵A共轭，共轭矢量方向为共轭方向。 对于n个n维矢量Si，i=1,2,n(Si不为0)，若满足则称n个n维矢量Si，i=1,2,n为对矩阵A共轭。 2）共轭方向与函数的极小值点关系 考察(koch)正定二次函数 其等值线为同心椭圆族021ASST1S2SAST1AST2jiASSjiASSjTijTi, 0, 0AXXXbaXFTT21)(第43页/共168页第四十四页，共169页。45ADM第四章 多维

28、无约束优化S2S1S1X1X2X1(0)X2(0)x1x2 从X1(0)出发沿S1方向作一维搜索，得最优点X1 （与椭圆相切）；从X2(0)出发沿S1方向作一维搜索，得最优点X2；连接X1 、 X2得矢量S2 ， S2过椭圆族中心(zhngxn)，即目标函数极小值点X*，且S1、S2对A正交，沿S1 的共轭方向S2可搜索到正定二元二次函数极值点。X*00)(0)(1112121211112ASSASXXSAXbSXFSAXbSXFTTTT二式相减1()F X第44页/共168页第四十五页，共169页。46ADM第四章 多维无约束优化4.2.2 原始(yunsh)鲍威尔法 S1 、S2、 S3为

29、共、轭方向（参见前页） 搜索方向: x1x3x2e1e2e3X0(1)S1e2e3S1X1(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轮)()()()1()()()()(minkkkkkkkSXXSXF)4(0)4(34321)3(0)3(33213)2(0)2(32132)1(0)1(31321,4,3,2,1XXSSSSXXSSSeXXSSeeXXSeee轮：第轮：第轮：第轮：第第45页/共168页第四十六页，共169页。47ADM第四章 多维无约束优化 原始鲍威尔法的严重缺陷：当某

30、一轮方向组中的矢量系出现线性相关时（特别是接近X*时），会出现退化，无法获得极小值点。4.2.3 改进鲍威尔法 与原始鲍威尔法的区别：每构造(guzo)一个新方向，根据判别条件决定是否替换原来的某个方向。构造(guzo)k+1轮方向组时，是否淘汰前一轮的某一个方向Sm(k) ，根据下面二个条件判断：31221231213( )10( )2( )( )30( )( )1).).222maxkknkknkkmmaFFbFFFFFFFFF XFF XFFXXF XF XDDD 第k轮初始点函数值；第k轮最后一个方向搜索(su su)终点函数值；X0(k)对Xn(k) 映射点Xn1(k)的函数值；一维

31、搜索(su su)中函数值下降最大者，其方向为Sm(k) 第46页/共168页第四十七页，共169页。48ADM第四章 多维无约束优化 条件式a)、b)同时或两者之一成立：第k+1轮仍沿用第k轮的方向组，取Xn(k)（ F2 F3）或映射(yngsh)点Xn1(k)（ F3 F(X(k)。不是严格的下降算法。原因： X(k+1)是近似二次式在牛顿方向上的极小点，而非F(X)在牛顿方向上的极小点。 2）对牛顿法的修正阻尼牛顿法 修正方法：在牛顿方向上作一维搜索求最优步长。 当F(X)的海赛矩阵Hk在迭代点处正定情况下，阻尼牛顿法可以保证每次迭代，迭代点的函数值都下降； Hk在迭代点处不定情况下，

32、函数值不会上升，但不一定下降； Hk在迭代点处奇异情况下，不能求逆，无法构造牛顿方向；要求(yoqi)F(X)二阶可微，需计算梯度、海赛矩阵及其逆矩阵，计算量大。4.4.3 收敛判据 同梯度法。kkkkkkkkgHXXSXF1)()()1()()()()(min步长：第51页/共168页第五十二页，共169页。53ADM第四章 多维无约束优化第52页/共168页第五十三页，共169页。54ADM第四章 多维无约束优化4.5 DFP变尺度法拟牛顿法，基于牛顿法的思想进行了重要改进。4.5.1 基本思想 综合梯度法和牛顿法的优有点(yudin)，克服梯度法收敛速度慢和牛顿法收敛快但稳定性差且计算量

33、大的缺点。 比较梯度法和牛顿法，)()()()()()1(1)()()1()()()()()()1()(:kkkkkkkkkkkkkkkkkkkSXgAXXDFPgHXXgXXFXXk：变尺度法迭代公式将二者统一为牛顿法：梯度法第53页/共168页第五十四页，共169页。55ADM第四章 多维无约束优化 Ak为nn对称矩阵， Ak为单位矩阵时，上式为梯度法； AkHk-1时，上式为阻尼牛顿法。 拟牛顿法的基本思想：用某种方法，人为构造一n阶对称矩阵 AkA(X(k)，近似替代牛顿法的Hk-1。通过迭代不断修正Ak， 使Ak Hk-1。 由于是不断变化的，它使搜索方向不断向牛顿方向逼近，故可把看

34、作是变化的尺度(chd)矩阵，这就是变尺度(chd)法叫法的由来。梯度法和牛顿法也属于变尺度(chd)法的范畴。 Ak应满足的条件： 1. 正定 保证迭代过程中函数值始终下降，要求S(k)与gk夹角为锐角，即0)(kTkgS第54页/共168页第五十五页，共169页。562. 拟牛顿(ni dn)条件使Ak Hk-1，Ak1可以由第k步的信息递推构造由得即 ADM第四章 多维无约束优化 00kkTkkTkkgAgggAXHXXgFXFkTTkkDDD21)()()1(1)()(kkkkkkkXHgXFgXHgXFgDD)(1kkkkkXHgggDDkkkkkkgAXgHXDDDD1)(1)(第

35、55页/共168页第五十六页，共169页。57ADM第四章 多维无约束优化.;min.1)()()()()1()(1)1(1)()()1()()(0010kkkkkTkkTkkkkTkTkkkkkkkkkkkkkkkkkkkkAAAgAgAggAgXXXAXXXgggXFggAXXgAXFAAAEADDDDDDDDDDDDD4.5.2 Ak序列的生成(shn chn)（DFP递推公式）第56页/共168页第五十七页，共169页。58ADM第四章 多维无约束优化4.5.3 算法 1）任选初始点X(0)，收敛精度 2）置k=0，Ak=E（单位矩阵）； 3）沿 4） 5）用DFP公式求Ak+1； 6

36、）置 。若kn（变量数目），转到3），否则返回到2）开始下一轮（从负梯度法重开始，有利于收敛）； 7）输出(shch)结果X*，F(X*)，结束。），否则进行下一步；转到，若点的梯度。计算700)0(ggX)(min)(,)()()()()()()(kkkkkkkkkSXFSXFgAS使优步长方向作一维搜索，求最），否则继续；，转到。若，7)(1)1(1)()()()1(kkkkkkkgXFgSXX1 kk第57页/共168页第五十八页，共169页。59ADM第四章 多维无约束优化4.6共轭梯度法 将梯度法和共轭方向法结合起来，每一轮搜索的第一步沿负梯度方向搜索，后续各步沿上一步的共轭方向搜索

37、，具有二次收敛速度，每一轮搜索n步。第一步的搜索方向负梯度方向 以后各步的搜索方向共轭方向的确定应使n维实空间中的两个非0向量S(k)和S(k1)关于矩阵A共轭，即应使 对于(duy)正定二次函数有)(1)()1()1()(kkkkkSgSXFS0SS(k)1)(kATAXXXbaXFTT21)()1()1(1)()()()(kkkkkkAXbXFgAXbXFg第58页/共168页第五十九页，共169页。60ADM第四章 多维无约束优化二式相减 而则可得即因 为一正交系，故有则 )()1(1kkkkXXAgg)()()()1(kkkkSXX)()(1kkkkSAgg01SSS)(11)(k(k

38、)1)(kkkkTTggA0SSS1)(111)(k(k)1)(kkkTkkkkTTggSgggA01.gggkk，00)(11kTkkTkSggg或011kTkkTkgggg22111kkkTkkTkgggggg第59页/共168页第六十页，共169页。61ADM第四章 多维无约束优化第60页/共168页第六十一页，共169页。62ADM第四章 多维无约束优化算法l任选初始点X(0)，给定收敛精度(jn d)和维数n；2令 ，求迭代初始点X(0)的梯度g0取第一次搜索的方向S(0)为初始点的负梯度3进行一维搜索，求最优步长(k)并求出新点 4计算X(k+1)点的梯度5收敛检查。满足条件则，计

39、算结束；否则继续下一步；6判断k+1是否等于n，若k+1n，则令X(0)=X(k+1)转步骤2；若k+1n，则继续下一步；7计算 0k)()(kkXFgkkgS)(2)1()(kXF)()()()1()()()()(minkkkkkkkSXXSXF)()1(1kkXFg第61页/共168页第六十二页，共169页。63ADM第四章 多维无约束优化8确定下一步的搜索方向 令 ，返回步骤3。讨论共轭梯度法具有(jyu)超线性收敛速度（1收敛速度阶数2）。计算效率高于梯度法，低于牛顿法，但对初始点没有特殊要求。不需计算二阶偏导数矩阵及其逆矩阵，计算量与梯度法相当，小于牛顿法。适用于各种规模的问题。 )

40、(1)1(kkkSgS1 kk第62页/共168页第六十三页，共169页。64ADM第四章 多维无约束优化4.7 单纯形法原理函数的导数是函数性态的反映，它对选择搜索方向提供了有用的信息。在不计算导数的情况下，先算出若干点处的函数值，从它们之间的大小关系中也可以看出函数变化的大概趋势，为寻求函数的下降方向提供依据(yj)。这里所说的若干点，一般取在单纯形的顶点上。所谓单纯形是指在n维空间中具有n+1个顶点的简单图形或凸多面体。利用单纯形的顶点，计算其函数值并加以比较，从中确定有利的搜索方向和步长，找出具有最大值的顶点并构造目标函数的下降方向，求出最小值点，以该点取代单纯形的最大值的顶点，重新构

41、造单纯形。随着这种取代过程的不断进行，新的单纯形不断向极小点收缩。这样经过若干次迭代，即可得到满足精度要求的近似解。这就是单纯形法的基本思想。第63页/共168页第六十四页，共169页。65ADM第四章 多维无约束优化第64页/共168页第六十五页，共169页。66ADM第四章 多维无约束优化算法选择新的比较好的点替代最差点的算法有4种：反射、扩张、压缩和收缩。现以二元函数F(X)=F(x1,x2)为例，说明单纯形法的算法。在x1-x2平面上取不在同一直线上的三点XH、XG、XL，以它们为顶点组成一单纯形（即三角形）XHXGXL。计算各顶点函数值，设F(XH)F(XG)F(XL)说明XL点最好

42、，XH点最差。为了寻找极小点，一般说来，应向最差点的反对称方向进行搜索，即通过XH并穿过XGXL的中点XC的方向进行搜索。在此方向上取作XH点相对于XC点的反射点XRXRXC(XCXH)2XCXH 计算反射点的函数值F(XR)，可能出现(chxin)以下几种情形：l. F(XR)F(XL) 即反射点比最好点还好，说明搜索方向正确，还可以往前迈进一步，也就是可以扩张。这时取扩张点XEXCk(XCXH)k扩张因子，一般取kl.2-2.0。 如果F(XE)F(XR)说明扩张有利，就以XE代替XH构成新单纯形XEXGXL。否则说明扩张不利，舍弃XE，仍以XR代替XH构成新单纯形XRXGXL。第65页/

43、共168页第六十六页，共169页。67ADM第四章 多维无约束优化2. F(XL)F(XR)F(XG) 即反射点比最好点差，但比次差点好，说明(shumng)反射可行，则以反射点代替最差点，仍构成新单纯形XRXGXL。3. F(XG)F(XR)F(XH) 即反射点比次差点差，但比最差点好，说明(shumng)XR走得太远，应缩回一些，即压缩。这时取压缩点XKXCm (XRXC)m收缩因子，常取成m0.5。如果F(XK)F(XH)，则用XK代替XH构成新单纯形XKXGXL。4. F(XR)F(XH) 即反射点比最差点还差，这时应压缩得更多一些，即将新点收缩在XHXC之间，取压缩点XKXCm(XC

44、XH)如果F(XK)F(XH)则用XK代替XH构成新单纯形XK XGXL。 5. F(X)F(XH) 即若XHXC方向上的所有点都比最差点差，则表明不能沿此方向搜索，这时应以XL为中心收缩，使顶点XH、XG向XL移近一半距离，得新单纯形XH XG XL，如图所示。第66页/共168页第六十七页，共169页。68ADM第四章 多维无约束优化从以上各步得到新的单纯形后，再重复(chngf)开始新一轮构造单纯形，逐渐缩小单纯形直至满足精度要求。第67页/共168页第六十八页，共169页。69ADM第四章 多维无约束优化计算步骤1. 构造初始单纯形。选初始点X0，从X0出发沿各坐标轴方向走步长h，得n

45、个顶点Xi（i1，2，n）与X0构成初始单纯形。这样可以保证此单纯形各棱是n个线性无关的向量，否则就会使搜索范围局限在某个较低维的空间内，有可能找不到极小点；2. 计算各顶点函数值。FiF(Xi)；3. 比较函数值的大小，确定(qudng)最好点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+1LLHFFFniHinXXnX011第68页/共16

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

47、(dit)XH，Fn+4代替(dit)FH，构成新单纯形，然后返回步骤3；否则接步骤8 ADM第四章 多维无约束优化)(22212nnHnnXFFXXXGnLFFF2)(1214nnnnXXmXX)(1213nnnnXXkXX第69页/共168页第七十页，共169页。71ADM第四章 多维无约束优化8. 收缩单纯形。最好点不动，其它点向最好点移近为原距离的一半 ，即 （i1，2，n）构成新单纯形，然后返回步骤2继续计算。习题分别用鲍威尔法、改进鲍威尔法、梯度法、阻尼牛顿法、 DFP变尺度法、单纯形法、共轭梯度法求解(qi ji)，迭代2次。TXxxxxxXF 1 , 1 ,242)(min)

48、1)0(2112221初始点TXxxXF2 , 2,25)(min)2)0(2221初始点)(21)(21LiLiLiiXXXXXXX第70页/共168页第七十一页，共169页。72坐标轮换法将n维问题转化为依次沿n个坐标方向轮回进行一维搜索。收敛速度较慢，适合n10的小型无约束优化问题，若目标函数具有“脊线”，算法将出现病态：沿两个坐标方向均不能使函数数 鲍威尔(Powell)法 属于模式搜索法。搜索方向不一定是共轭方向组，而是共轭程度越来越高的方向组（改进共轭方向），避免(bmin)原始鲍威尔法（共轭方向法）的方向组线性相关退化现象。对初始点没有特殊要求，具有超线性收敛速度。适合中小型无约

49、束优化问题。 单纯形法 对n维问题，构造由n+1线性独立的点为顶点的凸单纯形，找出具有最大值的顶点并构造目标函数的下降方向，求出最小值点，以该点取代单纯形的最大值的顶点，重新构造单纯形。适用于中小型无约束优化问题或目标函数没有数学表达式而只有其具体算法的情况。 ADM第四章 多维无约束优化第71页/共168页第七十二页，共169页。73最速下降法(梯度法) 搜索方向为目标函数负梯度方向。计算效率优于坐标轮换法。开始几步搜索下降快，但愈接近极值点下降愈慢。对初始点的选择要求不高，适合与其它方法结合使用（开始采用最速下降法，接近极值点时采用其它方法，如牛顿法）。 牛顿法（Newton-Raphso

50、n法） 用泰勒二次多项式近似原目标函数，以该二次多项式的极小点近似目标函数的极小点并逐渐逼近该极小点（搜索方向为牛顿方向，步长为1）。 要求目标函数连续，存在一、二阶偏导数，且海赛（Hessian）矩阵非奇异。初始点选择适当时，是收敛最快的算法；对初始点选择要求高。计算量大。 阻尼牛顿法（修正(xizhng)牛顿法或广义牛顿法） 搜索方向为牛顿方向，沿牛顿方向对步长做一维搜索优化。其它特点与牛顿法相同。 ADM第四章 多维无约束优化第72页/共168页第七十三页，共169页。74共轭梯度法 第一步搜索沿负梯度方向（最速下降方向），然后沿负梯度的共轭方向搜索。计算效率介于梯度法和牛顿法之间。对初

51、始点没有特殊要求。不需计算二阶偏导数矩阵及其逆矩阵，计算量与梯度法相当。适用于各种( zhn)规模的问题。 变尺度法（DFP法及BFGS法） 拟牛顿法，基于牛顿法的思想进行了重要改进。为公认的求解无约束优化问题的有效方法。适用于各种( zhn)规模的问题。DFP法有时存在数值稳定性不够理想的问题，BFGS法数值稳定性较好。 ADM第四章 多维无约束优化第73页/共168页第七十四页，共169页。75ADM第五章 多维有约束优化min(). .()0,1,2,.()0,1,2,.,jjF XstgXjmh Xjmmp分类1）直接法 直接利用迭代点和目标函数值构造搜索方向。网格法、分层降维枚举法。

52、2）间接法 需计算梯度构造搜索方向，将约束优化问题(wnt)转化为无约束优化问题(wnt)求解。罚函数法（内点、外点、混合） 。第74页/共168页第七十五页，共169页。76ADM第五章 多维有约束优化5.1 目标函数的约束极值问题目标函数的约束极值，又称为条件极值。与前面所讨论的无约束条件下函数的极值问题的区别(qbi)在于它是带有约束的条件下的函数极值问题。在约束条件下所求得的函数极值点，称为约束极值点。 对于带有约束条件的目标函数，其求最优解的过程可归结为，寻求一组设计变量,在满足约束方程的条件下，使目标函数值最小，这样求得的最优点X*，称为约束最优点。 两者重合 两者不重合 自然极值

53、点与约束最优点的相互关系第75页/共168页第七十六页，共169页。77 （a） （b）可行域形状对约束(yush)最优解的影响（a）可行域为凸集（b）可行域为非凸集ADM第五章 多维有约束优化第76页/共168页第七十七页，共169页。78ADM第五章 多维有约束优化 目标函数或约束函数的非凸性使约束极值点增多情况 Kuhn-Tucker最优胜条件简称为Kuhn-Tucker条件或K-T条件，可有效地用于对约束极值点存在条件的分析、检验。K-T条件如下：设X*为非线性规划(guhu)问题 pmmjhmjgtsFjjn, 2, 10)(, 2 , 10)(. .)(minXXEXX第77页/共

54、168页第七十八页，共169页。79ADM第五章 多维有约束优化的约束极值点，且在全部等式约束及不等式约束条件中共(zhn n)有q个约束条件为起作用约束，即 , (ij，i+j = 1,2,q p)。如果在X*处诸起作用约束的梯度向量 、 (i+j = 1,2,q p)线性无关，则存在向量使下述条件成立 ， 为非零、非负的乘子 为非零的乘子 ， 拉格朗日乘子向量 。满足Kuhn-Tucker条件的点，称为Kuhn-Tucker点。在一般的非线性规划问题中，Kuhn-Tucker点虽是约束极值点，但不定是全域最优点即K-T条件不是最优解的充分条件。但对于目标函数F(X)为凸函数、可行域D为凸集

55、的凸规划问题来说，Kuhn-Tucker条件不仅是确定约束极值点的必要条件同时也是全域最优解的充分条件。而且凸规划问题有唯一的Kuhn-Tucker点，但它所对应的拉格朗日乘子向量不一定是唯一的。 0)(*Xig0)(*XJh)(*Xig)(*XJh0)()()(1*qjijjiihgFXXXTq21qjiji, 2 , 1,ij第78页/共168页第七十九页，共169页。80ADM第五章 多维有约束优化 K-T条件的几何意义 Kuhn-Tucker条件条件表明(biomng)，若点X*是函数F(X)的极值点，要么, X*点位于可行域内；要么X*点位于某些约束的边界上，而在点X*，目标函数的负

56、梯度落在起作用约束梯度所成的夹角锥体之内。也就是说，目标函数的负梯度等于起作用约束梯度线性组合。 0)(*XF第79页/共168页第八十页，共169页。81ADM第五章 多维有约束优化例：用Kuhn-Tucker条件证明二维目标函数在不等式约束(yush)：的约束(yush)条件下，点为其约束(yush)极值点。2221)3()(xxfX0)(, 0)(, 04)(13222211xgxgxxgXXXT02*X (a)求证约束极值(j zh)点 (b)在约束极值(j zh)点处K-T条件不成立的情况 *X第80页/共168页第八十一页，共169页。82ADM第五章 多维有约束优化（1）由图可知

57、(k zh)，在点 处起作用的约束函数有 和 ；（2）求有关函数在点 的梯度*X)(1Xg)(2Xg*X022) 3(2)(21*xxf X1412)(1*1xgX10)(*2Xg（3）代入式(2-25)检验(jinyn)：000105 . 0145 . 002011402)()()(21*22*11*XXXggf第81页/共168页第八十二页，共169页。83ADM第五章 多维有约束优化即 ，故满足K-T条件，即点 确为约束极值点。而且由于(yuy)本题为凸规划，所以它也是全局最优点。5 . 021T02*X例：试分析约束(yush)最优化问题的约束(yush)最优解及其Kuhn-Tucke

58、r条件。0)(0)(0)1 ()(. .)(min231223111xXgxXgxxXgtsxXf图(b)给出了可行域，由图不难看出 是约束最优点，起作用(zuyng)约束函数有 和 。但由于T01*X)(1Xg)(3Xg01)(*Xf10)(*1Xg10)(*3Xg显然不可能找到 ,使Kuhn-Tucker条件031T第82页/共168页第八十三页，共169页。84ADM第五章 多维有约束优化0)()()(*33*11*XXXggf成立。这一矛盾产生的原因是由于即二者为线性相关而在Kuhn-Tucker点起作用约束的梯度(t d)向量应是线性无关的。)()(*3*1XXgg第83页/共168

59、页第八十四页，共169页。85ADM第五章 多维有约束优化5.2 网格法5.2.1 原理 1）在设计变量的界线区间内均匀地划分网格，计算节点上的目标函数值和约束函数值，舍去不满足约束条件的节点，比较满足约束条件的节点的目标函数值，找出目标函数值最小的节点； 2）以该最小值节点相邻的各节点为新的设计变量界线区间，细化网格，重复1），直至满足精度（收敛(shulin)）要求【网格分割间距 】ihmaxX*X(1)初始(ch sh)网格二次网格(wn )X(2)第84页/共168页第八十五页，共169页。86ADM第五章 多维有约束优化5.2.2 网格法的特点 1）不适合于等式约束； 2）对连续变量

60、和离散变量均适用； 3）总能搜索到解； 4）算法简单，计算量大，适合设计变量较少的情况。5.2.3 分层降维枚举法 改进的网格法，将设计变量分层处理，每一层有少量设计变量，前一层的设计变量的解作为常量进入下一层的求解过程，从而(cng r)减少网格节点数量，减少计算量。要求：优化模型必须能分层。第85页/共168页第八十六页，共169页。87ADM第五章 多维有约束优化5.3 罚函数法5.3.1 罚函数法的基本思路 1）拉格朗日乘子法 构造函数 的无约束极值(j zh)问题。,.,2 , 1, 0)(|)(minpjXhXDRDXXFjn0),(;),(min)()(),(11XRRXXXXL