现代设计理论与方法优化设计ppt课件.ppt

第2章 优化设计,主要内容：了解优化设计；会建立优化设计的数学模型；了解优化设计的数学基础知识；掌握一维优化方法；了解多维优化方法。,2.1 概述,2.1.1 优化设计的概念,优化设计是借助最优化数值计算方法和计算机技术，求取工程问题的最优设计方案。即：进行最优化设计时，首先必须将实际问题加以数学描述，形成一组由数学表达式组成的数学模型，然后选择一种最优化数值计算方法和计算机程序，在计算机上运算求解，得到一组最佳的设计参数。,2.1.2 优化设计的一般过程,机械设计的全过程一般可分为：,1.设计问题分析2.建立优化设计的数学模型。3.选择适当的优化方法。4.编写计算机程序，计算择优。,2.1.3 优化设计的数学模型,1、建立数学模型的基本原则,数学模型的建立要求确切、简洁的反映工程问题。,2、数学模型的三要素 设计变量、目标函数、约束条件。,1）设计变量,应注意各设计变量应相互独立，否则会给优化带来困难。,2.1.3 优化设计的数学模型,设计变量是指在设计过程中可以进行调整和优选的独立参数。（1）设计变量的选择：应该选择那些与目标函数和约束函数密切相关的，能够表达设计对象特征的基本参数。,2.1.3 优化设计的数学模型,（2）设计变量的分类连续变量 可以在实数范围内连续取值的变量。离散变量 只在给定数列或集合中取值的变量。,1）设计变量,2.1.3 优化设计的数学模型,1）设计变量,（3）设计空间 若n个设计变量x1,x2,xn相互独立，则由它们形成的向量X=x1,x2,xnT的全体集合构成的一个n维实欧氏空间，称为设计空间，记Rn。设计变量的个数n称为优化设计的维数。1）如n=2就是二维设计问题，可用平面直角坐标来表示；2）如n=3就是三维设计问题，可用空间直角坐标来表示；3）如n大于3就是超越空间。,2.1.3 优化设计的数学模型,1）设计变量,（3）设计空间,二维设计平面 三维设计空间,2.1.3 优化设计的数学模型,2）目标函数,目标函数是通过设计变量来表示的设计所追求目标的数学表达式，又称为标量函数。（1）目标函数的意义 目标函数值的大小是衡量设计方案优劣的定量标准。目标函数的值越小，对应的设计方案越好。因此，目标函数的最小值及其对应的设计变量的取值称为设计问题的最优解。,目标函数的一般表示式为：,2.1.3 优化设计的数学模型,2）目标函数,（2）目标函数的选择 必须针对具体问题，选择主要的技术指标作为设计的目标函数，如：利润、体积、重量、功率等。,（3）等值面和等值线 对于简单的问题，可用等值线或等值面来描述函数的变化趋势，还可以直观地给出极值点的位置。目标函数等值线（面），其数学表达式为：f（X）=c。在这种线或面上所有点的函数值均相等，因此，这种线或面称为函数的等值线或等值面。当c取一系列不同的常数值时，可以得到一组形态相似的等值线或等值面，称为函数的等值线簇或等值面簇。,2.1.3 优化设计的数学模型,2）目标函数,a）当n=2时，该点集是设计平面中的一条直线或曲线；b）当n=3时，该点集是设计空间中的一个平面或曲面；c）当n大于3时，该点集是设计空间中的一个超曲面。,（3）等值面和等值线,2.1.3 优化设计的数学模型,2）目标函数,目标函数f（X）一60 x1一120 x2的等值线簇。,（3）等值面和等值线,2.1.3 优化设计的数学模型,2）目标函数,函数：f（X）xl2十x22一4x1十4的图形(旋转抛物面)。用平面f（X）c切割该抛物面所得交线在设计空间中的投影，就是目标函数的等值线。,（3）等值面和等值线,2.1.3 优化设计的数学模型,2）目标函数,约束条件的作用：就是对设计变量的取值加以限制。,2.1.3 优化设计的数学模型,3）约束条件,对任何设计都有若干不同的要求和限制，将这些要求和限制表示成设计变量的函数并写成一系列不等式和等式表达式，就构成了设计的约束条件，简称设计约束。,2.1.3 优化设计的数学模型,3）约束条件,（1）约束条件的分类 a）约束条件根据形式不同分为不等式约束和等式约束。一般表示为：,b）根据性质不同分为边界约束和性能约束。边界约束：考虑了设计变量变化的范围，是对设计变量本身所加的直接限制。比如：ai-xi0 xi-bi0 性能约束：是根据设计性能或指标要求而定的一种约束条件。是对设计变量加的间接变量。例如：零件的强度条件，刚度条件，稳定性条件均属于性能约束。,2.1.3 优化设计的数学模型,3）约束条件,（1）约束条件的分类,约束边界,2.1.3 优化设计的数学模型,3）约束条件,（2）可行域 每一个不等式或等式约束都将设计空间分为两个部分，满足所有约束的部分形成一个交集，该交集称为此约束问题的可行域，记作D。可行域就是满足所有约束条件的设计点的集合，因此，可用集合式表示如下：,2.1.3 优化设计的数学模型,3）约束条件,（2）可行域,2.1.3 优化设计的数学模型,3）约束条件,此约束的可行域是由约束边界线围成的封闭五边形：OABCD,（2）可行域,2.1.3 优化设计的数学模型,3）约束条件,2.1.3 优化设计的数学模型,优化设计问题的的数学模型一般数学表达式为：,3、优化设计数学模型建立实例 例1：有一块边长为6m的正方形铝板，四角各裁去一个小的正方块，做成一个无盖的盒子。试确定裁去的四个小正方块的边长，以使做成的盒子具有最大的容积。解：设裁去的四个小正方块的边长为x，则盒子的容积可表示成x的函数F（X）x(6-2x)2,2.1.3 优化设计的数学模型,3、优化设计数学模型建立实例,2.1.3 优化设计的数学模型,变量 x 设计变量 f（X）x(6-2x)2 目标函数 g1（X）x 0 g2（X）x 3 约束条件使容积最大，即使f（X）=-x(6-2x)2 最小,3、优化设计数学模型建立实例,2.1.3 优化设计的数学模型,min f（X）=-x(6-2x)2 s.t.g1（X）-x 0 g2（X）x 3,例2：平面连杆机构的优化设计 曲柄摇杆机构再现已知运动规律的优化设计,3、优化设计数学模型建立实例,2.1.3 优化设计的数学模型,1）设计变量的确定,决定机构尺寸的各杆长度，以及当摇杆按已知运动规律开始运动时，曲柄所处的位置角0 为设计变量。,3、优化设计数学模型建立实例,2.1.3 优化设计的数学模型,2）目标函数的建立,目标函数可根据已知的运动规律与机构实际运动规律之间的偏差最小为指标来建立，即,3、优化设计数学模型建立实例,2.1.3 优化设计的数学模型,3）约束条件的确定,（1）曲柄摇杆机构满足曲柄存在的条件,3、优化设计数学模型建立实例,2.1.3 优化设计的数学模型,（2）若要求最小传动角应在 和 间，可得,3、优化设计数学模型建立实例,2.1.3 优化设计的数学模型,3）约束条件的确定,设计变量的确定,考虑到机构的杆长按比例变化时，不会改变其运动规律，因此在计算时常取l1=1，而其他杆长按比例取为l1 的倍数。,3、优化设计数学模型建立实例,2.1.3 优化设计的数学模型,1、按是否包含有约束条件分：无约束优化问题和约束优化问题。、按设计变量的多少可分：单变量优化和多变量优化。、按目标函数和约束函数的性质可分：线性规划和非线性规划。,2.1.4 优化问题的分类,1、图解法：用直接作图的方法来求解优化问题。在设计平面作出约束可行域，画出目标函数的一簇等值线，根据等值线与可行域的相互关系确定出最优点的位置。特点：优点：直观。缺点：一般仅限于求解n2的低 维优化问题。,2.1.5 优化问题数学模型的求解方法,图解法 数学解析法 数值迭代法,1）图解法的求解的步骤（1）确定设计空间；（2）作出约束可行域；（3）画出目标函数的一簇等值线；（4）最后判断确定最优点。,2.1.5 优化问题数学模型的求解方法,2.1.5 优化问题数学模型的求解方法,目标函数：f（X）一60 x1一120 x2,2）图解法的求解实例,约束条件：,生产甲产品一件获利60元，生产乙产品一件获利120元，受条件约束，如何安排生产可获最大利润？,此约束的可行域是由约束边界线围成的封闭五边形：OABCD,可行域,2.1.5 优化问题数学模型的求解方法,2）图解法的求解实例,2.1.5 优化问题数学模型的求解方法,2）图解法的求解实例,目标函数f（X）一60 x1一120 x2的等值线簇。,其可行域与目标函数的等值线图叠加在一起。求解得：每天生产甲产品20件，乙产品24件，可获最大利润4080元。,2.1.5 优化问题数学模型的求解方法,2）图解法的求解实例,2.1.5 优化问题数学模型的求解方法,2）图解法的求解实例,f（X）xl2十x22一4x1十4,等值面和等值线,目标函数,2.1.5 优化问题数学模型的求解方法,2）图解法的求解实例,2.1.5 优化问题数学模型的求解方法,2）图解法的求解实例,2.1.5 优化问题数学模型的求解方法,2）图解法的求解实例,图解法只适用于一些很简单的优化问题，所以实用意义不强。,2.1.5 优化问题数学模型的求解方法,2、数学解析法：把优化对象用数学模型描述出来后，用微分等方法求出最优解 数学解析法也只适用于一些维数较少，易于求导的优化问题。,2.1.5 优化问题数学模型的求解方法,例1：有一块边长为6m的正方形铝板，四角各裁去一个小的正方块，做成一个无盖的盒子。试确定裁去的四个小正方块的边长，以使做成的盒子具有最大的容积。,2.1.5 优化问题数学模型的求解方法,1）数学解析法求解实例,min f（X）=-x(6-2x)2 s.t.g1（X）-x 0 g2（X）x 3,2.1.5 优化问题数学模型的求解方法,1）数学解析法求解实例,例1：有一块边长为6m的正方形铝板，四角各裁去一个小的正方块，做成一个无盖的盒子。试确定裁去的四个小正方块的边长，以使做成的盒子具有最大的容积。,变量 x 设计变量 f（X）x(6-2x)2 目标函数 g（X）x 0 g（X）x x0 x=1 为所求解。,2.1.5 优化问题数学模型的求解方法,1）数学解析法求解实例,3、数值迭代法：,2.1.5 优化问题数学模型的求解方法,工程优化问题的目标函数和约束条件比较复杂，数值迭代法是优化设计问题的基本解法。数值迭代法的基本思路：进行反复的数值计算，寻求函数值不断下降的可行计算点，直到最后获得足够精度的近似解。,3、数值迭代法：,2.1.5 优化问题数学模型的求解方法,沿某个搜索方向S（k）以适当的步长（k）实现对X（k）的修正。,1）寻求极值点的搜索过程,3、数值迭代法：,2.1.5 优化问题数学模型的求解方法,1）寻求极值点的搜索过程,迭代法要解决的问题：（1）选择搜索方向（2）确定步长因子（3）给定终止准则,3、数值迭代法：,2.1.5 优化问题数学模型的求解方法,2）迭代计算的终止准则,(1)点距足够小准则,(2)函数值下降量足够小准则,(3)函数梯度充分小准则,2.2.1 二次型与正定矩阵,2.2 优化方法的数学基础,1.二次型函数,二次函数是最简单的非线性函数，可以写成以下向量形式：,称为二次型矩阵,称为二次型,2、正定与负定的判断 1）对所有非 0 向量 X,若：XTAX 0，则称矩阵 A 是正定矩阵；XTAX 0，则称矩阵 A 是半正定矩阵；XTAX 0，则称矩阵 A 是负定矩阵；XTAX 0，则称矩阵 A 是半负定矩阵；XTAX=0，则称矩阵 A 是不定矩阵。,2.2.1 二次型与正定矩阵,2、正定与负定的判断 2）若：矩阵A 的各阶主子式均大于零，,2.2.1 二次型与正定矩阵,即:一阶主子式,二阶主子式,n 阶主子式 0 则矩阵A 是正定的。,2、正定与负定的判断 2）若：矩阵A 的各阶主子式负正相间，,2.2.1 二次型与正定矩阵,即:一阶主子式,二阶主子式,即：奇数阶主子式小于0，偶数阶主子式大于0，则矩阵A 是负定的。,3、正定二次函数具有以下性质：1）正定二次函数的等值线或等值面是一簇同心椭圆或同心椭球，其中心就是该二次函数的极小值。2）非正定二次函数的极小值附近的等值线或等值面近似于椭圆或椭球。,2.2.1 二次型与正定矩阵,2.2.2 函数的方向导数和梯度,1、函数的方向导数,讨论函数 在一点P沿某一方向的变化率问题,1）方向导数的定义,2.2.2 函数的方向导数和梯度,1、函数的方向导数,1）方向导数的定义,且,的方向导数。,沿方向,则称这极限为函数在点,在，,时，如果此比的极限存,趋于,沿着,当,之比值，,两点间的距离,与,函数的增量,l,P,P/,l,P,P/,P,记为,2.2.2 函数的方向导数和梯度,1、函数的方向导数,1）方向导数的定义,2）方向导数的计算,定理如果函数,在点,是可微分,的，那么函数在该点沿任意方向,l,的方向导数都,存在，则有,2.2.2 函数的方向导数和梯度,1、函数的方向导数,2.2.2 函数的方向导数和梯度,1、函数的方向导数,推广可得三元函数方向导数的定义,其中,2.2.2 函数的方向导数和梯度,1、函数的方向导数,推导出n元函数f（X）在点X(k)处沿任意给定方向S的方向导数的表达式为：,2.2.2 函数的方向导数和梯度,1、函数的方向导数,1）梯度的定义 函数在点X(k)的梯度是由函数在该点的各个一阶偏导数组成的向量。2）梯度的表达式,2.2.2 函数的方向导数和梯度,2、梯度,2）梯度的表达式,2.2.2 函数的方向导数和梯度,2、梯度,2）梯度的表达式,2.2.2 函数的方向导数和梯度,2、梯度,2.2.2 函数的方向导数和梯度,2、梯度,等高线,梯度为等高线上的法向量,2.2.2 函数的方向导数和梯度,2、梯度,与梯度成锐角的方向是函数值上升的方向，而与梯度成钝角的方向则是函数值下降的方向。,2.2.2 函数的方向导数和梯度,2、梯度,2.2.2 函数的方向导数和梯度,2、梯度,例1 求函数f(X)(x12)2十(x21)2在点X(1)3,2T和X(2)2,2 T的梯度并作图表示。解：根据定义，梯度为,则,2.2.2 函数的方向导数和梯度,解：梯度的模为：,单位梯度的向量为：,2.2.2 函数的方向导数和梯度,在设计平面x1ox2内标出点(2,2)和点(0,2)，并将此两点分别与原点相连得到向量2,2T和 0,2T。将这两个向量各自平移至点X(1)和X(2)，所得新的向量就是点X(1)和X(2)的梯度。,2.2.2 函数的方向导数和梯度,2.2.3 多元函数的泰勒展开,由高等数学知，一元函数f(x)若在点x（k）的邻域内n阶可导，则函数可在该点的邻域内作如下泰勒展开：,多元函数f(x)在x（k）点也可以作泰勒展开,其展开式一般取三项,其形式与一次函数的形式的前三项是相似的.,写成矩阵形式：,式中,称为f(x)的海森(Hessian)矩阵，常用H(X(k)表示。,2.2.3 多元函数的泰勒展开,f(x)的海森(Hessian)矩阵，常用H(X(k)表示。,2.2.3 多元函数的泰勒展开,由于n元函数的偏导数有nn个，而偏导数得值与求导次序无关，所以函数的二阶偏导矩阵是对称矩阵。,例：一般二元二次函数,，求H(X)。,解：,2.2.3 多元函数的泰勒展开,例：一般二元二次函数,，求H(X)。,2.2.3 多元函数的泰勒展开,例2:用泰勒展开的方法将函数 f(X)x13-x23+3 x12+3 x22-9x1在 点X(1)=1,1T 简化成二次函数。,2.2.3 多元函数的泰勒展开,式中,例2:用泰勒展开的方法将函数 f(X)x13-x23+3 x12+3 x22-9x1在 点X(1)=1,1T 简化成二次函数。,解：(1)求函数在点X(1)的函数值、梯度：,2.2.3 多元函数的泰勒展开,(2)求得二阶导数矩阵为：而且,例2:用泰勒展开的方法将函数 f(X)x13-x23+3 x12+3 x22-9x1在 点X(1)=1,1T 简化成二次函数。,2.2.3 多元函数的泰勒展开,例2:用泰勒展开的方法将函数 f(X)x13-x23+3 x12+3 x22-9x1在 点X(1)=1,1T 简化成二次函数。,2.2.3 多元函数的泰勒展开,(3)得到泰勒展开式的二次项为：,例2:用泰勒展开的方法将函数 f(X)x13-x23+3 x12+3 x22-9x1在 点X(1)=1,1T 简化成二次函数。,2.2.3 多元函数的泰勒展开,式中,例2:用泰勒展开的方法将函数 f(X)x13-x23+3 x12+3 x22-9x1在 点X(1)=1,1T 简化成二次函数。,2.2.3 多元函数的泰勒展开,代入泰勒展开式得简化的二次函数：,2.2.4 无约束优化问题的极值条件,由高数知识知：任一单值、连续可导的一元函数在某点取得极值的条件是：函数在该点的一阶导数为0，当二阶导数不等于0。当二阶导数大于0，函数在该点有极小值；当二阶导数小于0，函数在该点有极大值。,多元函数在点X(k)取得极小值的条件是：函数在该点的梯度为零，二阶导数矩阵为正定。即,例1：试求f(x1,x2)2x12-8x1+2x22-4x2+20 的极值及极值点。解：由极值点存在的必要条件,得驻点X*=2，1T,在X*点海森矩阵为：,2.2.4 无约束优化问题的极值条件,由于其各阶主子行列式为,可知在X*点海森矩阵正定的，所以，X*为极小点，其极小值为：,例1：试求f(x1,x2)2x12-8x1+2x22-4x2+20 的极值及极值点。,2.2.4 无约束优化问题的极值条件,2.2.5 约束优化问题的极值条件,2.2.5 约束优化问题的极值条件,1.等式约束的极值条件,建立拉格朗日函数：,2.2.5 约束优化问题的极值条件,2.不等式约束的极值条件,加入松弛变量：,2.2.5 约束优化问题的极值条件,2.不等式约束的极值条件,2.3 一维优化方法,一维搜索法：就是一元函数极小化的数值迭代算法，其求解过程称一维搜索。一维搜索法是构成非线性优化方法的基本算法，因为多元函数的迭代解法可归结为在一系列逐步产生的下降方向上的一维搜索。,2.3 一维优化方法,采用数学规划法求函数极值点的迭代计算：,K+1次迭代的搜索方向,搜索的最佳步长因子,就是求一元函数的极值。,称为一维搜索。,是优化搜索方法的基础。,当搜索方向 给定，求最佳步长,2.3 一维优化方法,一维搜索法一般分两步：1）确定初始搜索区间，该区间应是包括一维函数极小点在内的单峰区间；2）在搜索区间内寻找极小点。,在函数的任一单峰区间上必存在一个极小点，而且在极小点的左侧，函数呈下降趋势，在极小点的右侧函数呈上升趋势。,1、进退法的定义 在某一方向上按一定方式逐次产生一些探测点，并比较这些探测点上函数值的大小，就可以找出函数值呈“大-小-大”变化的三个相邻点，其中两端点所确定的闭区间必定包含着极小点，这样的区间称为初始区间，记作a,b。这种寻找初始区间的方法称为进退法。,2.3.1 搜索区间的确定,2.3.1 搜索区间的确定,2、进退法确定搜索区间的方法 在函数的任一单峰区间上必存在一个极小点，而且在极小点的左侧，函数呈下降趋势，在极小点的右侧函数呈上升趋势。若已知方向S(k)上的三点x1x2x3及其函数值f(x1)、f(x2)和f(x3)，便可通过比较三个函数值的大小估计出极小点所在的位置。,极小点的估计,2.3.1 搜索区间的确定,2.3.1 搜索区间的确定,3、进退法确定搜索区间的运算步骤：1）给定初始点 a0和初始步长 h；2）确定试算点和对应函数值；3）比较试算点的函数值，确定搜索方向和区间；若f(a0)f(a0+h)，则说明极小点在试算点的右侧；需要进行前进试算；若f(a0)f(a0+h)，则说明极小点在试算点的右侧；需要进行后退试算；直到满足单峰区间条件为止。,例1：用进退法法求 的初始区间，设初始点，初始步长。解：用进退法确定初始区间：比较，因 作前进运算：,2.3.1 搜索区间的确定,因，则：,2.3.1 搜索区间的确定,因，作前进运算：,初始,因，结束迭代，输出：,2.3.1 搜索区间的确定,故初始搜索区间为：,假定：已经确定了单峰区间a,b,新搜索区间为a,x2,新搜索区间为x1,b,5.3.2 黄金分割法,区间缩小比例的确定：,黄金分割法又称0.618法。,5.3.2 黄金分割法,1、定义 黄金分割法：又称0.618法，是一种通过不断缩小区间得到极小点的一维搜索算法。,5.3.2 黄金分割法,2、基本过程：1）给出a,b,使得x*在a,b中。2）迭代缩短a,b的长度。3）当a,b的长度小于某个预设的值，或者其他终止条件时，则迭代终止。,确定a,b,计算探索点x1=a+0.382(b-a)x2=a+0.618(b-a),0.618法解题步骤：,停止,以a,x2为新的搜索区间,停止,以x1,b为新的搜索区间,5.3.2 黄金分割法,例：,解：,1)、第一轮：x1=a+0.382(b-a)=1.146x2=a+0.618(b-a)=1.854,x2-00.5,5.3.2 黄金分割法,2)、第二轮：x1=a+0.382(b-a)=0.708x2=1.146,x2-0=1.1460.5,1.854,x2,x1,x1=a+0.382(b-a)=1.146x2=a+0.618(b-a)=1.854,5.3.2 黄金分割法,1.146,x2,x1,3)、第三轮：x1=a+0.382(b-a)=0.438,x2=0.708,b-x1=1.146-0.4380.5,x1=a+0.382(b-a)=0.708x2=1.146,5.3.2 黄金分割法,4)、第四轮：x1=0.708 x2=a+0.618(b-a)=0.876,b-x1=1.146-0.7080.5,输出：x*=0.927为最优解，最优值为-0.0574。,0,1.146,x,x1,x2,x1=a+0.382(b-a)=0.438,x2=0.708,5.3.2 黄金分割法,2.3.3 二次插值法,1、定义：二次插值法又称抛物线法，它是以目标函数的二次插值函数的极小点作为新的中间插入点，进行区间缩小的一维搜索算法。,二次插值的基本思想是：利用目标函数在不同3点的函数值构成一个与原函数f(x)相近似的二次多项式p(x)，以函数p(x)的极值点 作为目标函数f(x)的近似极值点。,2.3.3 二次插值法,二次插值的基本思想是：利用目标函数在不同3点的函数值构成一个与原函数f(x)相近似的二次多项式p(x)，以函数p(x)的极值点 作为目标函数f(x)的近似极值点。,2.3.3 二次插值法,1、定义：二次插值法又称抛物线法，它是以目标函数的二次插值函数的极小点作为新的中间插入点，进行区间缩小的一维搜索算法。用f(x)在2 或3 个点的函数值或导数值，构造2 次或3次多项式作为f(x)的近似值，以这多项式的极小点为新的迭代点。3点2次，2点2次，3点3次，2点3次等 以3点2次为例：取x 1，x 2，x3，求出f(x1)，f(x2)，f(x3),2、二次多项式 p(x)的构成及其极小点 设原目标函数的初始单峰区间为x1,x3。函数在x1,x2,x33点处函数值分别为f1,f2,f3，通过（x1，f1）、（x2，f2）、（x3，f3）3点构造一个二次插值函数p(x).,2.3.3 二次插值法,2、二次多项式 p(x)的构成及其极小点 p(x)=A+Bx+Cx2一阶导为0时，极小值点xp*，xp*=-B/2 C,2.3.3 二次插值法,2.3.3 二次插值法,3、进行终止判断，若未终止，缩小区间,2.3.3 二次插值法,3、进行终止判断，若未终止，缩小区间,2.3.3 二次插值法,3、进行终止判断，若未终止，缩小区间,2.3.3 二次插值法,4、特点：1）二次插值法的中间插入点包含了函数在三个点上的函数值信息，因此这样的插入点比较接近函数的极小值。2）当收敛终止准则成立时，把 Xp作为此次一维搜索的极小点。,2.3.3 二次插值法,例：用二次插值法求函数f(x)=3x3-4x+2的极小值点，给定x0=0,h=1,=0.2。,解：1）确定初始区间,由于，应继续向前探测，,由于,a,b=0,2,可知初始区间已经找到,2.3.3 二次插值法,解：已经确定初始区间a,b=0,2,另取一中间点x2=1。,2）用二次插值法逼近极小点 相邻三点的函数值:x1=0,x2=1,x3=2;f1=2,f2=1,f3=18.,例：用二次插值法求函数f(x)=3x3-4x+2的极小值点，给定x0=0,h=1,=0.2。,2.3.3 二次插值法,2）用二次插值法逼近极小点 相邻三点的函数值:x1=0,x2=1,x3=2;f1=2,f2=1,f3=18.带入公式：,2.3.3 二次插值法,2）用二次插值法逼近极小点 相邻三点的函数值:x1=0,x2=1,x3=2;f1=2,f2=1,f3=18.,故新区间：,2.3.3 二次插值法,由于，故应继续作第二次插值计算。在新的区间内，相邻三点及其函数值依次为：将它们代入式，得,2.3.3 二次插值法,由于，,新区间,2.3.3 二次插值法,新区间,故一维搜索到此结束，极小点和极小值为：,2.4 多维优化方法,多维优化方法是进行多变量优化设计的数值迭代法。它包括了无约束优化方法和约束优化方法两种。1、无约束优化问题的一般形式：求解设计变量：X=x1,x2,xnT,XRn 满足目标函数minf(X)的无约束最优化解X*和最优化函数minf(X*)。,2.4 多维优化方法,2、无约束优化的分类 根据搜索方向的不同构成形式，可分类以下两类：,1）导数法：利用目标函数的一阶和二阶导数信息构成搜索方向的算法，称为导数法，如梯度法等。注：其收敛性和收敛速度都比较好的。2）模式法：通过几个已知点上函数值的比较构造搜索方向的算法。如鲍威尔法。对于较复杂的目标函数优化是有利的。,2.4 多维优化方法,3、约束优化方法 minf(X)s.t.gu(X)0(u=1,2,m)hv(X)=0(v=1,2,pn),为什么要研究多维无约束优化问题?(1)、有些实际问题，其数学模型本身就是一个多维无约束优化问题。(2)、通过熟悉它的解法可以为研究多维约束优化问题打下良好的基础。(3)、多维约束优化问题的求解可以通过一系列多维无约束优化方法来达到。所以多维无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。,2.4 多维优化方法,2.4.1 坐标轮换法,坐标轮换法是每次搜索只允许一个变量变化，其余变量保持不变，即沿坐标方向轮流进行搜索的寻优方法。,它把多变量的优化问题轮流地转化成单变量的优化问题。,因此又称变量轮换法。,2.4.1 坐标轮换法,其基本原理是将一个多维的无约束最优化问题转化为一系列较低维的最优化问题来求解，简单地说，就是先将(n-1)个变量固定不动，只对第一个变量进行一维搜索得到最优点x1（1）。然后，又保持(n-1)个变量不变，再对第二个变量进行一维搜索到x2（1）等等。,1.搜索方向与步长的确定,（1）搜索方向的确定,对于第k轮第i次的计算,第k轮第i次的迭代方向，它轮流取n维坐标的单位向量。,2.4.1 坐标轮换法,(2)搜索步长的确定,关于 值通常有以下几种取法（1）加速步长法（2）最优步长法,1.搜索方向与步长的确定,2.4.1 坐标轮换法,2.4.2 鲍威尔法,鲍威尔（Powell）法是直接利用函数值来构造共轭方向的一种方法。,2.4.2 鲍威尔法,二维情况描述鲍威尔的基本算法:,1）任选一初始点x0及两个线性无关的向量，如坐标轴单位向量e1=1,0T和e2=0,1T作为初始搜索方向。,2）从x0出发，顺次沿e1，e1作一维搜索，得 点，两点连线得一新方向S1,2.4.2 鲍威尔法,二维情况描述鲍威尔的基本算法:,1.共轭方向的生成,再从 出发，沿S1作一维搜索得点，完成第一次搜索，末点作为下一轮迭代的初始点。用 S1代替e1形成两个线性无关向量S1,e2，作为下一轮迭代的搜索方向。并把新方向放最后。,3）从 出发，顺次沿e2,S1 作一维搜索，得到点，两点连线得一新方向:S2,2.4.2 鲍威尔法,二维情况描述鲍威尔的基本算法:,1.共轭方向的生成,沿S2作一维搜索得点x2，完成第二次搜索。,即是二维问题的极小点x*.,把二维情况的基本算法扩展到n维，则鲍威尔基本算法的要点是：在每一轮迭代中总有一个始点（第一轮的始点是任选的初始点）和n个线性独立的搜索方向。从始点出发顺次沿n个方向作一维搜索得一终点，由始点和终点决定了一个新的搜索方向,按此方向搜索，完成第一轮搜索。用这个方向替换原来n个方向中的一个，于是形成新的搜索方向组。替换的原则是去掉原方向组的第一个方向而将新方向排在原方向的最后。此外规定，从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭代的始点。这样就形成算法的循环。,2.4.2 鲍威尔法,因为在迭代中的n个搜索方向有时会变成线性相关而不能形成共轭方向。这时张不成n维空间，可能求不到极小点，所以上述基本算法有待改进。,2.改进的算法,在鲍威尔基本算法中，每一轮迭代都用连结始点和终点所产生出的搜索方向去替换原向量组中的第一个向量，而不管它的“好坏”，这是产生向量组线性相关的原因所在。,2.4.2 鲍威尔法,2.改进的算法,在改进的算法中首先判断原向量组是否需要替换。如果需要替换，还要进一步判断原向量组中哪个向量最坏，然后再用新产生的向量替换这个最坏的向量，以保证逐次生成共轭方向。,2.4.2 鲍威尔法,2.4.2 鲍威尔法,为此，要解决两个关键问题：（1）Sk1是否较好？是否应该进入新的方向组？即方向组是否进行更新？（2）如果应该更新方向组，Sk1不一定替换方向，而是有选择地替换某一方向。,2.改进的算法,令在k次循环中,分别称为一轮迭代的始点、终点和反射点。,2.4.2 鲍威尔法,2.改进的算法,2.4.2 鲍威尔法,则在循环中函数下降最多的第m次迭代是,记：,相应的方向为。,因此,2.改进的算法,则选用新方向Sk，并在第k+1迭代中用Sk替换对应于 的方向。否则，仍然用原方向组进行第k+1迭代。,2.4.2 鲍威尔法,为了构成共轭性好的方向组，须遵循下列准则：,在k次循环中，若满足条件：,和,2.改进的算法,1.定义 什么方向是函数下降最快的方向呢？答案是负梯度方向。梯度法又称最速下降法，是无约束优化方法中间接法的一种。其基本原理：是将一个多维无约束优化问题转化为一系列沿目标函数负梯度方向进行一维搜索寻优的一种方法，即是在每一迭代点，选取搜索方向 为负梯度方向：,2.4.3 梯度法,再沿 进行一维搜索，以确定步长因子，找到新的设计点 按照上述迭代公式进行若干次一维搜索，每次迭代的初始点取上次迭代的终点，即可使迭代点逐渐逼近目标函数的极小点。,2.4.3 梯度法,1.定义,2.4.3 梯度法,2 梯度法的特点 1）梯度法理论明确，程序简单，计算量和存储量较少，对初始点的要求不严格。2）负梯度方向不是理想的搜索方向，梯度法也不是一种理想的方法，梯度法的收敛速度并不快。这是因为最速下降方向仅仅是指某点的一个局部性质，一旦离开这点，就不能保证仍是最速下降方向了。3）梯度法的迭代全过程的搜索路线呈锯齿状。,2.4.3 梯度法,2 梯度法的特点 由于梯度法的相邻两次搜索方向的正交性决定的，故前几次迭代函数值下降较快，但以后的迭代下降越来越慢。,2.4.3 梯度法,2 梯度法的特点 由于梯度法的相邻两次搜索方向的正交性决定的，故前几次迭代函数值下降较快，但以后的迭代下降越来越慢。,所以，梯度法常与其它方法联合使用，即在迭代的第一步或前几步使用，当接近极小点时，改为用其它算法，以此加快收敛速度。,例：用梯度法求下列无约束优化问题，已知函数X(0)=1 1T，0.1。min 解：1）第一次迭代 求 令 则,2.4.3 梯度法,对这种简单的一元函数，可以直接用解析法对其求极小。,2.4.3 梯度法,2)第二次迭代因,2.4.3 梯度法,2)第二次迭代,2.4.3 梯度法,因 可知X(2)不是极小点，还应继续进行迭代。最后得此问题最优解为：,2.4.4 牛顿法,1、牛顿法 在xk邻域内用一个泰勒二次函数(X)来近似代替原目标函数，并将(X)的极小点作为对目标函数的一次近似值，若此值不满足收敛精度要求，则将其作为求优的下一次迭代的初始点。经多次迭代，使之逼近目标函数的极小点。,2.4.4 牛顿法,如果目标函数是正定二次函数，海森矩阵是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。,2.4.4 牛顿法,例 求目标函数 的极小点。,解 取初始点,2.4.4 牛顿法,例 求目标函数 的极小点。,带入得：函数极小值为0,例：求目标函数 的极小点。解:取初始点则初始点处函数值及梯度分别为,2.4.4 牛顿法,例：求目标函数 的极小点。初始点,沿负梯度方向进行一维搜索，有,为一维搜索最佳步长，应满足极值必要条件,2.4.4 牛顿法,算出一维搜索最佳步长,第一次迭代设计点位置和函数值,2.4.4 牛顿法,继续作下去，经10次迭代后，得到最优解,2.4.4 牛顿法,2.4.4 牛顿法,从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念。,2.4.4 牛顿法,修正牛顿法（阻尼牛顿法）,阻尼因子(K)，沿牛顿方向进行一维搜索的最佳步长，由下式求得：,牛顿法和阻尼牛顿法统称为牛顿型方法。这类方法的主要缺点是每次迭代都要计算函数的二阶导数矩阵，并对该矩阵求逆。这样工作量很大。特别是矩阵求逆，当维数高时工作量更大。,2.4.4 牛顿法,修正牛顿法（阻尼牛顿法）,2.4.5 变尺度法,1.DFP变尺度法（Davidon,Fletcher,Powell）,最优步长,搜索方向,2.4.5 变尺度法,1.DFP变尺度法,A（k）是需要构造nn的一个对称正定矩阵，,如Ak=I,则得到梯度法；,则得到阻尼牛顿法；,如,2.4.5 变尺度法,1.DFP变尺度法,A（k）是需要构造nn的一个对称正定矩阵，,当矩阵A(k)不断地迭代而能很好地逼近,时，就可以不再需要计算二阶导数和逆阵。,变尺度法的关键在于尺度矩阵A（k）的产生。,2.4.5 变尺度法,1.DFP变尺度法,2.4.5 变尺度法,1.DFP变尺度法,令：,则：,2.4.5 变尺度法,1.DFP变尺度法,若：,校正正定矩阵：,例：用DFP算法求下列问题的极值：,解：1）取初始点，为了按DFP法构造第一次搜寻方向S0，需计算初始点处的梯度,取初始变尺度矩阵为单位矩阵A0=I，则第一次搜寻方向为,2.4.5 变尺度法,沿S0方向进行一维搜索，得,为一维搜索最佳步长，应满足,得:,2.4.5 变尺度法,2）再按DFP法构造点x1处的搜寻方向S1，需计算,2.4.5 变尺度法,代入校正公式,2.4.5 变尺度法,=,=,2.4.5 变尺度法,第二次搜寻方向为,再沿S1进行一维搜索，得,2.4.5 变尺度法,为一维搜索最佳步长，应满足,得,梯度:,2.4.5 变尺度法,3）判断x2是否为极值点,海森矩阵:,梯度为零向量,海赛矩阵正定。可见点满足极值充要条件，因此为极小点。,DFP变尺度法的几点说明:,(1)、在变尺度法中对A(k)矩阵是有要求的。因为对于极小化问题，为了使搜索方向 为下降方向，需要使搜索方向S(k)与负梯度方向的夹角为锐角，即 所以A(k)必须为正定矩阵,2.4.5 变尺度法,(2)、每次迭代都能使目标函数值单调下降即为算法的连续稳定性.为了提高实际计算中的稳定性，通常采用“重置”的方法，即在n次迭代后重新设置单位矩阵.,DFP变尺度法的几点说明:,2.4.5 变尺度法,2）BFGS算法(Broyden-Fletcher-Gold frob-Shanno),DFP算法由于舍入误差和一维搜索不精确，有可能导致构造矩阵的正定性遭到破坏，以至算法不稳定。BFGS算法对于维数较高问题具有更好的稳定性。,2.4.5 变尺度法,3.5 约束优化方法,约束优化设计问题，其数学模型为,根据求解方式的不同，约束优化