《现代设计方法优化设计.pptx》由会员分享，可在线阅读，更多相关《现代设计方法优化设计.pptx（168页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1序论第一部分 优化设计 第一章 优化设计的数学基础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页2ADM目录 第五章 多维有约束优化5.1概述5.2网格法5.3罚函数法 第六章 优化设计建模 第七章 机械优化设计示例第2页/共168页3ADM目录第二部分 有限元引言第一章 弹性力学简介 1.1 求和约定 1.2 应力与应变 1.2.1 应力 1.2.2 应变 1.2.3 小变形弹性理论
2、基本方程 第二章 有限元理论基础 2.1 变分法原理 2.1.1 变分法第一定理 2.1.2 泛函极值的求解欧拉方程 2.1.3 求解变分问题的近似计算法李兹(Ritz)法 2.2 虚功原理（虚功方程）与能量泛函 2.3 插值及单元位移 2.4 弹性力学有限元的矩阵方程第3页/共168页4ADM目录第三章平面问题有限元3.1平面问题基本方程及有限元矩阵方程3.1.1基本方程3.1.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.
3、1单元的等效节点力3.5.2总体载荷向量第4页/共168页5ADM目录3.6刚度方程求解3.6.1边界条件处理3.7有限元分析的实施步骤3.8有限元计算收敛性第四章轴对称问题有限元4.1基本方程4.1.1平衡方程4.1.2几何方程4.1.3物理方程4.2三角形截面环单元4.3轴对称问题的有限元矩阵表达式4.3.1单元刚度矩阵4.3.2组装总体刚度矩阵4.3.3单元等效节点力第5页/共168页6ADM目录第五章等参数单元5.1平面等参元5.1.1坐标变换及位移5.1.2应变及应变矩阵5.1.3单元刚度矩阵5.1.4单元等效节点力5.1.5高斯积分5.1.6等参元的完备性和协调性5.2轴对称等参元
4、5.2.1坐标变换及位移5.2.2应变及应变矩阵5.2.3单元刚度矩阵5.2.4单元等效节点力5.3等参元的应力、应变计算第6页/共168页7第六章杆件系统第七章薄板弯曲问题第八章结构动力学问题8.1结构动力学微分方程8.2结构动力学虚功方程8.3结构动力学有限元矩阵方程8.4结构自由振动有限元矩阵方程模态分析ADM目录第7页/共168页8ADM序 论现代设计方法的基本内容：1.CAD2.CAE有限元分析*3.优化设计*4.可靠性设计5.逆向设计6.模块化设计7.设计专家系统8.价值工程9.虚拟设计10.第8页/共168页9如何评价设计质量?m-1s+1s设计参数可靠性：性能的波动在允许的设计
5、界限内稳健性（鲁棒性）：降低在设计点上的敏感性下限上限-1s+1s第9页/共168页10设计质量，个案研究-SONY电视机有统一的系统设计和公差，任何不合格品都不卖给消费者调查显示，美国消费者一向喜欢日本产的电视机Target下限下限上限上限频率SONY JapanSONY JapanSONY U.S.SONY U.S.u日产电视机性能在期望值附近作小幅波动（方差很小），统计上看，大量的产品性能稳定，更加趋向设计目标（TARGET）u美国产的电视机性能呈扁平分布,多数产品的质量是刚好落在界限内第10页/共168页11DesignSpaceFeasibleDesignSpace例：悬臂梁减重优化
6、确定性优化DesignVariables:10BeamHeight80mm10FlangeWidth50mmConstraint: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.4第11
7、页/共168页12确定性最优点：应力绝对最小点函数最小值几何安装角x应力f(x)(安装误差 D x)稳健设计D f2 D f1 Dx不稳健:易受不确定因素影响而造成性能的大幅波动Dx稳健最优设计点牺牲部分性能，更可靠、更稳健的设计不可靠:应力大于许用应力问题：已知安装角x存在不确定误差，在保证可靠性和稳健性前提下，求使应力f最小的x值最大允许应力危险区安全区概念：质量设计稳健性、可靠性优化第12页/共168页13ADM第一章优化设计的数学基础1.1矢量Vector定义：有大小和方向的量1.1.1二维矢量x2x1P(x1,x2)P(x1,x2)O1.1.2n维矢量第13页/共168页14ADM第
8、一章优化设计的数学基础1.2 矩阵1.2.1 定义 由一组数按一定次序排列成的具有m行n列的表第14页/共168页15ADM第一章优化设计的数学基础1.2.2逆矩阵Lattice若则B为A的逆矩阵逆矩阵的求法A*为A的伴随矩阵第15页/共168页16ADM第一章优化设计的数学基础1.2.3矩阵的正定与负定二次型对若A为正定；A为半正定；A为负定；A为半负定不定第16页/共168页17ADM第一章优化设计的数学基础矩阵正、负定的判定 对称矩阵A正定的充要条件：其行列式各阶主子式之值均大于0;对称矩阵A负定的充要条件：各阶主子式的值，应负、正交替地变化符号。1.3 多元函数1.3.1 梯度：函数增
9、加最快的方向第17页/共168页18ADM第一章优化设计的数学基础1.3.2多元函数的二阶偏导与海赛矩阵1.3.3函数的泰勒级数展开第18页/共168页19ADM第一章优化设计的数学基础1.3.4多元函数极值极值定义：在X0点的某邻域内，若X0为严格极大值点；X0为严格极小值点；极值存在的必要条件：梯度为0T向量极值存在的充分条件：H(X0)正定，F(X0)为极小值；H(X0)负定，F(X0)为极大值。第19页/共168页20ADM第二章优化设计的基本概念参数优化：优化结构的参数拓扑优化：优化拓扑结构1.设计变量设计过程中，其数值可以改变的能够描述结构特性的独立变量。传动比，尺寸。2.目标函数
10、目标函数是比较和选择各种不同设计方案的量化指标，是设计变量的函数。质量，成本，利润，速度。第20页/共168页21ADM第二章优化设计的基本概念3.约束条件对设计变量取值范围的约束。强度，刚度，固有频率。4.设计空间和可行域设计空间：由设计变量构成的n维实空间可行域：设计空间内，满足约束条件的子空间5.数学描述不等式约束等式约束变量取值范围约束第21页/共168页22ADM第二章优化设计的基本概念6.例X*X*F(X)等值线g1(X)g2(X)x1x2可行域第22页/共168页237.注意事项设计变量1）以主要影响因素作为设计变量；2）根据优化问题的特殊性选择设计变量；3）注意独立变量和相关变
11、量，尽量不包括相关变量；4）变量群转换，减少变量数目，如变量在目标函数中以x1x2形式存在，可令y=x1x2；5）必须的设计变量不能遗漏；6）冗余变量相关变量，齿轮设计变量为i,z,m,b，齿轮孔径为冗余变量。ADM第二章优化设计的基本概念第23页/共168页24ADM第二章优化设计的基本概念约束函数1）不能矛盾；2）可行域不能无界；3）避免多余约束；4）尽量给定设计变量取值上下界，缩小可行域；5）谨慎对待等式约束；6）近似约束不能用精确数学表达式描述的约束的处理；7）不能遗漏必要的约束，如压簧优化设计忽略了工作状态下，相邻圈间间隙值约束；8）全部设计变量必须包含在约束函数集中。第24页/共1
12、68页25ADM第二章优化设计的基本概念目标函数1）目标函数必须包含全部或部分设计变量；2）当必须采用多目标优化时，可选择其中一个主要的目标作单目标优化，其它目标按满足一定值要求的约束处理，优化后在选另一目标优化；3）近似目标函数借助实验数据处理建立目标函数；4）转移或替代目标函数，如以中心距作为减速器重量的替代目标函数；5）单体设计对象的多目标评价设计变量和约束条件不变，建立多个不同的目标函数并分别优化，得到一组优化方案，优中择优；6）目标函数的规一化minF(X)第25页/共168页26ADM第二章优化设计的基本概念8.优化问题求解方法搜索法9.收敛判据1）相邻两轮搜索得到的近似极值点“相
13、对距离”小于某一小的正数；2）F(X)可微，则梯度绝对值小于某一小的正数。第26页/共168页27ADM第三章一维优化解析法搜索法 直接法（区间缩减法）：黄金分割法、对分法 间接法（插值法）：二次插值、三次插值 一维优化在多维优化中作用确定最优步长第27页/共168页283.1 单峰函数3.1.1 单峰函数在给定区间内仅有一个极小值点的函数多峰与单峰的关系 多峰函数区间分割成数个单峰区间，按单峰函数求极值点单峰函数极值点求解 单值区间缩小，(x1+x2)/2为极值点ADM第三章一维优化第28页/共168页29ADM第三章一维优化3.1.2初始单值区间确定算法进退步法（探索步长加倍）单峰区间：x
14、2,x4x5,x3h 2h 4h4h2hh hx1x2x3x4x5x4x3x1x2第29页/共168页30ADM第三章一维优化一阶导数法（f(x)连续可微）以h,2h,4h.，h0为步长，若f(xk-2)0或f(xk-2)0,f(xk)=2则xk-2,xk或xkxk-2为单峰区间xk-2xk-1xkh2hf0第30页/共168页31ADM第三章一维优化3.2黄金分割法3.2.1区间缩小求解极值点的基本思路按一定规则在a,b内取两个点x1,x2ax1x2bax1x2bax1x2b (a)(b)(c)f(x1)f(x2)f(x1)=f(x2)a,b a,x2 a,b x1,b a,b a,x2 或
15、x1,b 第31页/共168页32ADM第三章一维优化3.2.2取点规则黄金分割法(0.618法，均匀缩短率对称取点)黄金分割：将一线段分割成两段，使得整段长度L与较长段x的比值等于较长段x与较短段L-x的比值Lax1x2b第32页/共168页33ADM第三章一维优化3.2.3区间收缩参见3.21第33页/共168页34ADM第三章一维优化3.2.4收敛判据常用判据1）2）3）4）判据的使用1)、3)或2)、4)组合使用，并从a,b,(a+b)/2中选最优者abab第34页/共168页35ADM第三章一维优化3.3 对分法3.3.1 中心对分法（可微）比较的符号，将区间a,b缩短一半。3.3.
16、2 两点对分法（可不可微）a(a+b)/2bax1x2bf1f2(a+b)/2第35页/共168页36ADM第三章一维优化3.4二次插值法二次插值：二次多项式逼近3.4.1方法原理二次多项式逼近目标函数，以二次多项式的极小值点作为目标函数的近似最优点。3.4.2二次多项式构造单峰区间x1,x3内存在极小值点，在x1,x3内取点x2，则过x1,x2,x3构造其极小值点为x*x1x2x*x*x3f(x)p(x)第36页/共168页37ADM第三章一维优化3.4.3区间缩小原理比较f(x*)和f(x2)，以其中较小者对应的点为新的x2点，新x2左右相邻的点分别为新x1，新x3。3.4.4收敛判据见黄
17、金分割法习题初始区间a,b=-0.5,1.5，绝对精度分别用解析法、黄金分割法、中心对分法、两点对分法求解。第37页/共168页38ADM第四章多维无约束优化分类：1）直接法（不需计算导数）2）间接法（需计算导数）4.1 坐标轮换法（坐标方向为搜索方向）4.1.1 原理 将n维问题转化为依次沿n个坐标方向轮回进行一维搜索。第38页/共168页39ADM第四章多维无约束优化第39页/共168页40ADM第四章多维无约束优化4.1.2算法1）任选初始点设定初始步长置搜索方向2）以为初始点，沿方向作试探，步长计算，若说明试探成功；否则，若，置，若，第40页/共168页41ADM第四章多维无约束优化
18、则作一维搜索求最优步长和优化点若沿坐标轴正负方向试探均失败，则迭代点不变3）以为起点，按1）沿方向搜索，得沿n个坐标方向进行完一轮一维搜索后，得4）以作第二轮得起始点，重复2）、3）得第二轮搜索终点。5）如果从某轮起始点出发，依次沿n个坐标轴的正负方向试探均失败，则缩短试探步长（如减半），返回2）。当探索步长足够小，满足收敛判据时，终止迭代，所得点即为优化结果X*。第41页/共168页42ADM第四章多维无约束优化4.1.3讨论1）计算量小，程序简单，计算效率低，适合变量n10的情况。2）若目标函数具有脊线，算法将出现病态：沿两个坐标方向均不能使函数数值下降，误认为最优点。脊线第42页/共16
19、8页43ADM第四章多维无约束优化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）共轭方向与函数的极小值点关系 考察正定二次函数 其等值线为同心椭圆族第43页/共168页44ADM第四章多维无约束优化S2S1S1X1X2X1(0)X2(0)x1x2从X1(0)出发沿S1方向作一维搜索，得最优点X1（与椭圆相切）；从X2(0)出发沿S1方向作一维搜索，得最优点X2；连接X1
20、、X2得矢量S2，S2过椭圆族中心，即目标函数极小值点X*，且S1、S2对A正交，沿S1的共轭方向S2可搜索到正定二元二次函数极值点。X*第44页/共168页45ADM第四章多维无约束优化4.2.2原始鲍威尔法S1、S2、S3为共、轭方向（参见前页）搜索方向: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轮第45页/共168页46ADM第四章多维无约束优化原始鲍威尔法的严重缺陷：当某一轮方向组中的矢量系出现线性相关时（特别是接近X*时）
21、，会出现退化，无法获得极小值点。4.2.3改进鲍威尔法与原始鲍威尔法的区别：每构造一个新方向，根据判别条件决定是否替换原来的某个方向。构造k+1轮方向组时，是否淘汰前一轮的某一个方向Sm(k)，根据下面二个条件判断：第k轮初始点函数值；第k轮最后一个方向搜索终点函数值；X0(k)对Xn(k)映射点Xn1(k)的函数值；一维搜索中函数值下降最大者，其方向为Sm(k)第46页/共168页47ADM第四章多维无约束优化条件式a)、b)同时或两者之一成立：第k+1轮仍沿用第k轮的方向组，取Xn(k)（F2F3）或映射点Xn1(k)（F3F(X(k)。不是严格的下降算法。原因：X(k+1)是近似二次式在
22、牛顿方向上的极小点，而非F(X)在牛顿方向上的极小点。2）对牛顿法的修正阻尼牛顿法修正方法：在牛顿方向上作一维搜索求最优步长。当F(X)的海赛矩阵Hk在迭代点处正定情况下，阻尼牛顿法可以保证每次迭代，迭代点的函数值都下降；Hk在迭代点处不定情况下，函数值不会上升，但不一定下降；Hk在迭代点处奇异情况下，不能求逆，无法构造牛顿方向；要求F(X)二阶可微，需计算梯度、海赛矩阵及其逆矩阵，计算量大。4.4.3收敛判据同梯度法。第51页/共168页52ADM第四章多维无约束优化第52页/共168页53ADM第四章多维无约束优化4.5 DFP变尺度法拟牛顿法，基于牛顿法的思想进行了重要改进。4.5.1
23、基本思想 综合梯度法和牛顿法的优有点，克服梯度法收敛速度慢和牛顿法收敛快但稳定性差且计算量大的缺点。比较梯度法和牛顿法，第53页/共168页54ADM第四章多维无约束优化 Ak为nn对称矩阵，Ak为单位矩阵时，上式为梯度法；AkHk-1时，上式为阻尼牛顿法。拟牛顿法的基本思想：用某种方法，人为构造一n阶对称矩阵 AkA(X(k)，近似替代牛顿法的Hk-1。通过迭代不断修正Ak，使Ak Hk-1。由于是不断变化的，它使搜索方向不断向牛顿方向逼近，故可把看作是变化的尺度矩阵，这就是变尺度法叫法的由来。梯度法和牛顿法也属于变尺度法的范畴。Ak应满足的条件：1.正定 保证迭代过程中函数值始终下降，要求
24、S(k)与gk夹角为锐角，即第54页/共168页552.拟牛顿条件使AkHk-1，Ak1可以由第k步的信息递推构造由得即ADM第四章多维无约束优化第55页/共168页56ADM第四章多维无约束优化4.5.2Ak序列的生成（DFP递推公式）第56页/共168页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*)，结束。第57页/共168页58ADM第四章多维无约束优化4.6共轭
25、梯度法将梯度法和共轭方向法结合起来，每一轮搜索的第一步沿负梯度方向搜索，后续各步沿上一步的共轭方向搜索，具有二次收敛速度，每一轮搜索n步。第一步的搜索方向负梯度方向以后各步的搜索方向共轭方向的确定应使n维实空间中的两个非0向量S(k)和S(k1)关于矩阵A共轭，即应使对于正定二次函数有第58页/共168页59ADM第四章多维无约束优化二式相减而则可得即因 为一正交系，故有则第59页/共168页60ADM第四章多维无约束优化第60页/共168页61ADM第四章多维无约束优化算法l任选初始点X(0)，给定收敛精度和维数n；2令，求迭代初始点X(0)的梯度g0取第一次搜索的方向S(0)为初始点的负梯
26、度3进行一维搜索，求最优步长(k)并求出新点 4计算X(k+1)点的梯度5收敛检查。满足条件则，计算结束；否则继续下一步；6判断k+1是否等于n，若k+1n，则令X(0)=X(k+1)转步骤2；若k+1n，则继续下一步；7计算 第61页/共168页62ADM第四章多维无约束优化8确定下一步的搜索方向令 ，返回步骤3。讨论共轭梯度法具有超线性收敛速度（1收敛速度阶数2）。计算效率高于梯度法，低于牛顿法，但对初始点没有特殊要求。不需计算二阶偏导数矩阵及其逆矩阵，计算量与梯度法相当，小于牛顿法。适用于各种规模的问题。第62页/共168页63ADM第四章多维无约束优化4.7 单纯形法原理函数的导数是函
27、数性态的反映，它对选择搜索方向提供了有用的信息。在不计算导数的情况下，先算出若干点处的函数值，从它们之间的大小关系中也可以看出函数变化的大概趋势，为寻求函数的下降方向提供依据。这里所说的若干点，一般取在单纯形的顶点上。所谓单纯形是指在n维空间中具有n+1个顶点的简单图形或凸多面体。利用单纯形的顶点，计算其函数值并加以比较，从中确定有利的搜索方向和步长，找出具有最大值的顶点并构造目标函数的下降方向，求出最小值点，以该点取代单纯形的最大值的顶点，重新构造单纯形。随着这种取代过程的不断进行，新的单纯形不断向极小点收缩。这样经过若干次迭代，即可得到满足精度要求的近似解。这就是单纯形法的基本思想。第63
28、页/共168页64ADM第四章多维无约束优化第64页/共168页65ADM第四章多维无约束优化算法选择新的比较好的点替代最差点的算法有4种：反射、扩张、压缩和收缩。现以二元函数F(X)=F(x1,x2)为例，说明单纯形法的算法。在x1-x2平面上取不在同一直线上的三点XH、XG、XL，以它们为顶点组成一单纯形（即三角形）XHXGXL。计算各顶点函数值，设F(XH)F(XG)F(XL)说明XL点最好，XH点最差。为了寻找极小点，一般说来，应向最差点的反对称方向进行搜索，即通过XH并穿过XGXL的中点XC的方向进行搜索。在此方向上取作XH点相对于XC点的反射点XRXRXC(XCXH)2XCXH计算
29、反射点的函数值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。第65页/共168页66ADM第四章多维无约束优化2.F(XL)F(XR)F(XG)即反射点比最好点差，但比次差点好，说明反射可行，则以反射点代替最差点，仍构成新单纯形XRXGXL。3.F(XG)F(XR)F(XH)即反射点比次差点
30、差，但比最差点好，说明XR走得太远，应缩回一些，即压缩。这时取压缩点XKXCm(XRXC)m收缩因子，常取成m0.5。如果F(XK)F(XH)，则用XK代替XH构成新单纯形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，如图所示。第66页/共168页67ADM第四章多维无
31、约束优化从以上各步得到新的单纯形后，再重复开始新一轮构造单纯形，逐渐缩小单纯形直至满足精度要求。第67页/共168页68ADM第四章多维无约束优化计算步骤1.构造初始单纯形。选初始点X0，从X0出发沿各坐标轴方向走步长h，得n个顶点Xi（i1，2，n）与X0构成初始单纯形。这样可以保证此单纯形各棱是n个线性无关的向量，否则就会使搜索范围局限在某个较低维的空间内，有可能找不到极小点；2.计算各顶点函数值。FiF(Xi)；3.比较函数值的大小，确定最好点XL，最差点XH和次差点XG。FLF(XL)minF(Xi)（i1，2，n）FHF(XH)maxF(Xi)（i1，2，n）FGF(XG)maxF(
32、Xi)（i1，2，n；iH）4.检验是否满足精度要求满足要求，则X*XL，计算结束。否则，继续步骤5；5.计算除XH点之外各点的“重心”Xn+1第68页/共168页69和反射点当时，以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代替Xn+2，计算
33、其函数值Fn+4。若Fn+4 F H，则以Xn+4代替XH，Fn+4代替FH，构成新单纯形，然后返回步骤3；否则接步骤8ADM第四章多维无约束优化第69页/共168页70ADM第四章多维无约束优化8.收缩单纯形。最好点不动，其它点向最好点移近为原距离的一半，即 （i1，2，n）构成新单纯形，然后返回步骤2继续计算。习题分别用鲍威尔法、改进鲍威尔法、梯度法、阻尼牛顿法、DFP变尺度法、单纯形法、共轭梯度法求解，迭代2次。第70页/共168页71坐标轮换法将n维问题转化为依次沿n个坐标方向轮回进行一维搜索。收敛速度较慢，适合n10的小型无约束优化问题，若目标函数具有“脊线”，算法将出现病态：沿两个
34、坐标方向均不能使函数数 鲍威尔(Powell)法属于模式搜索法。搜索方向不一定是共轭方向组，而是共轭程度越来越高的方向组（改进共轭方向），避免原始鲍威尔法（共轭方向法）的方向组线性相关退化现象。对初始点没有特殊要求，具有超线性收敛速度。适合中小型无约束优化问题。单纯形法对n维问题，构造由n+1线性独立的点为顶点的凸单纯形，找出具有最大值的顶点并构造目标函数的下降方向，求出最小值点，以该点取代单纯形的最大值的顶点，重新构造单纯形。适用于中小型无约束优化问题或目标函数没有数学表达式而只有其具体算法的情况。ADM第四章多维无约束优化第71页/共168页72最速下降法(梯度法)搜索方向为目标函数负梯度
35、方向。计算效率优于坐标轮换法。开始几步搜索下降快，但愈接近极值点下降愈慢。对初始点的选择要求不高，适合与其它方法结合使用（开始采用最速下降法，接近极值点时采用其它方法，如牛顿法）。牛顿法（Newton-Raphson法）用泰勒二次多项式近似原目标函数，以该二次多项式的极小点近似目标函数的极小点并逐渐逼近该极小点（搜索方向为牛顿方向，步长为1）。要求目标函数连续，存在一、二阶偏导数，且海赛（Hessian）矩阵非奇异。初始点选择适当时，是收敛最快的算法；对初始点选择要求高。计算量大。阻尼牛顿法（修正牛顿法或广义牛顿法）搜索方向为牛顿方向，沿牛顿方向对步长做一维搜索优化。其它特点与牛顿法相同。AD
36、M第四章多维无约束优化第72页/共168页73共轭梯度法第一步搜索沿负梯度方向（最速下降方向），然后沿负梯度的共轭方向搜索。计算效率介于梯度法和牛顿法之间。对初始点没有特殊要求。不需计算二阶偏导数矩阵及其逆矩阵，计算量与梯度法相当。适用于各种规模的问题。变尺度法（DFP法及BFGS法）拟牛顿法，基于牛顿法的思想进行了重要改进。为公认的求解无约束优化问题的有效方法。适用于各种规模的问题。DFP法有时存在数值稳定性不够理想的问题，BFGS法数值稳定性较好。ADM第四章多维无约束优化第73页/共168页74ADM第五章多维有约束优化分类1）直接法直接利用迭代点和目标函数值构造搜索方向。网格法、分层降
37、维枚举法。2）间接法需计算梯度构造搜索方向，将约束优化问题转化为无约束优化问题求解。罚函数法（内点、外点、混合）。第74页/共168页75ADM第五章多维有约束优化5.1目标函数的约束极值问题目标函数的约束极值，又称为条件极值。与前面所讨论的无约束条件下函数的极值问题的区别在于它是带有约束的条件下的函数极值问题。在约束条件下所求得的函数极值点，称为约束极值点。对于带有约束条件的目标函数，其求最优解的过程可归结为，寻求一组设计变量,在满足约束方程的条件下，使目标函数值最小，这样求得的最优点X*，称为约束最优点。两者重合 两者不重合自然极值点与约束最优点的相互关系第75页/共168页76（a）（b
38、）可行域形状对约束最优解的影响（a）可行域为凸集（b）可行域为非凸集ADM第五章多维有约束优化第76页/共168页77ADM第五章多维有约束优化目标函数或约束函数的非凸性使约束极值点增多情况Kuhn-Tucker最优胜条件简称为Kuhn-Tucker条件或K-T条件，可有效地用于对约束极值点存在条件的分析、检验。K-T条件如下：设X*为非线性规划问题第77页/共168页78ADM第五章多维有约束优化的约束极值点，且在全部等式约束及不等式约束条件中共有q个约束条件为起作用约束，即,(ij，i+j=1,2,q p)。如果在X*处诸起作用约束的梯度向量、(i+j=1,2,q p)线性无关，则存在向量
39、使下述条件成立，为非零、非负的乘子 为非零的乘子，拉格朗日乘子向量。满足Kuhn-Tucker条件的点，称为Kuhn-Tucker点。在一般的非线性规划问题中，Kuhn-Tucker点虽是约束极值点，但不定是全域最优点即K-T条件不是最优解的充分条件。但对于目标函数F(X)为凸函数、可行域D为凸集的凸规划问题来说，Kuhn-Tucker条件不仅是确定约束极值点的必要条件同时也是全域最优解的充分条件。而且凸规划问题有唯一的Kuhn-Tucker点，但它所对应的拉格朗日乘子向量不一定是唯一的。第78页/共168页79ADM第五章多维有约束优化K-T条件的几何意义Kuhn-Tucker条件条件表明，
40、若点X*是函数F(X)的极值点，要么,X*点位于可行域内；要么X*点位于某些约束的边界上，而在点X*，目标函数的负梯度落在起作用约束梯度所成的夹角锥体之内。也就是说，目标函数的负梯度等于起作用约束梯度线性组合。第79页/共168页80ADM第五章多维有约束优化例：用Kuhn-Tucker条件证明二维目标函数在不等式约束：的约束条件下，点为其约束极值点。(a)求证约束极值点(b)在约束极值点处K-T条件不成立的情况第80页/共168页81ADM第五章多维有约束优化（1）由图可知，在点处起作用的约束函数有和；（2）求有关函数在点的梯度（3）代入式(2-25)检验：第81页/共168页82ADM第五
41、章多维有约束优化即，故满足K-T条件，即点确为约束极值点。而且由于本题为凸规划，所以它也是全局最优点。例：试分析约束最优化问题的约束最优解及其Kuhn-Tucker条件。图(b)给出了可行域，由图不难看出是约束最优点，起作用约束函数有和。但由于显然不可能找到,使Kuhn-Tucker条件第82页/共168页83ADM第五章多维有约束优化成立。这一矛盾产生的原因是由于即二者为线性相关而在Kuhn-Tucker点起作用约束的梯度向量应是线性无关的。第83页/共168页84ADM第五章多维有约束优化5.2网格法5.2.1原理1）在设计变量的界线区间内均匀地划分网格，计算节点上的目标函数值和约束函数值
42、，舍去不满足约束条件的节点，比较满足约束条件的节点的目标函数值，找出目标函数值最小的节点；2）以该最小值节点相邻的各节点为新的设计变量界线区间，细化网格，重复1），直至满足精度（收敛）要求【网格分割间距】X*X(1)初始网格二次网格X(2)第84页/共168页85ADM第五章多维有约束优化5.2.2网格法的特点1）不适合于等式约束；2）对连续变量和离散变量均适用；3）总能搜索到解；4）算法简单，计算量大，适合设计变量较少的情况。5.2.3分层降维枚举法改进的网格法，将设计变量分层处理，每一层有少量设计变量，前一层的设计变量的解作为常量进入下一层的求解过程，从而减少网格节点数量，减少计算量。要求
43、：优化模型必须能分层。第85页/共168页86ADM第五章多维有约束优化5.3罚函数法5.3.1罚函数法的基本思路1）拉格朗日乘子法构造函数的无约束极值问题。第86页/共168页87ADM第五章多维有约束优化2）罚函数法借鉴拉各朗日乘子法，将约束优化转化为序列无约束极小化问题：第87页/共168页883）罚函数求解过程（序列无约束极小化方法SUMT法）a.定义G和E的形式，选择r(k)、M(k)的递推序列及初始点X(0);b.从r(0)、M(0)开始，以X(0)为初始点求P(0)的无约束优化点X*(0)，随后以递推方式，以r(k)、M(k)和初始点X*(k-1)求P(k)的无约束优化点X*(k
44、)，得优化点序列X*(k);c.优化点序列X*(k)不断逼近最优解，满足收敛准则，X*(k)即为有约束优化得最优解。4）罚函数法分类内点法：在可行域内迭代，逼近最优解，适合于不等式约束；外点法：在可行域外迭代，逼近最优解，适合于不等式约束和等式约束；混合法：适合于不等式约束和等式约束。ADM第五章多维有约束优化第88页/共168页89ADM第五章多维有约束优化5.3.2内点法1.例构造泛函：罚函数极值：第89页/共168页90ADM第五章多维有约束优化迭代序号r(k)=cr(k1)c=0.1x*(k)f(x*(k)P(x,r(k)P(x*(k),r(k)r(k)Gg(x*(k)Gg(x*(k)
45、00.251.7070.85351.20711.414410.0251.2240.61180.72364.472320.00251.07070.53540.570814.14430.000251.02240.51120.522444.64340.0000251.00710.50350.5070140.84550.00000251.00220.50110.5022454.545第90页/共168页91f,P7654321ADM第五章多维有约束优化0123456789xx-1=0f(x)=x/2r(k)=1r(k)=0.25r(k)=0.0025x*210r(3)r(2)r(1)r(0)r(k)r
46、(k)递减时x*(k)逼近x*f和P的曲线第91页/共168页92ADM第五章多维有约束优化2.内点法泛函与罚函数构造1）是可行域D上的连续函数（采用需要梯度的优化方法时，需可导）；2）当X在可行域D内远离约束边界时，具有相当小的正值；X靠近约束边界，具有很大的正值（趋向无穷大）；第92页/共168页93ADM第五章多维有约束优化3）X的取值只能在可行域内，否则泛函G将不满足不为负值的要求；4）罚因子r(k)的作用：F(X)的有约束极值点可能在可行域靠近边界处或就在边界上，此时尽管泛函G的数值很大，但罚因子是不断递减的正值，经多次迭代，X*(k)向X*接近时，惩罚项r(k)G是很小的的正值（趋
47、向0），可以保证罚函数P(X)的无约束极值点序列收敛于F(X)约束极值点。3.算法1）在可行域内任选一严格初始内点X(0)，最好不要靠近约束边界；2）选一适当大的初始罚因子r(0)，求罚函数P(X,r(0)的无约束极值点X*(0)，选一罚因子递减率0c1罚因子为递减，递减率0c，令M(k+1)；（5）转步骤（2）。第115页/共168页1162 不等式约束问题不等式约束的增广拉格朗日函数的极小点求解的拉格朗日乘子的迭代式为 其它算法和计算步骤与等式约束的增广拉格朗日函数的极小点求解类似。3一般约束问题包括等式和不等式约束的增广拉格朗日函数的极小点求解的拉格朗日乘子的迭代式为其它算法和计算步骤与
48、等式约束的增广拉格朗日函数的极小点求解类似。ADM第五章多维有约束优化第116页/共168页117ADM第五章多维有约束优化5.3.5约束极值存在的必要条件和充分条件1.必要条件（Kuhn-Tucker，K-T条件）对约束极值（优化）问题：若X*是上述问题的一个极小点，且则存在乘子K-T条件第117页/共168页118ADM第五章多维有约束优化2.充分条件若X*是可行域内一点，若存在K-T条件成立，且对任何满足下式的向量V的均有则X*为约束优化问题的一个严格局部极小点。第118页/共168页119ADM第五章多维有约束优化5.5随机方向法一、原理随机方向法是一种直接解法。它的基本思路是在可行域
49、内选择一个初始点X(0)，利用随机数的概率特性，产生若干个随机方向，以适当步长，沿随机方向探索，从中选择一个能使目标函数值下降最快的随机方向作为可行搜索方向，记作S(0)。从初始点X(0)出发，沿S(0)方向以适当步长进行搜索，直至函数值不再下降且满足约束条件，得到新点X(1)。至此完成一次迭代。然后，将起始点移至X(1)。重复以上过程，得到序列，经过若干次迭代计算后，最终取得约束最优解。随机方向法的迭代公式为且X(k+1)应满足第119页/共168页120ADM第五章多维有约束优化随机方向法原理图第120页/共168页121ADM第五章多维有约束优化二、算法1随机数的产生首先令，取r2657
50、863（r为小于r1正奇数）,然后按以下步骤计算令若；若：若q即为(0，1)区间内的伪随机数。利用q，可求得任意区间(a，b)内的伪随机数x，第121页/共168页122ADM第五章多维有约束优化2初始点的选择随机方向法的初始点X(0)必须是一个可行点，即满足全部不等式约束条件的点。当约束条件较为复杂，用人工不易选择可行初始点时，可用随机选择的方法来产生。其计算步骤如下：l）给定设计变量的下限值和上限值，即2）在区间(0，l)内产生n个伪随机数qi（i1,2,n）3）计算随机点X的各分量4）判别随机点X是否可行，若随机点X为可行点，则取初始点；若随机点X为非可行点，则转步骤3)重新计算，直到产