机械优化设计方法ppt课件.ppt

机械优化设计方法,陈国定,西北工业大学机电学院,引言优化设计的数学模型优化方法的数学基础一维优化（搜索）方法无约束优化方法简介工程结构优化设计发展综述多目标优化问题和优化技术简介,i,在以往传统的常规机械设计中，已经包含了“优化”的思想。比如，设计人员针对具体的设计任务，可以同时提出几种不同的设计方案，通过分析评介，选出较好的方案加以采用，这就是一种“优化“的过程。当然，按这种方式“优化”出来的方案，在很大程度上带有经验性，具有一定的局限性。常规的工程设计，由于设计手段和设计方法的限制，设计者不可能在一次设计中得到很多个方案，也不可能进行多方案的分析比较，因此不能得到最佳的设计方案。,1,人们做任何事情都希望用最少的付出得到最佳的效果，这就是最优化问题的通俗说法。工程设计中，设计者更是力求寻求一种合理的设计参数，以使得由这组设计参数确定的设计方案既满足各种设计要求，又使其技术经济指标达到最佳，即实现最优化设计。优化设计正是在这样一种思想（需求）牵引下发展起来的。,2,现代电子计算机的发展与普及，以计算机为基础的数值计算方法的成熟和应用，为工程问题的优化设计提供了先进的手段和技术，先进思想和手段的组合构成了最优化设计方法。所谓最优化设计，就是借助最优化设计数值计算方法和计算机技术，求取工程问题的最优设计方案。进行最优化设计时，首先必须将实际问题加以数学描述，形成一组由数学表达式组成的数学模型，然后选择一种最优化数值计算方法和计算机程序，在计算机上运算求解，得到一组由数学表达式组成的设计参数。这组设计参数就是设计的最优解。,3,数学模型是对实际问题的数学描述和概括，是进行优化设计的基础。因此，根据设计问题的具体要求和条件建立完备的数学模型是关系优化设计成败的关键。工程设计问题通常是相当复杂的，欲建立便于求解的数学模型，必须对实际问题加以适当的抽象和简化。不同的简化方法，得到不同的数学模型和计算结果。不恰当的数学处理可能导致计算结果偏离实际要求，得出与实际问题不一致甚至相互矛盾的结果。下面通过两个设计实例，说明优化设计中建立数学模型的一般方法和步骤。,4,【例2.1】有一块边长为6m的正方形铝板，四角各裁去一个小的方块，做成一个无盖的盒子。试确定裁去的四个小方块的边长，以使做成的盒子具有最大的容积。解：设裁去的四个小方块边长为x，盒子的容积可表示成x的函数。于是，上述问题可描述为 求变量 x 使函数 极大化 这就是此问题的数学模型。其中，x称为设计变量；f(x)称为目标函数。由于目标函数是设计变量的一元三次函数，且没有附加的约束条件，故此问题属一元非线性无约束优化设计问题。根据一元函数的极值条件，令f(x)0，解得极值点和极值分别为 称为该设计问题的最优解。,5,【例2.2】某工厂生产甲、乙两种产品。生产每种产品所需的材料、工时、电力和可获得的利润，以及能够提供的材料、工时和电力见表2.1。试确定两种产品每天的产量，以使每天所获得的利润最大。,表2.1 生产条件与供给数据,6,解：这是一个生产计划问题，可归结为既满足各项生产条件，又使每天所能获得的利润达到最大的优化设计问题。设每天生产甲产品x1件，乙产品x2件，每天获得的利润可用函数f(x1,x2),表示，即 每天实际消耗的材料，工时和电力可分别用函数表示，即,7,于是上述生产计划问题可归结为求变量 x1,x2 使函数 极大化满足条件,8,这就是该设计问题的数学模型，其中f(x1,x2)代表设计目标，称为目标函数。gu(x1,x2)(u=1,2,5)代表5个已知的生产指标，称为约束函数。5个不等式代表5个生产条件，称为约束条件。由于目标函数和所有约束函数均为设计变量的线性函数，故此问题属线性约束优化问题。显然，这样的问题无法直接利用极值条件求解。,9,优化设计数学模型的一般形式 从以上两个实例可以看出，优化设计的数学模型由设计变量、目标函数和约束条件三部分组成，可写成以下统一形式：求变量 使极小化函数 满足约束条件(u=1,2,m)(v=1,2,p 其中，称不等式约束条件；称等式约束条件,10,如果用向量X=x1,x2,xnT表示设计变量，X R表示向量X属于n维实欧氏空间，用min表示极小化，s.t.(subject to)表示“满足于”或“受约束于”，m，p分别表示不等式约束和等式约束的个数。数学模型可写成以下向量形式：,11,由于工程设计的解一般都是实数解，故可省略,将优化设计的数学模型简记为（22）当设计问题要求极大化目标函数f(X)时，只要将目标函数改写为-f(X)即可。因为maxf(X)和min-f(X)具有相同的解。同样，当不等式约束条件中的不等号为“0”时，只要将不等式两端同乘以“1”即可得到“0”的一般形式。,12,最优化问题也称为数学规划问题。最优化问题根据数学模型中是否包含约束条件而分为无约束优化问题和约束优化问题；根据设计变量的多少可分为单变量优化和多变量优化问题；根据目标函数和约束函数的性质可分为线性规划和非线性规划问题。当数学模型中的目标函数和约束函数均为设计变量的线性函数时，称此设计问题为线性优化问题或线性规划问题。当目标函数和约束函数中至少有一个为非线性函数时，称此设计问题为非线性优化问题或非线性规划问题。线性规划和非线性规划是数学规划的两个重要分支。生产计划和经济管理方面的问题一般属于线性规划问题，而工程设计问题多属于非线性规划问题。,13,设计变量与设计空间 工程问题的一个设计方案通常是用特征参数表示的，一组特征参数值代表一个具体的设计方案。这种代表设计方案的特征参数一般应选作该问题优化设计的设计变量。一个工程问题的设计参数一般是相当多的，其中包括常量、独立变量和因变量三类。优化设计时，为了使建立的数学模型尽量简单易解，只能选择其中的独立变量作为设计变量。但是，一个设计问题中，独立变量和因变量的划分并不是一成不变的。同一设计问题，当设计条件或设计要求发生变化时，设计变量也应随之变化。综上所述，设计变量应该选择那些与目标函数和约束函数密切相关的、能够表达设计对象特征的独立参数和尺寸。同时，还要兼顾求解的精度和复杂性方面的要求一般来说，设计变量的个数越多，数学模型越复杂，求解越困难。,14,设计变量有连续变量和离散变量之分。可以在实数范围内连续取值的变量称为连续变量，只能在给定数列或集合中取值的变量称为离散变量，几乎所有的优化理论和方法都是针对连续变量提出来的而实际问题往往包含有各种各样的离散变量、整数变量和标准序列变量等。目前，关于离散变量优化问题的理论和方法还很不完善。因此，对于各种包含离散变量的优化问题，一般先将离散变量当作连续变量，求出连续变量最优解后，再作适当的离散化处理。,15,由线性代数可知，若n个设计变量x1,x2,xn相互独立，则由它们形成的向量X=x1,x2,xnT的全体集合构成一个n维实欧氏空间，称设计空间，记作Rn。于是，一组设计变量可看作设计空间中的一个点，称设计点。反之，所有设计点的集合构成一个设计空间。这里，设计变量的个数n称为设计空间的维数。当n2时，设计空间为二维平面；当n3时，设计空间为三维空间；当n3时，设计空间为n维空间,16,约束条件与可行域 对任何设计都有若干不同的要求和限制，将这些要求和限制表示成设计变量的函数并写成一系列不等式和等式表达式，就构成了设计的约束条件，简称约束。约束条件的作用是对设计变量的取值加以限制。约束条件根据形式不同可分为不等式约束和等式约束，根据性质可分为边界约束和性能约束。边界约束是对设计变量本身所加的直接限制，如 其中，第一个和第二个约束条件表示，第三个约束条件表示 它们都属于边界约束条件。,17,性能约束在形式上是对某些技术性能指标或参数所加的限制，实际上同样是对设计变量所加的间接限制。如例2.2中对材料、工时和电力所加的约束，属于性能约束。设计约束的几何意义是每一个不等式或等式约束都将设计空间分为两个部分，即对每一个约束在设计空间形成了可行域和非可行域。满足所有约束的部分形成一个交集，该交集称为此约束问题的可行域，记作D。可行域也可看作满足所有约束条件的设计点的集合，因此，可用集合式表示如下：(u=1,2,m;v=1,2,p),18,例2.2中的5个约束方程分别是：作出的5条约束边界及其约束可行域如图2.1所示，可以看出，此问题的约束可行域是由5条约束边界线围成的封闭五边形ABCDO。又如以下3个约束条件：3条约束边界线所围成的约束可行域如图2.2所示。,19,20,根据是否满足约束条件可把设计点分为可行点(也称内点)和非可行点(也称外点)。根据设计点是否在约束边界上，可将约束条件分为起作用约束和不起作用约束。,21,目标函数与等值线 要寻求设计问题的最优解就必须有判别设计方案好坏的尺度。在数学模型中这个尺度就是目标函数，它是关于设计变量的函数，是用于衡量设计方案优劣的定量标准。对极小化问题来说，目标函数的值越小，对应的设计方案越好，目标函数的最小值及其对应的设计变量的取值称为设计问题的最优解 不同的设计问题有不同的方案评价标准，甚至一个问题可能存在几个不同的评价标准。因此，必须针对具体问题，选择那些主要的技术经济指标作为设计的目标函数，如利润、体积、重量、功率等。一个设计问题只有一个目标函数，这是单目标优化问题。若采用了多个目标函数，则称之为多目标优化问题，例如一台机器期望得到最低的造价和最少的维修费用，它们各自的目标函数分别为f1(x)和 f2(x)，这就是多目标优化问题。目标函数越多，对设计的评价越周全，设计的综合效果越好，但对问题的求解也越复杂。关于多目标优化问题可参考有关文献。,22,要知道一个目标函数的最优点在设计空间中所处的位置，就需要了解目标函数的变化规律。对于简单的问题，等值线或等值面不仅可以直观地描绘函数的变化趋势，而且还可以直观地给出极值点的位置。令函数f(X)等于常数c，即使f(X)c，则满足此式的点X在设计空间中定义了一个点集。当n=2时，该点集是设计平面中的一条直线或曲线，当n3时，该点集是设计空间中的一个平面、曲面或超曲面。在这种线或面上所有点的函数值均相等。因此，这种线或面就称为函数的等值线或等值面。,23,当c取一系列不同的常数值时，可以得到一组形态相似的等值线或等值面，称为函数的等值线面簇，如图2.3所示。图2.3所示为函数 的图形(旋转抛物面)，以及用平面f(X)=c切割抛物面所得交线在设计空间中的投影该投影就是函数f(X)的一簇等值线，这簇等值线是以点X2，0T的一组同心圆，显然圆心X2，0T就是函数的极小点。,24,对简单的二维优化问题，可以在设计平面内直观地作出约束可行域，画出目标函数的一簇等值线，并且可以根据等值线与可行域的相互关系确定出最优点的位置。这种求解优化问题的方法就是图解法。图解法的步骤一般为：确定设计空间，作出约束可行域，画出目标函数的一簇等值线，最后判断确定最优点,25,例2.3 用图解法求解：这是一个二维非线性优化问题。约束的可行域如图2.2所示，目标函数的等值面簇如图2.3所示。将这两个图合并起来就是图2.4。由图可以看出，在可行域内使目标函数取极小值的最优点就是点A。该点也是目标函数的等值线在函数的下降方向上与可行域的最后一个交点，而且是一个切点。,26,27,可见，在作出约束可行域和一簇目标函数的等值线后，如果有最优解的话，最优点必定位于可行域内目标函数在下降方向上的等值线与可行域边界的最后一个交点。图解法只适用于一些简单的优化问题，虽然没有什么实用价值，但是，对于理解优化问题的诸多基本概念，掌握最优解的存在条件和规律却是十分重要的。,28,例题分析1 用薄钢板制造一体积等于1m3的货箱，各边的长度不小于0.5m，要求确定货箱的长宽高尺寸，以使钢板的用量最省，试写出该问题的数学模型。解：在不考虑货箱盖的情况下，设货箱的长宽高尺寸分别为x1x2x3 则优化数学模型为 如果考虑货箱盖的情况，则优化数学为,29,2 有宽0.5m长50m的钢带一条，欲做成高0.5m，直径分别为0.22m0.35m和0.5m的三种圆柱形筒料。要求每种筒料不少于10件。问如何下料最节省材料，试写出优化设计的数学模型。解：设三种圆柱形筒料分别为x1x2x3件 优化数学模型可写成,30,3 某工厂生产一批金属工具箱，要求工具箱的体积为0.5m3，高度不低于0.8m，试写出耗费金属板面积为最小的优化设计数学模型。解：设工具箱的长宽高尺寸分别为x1x2x3 则优化数学模型为,31,用图解法求解 解：如图解得 是最优点。目标函数的最小值,32,用图解法求解 解得 最优点大约在 最小值,33,6 如图，从直径D=100mm的圆木中锯出矩形梁，选择矩形的宽b和高h，以使其抗弯强度最大，建立优化模型 解：设矩形梁的高度为变量x1,宽度为x2,由材料力学知识，得抗弯模量 数学模型为：,34,优化设计问题实际上就是极值问题。工程设计一般可归结为多变量、多约束的非线性优化问题。尽管高等数学中的极值理论仍然是求解这种问题的基础，但是却不能用来直接求出它们的最优解。因此，有必要对多变量约束优化问题的求解的数学概念及有关理论进行补充和扩展。本章重点介绍多元函数的方向导数、梯度和泰勒展开等基本概念。,35,二次型函数 所谓二次型函数是指含有n个实变量的一个二次齐次多项式函数，其表达式为：（3-1）式中的aij称为二次型的系数。上式的矩阵形式为：（3-2）其中，矩阵A是由函数f(X)中各项所含系数所组成的 矩阵。若aij=aji,，即AT=A，则A为对称矩阵,并称式（31）和式（32）为实二次型函数。,36,在采用泰勒二次近似展开式讨论函数的极值时，常要分析二次型函数是否正定或负定二次型的正定与负定的定义如下：若对于任意的非零向量X=x1,x2,xnT，即x1,x2,xn不全为零，总有f(X)=XTAX0，则称此二次型为正定二次型，其对应的矩阵A称为正定矩阵；其余，对于所有非零向量X：(1)若有XTAX0，则称矩阵A是半正定的；(2)若有XTAX0，用称矩阵A是负定的，(3)若有XTAX0，则称矩阵A是半负定的：(4)若有XTAX0，则称矩阵A是不定的 矩阵A的正定与负定的判别，可用矩阵A的各阶顺序主子式的正负来判别，以正定矩阵和负定矩阵为例说明，若矩阵A的各阶顺序主子式均大于零，则该矩阵为正定；若所有奇数阶主子式均小于零，而偶数阶主子式均大于零，则该矩阵为负定。,37,为了能够定性地表明函数特别是多维函数在某一点的变化性态，需要引出函数的方向导数及梯度的概念。,38,39,40,41,42,43,函数的梯度具有以下性质：(1)函数在一点的梯度是一个向量。梯度的方向是该点函数值上升得最快的方向，与梯度相反的方向（负梯度方向）是该点函数值下降得最快的方向，梯度的大小就是它的模。(2)一点的梯度方向是与过该点的等值线或等值面的切线或切平面相垂直的方向，或者说是该点等值线或等值面的法线方向。(3)梯度是函数在一点邻域内局部形态的描述。在一点上升得快的方向，离开该邻域后就不一定上升得快，甚至可能下降。,44,函数的泰勒近似展开和黑塞矩阵,45,46,例题分析1求函数 在点 的梯度及其模。解：,47,2 求函数 在点 的泰勒展开二次式。解：,48,3 求函数 的极值点，并判断该点是极大值还是极小值。解：由必要条件，求驻点驻点为 再由充分条件,49,的一阶主子式 二阶主子式均大于零。故 为正定矩阵，则 为极小点，相应的极值为,50,4 用泰勒展开的方法将函数 在点 简化成线性函数和二次函数。解：分别求出函数在点 的函数值，梯度和Hession矩阵,51,线性函数二次函数,52,在优化设计的迭代运算中，在搜索方向 S（k）上寻求最优步长 的方法称一维搜索法。其实，一维搜索法就是一元函数极小化的数值迭代算法，其求解过程称一维搜索。一维搜索法是构成非线性优化方法的基本算法，因为多元函数的迭代解法都可归结为在一系列逐步产生的下降方向上的一维搜索。从点X（k）出发，在方向S（k）上的一维搜索可用数学式表达如下：（41）（42）,53,此式表示对包含唯一变量 的一元函数 求极小值，得到最优步长因子 和方向S（k）上的一维极小点X（k+1）。上式实际是把求多维目标函数极小值这个多维问题化解为求一个变量（步长因子）的最优值(k)的一维问题。一维搜索的数值解法可分两步进行首先在方向S（k）上确定一个包含极小点的初始区间，然后采用缩小区间或插值的方法逐步得到最优步长和一维极小点。,54,搜索区间的确定（进退法）函数的任一单谷区间上必存在一个极小点，而且在极小点的左侧，函数呈下降趋势，在极小点的右侧，函数呈上升趋势。若已知方向S(k)上的三点x1x2x3及其函数值f(x1)、f(x2)和f(x3)，便可通过比较三个函数值的大小估计出极小点所在的位置，如图4.1所示。,图4.1 极小点估计,55,(1)若f(x1)f(x2)f(x3)，极小点位于右端点x3的右侧；(2)若f(x1)f(x2)f(x3)，用极小点位于x1和x2之间，x1,x3就是一个包含极小点的区间。可见，在某一方向上按一定方式逐次产生一些探测点，比较这些探测点上函数值的大小，就可以找出函数呈“大一小一大”变化的三个相邻点，其中两端点所确定的闭区间必定包含着极小点，这样的区间称初始区间，记作(a,b)。这种寻找初始区间的方法称进退法，其具体探测步骤如下：,56,（1）给定初始点x0，初始步长h，令x1=x0，记f1=f(x1)；（2）产生新的探测点x2=x0+h，记f2=f(x2)；（3）比较函数值f1和f2的大小，确定向前或向后探测的策略。若f1f2，则加大步长h，令h2h，转(4)向前探测；若f1O时，a,b=x1,x3，当hf3，则继续加大步长，令h=2h,x1=x2,x2=x3，转(4)继续探测。,图4.2进退探测,57,用进退法确定搜索区间的程序框图如图4.3所示。,图4.3 进退法程序框图,58,例4.1 试用进退法确定函数f(X)=3x2-8x+9的初始单峰区 间，设给定的初始点X0=0，初始步长h=0.1。解：取x1=X0=0，则f(x1)=9 取x2=0+10h=1,f(x2)=312-81+9=4 取 x3=0+20h=2,f(x3)=322-82+9=5故确定搜索区间a,b=0,2，中间点x2=1 并且 f(a)=9,f(x2)=4,f(b)=5.,59,黄金分割法(0.618法)黄金分割法是一种通过不断缩小区间得到极小点的一维搜索算法。其中缩小区间采用序列消去法，即在已知区间a,b内，任选两个中间插入点x1和x2(x1f(x2),则极小点必在x1和b之间，消去区间a,x1,得到缩小后的新区间a,bx1,b;不断重复上述过程，就可以将极小点的区间逐渐缩小，当区间长度b-a小于给定精度时，便可将区间内的一点作为该方向上的极小点。,图4.4 缩小区间的原理,60,可见，只要引入任意两个中间插入点就可将区间缩小一次。但是，不同的中间插入点所产生的缩小效果是不同的。也就是说，区间舍去部分和保留部分的比例是不同的，得到极小点的速度也就不同。不同的中间插入点的产生方法构成了不同的一维搜索算法。黄金分割法就是其中一种常用的算法。黄金分割法亦称0.618法，它是按照对称原则选取中间插入点而缩小区间的一种一维搜索算法。,61,设区间a,b内的两个中间插入点由以下方式产生：x1=a+(1-)(b-a)x2=a+(b-a)(0,1)(4.3)0.618法就是说=0.618，所以（4.3）式成为：x1=a+0.382(b-a)x2=a+0.618(b-a)(4.4)这就是黄金分割法的迭代公式，0.618法也因此而得名。黄金分割法以区间长度是否充分小作为收敛准则，并以收敛区间的中点作为一维搜索的极小点，即当 时，取 x*=(a+b)/2(4.5),62,综上所述，黄金分割法的计算步骤如下：（1）给定初始区间a,b和收敛精度。（2）产生中间插入点并计算其函数值：x1=a+0.382(b-a)，f1=f(x1)x2=a+0.618(b-a)，f2=f(x2)（3）比较函数值f1和f2，确定区间的取舍：若f1f2，则新区间a,b=x1,b，令a=x1,x1=x2,f2=f1,记N0=1，见图4.5。,图4.5 区间取舍,63,收敛判断：若区间的长度足够小，即满足，则将区间作为一维极小点，即令x*=(a+b)/2，结束一维搜索；否则，转(5)。(5)产生新的插入点：若N0=0，则取x1=a+0.382(b-a),f1=f(x1)；若N0=1，则取x2=a+0.618(b-a),f2=f(x2)，转(3)进行新的区间缩小。,64,黄金分割法的程序框图如图4.6所示。,图4.6 黄金分割法的程序框图,65,例4.2 用黄金分割法求函数f(x)=2x2+1的最优解，给定 a,b=-1，2,=0.3。解：第1次缩小区间 因为，故新区间a,b=a,=-1,0.854 b-a=0.854+1=1.8540.3，继续缩小区间。,66,第2次缩小区间 令，因为，故新区间a,b=,b=-0.2918,0.854 b-a=0.854+0.2918=1.17030.3，继续缩小区间。,67,第3次缩小区间 令，因为，故新区间a,b=a,=-0.2918,0.4163 b-a=0.70810.3，继续缩小区间。,68,第4次缩小区间 令，因为，故新区间a,b=a,=-0.2918,0.146 b-a=0.43780.3，继续缩小区间。,69,第5次缩小区间 令，因为，故新区间a,b=,b=-0.12456,0.146 b-a=0.270560.3，得极小点和极小值 x*=0.5*(-0.12456+0.146)=0.01072 f(x*)=2*0.010722+1=1.00023,70,例4.3 用黄金分割法求函数f(x)=3x3-4x+2的极小点，给 定x0=0,h=1,=0.2。解：确定初始区间 由于，应加大步长继续向前探测。令由于，可知初始区间已经找到，即。,71,用黄金分割法缩小区间 第一次缩小区间。由于，故新区间 因为b-a=1.2360.2,所以应继续缩小区间。,72,第二次缩小区间。令 由于，故新区间。因为b-a=1.2360.4720.7640.2,所以应继续缩小区间。,73,第三次缩小区间。令 由于，故新区间 因为b-a=0.944-0.4720.4720.2,所以应继续缩小区间。,74,第四次缩小区间 令 由于，故新区间 因为b-a=0.764-0.4720.2920.2,所以应继续缩小区间。,75,第五次缩小区间 令 由于，故新区间。因为b-a=0.7640.5840.180.2,所以得到极小点和极小值。,76,二次插值法 二次插值法又称抛物线法，它是以目标函数的二次插值函数的极小点作为新的中间插入点，进行区间缩小的一维搜索算法。如上所述，在确定初始区间时已得到相邻的三个点afcfb，记x1=a,x2=c,x3=b,f1=fa,f2=fc,f3=fb。在fox坐标平面内，过(x1,f1)、(x2,f2)和(x3,f3)三点可以构成一个二次插值函数，设该插值函数为 p(x)=a0+a1x+a2x2(4.6)将该函数对x求导，得极小点(4.7),77,将区间内的三点及其函数值代人式(4.6)有(4.8)联立求解以上方程组，可得系数a0,a1和a2，将它们代入式(4.7)得(4.9)由上式求出的xp是插值函数式(46)的极小点，也是原目标函数的一个近似极小点以此点作为下一次缩小区间的一个中间插入点，无疑将使新的插入点向极小点逼近的过程加快，如图4.7所示。,78,图4.7 二次插值法的区同缩小和逼近过程,79,二次插值法以两个中间插入点的距离充分小作为收敛准则，即当 成立时，把xp作为此次一维搜索的极小点。二次插值法的计算步骤如下：(1)给定初始区间a,b，收敛精度和区间中的另外一个点c。(2)将三个已知点按顺序排列：x1=a,x2=c,x3=b,f1=f(x1),f2=f(x2),f3=f(x3);(3)按式(4.9)计算中间插入点xp及其函数值fp=f(xp)。(4)收敛判断：若，则转(6)，否则，转(5)。,80,(5)缩小区间：若，且当 时，令；且当 时，令。若，且当 时，令；且当 时，则令，转(3)求新的插入点。(6)若，则令；否则，令，结束一维搜索。二次插值法的区间取舍及替换如图4.8所示，程序框图如图4.9所示。,81,图4.8 二次插值法的区间取舍及替代,82,图4.9 二次插值法的程序框图,83,例4.4 用二次插值法求解例4.2。解：取中间点 x2=0.5，则 x1=-1,x3=2 f1=3,f2=1.5,f3=9 代入公式 fp=1由于 f1fpf2 新区间a,b=-1,0.5,84,第2次计算 x1=-1,x2=xp=0,x3=0.5 f1=3,f2=fp=1,f3=1.5 fp=1由于 f2=fpf1 新区间a,b=-1,0 或0,0.5 x*=xp=0,f*=1,85,例4.5 用二次插值法求解例4.3。解：初始区间的确定 初始区间的确定与上题相同，即,另有一中间x2=1.用二次插值法逼近极小点 记此初始区间内的相邻三点及其函数值依次为：。将它们代入式（4.9），得插值函数的极小点，即新的插入点及其函数值：由于，故新区间。由于，故应继续作第二次插值计算。,86,在新的区间内，相邻三点及其函数值依次为：。将它们代入式（4.9）得 由于，故新区间。由于，故一维搜索到此结束，极小点和极小值分别为 由以上计算可以看出，二次插值法的收敛速度比黄金分割法快得多。,87,多维无约束优化问题的一般数学表达式为(51)求解这类问题的方法称为多维无约束优化方法。在工程实际中，尽管所有优化设计问题几乎都是有约束的，但约束优化问题可以转化为无约束优化问题来求解。因此，无约束最优化方法是优化设计中极为重要的和基本的内容，所以人们对它的研究十分重视。,88,无约束优化问题的算法很多，主要分为两类：一类是直接法，即不用导数信息的算法，它只需进行函数值的计算与比较，来确定迭代方向和步长，如坐标轮换法、共轭方向法和鲍威尔法；另一类是间接法，即使用导数信息的算法，它需要利用函数的一阶或二阶偏导数矩阵，来确定迭代方向和步长，如梯度法、牛顿法和变尺度法。,89,5.1 坐标轮换法 5.2 共轭方向法 5.3 鲍威尔共轭方向法,90,坐标轮换法的基本原理 坐标轮换法是无约束最优化直接方法中的一种，其基本原理是将一个多维无约束优化问题转化为一系列一维优化问题来求解，即依次沿着坐标轴的方向进行一维搜索，求得极小点。对于n维无约束优化问题，就是先将(n1)个变量固定不动，只变化第一个变量x1，即由初始点沿着第一个变量x1的方向 进行一维搜索，得到好点；而后再保持(n-1)个变量不变，对第二个变量x2进行一维搜索，此时的搜索方向为，得到好点。如此沿 方向(即坐标方向)，且将前一次一维搜索的好点作为本次一维搜索的起始点，依次进行一维搜索后，完成一轮计算。若未收敛，则以前一轮的末点 为起始点，进行下一轮的循环，如此一轮一轮迭代下去，直到满足收敛准则、逼近最优点为止。,91,图5.1所示二元目标函数 的等值线。按照上述原理，先以 为初始点，沿坐标轴 方向 进行一维搜索，求得极小点；然后固定 不变，再改变，即从 出发，沿着坐标轴 方向 进行一维搜索，求得极小点，至此完成了一轮计算。因为没有达到问题的最优点，需要进行第二轮迭代，即从前一轮的最末点 出发，重复上述过程求得，如此继续下去，直到找到问题的最优解 为止。,92,图5.1 坐标轮换法的基本原理,93,坐标轮换法的特点 坐标轮换法简单易行，但由于它只能轮流沿n个坐标方向前进，因而效率低下，特别是维数较高或目标函数性态不好的情况下，收敛速度很慢。,94,共轭方向法及其构成 坐标轮换法的收敛速度很慢，原因在于其搜索方向总是平行于坐标轴，没有适应函数的变化情况。如图5.1所示，若把第二轮的起点 与末点 连接起来，形成一个新的搜索方向(图中虚线)，并沿此方向进行一维搜索，则由此图可以看到，它可以极大地加快收敛速度。那么，方向 具有什么性质，它与 方向有何关系?,95,设函数 的极值点为，若极值点附近的等值线是近似的同心椭圆族，如图5.2所示。设给定两个平行方向，沿这两个平行方向分别进行一维搜索，求得极小点 和。显然，和 分别是两条平行线与函数等值线(椭圆)的相切点。连接二切点构成向量，即，则可以证明，若函数 的黑塞矩阵H为正定对称矩阵，则方向 与 满足下式：(52)具有这种性质的方向，即是共轭方向。,96,图5.2共轭方向的形成,97,共轭方向的定义：设A为nXn阶实对称正定矩阵，而、为n维欧氏空间中的两个非零向量，如果满足 则称向量 与 关于实对称正定矩阵A是共轭的，或简称 与 关于A共轭。上述算法可以推广到n维函数，即在n维空间中可以逐步构成一组互相关于A共轭的向量。对于对称正定的二次n维函数，从任意初始点出发顺次沿着这n个线性无关的方向进行一维搜索，就能得到目标函数的极小点。因而说共轭方向法具有有限步收敛的特性。通常称具有这种性质的算法为二次收敛算法。但对于非二次n维目标函数，经过n步共轭方向一维搜索不一定就能达到极小点，在这种情况下，可取其二次泰勒近似式加以讨论。当进行一轮的n次迭代还未收敛时，可将 作为新的初始点，再进行第二轮的迭代。,98,共轭方向法的基本原理 共轭方向法的基本原理是：首先采用坐标轮换法进行第一轮迭代，然后以第一轮迭代的最末一个极小点和初始点相连，构成一个新方向，并以此新的方向为最末一个方向，而去掉第一个方向，得到第二轮迭代的n个方向。如此进行下去，直至求得问题的最小点。现以图5.3所示的二维问题为例来说明：,99,图5.3共轭方向法的迭代过程,100,（1）令循环次数，取初始点，初始搜索方向为坐标方向；（2）从 出发，依次沿 和 进行一维搜索，分别得到相应的极小点 和；（3）构造新方向，沿 进行一维搜索，得到第k次循环的极小点；（4）取下次循环的初始点，去掉原来的第一方向，构造新的搜索方向，令k=k+1，转(2)；继续循环(2)至(4)，直到满足收敛条件，迭代计算结束。,101,鲍威尔共轭方向法的基本原理 共轭方向法的基本要求是，各方向组的向量 应该是线性无关的。然而很不理想的是，上述方法每次迭代时所产生的新方向可能出现线性相关，使搜索运算将在维数下降了的空间进行，从而导致计算不能收敛到真正的极小点而失败。为此，鲍威尔提出了对共轭方向法的改进方法。这个方法解决了两个关键问题：（1）在每一轮迭代完成并产生共轭方向后，先对共轭方向的好坏进行判别，检验它是否与其它方向线性相关。若共轭方向不好，则不用它作为下一轮的迭代方向，而仍采用原来的一组迭代方向。（2）若共轭方向好，则可用它替换前一轮迭代中使函数值下降最多的一个方向，而不是替换第一个迭代方向。,102,在鲍威尔共轭方向法中，判别是否用新的方向替换原方向组中某一方向的判别准则按下式是否同时满足来进行处理：(53),103,式中各符号的含义说明如下(对应于图5.4所示)：f1表示在第k次循环中起始点 的函数值；f2表示在第k次循环中沿基本方向组中各迭代方向依次一维搜索后的终点 的函数值;f3为映射点的函数值,，为 对 的映射点，；表示循环中函数值下降量最大者，即 其相应的方向为。,104,图5.4 式（53）的符号含义,105,若同时满足判别准则(53)式，则在第k+1次循环中，选用新方向，将 补入k+1次循环基本方向组的最后，并去掉方向，即 以构成第k+1次循环的基本方向组，并取第k+1次循环的初始点为(为第k次循环中沿新方向 一维搜索求得的极小点)；否则第k1次循环仍用原来的n个搜索方向，而初始点 则应选取两点 中函数值较小者，亦即当 时，取；当 时，取。,106,鲍威尔共轭方向法的迭代步骤为：（1）给定初始点 和允许误差、；（2）取n个坐标轴的单位向量 为搜索方向，置k=1(k为迭代轮次)，；（3）从 出发，分别沿 作一维搜索，依次得n个极小点，计算各相邻极小点目标函数值的差值，并找出其中的最大差值及其相应的方向：（4）计算映射点，并求得；,107,（5）若同时满足式(5-3)，则由 出发，沿方向 进行一维搜索，求出该方向的极小点,并以 为kk+1轮迭代的初始点，即令；然后去掉方向，而将方向 作为k+1轮迭代的最末一个方向，即第k+1轮的搜索方向为：，.,，,，若不满足判别式(5-3)，则进入第k+1轮迭代时，仍采用第k轮迭代的方向，迭代初始点选取：当 时，置；当 时，置；（6）检验是否满足迭代终止条件，若满足 1或 2则可终止迭代，得 为最优点，输出结果为；否则，置，返回步骤(3)，进行下一轮迭代。,108,例5.1 用鲍威尔共轭方向法求解下列无约束优化问题：的最优点,计算精度=0.0001。解：取初始点，这时,109,第一次迭代：第一轮迭代取搜索方向为两个坐标轴，方向单位向量为；从 出发，先从方向 进行一维最优搜索，求得最优步长，由此得,110,注意：最优步长 的获得如下：由点 出发沿1,0T方向搜索，f(X)中的x2=0，则f(X)成为 搜索迭代公式为 代入f(X)公式中有 求导数 令其为0，得最优步长.,111,从 沿 方向进行一维搜索，求得最优步长，于是可求得 注意：最优步长 的获得如下：由点 出发沿0,1T方向搜索，f(X)表达式和搜索迭代公式分别为 f(X)=f(5,x2)=35-9x2+将 代入f(X)中，有 f(X)=求导获得,112,连接，构成共轭方向S1 并沿着共轭方向S1计算映射点,113,计算第一轮相邻两点函数值的下降量，并求其最大差值及其相应方向 所以：,114,计算本轮初始点、终点 和映射点 的函数值 F1=60,F2=14.75,F3=15 检验判别条件由于 F3=15 F1=60和(F1-2F2+F3)(F1-F2-)20.5(F1-F3)2即 18657.825312.5同时成立，故应以S1=5,4.5T替换（下降值最大的方向），并沿S1方向求极小点，用一维搜索可求得最优步长，从而求得,115,注意：最优步长 的获得如下：搜索迭代方程为：将其代入f(X)中有 求导得,116,令第二轮迭代的初始点为 第二轮的搜索方向为,进行迭代终止检验 由于 故需进行下一轮迭代。,117,第二次迭代：给定初始点；第二轮搜索方向为 从 出发，以 方向进行一维最优搜索，求得最优步长，由此得,118,注意：最优步长 的获得如下：因为 代入f(X)公式中有 求导数得到,119,从 出发沿 进行一维搜索，求得最优步长，于是可求得 注意：最优步长 的获得如下：迭代公式为 代入f(X)中，有 f(X)=求导得：得,120,连接，构成共轭方向S2 由于二元二次方程的特点，所以可以直接获得优化 点X2，沿S2方向求极小点X2，用一维搜索求得最优步 长 求得 精确解为：X*=8,6T，误差已小于0.0001，故可以停止迭代运算。,121,例5.2 试用鲍威尔共轭方向法求解下列无约束优化问题：解：取初始点，这时,122,第一次迭代：选取搜索方向，从 出发，沿方向 进行一维搜索：由 得 用一维优化方法如二次插值法来求解，因本题较为简单，可用解析法求解。令，有 22得 因此,123,然后从 出发，沿方向 进行一维搜索，可得 计算映射点：计算函数值：由于，不满足判别准则式（53），因此不能采用新方向。,124,第二次迭代：取，沿方向 进行一维搜索，得极小点 再从 出发，沿方向 进行一维搜索，得极小点,125,计算下列值=5.0296所以，m=1,126,用式（53）进行检查：成立，而 即有 检查结果说明，式（53）的两条件同时满足，应该采用新方向，去掉对应于 的方向，因此新的方向组为,127,而下一次迭代的起始点 则取为 方向上的极小点，沿 方向进行一维搜索得极小点=，通过计算可得 由于，与目标函数的理论极小点 和理论极小值 已十分接近，故可终止迭代。,128,6.1 引言 6.2 结构优化的发展和研究现状 6.3 结构优化中的优化算法 6.4 结论和展望,129