机械优化设计ppt课件第三章一维优化方法.ppt

机械优化设计,太原科技大学张学良,第三章 一维优化方法,3.1 进退法确定初始搜索区间,欲求一元函数f(x)的极小点，首先必须确定极小点所在的区间，然后再不断缩小此区间，从而求得其极小点的数值近似解。所以，一维搜索包括两个内容：其一是确定包含有极小点的搜索区间，其二是缩短区间获得极小点。,一维搜索时，假设一元函数 f(x)具有凸性（单谷性），即在所考虑区间具有唯一的极小点 x*。,进退法的基本思想：按照一定规则试算若干个点，比较其函数值的大小，直到找到按“大小大”变化的单谷区间为止。,x1,x2,h0,2h0,x3,1.选择一个适当的初始步长 h=h0。,从任意点 x1 出发，以 x1 和 x2=x1+h 为两个试算点，计算两点处的函数值。,f1=f(x1)f2=f(x2),3.比较f1 和 f2 的大小,若 f1 f2，h 2h，继续做前进计算 x3=x2+h=x2+2 h0，并计算f3=f(x3),若 f1 f2，h-h，则做后退计算。x1与x2 进行置换:x1 x2，x2 x1f1 f2，f2 f1 x3=x2+h,x1,x2,x2,x1,x3,-h0,h0,4.比较f2 和 f3 的大小,若 f3 f2，则满足f1 f2 f3，对于前进计算，函数极小点必在区间x1,x3内，令 a=x1,b=x3，初始搜索区间a,b确定。,对于后退计算，函数极小点必在区间x3,x1内，令 a=x3,b=x1，初始搜索区间a,b确定。,若 f3 f2，对于前进计算，函数极小点还在 x3 右侧，放弃x1,作置换：x1 x2，x2 x3，f1 f2，f2 f3 h 2h，再取新点 x3=x2+h，并求 f3=f(x3)，返回 4。,对于后退计算，函数极小点还在 x3 左侧，放弃x1,作置换：x1 x2，x2 x3，f1 f2，f2 f3 h 2h，再取新点 x3=x2+h，并求 f3=f(x3)，返回 4。,3.2 黄金分割法,黄金分割法的基本原理,在目标函数的初始搜索区间a,b内任取两点x1、x2，且 x1 x2，计算 f1=f(x1)，f2=f(x2)。,比较f1 和 f2 的大小：,当 f1 f2 时，去掉（x2，b，保留a，x2 区间缩短为a，x2。作置换 b x2，新区间形成。,在新区间 a,b内如此反复进行，直至区间足够短，就可以找到最优点。,当 f1 f2 时，去掉a，x1)，保留x1，b 区间缩短为x1，b。作置换 a x1，新区间形成。,该方法的缺陷是：每次需要计算两个新点。,要提高计算效率，就得减少每次计算的点数，因此只能每次增加一个计算点，这就要求新区间与原区间满足一定的比例关系，所选的两个计算点在区间 a,b 内的位置应是对称的。,设区间 a,b的长度为1，即单位长度区间，在其上初取两对称点 x1、x2，且满足 a x2=X，a x1=1-X,计算 f1=f(x1)，f2=f(x2)，并比较 f1 和 f2 的大小。,当 f1 f2 时，去掉（x2，b，保留a，x2 区间缩短为a，x2。作置换 b x2，新区间a,b 形成，点 x1 留在新区间a,b 内。,那么 X 该取多大呢？,留在新区间a,b 内的点 x1 留应该相当于去掉的 x2 点在旧区间内的位置，因此应该满足如下关系：,ax2/ab=a x1/ax2,即 X/1=(1 X)/X,解得 X=0.618,若f1 f2，可以求得同样的值。,可见，新区间是原区间的0.618。所以称为0.618法或黄金分割法。,黄金分割法的计算步骤及算法框图（略）,举例：用黄金分割法求目标函数 f(x)=x2-5 x+2 的最优解。,3.3 二次插值法（抛物线法）,基本思想：在目标函数极小点所在区间内，利用三个点的函数值构造一个二次插值多项式(x)=ax2+b x+c 是来近似表达原目标函数f(x)，并用(x)的极小点x*近似代替f(x)的最优点x*。当这种近似代替不满足精度,要求时，按照一定规律缩短区间，并在新区间内重新构造三点二次插值多项式，再求其极小点。如此反复，直到满足精度要求为止。,在目标函数极小点所在区间内取三点x1=a，x2=(a+b)/2，x3=b，计算相应的目标函数值f 1、f 2、f 3，则应有,(x1)=a x1 2+b x1+c=f 1(x2)=a x2 2+b x2+c=f 2(x3)=a x3 2+b x3+c=f 3,解该线性方程组，可以得到a、b、c，并由此可以求得,x*=（x1+x3-d1/d2）/2 d1=(f3 f1)/(x3-x1）d2=(f2 f1)/(x2-x1）-d1/(x2 x3)f=f(x*),检验收敛准则|x*-x2|1？若满足，以x*代替f(x)的最优点x*，并输出x*=x*，f*=f(x*)。,若不满足，缩短区间后重复上述迭代计算过程，直至满足要求为止。,缩短区间分两种情况，即,1)x*x2,2)x*x2,i)f f 2;ii)f f 2,i)f f 2;ii)f f 2,举例：用二次插值法求目标函数 f(x)=x2-5 x+2 的最优解。,二次插值法的计算步骤及算法框图（略）,海赛矩阵,设目标函数f(X)在某点X（k）处存在连续的一阶、二阶偏导数：,则函数f(X)在X（k）点的n2个二阶偏导数所构成的 nn 阶方阵称为函数f(X)在X（k）点的海赛矩阵。,若函数f(X)的一阶偏导数在定义域内处处连续可微，则海赛矩阵为对称方阵。,目标函数的近似表达泰勒展开,一元函数f(x)的泰勒展开：,二元函数f(x1，x2)的泰勒展开：,n元函数f(X)的泰勒展开：,可计算函数与等值面 给定一组设计变量的值，就对应一个确定的目标函数值f(X)=C，具有这种性质的函数叫可计算函数。反之，给定目标函数f(X)的值C，即f(X)=C，那么将有无限多个设计点X使该式成立，这些设计点在n维设计空间中将组成一个点集，称之为等值曲面（三维空间）或等值超曲面（n3），通称等值面。在二维平面中为等值线。若给定一系列目标函数的值，将在设计空间得到一组等值面（线）族。,目标函数的等值线（面）,f(X)=ax12+2bx1x2+cx22 a0 c0 ac-b20,一、最速下降方向负梯度方向,2.2 最速下降方向和共轭方向,函数的方向导数,n元函数的方向导数:,与负梯度方向成锐角的方向为目标函数值的下降方向，成钝角的方向为目标函数值的增加方向。,目标函数的梯度方向是目标函数等值线（面）在同一点的法向矢量方向。,f(X(k),-f(X(k),X(k),t,所以，目标函数在某一点的最速下降方向为负梯度方向,两个向量的共轭 设两个非零向量S(0)、S(1)及对称正定矩阵H，若满足,二、共轭方向,则称S(0)、S(1)关于H共轭，或称S(0)与S(1)为共轭方向。若H为单位阵，即H=I，则S(0)与S(1)正交。,一组向量的共轭 设有一组非零向量S(0)、S(1)S(n-1)及对称正定矩阵H，若满足,则称它们关于H共轭，或称它们为一组共轭方向。若H为单位阵，则称它们相互正交。,凸集 一个点集（或区域），如果连接其中任意两点的线段都全部包含在该点集内，则称该点集为凸集。否则，称为非凸集。,2.3 凸集、凸函数与凸规划,凸函数 设函数f(X)定义域为凸集G，X(1)、X(2)为凸集G上的任意两点，若函数f(X)在线段X(1)X(2)上的函数值总小于或等于用f(X(1)及f(X(2)作线性内插所得的值，则称函数f(X)为凸集G上的凸函数，即满足,的函数f(X)为凸函数。若同时去掉式中的等号，则称函数f(X)为严格凸函数。,凸规划 对于约束优化问题,若函数f(X)、gj(X)均为凸函数，则称此约束优化问题为凸规划。,凸规划的性质 1）凸规划的可行域为凸集 2）凸规划的任何局部最优解就是全局最优解,2.4 优化问题的几何解释,2.5 优化方法的简单分类,按有无约束分类 无约束优化方法、约束优化方法 按目标函数的维数分类 一维优化方法、多维优化方法 按目标函数的数目分类 单目标优化方法、多目标优化方法 按求优途径的不同分类 直接法、解析法（间接法）、实验法、图解法,2.6 迭代方法及其收敛准则,无论是直接法还是解析法，求优的过程都是采用数值迭代法，且迭代公式的形式一致。,迭代方法,X(k+1)=X(k)+(k)S(k)(k=0,1,2,),两个特性,1）下降性:f(X(k+1)f(X(1)f(X(k)f(X(k+1)f(X*),确定步长(k)的方法,1）定步长法,取(k)=p(p为常数)，检验下列不等式 f(X(k)+(k)S(k)f(X(k)？,若成立，则继续下一步迭代计算；,否则，取(k)=p（0 1），再检验不 等式 f(X(k)+(k)S(k)f(X(k)？直至满足为止。,2）最优步长法,用一维寻优方法确定(k)：,若成立，则继续下一步迭代计算；,否则，取(k)=p（0 1），再检验不 等式 f(X(k)+(k)S(k)f(X(k)？直至满足为止。,搜索方向S(k)的讨论,1）三种常用搜索方向,负梯度方向：S(k)=-f(X(k),共轭方向：将n维优化问题转化为每一个循环n次一维搜索，依次取n个相互共轭的方向为搜索方向。,随机搜索方向：S(k)随机产生，只要求沿S(k)方向所得X(k+1)点处函数值下降。,2）S(k)与-f(X(k)和 f(X(k+1)的关系,目标函数下降：f(X(k)+(k)S(k)f(X(k)0,f(X(k)+(k)S(k)f(X(k)(k)T f(X(k)S(k),故(k)T f(X(k)S(k)0 T f(X(k)S(k)0,用一维优化方法确定(k)时，必须满足：f(X(k)+S(k)=0,所以 T f(X(k)+S(k)S(k)=0 即 T f(X(k+1)S(k)=0 第k次迭代的搜索方向S(k)与目标函数在本次迭代所得点X(k+1)处的梯度方向 f(X(k+1)正交。,X(k),X(k+1),S(k),-f(X(k+1),3）共轭搜索方向的一个重要性质,n维正定二次函数的n次收敛性,即 对于n维正定二次函数，若相继以一组相互共轭的向量S(0)、S(1)、S(n-1)为搜索方向，则不论从任何初始点出发，经过n次一维搜索，就可以得到该正定二次函数的极小点。,收敛性与收敛准则,迭代算法应具有收敛性，即产生的极小点序列或者其中某一点就是极小点，或者序列有一个极限，它是目标函数的极小点。,点距准则：|X(k+1)X(k)|1（1 0）,函数下降量准则：|f(X(k+1)f(X(k)|2（2 0）,梯度准则：|f(X(k)|3（3 0）,管支柱质量：,正常工作条件:,强度条件,稳定条件,边界条件,数学模型 用一组设计变量描述优化设计对象的设计内容,即描述优化意图(目标、指标)和有关限制条件的数学表达式，称为优化设计的数学模型。数学模型的三要素 设计变量、约束条件、目标函数,1.2 优化设计的基本概念,设计变量,设计变量,设计常量,基本设计参数,优化问题的维数：设计变量的个数,一维优化问题，n维优化问题,设计变量向量：,或,连续设计变量、离散设计变量,设计空间 它是所有设计方案的集合。2.可行设计与不可行设计 有些设计方案有些是工程上所不能接受的。如果一个设计方案满足所有对它提出的要求，就称为可行设计，反之称为不可行设计。约束条件 一个可行设计必须满足的设计限制条件。,约束条件,4.约束分类 按约束性质：性能约束、边界约束 按数学表达式：等式约束 不等式约束,5.可行域与非可行域,满足所有约束条件的设计点 的集合可行域D 可行域之外的区域非可行域,用来使设计得以优化的函数，或可以评价设计方案好坏的函数。它是评价设计方案优劣的依据和标准或指标。实际上它是反映优化意向的关于设计变量的数学表达式。为规范化，通常规定求目标函数的极小值，即,目标函数f(X),单目标优化（标量优化）：1个目标函数 多目标优化（向量优化）：2个或2个以上 目标函数,优化问题的数学模型,最优点,优化问题的最优解,最优值,