《优化设计ch》PPT课件.ppt

第三章 优化设计,优化设计概论 优化设计的基本概念 一维搜索方法 无约束设计的最优化方法 有约束优化设计的方法 优化设计的若干问题 LINGO在优化设计中的应用,3.1 优化设计概论,优化设计和示例 优化设计：亦称最优化设计，它是以数学规划理论为基础，以电子计算机为辅助工具的一种设计方法。它首先将设计问题按规定的格式建立数学模型，选择合适的优化方法，选择或编制计算机程序，通过计算机计算获得最优设计方案。 优化方法： 直接法：直接计算目标函数值，比较目标函数值，并以之作为迭代、收敛根据； 求导法：以多变量函数极值理论为基础。,3.1 优化设计概论,优化问题的分类 无约束问题 单变量 多变量 有约束问题 线性约束，线性目标函数 线性约束，非线形目标函数 非线形约束，非线形目标函数,3.1 优化设计概论,优化设计的数学模型 识别要确定的未知变量 识别目标，写成最小化的函数 识别问题的约束或限制;写成等式或不等式 例题：容积为7850立方厘米的圆罐头盒，用料最省。确定D和H值,优化设计数学模型,设计变量,目标函数: 最小化,约束条件：,3.1 优化设计概论,设计变量和设计空间 设计变量：设计方案可用一组参数表示，有些参数预先给定，称为设计常量；而另一些在设计过程中优化选定，称为设计变量。 设计空间：某方案有n个设计变量，组成一个n维列矢量。该矢量可在以n个设计变量为坐标轴组成的n维空间中用一个点来表示。这n维空间称为设计空间，空间内任意一点称为设计点，它代表一个设计方案。 通常在保证设计精度的前提下设计变量尽量取的少些。 设计变量有连续和离散两种,3.1 优化设计概论,约束条件和可行域 约束条件：设计变量的取值范围有限制或必须满足一定的条件，这种对设计变量的限制，称为约束条。 约束条件的分类： 等式约束与不等式约束 边界约束和性能约束:前者指取值范围的限制；后者指力学性能要求的限制。,3.1 优化设计概论,约束条件和可行域 可行域:每个不等式约束将设计空间划分成满足和不满足约束条件的两部分，若干个不等式约束把设计空间分成两个区域，阴影线内侧区的点都满足所有不等式约束，称为可行域。 当有等式约束时，只能在可行域内的等式约束线上取值.等式约束大大缩小可行域,二维设计问题约束的几何关系,3.1 优化设计概论,目标函数 定义：优化设计把设计变量与某种标准的关系用函数式表达，追求该函数值最小（或最大），以求得一组设计变量值，从而获得一个最优设计方案。此函数称为目标函数。（设计中欲达到的目标） 作用：衡量设计方案的标准。 目标类型： 产品设计：技术性能、成本、价格、寿命等； 零部件设计：承载能力、可靠性、重量、体积等； 机构设计：运动学和动力学性质、运动误差等。,3.1 优化设计概论,优化设计的几何解释 目标函数 ：max F(X)=60x1+120x2 约束条件 材料约束：g1(X)=9x1+4x2360 工时约束：g2(X)=3x1+10x2300 电力约束: g3(X)=4x1+5x2200 边界约束: g4(X)=-x10 g5(X)=-x20,线性规划问题的图解法。,C是g2(X)与g3(X)的交点,3.1 优化设计概论,优化设计的几何解释 目标函数 ： 约束条件,非线性优化问题的图解法。,3.1 优化设计概论,目标函数的等值线（面） 依次令目标函数F（X）分别等于常数C1，C2，C3等，则在目标函数曲面上，获得等值曲线（面）族。,3.1 优化设计概论,线形与非线性规划 线性规划：当目标函数和约束条件都是设计变量的线性函数时，列出这种数学模型并求解的过程； 非线性规划：当目标函数和约束条件有一个或多个是设计变量的非线性函数时，列出这种表达式并求解的过程。,3.2 优化设计的基本概念,函数的方向导数与梯度 偏导数： 一元函数中的导数：描述函数相对于自变量的变化率； 多元函数中的偏导数：描述函数只相对于其中一个自变量(其余自变量保持不变)的变化率。 对n函数，函数在 处沿各坐标轴的一阶偏导数或变化率分别为：,3.2 优化设计的基本概念,函数的方向导数与梯度 方向导数:函数在某点沿给定方向的变化率。,函数的方向导数,式中:cos，cos为某方向S的方向余弦,n元函数在点x0处沿S方向的方向导数 上式表明了方向导数与偏导数之间的数量关系 方向导数是偏导数概念的推广 方向导数表明了函数F(X)在点X(0)沿S方向的变化率，它是一个标量 + : 函数F(X)在X(0)点处沿S方向是增加的 - : 函数F(X)在X(0)点处沿S方向是减小的,3.2 优化设计的基本概念,函数的方向导数与梯度 梯度 二元函数的梯度,为函数F(x1，x2)在X0点处的梯度,梯度的模：,设:,由上式可见：梯度方向和h 方向重合时，方向导数值最大。,梯度方向是函数值变化最快的方向，而梯度的模就是函数变化率的最大值 。,梯度方向与等值线的关系,因：,则有,为单位方向向量。,多元函数的梯度,梯度 模： 函数的梯度方向与函数等值面相垂直，也就是和等值面上过x0的一切曲线相垂直。 由于梯度的模因点而异，即函数在不同点处的最大变化率是不同的。因此，梯度是函数的一种局部性质。,求函数 在点3,2T 、2,0T的梯度 解 在点x(1)=3,2T, x(2)=2,0T处的梯度为：,若函数在某点取得极值，则该点的所有一阶偏导数必定为零，即梯度为零,3.2 优化设计的基本概念,无约束目标函数的极值条件 一元函数的极值 必要条件：F（x）连续可微, 充分必要条件：F（x）单值连续可微，若,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)及01,恒有： 则 F (X)为定义在凸集D上的一个凸函数 几何意义为：这两个点的连线完全处在F(X)曲线(曲面)的上方，或在F (X)。曲线(曲面)上,凸函数的判别方法,F(X)在D1连续一阶可导，而D是D1内的一个凸集(D1D)，对任意两点 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一维搜索方法,0618法：又称黄金分割法 试探法 单谷(峰）区间:在给定区间内仅有一个谷值(极大或极小)的函数称为单峰函数，其区间称为单谷区间. 单峰函数的特点：函数值:”大小大”，图形：“高低高”,单谷区间中一定能求得一个极小点. 试探法原理： F(X)在区间a,b是单峰凸函数，为缩小该区间，在中间任取两点a1, a2。比较F(a1), F(a2)的大小，即可缩小搜索区，从而精确估出 的位置。,(1)如F(a1)F(a2)，则缩小的新区间为a1,b; (3)如F(a1) = F(a2), 则缩小的新区间为a1, a2,消去原则：消除大函数值一边的区间。,3.3一维搜索方法,0618法：又称黄金分割法 0618法 黄金分割律：是公元前六世纪，希腊的大数学家毕达哥拉斯发现的：如果把一条线段分成两部分，长段和短段的长度之比是1:0.618，整条线段和长段的比也是1:0.618时，才是和黄金一样最完美的分割，进行分割的这个点就叫黄金分割点 基本思想:在待定的单峰区间内，不断消去一部分区间，把区间越缩越小，且每次区间缩短率都相等，新区间长度为原区间长度的0.618，直到极小点所在的区间小至满足精度要求，再取最后区间的中点作为近似最优点。 对函数的要求：单峰.,将区间分成三段,黄金分割法还要求在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布。,3.3一维搜索方法,插值法(二次插值法，亦称抛物线法) 基本思想：在选定的单峰区内取一点，连同两端点，用这三点函数值构成一个二次多项式，做原函数的近似，求出该二次多项式的极小值做原函数的近似最优值。,1、二次多项式 P(x) 的构成及其极小点 设原目标函数的初始单峰区间为x1, x3 。函数在x1, x2, x3 3点处函数值分别为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，再进行二次插值。 选点要求： x1F2，F2F3 （高低高形态） 如果 ，以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转入步骤3,3.5 有约束优化设计的方法,直接法与间接法：前者设法使每次迭代点在可行域内；后者将约束问题通过一定形式的变换，转化成无约束问题。 复合形法 基本思想：在可行域内选k个设计点，作为初始复合形的顶点，构成一个多面体。经各顶点比较，找出目标函数最大的为坏点，按一定规则以新点代替坏点，构成新的多边形。多次重复，使复合性向最优点靠近，最后以顶点中目标函数最小的做最优点。,3.5有约束优化设计的方法,复合形法 顶点数目：为克服退化顶点数n+1k2n。 以二维函数为例：3k4。 具体方法： 三个复合形顶点构成一个三角形，Xh是最坏点，Xc是除最坏点外的形心，沿Xh，Xc方向取Xr为映射点Xr=Xc+a(Xc-Xh),映射系数=1.3。 首先检查Xr是否在可行域内，若不在将减半再检查，直至退入可行域； 再检查函数值，若F(Xr)F(Xh)以新点代替坏点，否则将减半再检查，直至满足上式。若减至很小，则依次坏点代替坏点进行映射。直至复合形收缩到规定的精度范围内。,迭代步骤,产生初始复合形 对顶点的要求：在可行域内；在k个点中至少有n+1个线性无关（n+1k 2n）。 顶点的产生：简单的可在可行域内任意选取；复杂的需用随机方法：选一个初始点 , 其余点: j为复合形顶点的标号2，k； i为设计变量的标号1，n。设计变量的解域 ji为0，1间的伪随机数。 然后检查各顶点是否在可行域内，不满足则向形心靠拢。,迭代步骤,寻找映射点 找出最坏点Xh，求出其余各点的形心Xc。 获得映射点,检查其可行性，不满足则减半。,迭代步骤,比较函数值构成新复合形 F(Xr)F(Xh)，用映射点代替坏点转向2 。 F(Xr)F(Xh)，将减半，直至满足。若过小(10-5 )，用次坏点代替坏点。 终止迭代：若 取顶点中目标函数最小者为最优点。 。,3.5 有约束优化设计的方法,罚函数法 基本思想：把一个有约束的问题转