现代设计方法优化设计

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,现代设计方法,优化设计、有限元,Advanced Design Methods,Design Optimization and Finite Element Method,1,序论,第一部分 优化设计,第一章 优化设计的数学基础,1.1 矢量,1.2,矩阵,1.3 多元函数,第二章 优化设计的基本概念,第三章 一维优化,3.1 单峰函数,3.2,黄金分割法,3.3 对分法,4.4 二次插值法,第四章 多维无约束优化,4.1 直接法,4.2,鲍威尔法,4.3 梯度法（最速下降法）,4.4 牛顿法,目 录,ADM,2,ADM,目 录,第五章 多维有约束优化,5.1 概述,5.2,网格法,5.3 罚函数法,第六章 优化设计建模,第七章 机械优化设计示例,3,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 插值及单元位移,2.4 弹性力学有限元的矩阵方程,4,ADM,目 录,第三章 平面问题有限元,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.1 单元的等效节点力,3.5.2 总体载荷向量,5,ADM,目 录,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 单元等效节点力,6,ADM,目 录,第五章 等参数单元,5.1 平面等参元,5.1.1 坐标变换及位移,5.1.2 应变及应变矩阵,5.1.3 单元刚度矩阵,5.1.4 单元等效节点力,5.1.5 高斯积分,5.1.6 等参元的完备性和协调性,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,目 录,8,ADM,序 论,现代设计方法的基本内容：,CAD,CAE,有限元分析*,优化设计*,可靠性设计,逆向设计,模块化设计,设计专家系统,价值工程,虚拟设计,9,如何评价设计质量?,m,-1,s,+1,s,设计参数,可靠性：性能的波动在允许的设计界限内,稳健性（鲁棒性）：降低在设计点上的敏感性,下限,上限,-1,s,+1,s,10,设计质量， 个案研究 - SONY,电视机有统一的系统设计和公差，任何不合格品都不卖给消费者,调查显示，美国消费者一向喜欢日本产的电视机,Target,下限,上限,频率,SONY Japan,SONY U.S.,日产电视机性能在期望值附近作小幅波动（方差很小），统计上看，大量的产品性能稳定，更加趋向设计目标（,TARGET ）,美国产的电视机性能呈扁平分布,多数,产品的质量是刚好落在界限内,11,Design,Space,Feasible,Design,Space,例：悬臂梁减重优化确定性优化,Design Variables:,10,Beam Height,80 mm,10,Flange Width,50 mm,Constraint:,Stress,16 MPa,Objective:,Minimize Mass,(minimize area),10,80,10,50,20,30,40,50,60,70,20,30,40,Beam Height, mm,Flange Width, mm,Stress,= 16,Loads at,free end,Flange,Width,Beam,Height,Area = 400,Area = 300,Solution,:,Beam Height= 38.4,Flange Width= 22.7,Stress= 16,Area=,233.4,12,确定性最优点：,应力绝对最小点,函数最小值,几何安装角,x,应力,f(x),(,安装误差,D,x),稳健设计,D,f2,D,f1,D,x,不稳健,:,易受不确定因素影响而造成性能的大幅波动,D,x,稳健最优设计点,牺牲部分性能，,更可靠、更稳健的设计,不可靠,:,应力大于许用应力,问题：已知安装角,x,存在不确定误差，在保证可靠性和稳健性前提下，求使应力,f,最小的,x,值,最大允许应力,危险区,安全区,概念：质量设计,稳健性、可靠性优化,13,ADM,第一章 优化设计的数学基础,1.1 矢量,Vector,定义：有大小和方向的量,1.1.1,二维矢量,x,2,x,1,P(x,1,x,2,),P(x,1,x,2,),O,1.1.,2,n,维矢量,14,ADM,第一章 优化设计的数学基础,1.2 矩阵,1.2.1,定义,由一组数按一定次序排列成的具有,m,行,n,列的表,15,ADM,第一章 优化设计的数学基础,1.2.2 逆矩阵,Lattice,若,则,B,为,A,的逆矩阵,逆矩阵的求法,A*,为,A,的伴随矩阵,16,ADM,第一章 优化设计的数学基础,1.2.3 矩阵的正定与负定,二次型,对,若,A,为正定；,A,为半正定；,A,为负定；,A,为半负定,不定,17,ADM,第一章 优化设计的数学基础,矩阵正、负定的判定,对称矩阵,A,正定的充要条件：其行列式各阶主子式之值均大于0;,对称矩阵,A,负定的充要条件：,各阶主子式的值，应负、正交替地变化符号,。,1.3 多元函数,1.3.1,梯度：函数增加最快的方向,18,ADM,第一章 优化设计的数学基础,1.3.2 多元函数的二阶偏导与海赛矩阵,1.3.3 函数的泰勒级数展开,19,ADM,第一章 优化设计的数学基础,1.3.4 多元函数极值,极值定义：在,X,0,点的某邻域 内，若,X,0,为严格极大值点；,X,0,为严格极小值点；,极值存在的必要条件：梯度为0,T,向量,极值存在的充分条件：,H(X,0,),正定，,F(X,0,),为极小值；,H(X,0,),负定，,F(X,0,),为极大值。,20,ADM,第二章 优化设计的基本概念,参数优化：优化结构的参数,拓扑优化：优化拓扑结构,1. 设计变量,设计过程中，其数值可以改变的能够描述结构特性的独立变量。传动比，尺寸。,2. 目标函数,目标函数是比较和选择各种不同设计方案的量化指标，是设计变量的函数。质量，成本，利润，速度。,21,ADM,第二章 优化设计的基本概念,3. 约束条件,对设计变量取值范围的约束。强度，刚度，固有频率。,4. 设计空间和可行域,设计空间：由设计变量构成的,n,维实空间,可行域：设计空间内，满足约束条件的子空间,5. 数学描述,不等式约束,等式约束,变量取值范围约束,22,ADM,第二章 优化设计的基本概念,6. 例,X*,X*,F(X),等值线,g,1,(X),g,2,(X),x,1,x,2,可行域,23,7. 注意事项,设计变量,1）以主要影响因素作为设计变量；,2）根据优化问题的特殊性选择设计变量；,3）注意独立变量和相关变量，尽量不包括相关变量；,4）变量群转换，减少变量数目，如变量在目标函数中以,x,1,x,2,形式存,在，可令,y= x,1,x,2,；,5）必须的设计变量不能遗漏；,6）冗余变量相关变量，齿轮设计变量为,i,z,m,b,，,齿轮孔径为冗,余变量。,ADM,第二章 优化设计的基本概念,24,ADM,第二章 优化设计的基本概念,约束函数,1）不能矛盾；,2）可行域不能无界；,3）避免多余约束；,4） 尽量给定设计变量取值上下界，缩小可行域；,5）谨慎对待等式约束；,6）近似约束不能用精确数学表达式描述的约束的处理；,7）不能遗漏必要的约束，如压簧优化设计忽略了工作状态下，相邻,圈间间隙值约束；,8）全部设计变量必须包含在约束函数集中。,25,ADM,第二章 优化设计的基本概念,目标函数,1）目标函数必须包含全部或部分设计变量；,2）当必须采用多目标优化时，可选择其中一个主要的目标作单目标,优化，其它目标按满足一定值要求的约束处理，优化后在选另一,目标优化；,3）近似目标函数借助实验数据处理建立目标函数；,4）转移或替代目标函数，如以中心距作为减速器重量的替代目标函,数；,5）单体设计对象的多目标评价设计变量和约束条件不变，建立,多个不同的目标函数并分别优化，得到一组优化方案，优中择优；,6）目标函数的规一化,minF(X,),26,ADM,第二章 优化设计的基本概念,8. 优化问题求解方法,搜索法,9. 收敛判据,1）,相邻两轮搜索得到的近似极值点“相对距离”小于某一小的正数；,2）,F(X),可微，则梯度绝对值小于某一小的正数。,27,ADM,第三章 一维优化,解析法,搜索法,直接法（区间缩减法）：黄金分割法、对分法,间接法（插值法）：二次插值、三次插值,一维优化在多维优化中作用确定最优步长,28,3.1 单峰函数,3.1.1 单峰函数,在给定区间内仅有一个极小值点的函数,多峰与单峰的关系,多峰函数区间分割成数个单峰区间，按单峰函数求极值点,单峰函数极值点求解,单值区间缩小，,(,x,1,+x,2,)/2,为极值点,ADM,第三章 一维优化,29,ADM,第三章 一维优化,3.1.2 初始单值区间确定算法,进退步法（探索步长加倍）,单峰区间：,x,2, x,4, ,x,5, x3,h,2,h,4,h,4,h,2,h,h h,x,1,x,2,x,3,x,4,x,5,x,4,x,3,x,1,x,2,30,ADM,第三章 一维优化,一阶导数法（,f(x,),连续可微）,以,h,2h,4h.，h0,为步长，,若,f(x,k-2,)0,或,f(x,k-2,)0,f(x,k,)=2,则,x,k-2,x,k,或,x,k,x,k-2,为单峰区间,x,k-2,x,k-1,x,k,h 2h,f0,31,ADM,第三章 一维优化,3.2 黄金分割法,3.2.1 区间缩小求解极值点的基本思路,按一定规则在,a,b,内取两个点,x,1,x,2,a x,1,x,2,b a x,1,x,2,b a x,1,x,2,b,(a) (b) (c),f(x,1,)f(x,2,) f(x,1,)=f(x,2,),a,b a,x,2, a,b x,1,b a,b a,x,2,或,x,1,b,32,ADM,第三章 一维优化,3.2.2 取点规则黄金分割法(0.618法，均匀缩短率对称取点),黄金分割：将一线段分割成两段，使得整段长度,L,与较长段,x,的比值等于较长段,x,与较短段,L-x,的比值,L,a x,1,x,2,b,33,ADM,第三章 一维优化,3.2.3 区间收缩,参见,3.2 1,34,ADM,第三章 一维优化,3.2.4 收敛判据,常用判据,1）,2）,3）,4）,判据的使用,1)、3)或2)、4)组合使用，并从,a, b, (a+b)/2,中选最优者,a b a b,35,ADM,第三章 一维优化,3.3 对分法,3.3.1 中心对分法（可微,）,比较,的符号，将区间,a,b,缩短一半。,3.3.2 两点对分法（可不可微,）,a (a+b)/2 b,a x,1,x,2,b,f,1,f,2,(a+b)/2,36,ADM,第三章 一维优化,3.4 二次插值法,二次插值：二次多项式逼近,3.4.1 方法原理,二次多项式逼近目标函数，以二次多项式的极小值点作为目标函数的近似最优点。,3.4.2 二次多项式构造,单峰区间,x,1,x,3,内存在极小值点，,在,x,1,x,3,内取点,x,2,，,则,过,x,1,x,2,x,3,构造,其极小值点为,x*,x,1,x,2,x* x* x,3,f(x),p(x),37,ADM,第三章 一维优化,3.4.3 区间缩小原理,比较,f(x*),和,f(x,2,)，,以其中较小者对应的点为新的,x,2,点，新,x,2,左右相邻的点分别为新,x,1,，新,x,3,。,3.4.4 收敛判据见黄金分割法,习题,初始区间 ,a,b = -0.5,1.5，,绝对精度,分别用解析法、黄金分割法、中心对分法、两点对分法求解。,38,ADM,第四章 多维无约束优化,分类：1）直接法（不需计算导数）,2）间接法（需计算导数）,4.1 坐标轮换法（坐标方向为搜索方向）,4.1.1 原理,将,n,维问题转化为依次沿,n,个坐标方向轮回进行一维搜索。,39,ADM,第四章 多维无约束优化,40,ADM,第四章 多维无约束优化,4.1.2 算法,1）,任选初始点,设定初始步长,置搜索方向,2）以 为初始点，沿 方向作试探，步长,计算 ，若 说明试探成功；否则，,若 ，置 ，若 ，,41,ADM,第四章 多维无约束优化,则作一维搜索求最优步长和优化点,若沿坐标轴正负方向试探均失败，则迭代点不变,3）以 为起点，按1）沿 方向搜索，得,沿,n,个坐标方向进行完一轮一维搜索后，得,4）以 作第二轮得起始点 ，重复2）、3）得第二轮搜索终点 。,5）如果从某轮起始点出发，依次沿,n,个坐标轴的正负方向试探均失败，则缩短试探步长（如减半），返回2）。当探索步长足够小，满足收敛判据 时，终止迭代，所得点即为优化结果,X*。,42,ADM,第四章 多维无约束优化,4.1.3 讨论,1）计算量小，程序简单，计算效率低，适合变量,n10,的情况。,2）若目标函数具有脊线，算法将出现病态：沿两个坐标方向均不能使函数数值下降，误认为最优点。,脊线,43,ADM,第四章 多维无约束优化,4.2 鲍威尔法（共轭方向为搜索方向）,4.2.1 共轭方向,1）定义,A,为,n,阶正定矩阵，若两个,n,维矢量满足,则称,S,1,和,S,2,对矩阵,A,共轭，共轭矢量方向为共轭方向。,对于,n,个,n,维矢量,S,i,，i=1,2,n(S,i,不为0)，若满足,则称,n,个,n,维矢量,S,i,，i=1,2,n,为对矩阵,A,共轭。,2）共轭方向与函数的极小值点关系,考察正定二次函数,其等值线为同心椭圆族,44,ADM,第四章 多维无约束优化,S,2,S,1,S,1,X,1,X,2,X,1,(0),X,2,(0),x,1,x,2,从,X,1,(0),出发沿,S,1,方向作一维搜索，得最优点,X,1,（与椭圆相切）；从,X,2,(0),出发沿,S,1,方向作一维搜索，得最优点,X,2,；连接,X,1,、,X,2,得矢量,S,2,， S,2,过椭圆族中心，即目标函数极小值点,X*，,且,S,1,、,S,2,对,A,正交，,沿,S,1,的共轭方向,S,2,可搜索到正定二元二次函数极值点,。,X*,45,ADM,第四章 多维无约束优化,4.2.2 原始鲍威尔法,S,1,、S,2,、,S,3,为共、轭方向（,参见前页,）,搜索方向:,x,1,x,3,x,2,e,1,e,2,e,3,X,0,(1),S,1,e,2,e,3,S,1,X,1,(1),X,2,(1),X,3,(1),X,0,(2),X,1,(2),X,2,(2),X,3,(2),X,0,(3),S,2,e,3,S,1,S,2,S,3,X,1,(3),X,2,(3),X,3,(3),X,0,(4),第1轮,第2轮,第3轮,46,ADM,第四章 多维无约束优化,原始鲍威尔法的严重缺陷：当某一轮方向组中的矢量系出现线性相关时（特别是接近,X*,时），会出现退化，无法获得极小值点。,4.2.3 改进鲍威尔法,与原始鲍威尔法的区别：每构造一个新方向，根据判别条件决定是否替换原来的某个方向。构造,k+1,轮方向组时，是否淘汰前一轮的某一个方向,S,m,(k),，,根据下面二个条件判断：,第,k,轮初始点函数值；,第,k,轮最后一个方向搜索终点函数值；,X,0,(k),对,X,n,(k),映射点,X,n1,(k),的函数值；,一维搜索中函数值下降最大者，其方向为,S,m,(,k),47,ADM,第四章 多维无约束优化,条件式,a)、b),同时或两者之一成立：第,k+1,轮仍沿用第,k,轮的方向组，取,X,n,(k),（,F,2,F,3,）或映射点,X,n1,(k),（,F,3,F(X,(k),)。,不是严格的下降算法。原因：,X,(k+1),是近似二次式在牛顿方向上的极小点，而非,F(X),在牛顿方向上的极小点。,2）对牛顿法的修正阻尼牛顿法,修正方法：在牛顿方向上作一维搜索求最优步长。,当,F(X),的海赛矩阵,H,k,在迭代点处,正定,情况下，阻尼牛顿法可以保证每次迭代，迭代点的函数值都,下降；,H,k,在迭代点处,不定,情况下，函数值不会上升，但不一定下降；,H,k,在迭代点处,奇异,情况下，不能求逆，无法构造牛顿方向；要求,F(X),二阶可微，需计算梯度、海赛矩阵及其逆矩阵，计算量大,。,4.4.3 收敛判据,同梯度法。,52,ADM,第四章 多维无约束优化,53,ADM,第四章 多维无约束优化,4.5,DFP,变尺度法,拟牛顿法，基于牛顿法的思想进行了重要改进。,4.5.1 基本思想,综合梯度法和牛顿法的优有点，克服梯度法收敛速度慢和牛顿法收敛快但稳定性差且计算量大的缺点。,比较梯度法和牛顿法，,54,ADM,第四章 多维无约束优化,A,k,为,n,n,对称矩阵，,A,k,为单位矩阵时，上式为梯度法；,A,k,H,k,-1,时，上式为阻尼牛顿法。,拟牛顿法的基本思想：用某种方法，人为构造一,n,阶对称矩阵,A,k,A(X,(k),)，,近似替代牛顿法的,H,k,-1,。通过迭代不断修正,A,k,，,使,A,k,H,k,-1,。,由于是不断变化的，它使搜索方向不断向牛顿方向逼近，故可把看作是变化的尺度矩阵，这就是变尺度法叫法的由来。梯度法和牛顿法也属于变尺度法的范畴。,A,k,应满足的条件,：,1. 正定,保证迭代过程中函数值始终下降，要求,S,(,k,),与,g,k,夹角为锐角，即,55,2. 拟牛顿条件使,A,k,H,k,-1,，A,k1,可以由第,k,步的信息递推构造,由,得,即,ADM,第四章 多维无约束优化,56,ADM,第四章 多维无约束优化,4.5.2 A,k,序列的生成（,DFP,递推公式）,57,ADM,第四章 多维无约束优化,4.5.3 算法,1）任选初始点,X,(0),，,收敛精度,2）,置,k=0，A,k,=E（,单位矩阵）；,3）沿,4）,5）用,DFP,公式求,A,k+1,；,6）,置 。若,kn（,变量数目），转到3），否则返回到2）开始下一轮（从负梯度法重开始，有利于收敛）；,7）输出结果,X*，F(X*)，,结束。,58,ADM,第四章 多维无约束优化,4.6,共轭梯度法,将梯度法和共轭方向法结合起来，每一轮搜索的第一步沿负梯度方向搜索，后续各步沿上一步的共轭方向搜索，具有二次收敛速度，每一轮搜索,n,步。,第一步的搜索方向负梯度方向,以后各步的搜索方向共轭方向,的确定,应使,n,维实空间中的两个非0向量,S,(,k,),和,S,(,k,1),关于矩阵,A,共轭，,即应使,对于正定二次函数,有,59,ADM,第四章 多维无约束优化,二式相减,而,则,可得,即,因 为一正交系，,故有,则,60,ADM,第四章 多维无约束优化,61,ADM,第四章 多维无约束优化,算法,l,任选初始点,X,(0),，,给定收敛精度,和维数,n,；,2,令 ，求迭代初始点,X,(0),的梯度,g,0,取第一次搜索的方向,S,(0),为初始点的负梯度,3进行一维搜索，求最优步长,(,k,),并求出新点,4计算,X,(,k,+1),点的梯度,5收敛检查。满足条件,则，计算结束；否则继续下一步；,6,判断,k,+1,是否等于,n,，,若,k,+1,n,，,则令,X,(0),=,X,(,k,+1),转步骤,2,；若,k,+1,n,，,则继续下一步；,7计算,62,ADM,第四章 多维无约束优化,8,确定下一步的搜索方向,令 ，返回步骤,3,。,讨论,共轭梯度法具有超线性收敛速度（1收敛速度阶数2）。计算效率高于梯度法，低于牛顿法，但对初始点没有特殊要求。不需计算二阶偏导数矩阵及其逆矩阵，计算量与梯度法相当，小于牛顿法。适用于各种规模的问题。,63,ADM,第四章 多维无约束优化,4.7 单纯形法,原理,函数的导数是函数性态的反映，它对选择搜索方向提供了有用的信息。在不计算导数的情况下，先算出若干点处的函数值，从它们之间的大小关系中也可以看出函数变化的大概趋势，为寻求函数的下降方向提供依据。这里所说的若干点，一般取在单纯形的顶点上。所谓单纯形是指在,n,维空间中具有,n,+1,个顶点的简单图形或凸多面体。利用单纯形的顶点，计算其函数值并加以比较，从中确定有利的搜索方向和步长，找出具有最大值的顶点并构造目标函数的下降方向，求出最小值点，以该点取代单纯形的最大值的顶点，重新构造单纯形。随着这种取代过程的不断进行，新的单纯形不断向极小点收缩。这样经过若干次迭代，即可得到满足精度要求的近似解。这就是单纯形法的基本思想。,64,ADM,第四章 多维无约束优化,65,ADM,第四章 多维无约束优化,算法,选择新的比较好的点替代最差点的算法有4种：,反射、扩张、压缩,和,收缩,。现以二元函数,F,(,X,)=,F,(,x,1,x,2,),为例，说明单纯形法的算法。,在,x,1,-,x,2,平面上取不在同一直线上的三点,X,H,、,X,G,、,X,L,，,以它们为顶点组成一单纯形（即三角形）,X,H,X,G,X,L,。,计算各顶点函数值，设,F(,X,H,)F(,X,G,)F(,X,L,),说明,X,L,点最好，,X,H,点最差。为了寻找极小点，一般说来，应向最差点的反对称方向进行搜索，即通过,X,H,并穿过,X,G,X,L,的中点,X,C,的方向进行搜索。在此方向上取作,X,H,点相对于,X,C,点的,反射,点,X,R,X,R,X,C,(,X,C,X,H,)2,X,C,X,H,计算反射点的函数值,F,(,X,R,)，,可能出现以下几种情形：,l.,F,(,X,R,),F,(,X,L,),即反射点比最好点还好，说明搜索方向正确，还可以往前迈进一步，也就是可以,扩张,。这时取扩张点,X,E,X,C,k(,X,C,X,H,),k,扩张因子，一般取,kl.2-2.0。,如果,F,(,X,E,),F,(,X,R,),说明扩张有利，就以,X,E,代替,X,H,构成新单纯形,X,E,X,G,X,L,。,否则说明扩张不利，舍弃,X,E,，,仍以,X,R,代替,X,H,构成新单纯形,X,R,X,G,X,L,。,66,ADM,第四章 多维无约束优化,2.,F,(,X,L,),F,(,X,R,),F,(,X,G,),即反射点比最好点差，但比次差点好，说明反射可行，则以反射点代替最差点，仍构成新单纯形,X,R,X,G,X,L,。,3.,F,(,X,G,),F,(,X,R,),F,(,X,H,),即反射点比次差点差，但比最差点好，说明,X,R,走得太远，应缩回一些，即,压缩,。这时取压缩点,X,K,X,C,m,(,X,R,X,C,),m,收缩因子，常取成,m0.5。,如果,F,(,X,K,),F,(,X,H,)，,则用,X,K,代替,X,H,构成新单纯形,X,K,X,G,X,L,。,4.,F,(,X,R,),F,(,X,H,),即反射点比最差点还差，这时应,压缩,得更多一些，即将新点收缩在,X,H,X,C,之间，取压缩点,X,K,X,C,m(,X,C,X,H,),如果,F,(,X,K,),F,(,X,H,),则用,X,K,代替,X,H,构成新单纯形,X,K,X,G,X,L,。,5.,F,(,X,),F,(,X,H,),即若,X,H,X,C,方向上的所有点都比最差点差，则表明不能沿此方向搜索，这时应以,X,L,为中心,收缩,，使顶点,X,H,、,X,G,向,X,L,移近一半距离，得新单纯形,X,H,X,G,X,L,，,如图所示。,67,ADM,第四章 多维无约束优化,从以上各步得到新的单纯形后，再重复开始新一轮构造单纯形，逐渐缩小单纯形直至满足精度要求。,68,ADM,第四章 多维无约束优化,计算步骤,1.,构造初始单纯形。选初始点,X,0,，,从,X,0,出发沿各坐标轴方向走步长,h,，,得,n,个顶点,X,i,（,i,1，2，,n,）,与,X,0,构成初始单纯形。这样可以保证此单纯形各棱是,n,个线性无关的向量，否则就会使搜索范围局限在某个较低维的空间内，有可能找不到极小点；,2.,计算各顶点函数值。,F,i,F,(,X,i,)；,3.,比较函数值的大小，确定最好点,X,L,，,最差点,X,H,和次差点,X,G,。,F,L,F,(,X,L,)min,F,(,X,i,) （,i,1，2，,n,）,F,H,F,(,X,H,)max,F,(,X,i,) （,i,1，2，,n,）,F,G,F,(,X,G,)max,F,(,X,i,) （,i,1，2，,n,；,iH,）,4.,检验是否满足精度要求,满足要求，则,X,*,X,L,，,计算结束。否则，继续步骤5；,5.,计算除,X,H,点之外各点的“重心”,X,n+1,69,和反射点,当 时 ，以,X,n+2,代替,X,H,，,F,n+2,代替,F,H,，,构成一新单纯形，然后返回步骤2；,6.,扩张。当,F,n+2,F,L,时，取扩张点,并计算其函数值,F,n+3,。若,F,n+3,F,n+2,，,则以,X,n+3,代替,X,H,，,F,n+3,代替,F,H,，,构成新单纯形；否则，以,X,n+2,代替,X,H,，,F,n+2,代替,F,H,，,构成新单纯形，然后返回步骤2；,7.,压缩。当,F,n+2,F,G,时则需收缩，如果,F,n+2,F,H,，,则取收缩点,否则，,若,F,(,X,R,),F,(,X,H,),，,在上式中以,X,H,代替,X,n,+2,，,计算其函数值,F,n+4,。若,F,n+4,F,H,，,则以,X,n+4,代替,X,H,，,F,n+4,代替,F,H,，,构成新单纯形，然后返回步骤3；否则接步骤8,ADM,第四章 多维无约束优化,70,ADM,第四章 多维无约束优化,8.,收缩单纯形。,最好点不动，其它点向最好点移近为原距离的一半,，即,（,i,1，2，,n,）,构成新单纯形，然后返回步骤2继续计算。,习题,分别用鲍威尔法、改进鲍威尔法、梯度法、阻尼牛顿法、,DFP,变尺度法、单纯形法、共轭梯度法求解，迭代2次。,71,坐标轮换法,将,n,维问题转化为依次沿,n,个坐标方向轮回进行一维搜索。收敛速度较慢，适合,n,10,的小型无约束优化问题，若目标函数具有“脊线”，算法将出现病态：沿两个坐标方向均不能使函数数,鲍威尔,(,Powell),法,属于模式搜索法。搜索方向不一定是共轭方向组，而是共轭程度越来越高的方向组（改进共轭方向），避免原始鲍威尔法（共轭方向法）的方向组线性相关退化现象。对初始点没有特殊要求，具有超线性收敛速度。适合中小型无约束优化问题。,单纯形法,对,n,维问题，构造由,n,+1,线性独立的点为顶点的凸单纯形，找出具有最大值的顶点并构造目标函数的下降方向，求出最小值点，以该点取代单纯形的最大值的顶点，重新构造单纯形。适用于中小型无约束优化问题或目标函数没有数学表达式而只有其具体算法的情况。,ADM,第四章 多维无约束优化,72,最速下降法,(,梯度法,),搜索方向为目标函数负梯度方向。计算效率优于坐标轮换法。开始几步搜索下降快，但愈接近极值点下降愈慢。对初始点的选择要求不高，适合与其它方法结合使用（开始采用最速下降法，接近极值点时采用其它方法，如牛顿法）。,牛顿法（,Newton-Raphson,法）,用泰勒二次多项式近似原目标函数，以该二次多项式的极小点近似目标函数的极小点并逐渐逼近该极小点（搜索方向为牛顿方向，步长为,1,）。,要求目标函数连续，存在一、二阶偏导数，且海赛（,Hessian,）,矩阵非奇异。初始点选择适当时，是收敛最快的算法；对初始点选择要求高。计算量大。,阻尼牛顿法（修正牛顿法或广义牛顿法）,搜索方向为牛顿方向，沿牛顿方向对步长做一维搜索优化。其它特点与牛顿法相同。,ADM,第四章 多维无约束优化,73,共轭梯度法,第一步搜索沿负梯度方向（最速下降方向），然后沿负梯度的共轭方向搜索。计算效率介于梯度法和牛顿法之间。对初始点没有特殊要求。不需计算二阶偏导数矩阵及其逆矩阵，计算量与梯度法相当。适用于各种规模的问题。,变尺度法（,DFP,法及,BFGS,法）,拟牛顿法，基于牛顿法的思想进行了重要改进。为公认的求解无约束优化问题的有效方法。适用于各种规模的问题。,DFP,法有时存在数值稳定性不够理想的问题，,BFGS,法数值稳定性较好。,ADM,第四章 多维无约束优化,74,ADM,第五章 多维有约束优化,分类,1）直接法,直接利用迭代点和目标函数值构造搜索方向。网格法、分层降维枚举法。,2）间接法,需计算梯度构造搜索方向，,将约束优化问题转化为无约束优化问题,求解。罚函数法（内点、外点、混合） 。,75,ADM,第五章 多维有约束优化,5.1 目标函数的约束极值问题,目标函数的,约束极值,，又称为,条件极值,。与前面所讨论的无约束条件下函数的极值问题的区别在于它是带有约束的条件下的函数极值问题。在约束条件下所求得的函数极值点，称为,约束极值点,。,对于带有约束条件的目标函数，其求最优解的过程可归结为，寻求一组设计变量,在满足约束方程的条件下，使目标函数值最小，这样求得的最优点,X,*,，,称为,约束最优点,。,两者重合 两者不重合,自然极值点与约束最优点的相互关系,76,（,a） （b）,可行域形状对约束最优解的影响,（,a）,可行域为凸集（,b）,可行域为非凸集,ADM,第五章 多维有约束优化,77,ADM,第五章 多维有约束优化,目标函数或约束函数的非凸性使约束极值点增多情况,Kuhn-Tucker,最优胜条件,简称为,Kuhn-Tucker,条件或,K-T,条件，可有效地用于对约束极值点存在条件的分析、检验。,K-T,条件如下：设,X,*,为非线性规划问题,78,ADM,第五章 多维有约束优化,的约束极值点，且在全部等式约束及不等式约束条件中共有,q,个约束条件为起作用约束，即, (,i,j,，,i,+,j,= 1,2,q,p,)。,如果在,X,*,处诸起作用约束的梯度向量,、 (,i,+,j,= 1,2,q,p,),线性无关，则存在向量使下述条件成立,，,为非零、非负的乘子,为非零的乘子,，,拉格朗日乘子向量,。,满足,Kuhn-Tucker,条件的点，称为,Kuhn-Tucker,点。在一般的非线性规划问题中，,Kuhn-Tucker,点虽是约束极值点，但不定是全域最优点即,K-T,条件不是最优解的充分条件。但对于目标函数,F,(,X,),为凸函数、可行域,D,为凸集的凸规划问题来说，,Kuhn-Tucker,条件不仅是确定约束极值点的必要条件同时也是全域最优解的充分条件。而且凸规划问题有唯一的,Kuhn-Tucker,点，但它所对应的拉格朗日乘子向量不一定是唯一的。,79,ADM,第五章 多维有约束优化,K-T,条件的几何意义,Kuhn-Tucker,条件条件表明，若点,X,*,是函数,F,(,X,),的极值点，要么,X,*,点位于可行域内；要么,X,*,点位于某些约束的边界上，而在点,X,*,，,目标函数的负梯度落在起作用约束梯度所成的夹角锥体之内。也就是说，目标函数的负梯度等于起作用约束梯度线性组合。,80,ADM,第五章 多维有约束优化,例：用,Kuhn-Tucker,条件证明二维目标函数,在不等式约束：,的约束条件下，点,为其约束极值点。,(,a),求证约束极值点,(,b),在约束极值点处,K-T,条件不成立的情况,81,ADM,第五章 多维有约束优化,（1）由图可知，在点 处起作用的约束函数有 和 ；,（2）求有关函数在点 的梯度,（3）代入式(2-25)检验：,82,ADM,第五章 多维有约束优化,即 ，故满足,K-T,条件，即点 确为约束极值点。而且由于本题为凸规划，所以它也是全局最优点。,例：试分析约束最优化问题,的约束最优解及其,Kuhn-Tucker,条件。,图(,b),给出了可行域，由图不难看出 是约束最优点，起作用约束函数有 和 。但由于,显然不可能找到 ,使,Kuhn-Tucker,条件,83,ADM,第五章 多维有约束优化,成立。这一矛盾产生的原因是由于,即二者为线性相关而在,Kuhn-Tucker,点起作用约束的梯度向量应是线性无关的。,84,ADM,第五章 多维有约束优化,5.2 网格法,5.2.1 原理,1）在设计变量的界线区间内均匀地划分网格，计算节点上的目标函数值和约束函数值，舍去不满足约束条件的节点，比较满足约束条件的节点的目标函数值，找出目标函数值最小的节点；,2）以该最小值节点相邻的各节点为新的设计变量界线区间，细化网格，重复1），直至满足精度（收敛）要求【网格分割间距 】,X*,X,(1),初始网格,二次网格,X,(2),85,ADM,第五章 多维有约束优化,5.2.2 网格法的特点,1）不适合于等式约束；,2）,对连续变量和离散变量均适用；,3）总能搜索到解；,4）算法简单，计算量大，适合设计变量较少的情况。,5.2.3 分层降维枚举法,改进的网格法，将设计变量分层处理，每一层有少量设计变量，前一层的设计变量的解作为常量进入下一层的求解过程，从而减少网格节点数量，减少计算量。要求：优化模型必须能分层。,86,ADM,第五章 多维有约束优化,5.3 罚函数法,5.3.1 罚函数法的基本思路,1）拉格朗日乘子法,构造函数, 的无约束极值问题。,87,ADM,第五章 多维有约束优化,2）罚函数法 借鉴拉各朗日乘子法，将约束优化转化为,序列无约束极小化,问题：,88,3）罚函数求解过程（序列无约束极小化方法,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),，得优化点序列,X*,(k),;,c.,优化点序列,X*,(k),不断逼近最优解，满足收敛准则,， X*,(k),即为有约束优化得最优解。,4）,罚函数法分类,内点法：在可行域内迭代，逼近最优解，适合于不等式约束；,外点法：在可行域外迭代，逼近最优解，适合于不等式约束和等式约束；,混合法：适合于不等式约束和等式约束。,ADM,第五章 多维有约束优化,89,ADM,第五章 多维有约束优化,5.3.2 内点法,1. 例,构造泛函：,罚函数极值：,90,ADM,第五章 多维有约束优化,91,f,P,7,6,5,4,3,2,1,ADM,第五章 多维有约束优化,0 1 2 3 4 5 6 7 8 9,x,x-1=0,f(x)=x/2,r,(k),=1,r,(k),=0.25,r,(k),=0.0025,x*,2,1,0,r,(3),r,(2),r,(1),r,(0 ),r,(k),r,(k),递减时,x*,(k),逼近,x*,f,和,P,的曲线,92,ADM,第五章 多维有约束优化,2. 内点法泛函与罚函数构造,1） 是可行域,D,上的连续函数（采用需要梯度的优化方法时，需可导）；,2） 当,X,在可行域,D,内远离约束边界时，具有相当小的正值；,X,靠近约束边界，具有很大的正值（趋向无穷大）；,93,ADM,第五章 多维有约束优化,3）,X,的取值只能在可行域内，否则泛函,G,将不满足不为负值的要求；,4）,罚因子,r,(k),的作用：,F(X),的有约束极值点可能在可行域靠近边界处或就在边界上,，此时尽管泛函,G,的数值很大，但罚因子是不断递减的正值，经多次迭代，,X*,(k),向,X*,接近时，惩罚项,r,(k),G,是很小的的正值（趋向0），可以保证罚函数,P(X),的无约束极值点序列收敛于,F(X),约束极值点。,3. 算法,1）在可行域内任选一严格初始内点,X,(0),，最好不要靠近约束边界；,2）选一适当大的初始罚因子,r,(0),，求罚函数,P(X, r,(0),),的无约束极值点,X*,(0),，,选一罚因子递减率0,c1，,递减后的罚因子,r,(1),c r,(0),，,以,X*,(0),为初始点，求罚函数,P(X, r,(1),),的无约束极值点,X*,(1),；,3）按,r,(k,),c r,(k-1),k1,2,，,逐次递减罚因子，并依次取上一次迭代的极值点,X*,(k-1,),作为本次迭代的初始点，重复上述步骤，直至满足收敛精度，即得最优解,X*,和最优值,F(X*)。,94,ADM,第五章 多维有约束优化,4. 内点法讨论,1）初始点为严格内点；,2）不适用于等式约束，如等式约束不要求严格满足时可处理为：,3）初始罚因子对收敛性影响大，但难以选择，一般用试算法调整；,4）罚因子递减率大小对收敛性影响不大，,c = 0.10.02;,5）,进行罚函数的无约束优化的一维搜索时，应保证不超出可行域。每作一次一维搜索，都要检查是否破坏约束，如不破坏，可继续进行；否则，缩短寻优区间，直至满足约束。,6）内点法的规律性：,a. P(X*,(k,), r,(k,),),为严格单调下降数列，且其极限为,F(X*)；,b. F(X*,(k,),),为单调非增数列，,95,ADM,第五章 多维有约束优化,c. Gg(X *,(k,),),为单调非降数列,7）可以得到多个优化方案,X*,(k,),F(X*,(k,),),。,5. 收敛判据,前后两次迭代的极小值点间的“距离”或“相对距离”满足精度要求。,96,ADM,第五章 多维有约束优化,5.3.3 外点法,1 例,构造泛函和罚函数,x,取值即可在可行域内，也可在可行域外。,M,(k),为外点法的罚因子，是递增序列：,97,ADM,第五章 多维有约束优化,求,P,的无约束极值点：,98,ADM,第五章 多维有约束优化,99,ADM,第五章 多维有约束优化,2. 外点法泛函与罚函数构造,优化模型：,泛函的构造：,要求 ：,a.,泛函应是,R,n,中的连续函数；,b. X,在可行域外远离约束边界时，泛函有相当大的正值，离边界越远，其 正值越大；,X,在可行域外靠近约束边界时，泛函有较小的正值，在边界上和可行域内，其值为0。,1）不等式约束,100,ADM,第五章 多维有约束优化,2）等式约束,罚函数构造：,3. 算法,1）任选初始点,X,(0),（,内点、外点均可），选定适当的初始罚因子,M,(0),和递增率,c，,求,P(X, M,(0),),的无约束优化点,X*,(0),；,2）以,X*,(0),作为下一次迭代的初始点，取,M,(1),c M,(0),为递增的罚因子，求,P(X, M,(1),),的无约束优化点,X*,(1),；,3）按,M,(k),c M,(k-1),，,k=1,2,，,逐次递增罚因子，依次取上一次的优化点,X*,(k-1),为本次迭代的初始点，求,P(X, M