优化设计ch3课件

第三章优化设计优化设计概论

优化设计的基本概念一维搜索方法

无约束设计的最优化方法

有约束优化设计的方法

优化设计的若干问题LINGO在优化设计中的应用3.1优化设计概论优化设计和示例优化设计：亦称最优化设计，它是以数学规划理论为基础，以电子计算机为辅助工具的一种设计方法。它首先将设计问题按规定的格式建立数学模型，选择合适的优化方法，选择或编制计算机程序，通过计算机计算获得最优设计方案。优化方法：直接法：直接计算目标函数值，比较目标函数值，并以之作为迭代、收敛根据；求导法：以多变量函数极值理论为基础。3.1优化设计概论优化问题的分类无约束问题单变量多变量有约束问题线性约束，线性目标函数线性约束，非线形目标函数非线形约束，非线形目标函数优化设计数学模型设计变量

目标函数:最小化约束条件：3.1优化设计概论设计变量和设计空间设计变量：设计方案可用一组参数表示，有些参数预先给定，称为设计常量；而另一些在设计过程中优化选定，称为设计变量。设计空间：某方案有n个设计变量，组成一个n维列矢量。该矢量可在以n个设计变量为坐标轴组成的n维空间中用一个点来表示。这n维空间称为设计空间，空间内任意一点称为设计点，它代表一个设计方案。通常在保证设计精度的前提下设计变量尽量取的少些。设计变量有连续和离散两种3.1优化设计概论约束条件和可行域约束条件：设计变量的取值范围有限制或必须满足一定的条件，这种对设计变量的限制，称为约束条。约束条件的分类：等式约束与不等式约束边界约束和性能约束:前者指取值范围的限制；后者指力学性能要求的限制。二维设计问题约束的几何关系X1X23.1优化设计概论目标函数定义：优化设计把设计变量与某种标准的关系用函数式表达，追求该函数值最小（或最大），以求得一组设计变量值，从而获得一个最优设计方案。此函数称为目标函数。（设计中欲达到的目标）作用：衡量设计方案的标准。目标类型：产品设计：技术性能、成本、价格、寿命等；零部件设计：承载能力、可靠性、重量、体积等；机构设计：运动学和动力学性质、运动误差等。3.1优化设计概论优化设计的几何解释目标函数：maxF(X)=60x1+120x2约束条件材料约束：g1(X)=9x1+4x2＜360工时约束：g2(X)=3x1+10x2＜300电力约束:g3(X)=4x1+5x2＜200边界约束:g4(X)=-x1＜0

g5(X)=-x2＜03.1优化设计概论优化设计的几何解释目标函数：约束条件非线性优化问题的图解法。3.1优化设计概论目标函数的等值线（面）依次令目标函数F（X）分别等于常数C1，C2，C3等，则在目标函数曲面上，获得等值曲线（面）族。3.2优化设计的基本概念函数的方向导数与梯度偏导数：一元函数中的导数：描述函数相对于自变量的变化率；多元函数中的偏导数：描述函数只相对于其中一个自变量(其余自变量保持不变)的变化率。对n函数，函数在处沿各坐标轴的一阶偏导数或变化率分别为：3.2优化设计的基本概念函数的方向导数与梯度方向导数:函数在某点沿给定方向的变化率。函数的方向导数式中:cosα，cosβ为某方向S的方向余弦3.2优化设计的基本概念函数的方向导数与梯度梯度二元函数的梯度

为函数F(x1，x2)在X0点处的梯度梯度的模：设:由上式可见：梯度方向和h

方向重合时，方向导数值最大。

梯度方向是函数值变化最快的方向，而梯度的模就是函数变化率的最大值

。

梯度方向与等值线的关系因：则有

为单位方向向量。梯度模：函数的梯度方向与函数等值面相垂直，也就是和等值面上过x0的一切曲线相垂直。

由于梯度的模因点而异，即函数在不同点处的最大变化率是不同的。因此，梯度是函数的一种局部性质。求函数在点[3,2]T、[2,0]T的梯度解

在点x(1)=[3,2]T,x(2)=[2,0]T处的梯度为：3.2优化设计的基本概念无约束目标函数的极值条件一元函数的极值多元函数的Taylor展开式：函数在某点附件的近似表达式多元函数的泰勒展开式一元函数展开成泰勒(Taylor)公式：二元函数展开成泰勒(Taylor)公式：n元函数展开成泰勒(Taylor)公式：一元函数泰勒Taylor展开式二元函数Taylor展开式对二元函数泰勒展开式只取两项称为海森(Hessian)矩阵，二阶偏导矩阵,常用H(X)表示。n元函数Taylor展开式当在驻点第二项为零，可得：3.2优化设计的基本概念无约束目标函数的极值条件二次型函数二次型：含有n个变量x1,x2,…,xn的二次齐次多项式实二次型函数：若aij均为实常数，简称实二次型。1.对所有非零矢量X，若：则称F(X)正定的2.若对所有非零矢量X，若：则称F(X)负定的

3.2优化设计的基本概念无约束目标函数的极值条件多元函数的极值必要条件：实二次型函数：若aij均为实常数，简称实二次型。当，为极大值点在邻域内，对所有X根据二次型函数性质，也可只用Hessian矩阵判断。当，为极小值点当，为鞍点当H（X＊）正定，X＊为极小值点当H（X＊）负定，X＊为极大值点当H（X＊）不定，X＊为鞍点矩阵的正定条件是：其各阶主子式（对应的各阶行列式）均大于零；负定的条件是：其各阶主子式负正相间。奇数阶小于零；偶数阶大于零无约束目标函数的极值条件例:目标函数如下，求极值点及性质。解：先求子函数的一阶偏导数并其等于0，求解驻点，即驻点为（1，1）求H（X）矩阵正定驻点（1，1）为极小值F（）=4

3.2优化设计的基本概念有约束目标函数的极值条件函数的凸性一元函数的凸性多元函数的凸性约束问题的极值条件3.2优化设计的基本概念有约束目标函数的极值条件函数的凸性一元函数的凸性：其曲线上任意两点的连线永不在曲线下方。反之为凹曲线。凸函数

凹函数一元函数的凸性在线段中任取一点x(3)，则有：或凸函数表达式：几何意义：任意两点间的曲线永远在连该两点的直线之下。3.2优化设计的基本概念有约束目标函数的极值条件函数的凸性多元函数的凸性：先研究凸集才能研究函数的凸性。凸集几何特征：其中的任意两点间连线都在这集合内凸集含义：区域内部无空洞区域边界无凹陷凸函数

对凸集D内，任两点X(1)、X(2)及0<λ<1,恒有：则F(X)为定义在凸集D上的一个凸函数几何意义为：这两个点的连线完全处在F(X)曲线(曲面)的上方，或在F(X)。曲线(曲面)上凸函数的判别方法F(X)在D1连续一阶可导，而D是D1内的一个凸集(D1>D)，对任意两点F(X)在D1上有二阶的连续导数，D是D1内的一个凸集，为凸函数的充要条件为Hessian矩阵半正定，要求各阶主子式的值大于或等于零。函数凸性的判定：若F(X)在D1上为一阶连续导数，而D又是D1内部的一个凸集，则F(X)为D上的凸函数的充分必要条件为：若F(X)在D1上为二阶连续导数，而D又是D1内部的一个凸集，则F(X)为D上的凸函数的充分必要条件为:F(X)的Hessian矩阵为半正定。即

H(X)0综上所述：若F(X)其定义域是凸集，它是该凸集内的一个凸函数，则在该凸集内最多只有一个极小值，且它一定是该集内的全局最小值。

★凸规划的局部极小点一定是全局极小点

3.2优化设计的基本概念有约束目标函数的极值条件约束问题的极值条件目标函数及约束函数都是凸函数目标函数及约束函数有一个为非凸函数结论库恩-塔克条件（约束极值存在的必要条件）3.2优化设计的基本概念有约束目标函数的极值条件约束问题的极值条件目标函数及约束函数都是凸函数约束最优点不一定是自然极值点3.2优化设计的基本概念有约束目标函数的极值条件约束问题的极值条件目标函数及约束函数有一个为非凸函数可行域内可出现两个或多个相对极小点，图中X*是全域约束极小点。3.2优化设计的基本概念有约束目标函数的极值条件约束问题的极值条件结论:对约束优化既要解决“约束极值存在条件”还要解决“全域最优点”的问题。3.2优化设计的基本概念有约束目标函数的极值条件约束问题的极值条件库恩-塔克条件KT:（约束极值存在的必要条件）不是充分条件，因不能确定全局最优解。只判断是否是一个局部最优解。内容：目标函数梯度可表示成诸约束面梯度线性组合的负值，亦即q：为在该设计点X处的约束面数；λ：拉格朗日乘子。库恩-塔克条件只有一个起作用的约束条件目标函数的负梯度方向与约束函数梯度方向一致库恩-塔克条件有两个起作用的约束条件目标函数的负梯度方向在两个约束函数梯度的夹角内库恩-塔克条件有多个起作用的约束条件目标函数梯度可表示成诸约束面梯度线性组合的负值.库恩-塔克条件是约束优化极值的必要条件，不是充分条件。只有当目标函数及约束函数都为凸函数时，才是充分必要条件。例:目标函数约束条件判断是否为极小点解：目标函数和约束函数在X点的梯度

得λ1=1，λ2=1，λ3=0满足库恩-塔克条件，X*是约束极小值。g1(X),g2(X)起作用一、一维搜索和一维搜索最优化方法当采用数学规划法寻求多元函数的极值点时，一般要进行一系列如下格式的迭代计算:当方向给定，求最佳步长因子就是求一元函数

:的极值问题，这一过程被称为一维搜索(单变量优化).为求得值而采用的方法，称为一维搜索最优化方法。3.3一维搜索方法一维搜索3.3一维搜索方法0．618法：又称黄金分割法试探法单谷(峰）区间:在给定区间内仅有一个谷值(极大或极小)的函数称为单峰函数，其区间称为单谷区间.单峰函数的特点：函数值:”大－小－大”，图形：“高—低—高”,单谷区间中一定能求得一个极小点.试探法原理：

F(X)在区间[a,b]是单峰凸函数，为缩小该区间，在中间任取两点a1,a2。比较F(a1),F(a2)的大小，即可缩小搜索区，从而精确估出的位置。(1)如F(a1)<F(a2),则缩小的新区间为[a,a2];(2)如F(a1)>F(a2)，则缩小的新区间为[a1,b];(3)如F(a1)=F(a2),则缩小的新区间为[a1,a2]消去原则：消除大函数值一边的区间。3.3一维搜索方法0．618法：又称黄金分割法0．618法黄金分割律：是公元前六世纪，希腊的大数学家毕达哥拉斯发现的：如果把一条线段分成两部分，长段和短段的长度之比是1:0.618，整条线段和长段的比也是1:0.618时，才是和黄金一样最完美的分割，进行分割的这个点就叫黄金分割点基本思想:在待定的单峰区间内，不断消去一部分区间，把区间越缩越小，且每次区间缩短率都相等，新区间长度为原区间长度的0.618，直到极小点所在的区间小至满足精度要求，再取最后区间的中点作为近似最优点。对函数的要求：单峰.

将区间分成三段

黄金分割法还要求在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布。3.3一维搜索方法插值法(二次插值法，亦称抛物线法)基本思想：在选定的单峰区内取一点，连同两端点，用这三点函数值构成一个二次多项式，做原函数的近似，求出该二次多项式的极小值做原函数的近似最优值。

1、二次多项式P(x)的构成及其极小点设原目标函数的初始单峰区间为x1,x3

。函数在x1,x2,x33点处函数值分别为F1,F2,F3，求待定系数a,b和c,并代入上式，得：计算步骤1)确定单峰区[x1，x3]2)选定x2。可为单峰区中点，或不等间距点常用3)求4)判定是否终止计算5)缩小搜索区缩短区间

假若F(x)本身为二次函数，则在理论上按前式一次求值就可找到最优点。

若F(x)为高于二次的函数或为其他函数,可采用区间消去法逐步缩小区间。根据xp*

，x2，F(xp*)和F(x2)的相互关系，分6种情况进行区间缩小。在已有的四x1，x2，x3，xp*中选择新的三个点x1，x2，x3，再进行二次插值。选点要求：

☆x1<x2<x3，F1>F2，F2<F3（高－低－高形态）☆如果，以x2,xp*中函数值较小的点作为最优点x*。二次插值法区间缩短的几种情况二次插值法新区间的取舍二次插值法区间缩短的几种情况二次插值法区间缩短的几种情况例：从初始点沿给定方向搜索，求最优步长目标函数

的极小值初始点为：搜索方向：3.4无约束的优化方法两大类方法：1、只利用目标函数值本身；

2、利用函数的一阶导数甚至二阶导数。Powell法梯度法共轭梯度法:解决梯度法变尺度法3.4无约束的优化方法Powell法：直接利用函数值来构造共轭方向的一种方法

共轭方向的概念定义:设A为实对称正定n阶方阵，若有两个n维矢量S1与S2满足时，称矢量S1与S2对于实对称正定矩阵A共轭。若A为单位矩阵，则两矢量正交（即相互垂直）。共轭方向是正交方向的推广。性质：对n维二次目标函数，从任意点出发，可找到n个共轭矢量，依次对这些矢量分别进行一维搜索，就可找到该n维二次目标函数的极小点。对二元函数：若其Hessian矩阵为正定，其目标函数的等值线是同心椭圆族。二次收敛性对二元函数特性任意两条平行切线与椭圆族的切点的连线，一定通过椭圆族的中心。对一个正定的二元函数，只要沿两个相互共轭的方向进行一维搜索，便可找到极小点。3.4无约束的优化方法Powell法共轭方向的形成选任意初始点X(0)

依次沿各坐标方向进行一维搜索。构成第一个共轭方向

，再沿S(1)

进行一维搜索得极小点

。进行第二轮搜索，获第二个共轭方向。搜索时去掉e1，从e2方向开始，将

加到最后。

再沿此方向进行搜索得极小点X

。此两方向共轭多维无约束优化方法算法的基本过程是:

从选定的某初始点x(k)出发，沿着以一定规律产生的搜索方向S(k),取适当的步长a(k),逐次搜寻函数值下降的新迭代点x(k+1),使之逐步通近最优点x*。可以把初始点x(k)

、搜索方向S(k)

、迭代步长a(k)

称为优化方法算法的三要素。其中以搜索方向S(k)更为突出和重要，它从根本上决定若一个算法的成败、收敛速率的快慢等。一个算法的搜索方向成为该优化方法的基本标志，分析、确定搜索方向S(k)是研究优化方法的最根本的任务之一。共轭方向的形成过程3.4无约束的优化方法Powell法Powell法的基本步骤选任意初始点X(0)

依次沿各坐标方向进行一维搜索。进行第二轮搜索,构成第一个共轭方向.

进行第二轮搜索，构成第二个共轭方向。以后各轮，均以新获得的共轭方向替换前一轮搜索的第一个搜索方向。经n轮搜索后，构成n个相互共轭的方向。对n维二次正定函数，相继沿n个共轭方向做一维搜索，即可得到极值点。3.4无约束的优化方法Powell法Powell法的基本步骤为防止线性相关，第k轮新算出的共轭方向要满足下式，否则抛弃该方向：令k轮搜索出的共轭方向及其反映点分别为:式中：3.4无约束的优化方法梯度法基本思想:梯度方向是函数变化率最大的方向;负梯度方向是目标函数下降最快的方向。迭代公式最佳步长因子采用一维搜索的方法决定。终止条件:点距准则；梯度准则；相对准则3.4无约束的优化方法梯度法迭代步骤：给定初始点X(0)

，允差ε，置k=0。计算迭代点的梯度和负梯度方向。计算最优步长因子迭代计算检查是否满足终止条件令k=k+1转下一步计算特点:只需求一阶导数，迭代计算简单，存储单元少，对初始点要求不高。开始收敛快，接近极小点时收敛慢。3.4无约束的优化方法共轭梯度法:解决梯度法接近最优点时收敛慢的缺点.基本原理：利用目标函数的梯度确定共轭方向.为避免梯度方向后期收敛慢，用新搜索方向使之与所算出的梯度方向共轭。其共轭矩阵为该点的海森矩阵。海森矩阵及逆阵难求，需找新路目标函数不是二阶，海森矩阵因点而异，要顺序地求解共轭梯度法基本原理3.4无约束的优化方法共轭梯度法共轭方向的形成：若A已知，可直接求。一般将共轭方向写成该点负梯度矢量与前一步搜索方向的线性组合.新的共轭方向应满足:(1)要写成如下形式：(2)共轭系数求法：将（2）代入（1）:(3)因相邻两次迭代的负梯度方向正交，故有:式(3)简化为：结论：选初始点X(0)，允差ε，维数n。计算初始点负梯度方向为搜索方向。求最优步长并计算新点的梯度。精度判断判断k+1是否等于n，若相等令X(0)

=X(k+1)

,并转回步骤1；否则转入下一步.计算共轭方向令k=k+1转入步骤

2.3.迭代步骤3.4无约束的优化方法共轭梯度法特点：二次收敛，程序简单，存储量小适用于多变量优化；但目标函数必可求一阶导数。3.4无约束的优化方法变尺度法基本思想和公式:加速收敛，避免求二阶导数矩阵及其逆阵。将负梯度方向乘一个对称正定矩阵（变尺度矩阵）修正后做为搜索方向。。迭代步骤对二次函数难求，且所以实际运算中求E有许多公式:常用的有DFP法和BFGS法

迭代步骤给定初始点，允差和维数设变尺度矩阵的初值为单位矩阵，置k=0求搜索方向和最优步长：求出下一个迭代点:检验终止条件，终止，否则转下一步检查迭代次数；若k=n则X(0)

=X(k+1)，转步骤2，否则转下一步构造新的搜索方向：令k=k+1转入步骤33.5有约束优化设计的方法直接法与间接法：前者设法使每次迭代点在可行域内；后者将约束问题通过一定形式的变换，转化成无约束问题。复合形法基本思想：在可行域内选k个设计点，作为初始复合形的顶点，构成一个多面体。经各顶点比较，找出目标函数最大的为坏点，按一定规则以新点代替坏点，构成新的多边形。多次重复，使复合性向最优点靠近，最后以顶点中目标函数最小的做最优点。3.5有约束优化设计的方法复合形法顶点数目：为克服退化顶点数n+1≤k≤2n。以二维函数为例：3≤k≤4。具体方法：三个复合形顶点构成一个三角形，Xh是最坏点，Xc是除最坏点外的形心，沿Xh，Xc方向取Xr为映射点Xr=Xc+a(Xc-Xh),映射系数α=1.3。首先检查Xr是否在可行域内，若不在将α减半再检查，直至退入可行域；再检查函数值，若F(Xr)<F(Xh)以新点代替坏点，否则将α减半再检查，直至满足上式。若减至很小，则依次坏点代替坏点进行映射。直至复合形收缩到规定的精度范围内。迭代步骤产生初始复合形对顶点的要求：在可行域内；在k个点中至少有n+1个线性无关（n+1≤k≤2n）。顶点的产生：简单的可在可行域内任意选取；复杂的需用随机方法：选一个初始点,其余点:j为复合形顶点的标号[2，k]；i为设计变量的标号[1，n]。设计变量的解域γji为[0，1]间的伪随机数。然后检查各顶点是否在可行域内，不满足则向形心靠拢。迭代步骤寻找映射点找出最坏点Xh，求出其余各点的形心Xc。获得映射点,检查其可行性，不满足则减半α。迭代步骤比较函数值构成新复合形F(Xr)＜F(Xh)，用映射点代替坏点转向2。F(Xr)>F(Xh)，将α减半，直至满足。若α过小(10-5)，用次坏点代替坏点。终