机械优化设计课件.ppt

机械优化设计,第一章绪论第二章优化设计的数学模型和基本概念第三章无约束问题的最优化方法第四章约束问题的最优化方法第五章多目标问题的最优化方法第六章现代优化设计方法第七章离散变量和随机变量的最优化方法第八章优化设计过程中应注意的问题,第一章绪论,一.优化,优化是万物演化的自然选择和必然趋势。优化作为一种观念和意向，人类从很早开始就一直在自觉与不自觉地追求与探索。而优化作为一门学科与技术，则是一切科学与技术所追求的永恒主题，旨在从处理各种事物的一切可能的方案中，寻求最优的方案。,例如，古代人类在生产和生活活动中经过无数次摸索认识到，在使用同样数量和质量材料的条件下，圆截面的容器比其他任何截面的容器能够盛放的谷物都要多，而且容器的强度也最大。,优化的原理与方法，在科学的、工程的和社会的实际问题中的应用，便是优化设计。,第一章绪论,1.优化在规定的范围内（或条件下），寻找给定函数取得的最大值（或最小值）的条件。,例如,在右图中，求得一维函数f(x)最小值的条件为：若取x*，则f(x)取得最小值f(x*)。,目的是为了在完成某一任务时所作的努力最少、付出最小，而使其收益最大、效果最好。,第一章绪论,2.优化过程,例如：要求设计一个如右下图所示的防洪堤坝。为了能防洪水，高度必须足以保证洪峰到来时，洪水不会漫入堤岸；堤坝的强度足以保证巨浪不会冲垮堤坝；同时希望得到一个省时省力省经费的设计方案。,获得设计方案的过程是一个决策的过程，也是优化的过程。,所作的努力或希望的效益在实际问题中均可表达为一些决策变量的函数。,优化过程就是求解一个付出的努力最小、获得效益最大的方案。,是寻找约束空间下给定函数取极大值（以max表示)或极小(以min表示)的过程.,第一章绪论,实际问题表达成的函数类型很多：确定型、不确定型函数；线形、非线形（二次、高次、超越）函数。,变量类型也很多：连续、离散、随机变量等等。,求解问题的优化方法也很多，最常用的为数学规划法，它是运筹学的一部分。而运筹学是数学的一个分支。,产生很多的优化算法：无约束优化、约束优化：单目标函数优化、多目标函数优化；连续变量优化、离散变量优化、随机变量优化。,3.优化方法:是用科学方法和手段进行决策及确定最优解的数学；,第一章绪论,优化的原理与方法，在科学的、工程的和社会的实际问题中的应用，便是优化设计。优化设计是在现代计算机广泛应用的基础上发展起来的一项新技术。是根据最优化原理和方法，以人机配合方式或“自动探索”方式，在计算机上进行的半自动或自动设计，以选出在现有工程条件下的最佳设计方案的一种现代设计方法。优化设计反映出人们对于设计规律这一客观世界认识的深化。,二.优化设计,第一章绪论,传统设计与优化设计传统设计：求得可行解。优化设计：解得最优解。,2.优化设计与最优控制优化运用在设计领域优化设计优化运用在控制领域最优控制,优化设计运用于各领域土木工程、水利工程、城市规划、化工系统、电气系统、电子产品、机械产品优化运用于机械产品的设计，称机械优化设计。,第一章绪论,1.传统机械设计理论与方法疲劳寿命理论、强度理论、振动理论常凭经验、试算、校核等方法。,现代机械设计理论与方法60年代出现：计算机辅助设计CAD、有限单元法、可靠性设计、优化设计、设计方法学、价值工程、反求工程90年代出现：并行设计、虚拟设计、仿生设计、协同设计,三.机械优化设计,把机械设计与优化设计理论及方法相结合，借助电子计算机，为实现预期目标,自动寻找最优设计方案和最佳设计参数。,优化设计流程,传统设计流程,设计要求,方案设计,综合与分析,评价,输出图文技术资料,优化设计数学模型,优选设计变量,优化算法程序,是,否,是否满足要求,输出,传统设计与优化设计：,第一章绪论,3.机械优化设计的发展,经典优化设计:本世纪40年代初，由于军事上的需要产生了运筹学，并使优化技术首先应用于解决战争中的实际问题，例如轰炸机最佳俯冲轨迹的设计等。50年代末数学规划方法被首次用于结构最优化，并成为优化设计中求优方法的理论基础。数学规划论和计算机技术的发展使最优化设计计算成为可能。优化设计从无约束有约束优化问题；连续变量离散变量；确定型随机型模型；单目标优化多目标优化。,历史上最早记载下来的最优化问题可追溯到古希腊的欧几里得（Euclid，公元前300年左右），他指出：在周长相同的一切矩形中，以正方形的面积为最大。古典优化思想:十七、十八世纪微积分的建立给出了求函数极值的一些准则，对最优化的研究提供了某些理论基础。,第一章绪论,现代优化设计：20世纪80年代出现许多现代优化算法：模拟退火算法、遗传算法、人工神经网络算法、蚁群优化算法等；并采用专家系统技术实现寻优策略的自动选择和优化过程的自动控制，智能寻优策略迅速发展。并从狭义优化设计（零部件参数）转向广义优化设计（面向产品的全系统、设计全过程、全寿命周期）。例如,针对涉及多领域复杂系统的多学科设计优化。,第一阶段人类智能优化：与人类史同步，直接凭借人类的直觉或逻辑思维，如黄金分割法、穷举法和瞎子爬山法等。,随着人类对自然界认识的不断深入，寻找最优逐渐从下意识的、缺乏系统性的行为发展到目的明确的有意识活动，并在数学工具日渐完善的基础上，对各种寻找最优的活动进行数学描述和分析，指导寻优活动更有效地进行，从而形成了最优化理论与方法这一应用数学理论分支,第二阶段数学规划方法优化：从三百多年前牛顿发明微积分算起，电子计算机的出现推动数学规划方法在近五十年来得到迅速发展。第三阶段工程优化：近二十余年来，计算机技术的发展给解决复杂工程优化问题提供了新的可能，非数学领域专家开发了一些工程优化方法，能解决不少传统数学规划方法不能胜任的工程优化问题。在处理多目标工程优化问题中，基于经验和直觉的方法得到了更多的应用。优化过程和方法学研究，尤其是建模策略研究引起重视，开辟了提高工程优化效率的新的途径。第四阶段现代优化方法：如遗传算法、模拟退火算法、蚁群算法、神经网络算法等，并采用专家系统技术实现寻优策略的自动选择和优化过程的自动控制，智能寻优策略迅速发展。,第一章绪论,4.机械优化设计的作用,使传统机械设计中，求解可行解上升为求解最优解成为可能；使传统机械设计中，性能指标的校核可以不再进行；使机械设计的部分评价，由定性改定量成为可能；使零缺陷（废品）设计成为可能；大大提高了产品的设计质量，从而提高了产品的质量。,例如，工厂在安排生产计划时，首先要考虑在现有原材料、设备、人力等资源条件下，如何安排生产，使产品的产值最高，或产生的利润最大；又如，在多级火箭发射过程中，如何控制燃料的燃烧速率，从而用火箭所载的有限燃料使火箭达到最大升空速度；再如，在城市交通管理中，如何控制和引导车辆的流向，尽量减少各个交叉路口的阻塞和等待时间、提高各条道路的车辆通行速度，在现有道路条件下取得最大的道路通行能力。,美国波音飞机公司对大型机翼用138个设计变量进行结构优化，使重量减少了三分之一；大型运输舰用10个变量进行优化设计，使成本降低约10%。,实践证明，最优化设计是保证产品具有优良的性能，减轻自重或体积，降低产品成本的一种有效设计方法。同时也可使设计者从大量繁琐和重复的计算工作中解脱出来，使之有更多的精力从事创造性的设计，并大大提高设计效率。,该课程的主要目的和任务：,解决简单工程问题。,掌握基本理论和基本方法；,扩大视野；,了解和掌握机械优化设计的基本知识；,基础：（1）最优化数学理论（2）现代计算技术内容：（1）将工程实际问题数学化；（建立优化设计数学模型）（2）用最优化计算方法在计算机上求解数学模型。,优化设计是一种现代设计方法，是很好的工具。,第二章优化设计的数学模型和基本概念,2.1优化设计的数学模型2.2优化设计的三大要素2.3优化设计的分类2.4优化设计的数学基础2.5优化设计的最优解及获得最优解的条件2.6优化设计问题的数值迭代法及其收敛条件,2.1优化设计的数学模型,一.机械优化设计方法解决实际问题的步骤1.分析实际问题，建立优化设计的数学模型；,分析：设计的要求（目标、准则）；设计的限制（约束）条件；设计的参数，确定设计变量。,建立：机械优化设计方法相应的数学模型。,2.分析数学模型的类型，选择合适的求解方法（优化算法）。,3.编程上机求数学模型的最优解，并对计算的结果进行评价分析,最终确定是否选用此次计算的解。,2.1优化设计的数学模型,举例：箱盒优化设计的数学模型制造一体积为100m3，长度不小于5m，不带上盖的箱盒，试确定箱盒的长x1，宽x2，高x3，使箱盒用料最省。,分析：设计目标：表面积min.；,设计限制：（a）体积要求；（b）长度要求；,设计参数中的未定变量：长x1，宽x2，高x3,数学模型：,设计参数：,设计目标：,约束条件：,2.1优化设计的数学模型,举例：最大产值生产资源分配问题,某工厂生产A和B两种产品，A产品单位价格为PA万元，B产品单位价格为PB万元。每生产一个单位A产品需消耗煤aC吨，电aE度，人工aL个人日；每生产一个单位B产品需消耗煤bC吨，电bE度，人工bL个人日。现有可利用生产资源煤C吨，电E度，劳动力L个人日，欲找出其最优分配方案，使产值最大。分析：（1）产值的表达式；（2）设计参数确定：A产品xA，B产品xB；（3）设计约束条件：（a）生产资源煤约束；（b）生产资源电约束；（C）生产资源劳动力约束；,数学模型,设计参数：,设计目标：,约束条件：,以最低成本确定满足动物所需营养的最优混合饲料。设每天需要混合饲料的批量为100磅，这份饲料必须含：至少0.8%而不超过1.2%的钙;至少22%的蛋白质;至多5%的粗纤维。假定主要配料包括石灰石、谷物、大豆粉。这些配料的主要营养成分为：,混合饲料配合,解:根据前面介绍的建模要素得出此问题的数学模型如下:设是生产100磅混合饲料所须的石灰石、谷物、大豆粉的量（磅）。,举例：圆形等截面销轴的优化设计的数学模型已知：轴的一端作用载荷P=1000N，扭矩M=100Nm；轴长不得小于8cm；材料的许用弯曲应力w=120MPa，许用扭剪应力=80MPa，许用挠度f=0.01cm；密度=7.8t/m，弹性模量E=2105MPa。,要求：设计销轴，在满足上述条件的同时，轴的质量应为最轻。,分析：设计目标是轴的质量最轻Q=1/4d2lmin.；,设计限制条件有5个：弯曲强度：maxw扭转强度：刚度：ff结构尺寸：l8d0,设计参数中的未定变量：d、l,具体化：目标函数Q=1/4d2lmin.约束函数max=Pl/(0.1d3)w=M/(0.2d3)f=Pl3/(3EJ)fl8d0,代入数据整理得数学模型：设：X=x1,x2T=d,lTmin.f(x)=x12x2XR2s.t.g1(x)=8.33x2-x130g2(x)=6.25-x130g3(x)=0.34x23-x140g4(x)=8-x20g5(x)=-x10,设计变量目标函数约束函数,（性能约束）,约束函数（性能约束）约束函数（性能约束）约束函数（几何约束）约束函数（几何约束）,属于2维欧氏空间,根据例子中的数学模型：设：X=x1,x2T=d,lTmin.f(x)=x12x2XR2s.t.g1(x)=8.33x2-x130g2(x)=6.25-x130g3(x)=0.34x23-x140g4(x)=8-x20g5(x)=-x10,已知：传动比i,转速n,传动功率P，大小齿轮的材料，设计该齿轮副，使其重量最轻。,直齿圆柱齿轮副的优化设计,直齿圆柱齿轮副的优化设计,（1）圆柱齿轮的体积(v)与重量(w)的表达；（2）设计参数确定：模数m，齿宽b，齿数z1；（3）设计约束条件：大齿轮满足弯曲强度要求；小齿轮满足弯曲强度要求；齿轮副满足接触疲劳强度要求；齿宽系数要求；最小齿数要求。,分析：,设计参数：,设计目标：,约束条件：,数学模型：,机械优化设计数学模型的一般形式：设X=x1,x2,xnTmin.f(x)=f(x1,x2,xn)XRns.t.gu(x)0u=1,2,mhv(x)=0v=1,2,py2,向右前进；加大步长h2h，转（3）向前；（b）如y1y3,加大步长h2h，a1=a2,a2=a3,转（3）继续探测。（b）如y2f2,应加大步长继续向前探测。,x3=x0+2h=0+2=2,f3=f(x3)=18由于f2f2,故新区间a,b=x1,b=0.472,1.236因为b-a=1.236-0.472=0.7640.2,应继续缩小区间。,3.2一维搜索方法,四.一维搜索的插值类方法,1.牛顿法,设f(x)为一个连续可微的函数，则在x0附近，该函数应该与一个二次函数接近，即可在点x0附近用一个二次函数(x)来逼近函数f(x)，即：,用二次函数的(x)极小点x1作为f(x)极小点的一个近似点。根据极值必要条件:得到：,依次继续下去，可得牛顿迭代公式：,牛顿法的优点是收敛速度快。缺点是要计算函数的一阶和二阶导数，因而增加了每次迭代的工作量。如果用数值微分计算函数的二阶导数，其舍入误差将严重影响牛顿法的收敛速度，f(x)的值越小，这个问题就越严重。另外，牛顿法要求初始点选的比较好，也就是说应离极小点不太远，否则有可能使极小化序列发散或收敛到非极小点。,3.2一维搜索方法,二次插值法.基本原理：,步骤：,3.2一维搜索方法,缩短区间,若f(x)本身为二次函数，则在理论上按前式一次求值就可找到最优点；若f(x)为高于二次的函数或为其他函数,可采用区间消去法逐步缩小区间。根据xp*，x2，f(xp*)和f(x2)的相互关系，分4种情况进行区间缩小。在已有的四x1,x2,x3,xp*中选择新的三个点x1,x2,x3，再进行二次插值。,3.2一维搜索方法,方法评价：与黄金分割法相比，二次插值法充分利用函数值的信息；收敛快；调用函数次数少。,二次插值法的程序框图,例：用二次插值法求函数f(x)=3x3-4x+2的极小点，给定x0=0,=0.2。,解：1）确定初始区间初始区间a,b=0,2,中间点x2=1。,2）用二次插值法逼近极小点相邻三点的函数值:x1=0,x2=1,x3=2;f1=2,f2=1,f3=18.代入公式：,xp*0.555,fp=0.292,由于fp0.2,应继续迭代。,在新区间，相邻三点的函数值:x1=0,x2=0.555,x3=1;f1=2,f2=0.292,f3=1.xp*0.607,fp=0.243由于fpx2,新区间a,b=x2,b=0.555,1|x2-xp*|=0.0520.2,迭代终止。xp*0.607,f*=0.243,3.3多维优化算法,无约束优化问题的概念和数学模型：求n维设计变量x=x1，x2，xnT使目标函数为minf（x），而对x没有任何限制；如果存在x*，使minf（x）=f（x*），则称x*为最优点，f（x*）为最优值。数学模型:minF(x)x=x1，x2，xnTRn求上述问题最优解的方法，称为无约束优化方法。,无约束优化的地位：1、有些实际问题，其数学模型本身就是无约束优化问题，或者除了在非常接近极小点的情况下，都可以按无约束问题来处理。2、通过熟悉无约束优化问题的解法，可以为研究约束优化问题打下良好的基础。3、约束优化问题的求解往往可以通过一系列无约束优化方法来实现。所以，无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。,无约束优化方法数值计算方法的步骤：1、选择一个初始点x（0），这一点越靠近极小点x*越好。2、若已经取得某设计点x（k），并且该点不是近似极小点，则在x（k）点根据函数f（x）的性质，选择一个方向S（k），并且沿此方向搜索函数值是下降的，称下降方向。3、当搜索方向S（k）确定后，由x（k）点出发，沿S（k）方向进行搜索，定出步长因子（k），得到新的设计点x（k+1）=x（k）+（k）S（k），并满足f（x（k+1）f（x（k）4、若x（k+1）满足迭代计算终止条件，x（k+1）点作为x*；否则从该点出发，返回第二步继续搜索迭代。,无约束优化数值计算方法的关键问题：无约束优化数值计算方法采用的是搜索方法，其基本思想是从给定的初始点出发，沿某一个搜索方向进行不断的搜索，确定最佳步长使函数值沿搜索方向下降最大，其迭代公式为x（k+1）=x（k）+（k）S（k）各种无约束优化方法的区别在于确定其搜索方向的S（k）的方法不同。所以，搜索方向的构成问题使无约束优化问题的关键。,用直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。这类方法较适用于解决变量个数较少的（n20）问题，一般情况下比间接法效率低。间接法除要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛矩阵。,（1）间接法：要使用导数，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度法等。（2）直接法：不使用导数信息，如坐标轮换法、鲍威尔法单纯形法等。,无约束优化方法的分类：无约束优化方法的分类依据就是根据（k）和S（k）的确定方法而定的。若根据构成搜索方向所使用的信息性质的不同，可以分为两类。,1、梯度法,基本思想：函数的负梯度方向是函数值在该点下降最快的方向。将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最速下降法或梯度法。,搜索方向s取该点的负梯度方向(最速下降方向)，使函数值在该点附近的范围内下降最快。,为了使目标函数值沿搜索方向能够获得最大的下降值，其步长因子应取一维搜索的最佳步长。即有,根据一元函数极值的必要条件和多元复合函数求导公式，得：,在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。这就是说在迭代点向函数极小点靠近的过程，走的是曲折的路线。形成“之”字形的锯齿现象，而且越接近极小点锯齿越细。,方法特点：（1）初始点可任选，每次迭代计算量小，存储量少，程序简短。即使从一个不好的初始点出发，开始的几步迭代，目标函数值下降很快，然后慢慢逼近局部极小点。（2）任意相邻两点的搜索方向是正交的，它的迭代路径为绕道逼近极小点。当迭代点接近极小点时，步长变得很小，越走越慢。,沿负梯度方向进行一维搜索，有,为一维搜索最佳步长，应满足极值必要条件,例：求目标函数的极小点。解：取初始点则初始点处函数值及梯度分别为,算出一维搜索最佳步长,继续作下去，经10次迭代后，得到最优解,第一次迭代设计点位置和函数值,这个问题的目标函数的等值线为一簇椭圆，迭代点从起点出发走的是锯齿形路线。,将上例中目标函数引入变换,其等值线由椭圆变成一簇同心圆。,仍从即出发进行最速下降法寻优。,则函数f(X)变为：,y1=x1,y2=5x2,经变换后，只需一次迭代，就可找到最优解。这是因为经过尺度变换等值线由椭圆变成圆。,梯度法特点：,（1）理论明确，程序简单，对初始点要求不严格。（2）对一般函数而言，梯度法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。（3）梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。（4）梯度法的收敛速度与目标函数的性质密切相关。对于等值线(面)为同心圆（球）的目标函数，一次搜索即可达到极小点。,2、牛顿法及其改进,设为的极小点，则,基本思想：将f(x)在x(k)点作台劳展开，取二次函数式(x)作为近似函数,以(x)的极小值点作为f(x)的近似极小值点。,牛顿法是求函数极值的最古老算法之一。,这就是多元函数求极值的牛顿法迭代公式。,对于二次函数，海赛矩阵H是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。,例：求目标函数的极小点。解：取初始点,经过一次迭代即求得极小点,从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念。因此对于非二次函数，如果采用上述牛顿迭代公式，有时会使函数值上升。,阻尼牛顿法：,阻尼因子，沿牛顿方向进行一维搜索的最佳步长，由下式求得：,阻尼牛顿法程序框图,方法特点：（1）初始点应选在X*附近，有一定难度；（2）尽管每次迭代都不会是函数值上升，但不能保证每次下降；（3）若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向；（4）不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。此外，对于二阶不可微的F(X)也不适用。虽然阻尼牛顿法有上述缺点，但在特定条件下它具有收敛最快的优点，并为其他的算法提供了思路和理论依据。,一般迭代式：,梯度法：,牛顿法：,阻尼牛顿法：,3、变尺度法,DFP变尺度法首先有戴维顿（Davidon）与1959年提出，又于1963年由弗莱彻（Fletcher）和鲍维尔加以发展和完善，成为现代公认的较好的算法之一。DFP法是基于牛顿法的思想又作了重要改进。这种算法仅用到梯度，不必计算海赛阵及其逆矩阵，但又能使搜索方向逐渐逼近牛顿方向，具有较快的收敛速度。,基本思想：变尺度法的基本思想与牛顿法和梯度法有密切联系。观察梯度法和牛顿法的迭代公式x(k+1)=x(k)-(k)g(k)和xk+1=xk-(k)G(xk)-1g(k)分析比较这两种方法可知：梯度法的搜索方向为-g(k)，只需计算函数的一阶偏导数，计算量小，当迭代点远离最优点时，函数值下降很快，但当迭代点接近最优点时收敛速度极慢。牛顿法的搜索方向为-G(xk)-1g(k)，不仅需要计算一阶偏导数，而且要计算二阶偏导数及其逆阵，计算量很大，但牛顿法具有二次收敛性，当迭代点接近最优点时，收敛速度很快。,思考：若迭代过程先用梯度法，后用牛顿法并避开牛顿法的海赛矩阵的逆矩阵的烦琐计算，则可以得到一种较好的优化方法，这就是“变尺度法”产生的基本构想。为此，综合梯度法和牛顿法的优点，提出变尺度法的基本思想。变尺度法的基本迭代公式写为下面的形式：xk+1=xk-kA(k)g(k)式中的A(k)为构造的nn阶对称矩阵，它是随迭代点的位置的变化而变化的。变尺度法的搜索方向-A(k)g(k)，称为拟牛顿方向。若A(k)=I，上式为梯度法的迭代公式，若A(k)=G(xk)-1，上式为阻尼牛顿法的迭代公式。,当矩阵Ak不断地迭代而能很好地逼近A(k)=G(xk)-1,时，就可以不再需要计算二阶导数。,变尺度法的关键在于尺度矩阵Ak的产生。,尺度矩阵的概念：,通过坐标变换可以改变函数的偏心程度，我们也称之为尺度变换。尺度变换能显著地改进几乎所有极小化方法的收敛性质。如用梯度法求f(x)=x12+25x22的极小值时，需要迭代10次才能到达极小点x*=00T。若作变换y1=x1y2=5x2则可以将函数的等值线由椭圆变为圆，即(y)=y12+y22，从而消除了函数的偏心，用梯度法只需一次迭代即能求得极小点。,用Q-1右乘等式两边，得QTG=Q-1再用Q左乘等式两边，得QQTG=I所以QQT=G-1这说明二次函数矩阵G的逆阵，可以通过尺度变换矩阵Q求得。QQT实际上是在空间内测量距离大小的一种度量，称为尺度矩阵，记作A，即A=QQT,对于一般二次函数为减低函数二次项的偏心程度，进行尺度变换xQx则在新的坐标系中，函数的二次项变为若矩阵是正定的，则总存在矩阵Q使QTGQ=I将函数的偏心变为零。,尺度变换矩阵的建立：根据变尺度法的基本原理，需要构造一个变尺度矩阵序列Ak来逼近海赛逆矩阵序列Gk-1，每迭代一次，尺度改变一次。从初始矩阵A0=I(单位矩阵)开始，通过对公式中修正矩阵Ak的不断修正，在迭代中逐步逼近于Gk-1.因此，一旦达到最优点附近，就可望达到牛顿法的收敛速度。,尺度变换矩阵的建立：根据变尺度法的基本原理，需要构造一个变尺度矩阵序列Ak来逼近海赛逆矩阵序列Gk-1，每迭代一次，尺度改变一次。为了建立变尺度矩阵Ak，必须对其附加某些条件。1、为保证迭代公式的下降性质，要求Ak中的每一个矩阵都是对称正定的。因为若要求搜索方向Sk=-Akgk为下降方向，即要求gkTSk0，即Ak应为对称正定。2、要求Ak之间的迭代具有简单的形式，显然Ak+1=Ak+Ak为最简单的形式，其中Ak为校正矩阵。3、要求必须满足拟牛顿条件。,Ak+1gk=xk,其中：gk=gk+1-gkxk=xk+1-xk,一般步骤：1、选定初始点和收敛精度；2、计算初始点处的梯度，选取初始对称正定矩阵A0，置k=0。3、计算搜索方向Sk=-Akgk4、沿Sk方向一维搜索，计算gk+1、gk、xk。5、判断是否满足终止准则，若满足输出最优解，否则转6。6、当迭代n次还未找到极小点，重置Ak为单位矩阵，并以当前点为初始点返回2，否则转7。7、计算Ak+1=Ak+Ak，置k=k+1返回3。,DFP算法由于舍入误差和一维搜索的不精确，有可能导致Ak奇异，而使数值稳定性方面不够理想。所以1970年提出更稳定的算法，称为BFGS算法，其校正公式为,方法评价：,DEF变尺度法以逐次逼近的方法实现H-1的计算，当目标函数的一阶导数易求时，以一阶代替二阶导数的计算是有效的方法。算法的第一步是梯度法，最速下降；接近x*时，又采用二次收敛的共轭方向，总的收敛速度较快。H(k)近似代表x(k)点的二阶导数，当其为零时，可判断x(k)为鞍点。H(k)的计算较复杂，存储量较大。算法稳定性较差，由于计算机有舍入误差，容易使H(k)的正定性破坏，趋于奇异。,例：用DFP算法求下列问题的极值：,解：1）取初始点，为了按DFP法构造第一次搜寻方向d0，需计算初始点处的梯度,取初始变尺度矩阵为单位矩阵A0=I，则第一次搜寻方向为,沿d0方向进行一维搜索，得,为一维搜索最佳步长，应满足,得:,2）再按DFP法构造点x1处的搜寻方向d1，需计算,代入校正公式,=,=,第二次搜寻方向为:,再沿d1进行一维搜索，得,为一维搜索最佳步长，应满足,3）判断x2是否为极值点,梯度:,海赛矩阵:,梯度为零向量,海赛矩阵正定。可见点满足极值充要条件，因此为极小点。,4、共轭方向法,1.共轭方向：设G为nn阶实对称正定矩阵，如果有两个n维向量d0和d1满足，则称向量d0与d1关于矩阵G共轭。,当G为单位矩阵时，,假设目标函数f(x)在极值点附近的二次近似函数为,对二维情况：,任选取初始点x0沿某个下降方向d0作一维搜索，得x1,因为是沿d0方向搜索的最佳步长，即在点x1处函数f（x）沿方向d0的方向导数为零。考虑到点x1处方向导数与梯度之间的关系，故有,如果按最速下降法，选择负梯度方向为搜索方向，则将发生锯齿现象。,取下一次的迭代搜索方向d1直指极小点x*。,如果能够选定这样的搜索方向，那么对于二元二次函数只需顺次进行d0、d1两次直线搜索就可以求到极小点x*，即有,那么这样的d1方向应该满足什么条件呢?,对于前述的二次函数:,当时，,x*是f(x)极小点，应满足极值必要条件，故有,将等式两边同时左乘得：,有,就是使d1直指极小点x*，d1所必须满足的条件。,两个向量d0和d1称为G的共轭向量，或称d0和d1对G是共轭方向。,共轭方向的性质：,性质1若非零向量系d0,d1,d2,dm-1是对G共轭，则这m个向量是线性无关的。,性质2在n维空间中互相共轭的非零向量的个数不超过n。,性质3从任意初始点出发，顺次沿n个G的共轭方向d0,d1,d2,进行一维搜索，最多经过n次迭代就可以找到的二次函数f(x)极小点。,关键：新的共轭方向确定？,在无约束方法中许多算法都是以共轭方向作为搜索方向，它们具有许多特点。根据构造共轭方向的原理不同，可以形成不同的共轭方向法。,共轭梯度法：,共轭梯度法是共轭方向法中的一种，该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来。从xk出发，沿负梯度方向作一维搜索:,设与dk共轭的下一个方向dk+1由dk和点xk+1的负梯度的线形组合构成，即：,共轭条件：,则：,解得：,令,为函数的泰勒二次展开式,则,上两式相减，并代入,将式,与式,两边相乘，并应用共轭条件,得：,因此,算法步骤：,算法特点：共轭梯度法属于解析法，其算法需求一阶导数，所用公式及算法简单，所需存储量少。该方法以正定二次函数的共轭方向理论为基础，对二次型函数可以经过有限步达到极小点，所以具有二次收敛性。但是对于非二次型函数，以及在实际计算中由于计算机舍入误差的影响，虽然经过n次迭代，仍不能达到极小点，则通常以重置负梯度方向开始，搜索直至达到预定精度，其收敛速度也是较快的。,，已知初始点1,1T,例：求下列问题的极值,解：1）第一次沿负梯度方向搜寻计算初始点处的梯度,为一维搜索最佳步长，应满足,迭代精度。,得:,2）第二次迭代：,代入目标函数,由,得,从而有：,因,收敛。,5、坐标轮换法,坐标轮换法属于直接法，既可以用于无约束优化问题的求解，又可以经过适当处理用于约束优化问题求解。坐标轮换法是每次搜索只允许一个变量变化，其余变量保持不变，即沿坐标方向轮流进行搜索的寻优方法。它把多变量的优化问题轮流地转化成单变量（其余变量视为常量）的优化问题，因此又称这种方法为变量轮换法。此种方法只需目标函数的数值信息而不需要目标函数的导数。,基本思想：,搜索方向与步长：,每次以一个变量坐标轴作为搜索方向，将n维的优化问题转化为一维搜索问题。例，第k轮迭代的第i次搜索，是固定除xi外的n-1个变量，沿xi变量坐标轴作一维搜索，求得极值点xi(k)n次搜索后获得极值点序列x1(k),x2(k）,xn(k)，若未收敛，则开始第k+1次迭代，直至收敛到最优点x*。,终止准则：可以采用点距准则或者其它准则。注意：若采用点距准则或函数值准则，其中采用的点应该是一轮迭代的始点和终点，而不是某搜索方向的前后迭代点。,流程图:,入口,给定：x0，,K=1,i=1,Xik=x0,沿ei方向一维搜索求ixik=xi-1k+ikeix=xkf=f(x),i=n?,|xnk-x0k|?,x*=xf*=f(x*),出口,i=i+1,x0=x0k,k=k+1,N,Y,N,Y,方法评价：,方法简单，容易实现。当维数增加时，效率明显下降。收敛慢，以振荡方式逼近最优点。,受目标函数的性态影响很大。如图a)所示，二次就收敛到极值点；如图b)所示，多次迭代后逼近极值点；如图c)所示，目标函数等值线出现山脊（或称陡谷），若搜索到A点，再沿两个坐标轴，以t0步长测试，目标函数值均上升，计算机判断A点为最优点。事实上发生错误。,6、鲍威尔方法,鲍威尔法是以共轭方向为基础的收敛较快的直接法之一，是一种十分有效的算法。1964年，鲍维尔提出这种算法，其基本思想是直接利用迭代点的目标函数值来构造共轭方向，然后从任一初始点开始，逐次沿共轭方向作一维搜索求极小点。并在以后的实践中进行了改进。,对函数：,基本思想：在不用导数的前提下，在迭代中逐次构造G的共轭方向。,共轭方向的生成：,设xk,xk+1为从不同点出发，沿同一方向dj进行一维搜索而到的两个极小点。,这种方法是在研究具有正定矩阵G的二次函数的极小化问题时形成的。,梯度和等值面相垂直的性质,dj和xk,xk+1两点处的梯度gk,gk+1之间存在关系:,另一方面，对于上述二次函数，其xk,xk+1两点处的梯度可表示为:,因而有,取,这说明只要沿dj方向分别对函数作两次一维搜索，得到两个极小点xk和xk+1，那么这两点的连线所给出的方向dk就是与dj一起对G共轭的方向。,算法步骤：（二维情况为例）,方法的基本迭代格式包括共轭方向产生和方向替换两主要步骤。把二维情况的基本算法扩展到n维，则鲍威尔基本算法的要点是：在每一轮迭代中总有一个始点（第一轮的始点是任选的初始点）和n个线性独立的搜索方向。从始点出发顺次沿n个方向作一维搜索得一终点，由始点和终点决定了一个新的搜索方向。用这个方向替换原来n个方向中的一个，于是形成新的搜索方向组。替换的原则是去掉原方向组的第一个方向而将新方向排在原方向的最后。此外规定，从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭代的始点。这样就形成算法的循环。,鲍威尔基本算法的缺陷：可能在某一环迭代中出现基本方向组为线性相关的矢量系的情况。如第k环中，产生新的方向：Sk=xnk-x0k=1kS1k+2kS2k+nkSnk式中，S1k、S2k、Snk为第k环基本方向组矢量，1k、2k、nk为个方向的最优步长。若在第k环的优化搜索过程中出现1k=0，则方向Sk表示为S2k、S3k、Snk的线性组合，以后的各次搜索将在降维的空间进行，无法得到n维空间的函数极小值，计算将失败。,如图所示为一个三维优化问题的示例，设第一环中1=0，则新生方向与e2、e3共面，随后的各环方向组中，各矢量必在该平面内，使搜索局限于二维空间，不能得到最优解。,鲍威尔基本算法的退化,x1,x2,x3,1=0,1e2,3e3,S1,鲍威尔修正算法：在某环已经取得的n+1各方向中，选取n个线性无关的并且共轭程度尽可能高的方向作为下一环的基本方向组。鲍威尔修正算法的搜索方向的构造：在第k环的搜索中，x0k为初始点，搜索方向为S1k、S2k、Snk，产生的新方向为Sk，此方向的极小点为xnk。点xn+1k=2xnk-x0k，为x0k对xnk的映射点。计算x0k、x1k、xnk、xk、xn+1k各点的函数值，记作：F1=F(x0k)F2=F(xnk)F3=F(xn+1k)=F(xmk)-F(xm-1k)其中：是第k环方向组中，依次沿各方向搜索函数值下降最大值，即Smk方向函数下降最大。,x0k,x1k,x2k,x3k,xm-1k,xmk,Snk,xnk,Smk,S3k,S2k,Sk,xk,xn+1k,F1,F2,F3,为了构造第k+1环基本方向组，采用如下判别式：按照以下两种情况处理：1、上式中至少一个不等式成立，则第k+1环的基本方向仍用老方向组S1k、S2k、Snk。k+1环初始点取：x0k+1=xnkF2F3x0k+1=xn+1kF2F32、两式均不成立，则淘汰函数值下降最大的方向，并用第k环的新生方向补入k+1环基本方向组的最后，即k+1环的方向组为S1k、S2k、Sm-1k、Sm+1k、Snk、Sn+1k。k+1环的初始点取x0k+1=xnkxnk是第k环沿Sn+1k方向搜索的极小点。,方法评价：,计算步骤复杂;是二次收敛方法，收敛快。对非正定函数，也很有效;是比较稳定的方法。,说明：,若是正定二次函数，n轮迭代后收敛于最优点x*。若是非正定二次函数，则迭代次数增加。,本章介绍了多种无约束优化方法，在实际应用中如何选择这些优化方法就显得尤为重要。为了比较各种优化方法的特性，必须建立合理的评价准则。无约束优化方法的评价准则主要包括以下几个方面：1、可靠性。即在合理的精度要求下，在一定允许时间内能解出各种不同类型问题的成功率。能够解出的问题越多，则算法的可靠性越好。2、有效性。即算法的解题效率。它有两个衡量标准。其一是对同一题目，在相同精度和初始条件下，比较机时多少。其二是在相同精度下，计算同一题目所需要的函数的计算次数。3、简便性。一方面指实现该算法的准备工作量的大小。另一方面指算法占用存储单元的数量。,3.4无约束优化设计方法小结,可靠性：牛顿法较差，因为它对目标函数要求太高，解题成功率较低。有效性：坐标变换法和梯度法的计算效率较低，因为它们从理论上不具有二次收敛性。简便性：牛顿法和变尺度法的程序编制较复杂，牛顿法还占用较多的存储单元。由以上讨论可知，在选用无约束优化方法时，一方面要考虑优化方法的特点，另一方面要考虑目标函数的情况。1、一般而言，对于维数较低或者很难求得导数的目标函数，使用坐标轮换法或鲍威尔法较合适。2、对于二次性较强的目标函数，使用牛顿法效果好。3、对于一阶偏导数易求的目标函数，使用梯度法可使程序编制简单，但精度不宜过高。4、综合而言，鲍威尔法和DFP法具有较好的性能。,适用范围：,例：,解：,用Poweel法、共轭梯度法、牛顿法、变尺度(DEF)法进行计算，并进行比较。,Poweel法共轭梯度法牛顿法变尺度(DEF)法迭代次数搜索次数搜索方向收敛速度存储量适用维数稳定性,22126212共轭方向,零阶算法一阶算法二阶算法超线性较慢二次收敛收敛最快二次收敛小中最大较大,存储量随n2随n，tn20n200300好中差中下,4.1引言,无约束优化方法是优化方法中最基本最核心的部分。但是，在工程实际中，优化问题大都是属于有约束的优化问题，即其设计变量的取值要受到一定的限制，用于求解约束优化问题最优解的方法称为约束优化方法。,根据约束条件类型的不同可以分为三种，其数学模型分别如下：1、不等式约束优化问题（IP型）,2、等式约束优化问题（EP型）,3、一般约束优化问题（GP型）,直接解法：随机方向搜索法、复合形法、可行方向法间接解法：内点惩罚函数法、外点惩罚函数法、混合惩罚函数法,约束优化问题解法分类：约束优化方法按求解原理的不同可以分为直接法和间接法两类。,二.直接解法：,基本思想：合理选择初始点，确定搜索方向，以迭代公式x(k+1)=x(k)+(k)S(k)在可行域中寻优，经过若干次迭代，收敛至最优点。,基本要点：选取初始点、确定搜索方向及适当步长。搜索原则：每次产生的迭代点必须满足可行性与适用性两个条件。可行性：迭代点必须在约束条件所限制的可行域内，即满足gu(x)0,u=1,2,p,适用性：当前迭代点的目标函数值较前一点是下降的，即满足F(xk+1)F(xk),适用范围：只能求解不等式约束优化问题的最优解。,特点：在可行域内进行；若可行域是凸集，目标函数是定义在凸集上的凸函数，则收敛到全局最优点；否则，结果与初始点有关。,收敛条件：边界点的收敛条件应该符合K-T条件；内点的收敛条件为：,目的：将有约束优化问题转化为无约束优化问题来解决。前提：一不能破坏约束问题的约束条件，二使它归结到原约束问题的同一最优解上去。惩罚函数法：通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解。惩罚函数法是一种使用很广泛、很有效的间接解法。基本思想：以原目标函数和加权的约束函数共同构成一个新的目标函数(x,r1,r2)，将约束优化问题转化为无约束优化问题。通过不断调整加权因子，产生一系列函数的极小点序列x(k)*(r1(k),r2(k)k=0,1,2，逐渐收敛到原目标函数的约束最优解。,三.间接解法：,新目标函数：,加权因子（即惩罚因子）：r1,r2,无约束优化问题：,函数的极小点序列x(k)*(r1(k),r2(k)k=0,1,2其收敛必须满足：,其中和称为加权转化项，并根据它们在惩罚函数中的作用，分别称为障碍项和惩罚项。障碍项：当迭代点在可行域内时，在迭代过程中阻止迭代点越出边界。惩罚项：当迭代点在非可行域或不满足不等式约束条件时，在迭代过程之中迫使迭代点逼近约束边界或等式约束曲面。,分类：根据约束形式和定义的泛函及罚因子的递推方法等不同，罚函数法可分为内点法、外点法和混合罚函数法三种。这种方法是1968年由美国学者AVFiacco和GPMcormick提出的，把不等式约束引入数学模型中，为求多维有约束非线性规划问题开创了一个新局面。,适用范围：求解等式约束优化问题和一般约束优化问题。,4.2内点惩罚函数法（障碍函数法）,一.基本思想：,内点法将新目标函数(x,r)构筑在可行域D内，随着惩罚因子r(k)的不断递减，生成一系列新目标函数(xk,r(k)，在可行域内逐步迭代，产生的极值点xk*(r(k)序列从可行域内部趋向原目标函数的约束最优点x*。内点法只能用来求解具有不等式约束的优化问题。,二.惩罚函数的形式：,其中：惩罚（加权）因子降低系数c：0c1,例：用内点法求,的约束最优解。,解:首先构造内点惩罚函数:,用解析法求函数的极小值，运用极值条件：,联立求解得：,时不满足约束条件,应舍去。,无约束极值点为：,当,内点法的迭代过程在可行域内进行，“障碍项”的作用是阻止迭代点越出可行域。,三.步骤：,选取合适的初始点x(0)，以及r(0)、c、计算精度1、2，令k=0；,2.构造惩罚（新目标）函数；,3.调用无约束优化方法，求新目标函数的最优解xk*和(xk,r(k)；,4.判断是否收敛：运用终止准则,若均满足，停止迭代，有约束优化问题的最优点为x*=xk*；若有一个准则不满足，则令并转入第3步，继续计算。,四.几个参数的选择：,2.惩罚因子初始值r(0)的选择：,1.初始点x(0)的选择：,要求：在可行域内；不要离约束边界太近。如太靠近某一约束边界，构造的惩罚函数可能由于障碍项的值很大而变得畸形，使求解无约束优化问题发生困难.,方法：人工估算，需要校核可行性；计算机随机产生，也需校核可行性。,惩罚因子的初值应适当，否则会影响迭代计算的正常进行。一般而言，太大，将增加迭代次数；太小，会使惩罚函数的性态变坏，甚至难以收敛到极值点。对于不同的问题，都要经过多次试算，才能决定一个适当r0。,3.降低系数c的选择：,在构造序列惩罚函数时，惩罚因子r是一个逐次递减到0的数列，相邻两次迭代的惩罚因子的关系为:,式中的c称为惩罚因子的缩减系数，c为小于1的正数。一般的看法是，c值的大小在迭代过程中不起决定性作用，通常的取值范围在0.10.7之间。,4.收敛条件：,五.方法评价：,用于目标函数比较复杂，或在可行域外无定义的场合下：由于优化过程是在可行域内逐步改进设计方案，故在解决工程问题时，只要满足工程要求，即使未达最优解，接近的过程解也是可行的；初始点和序列极值点均需严格满足所有约束条件；不能解决等式约束问题。,六.举例：盖板问题,b,h,ts,tf,设计一个箱形截面的盖板。已知：长度l0=600cm，宽度b=60cm，侧板厚度ts=0.5cm，翼板厚度为tf(cm)，高度为h(cm)，承受最大的单位载荷q=0.01Mpa。,要求：在满足强度、刚度和稳定性等条件下，设计一个最轻结构。,优化方法：选用内点惩罚法，惩罚函数形式为：,调用Powell法求序列无约束优化极值，以逐渐逼近原问题的极值点。,设计分析：（略）,数学模型：,4.求解过程分析：,4.3外点惩罚函数法(衰减函数法）,一.基本思想：,外点法将新目标函数(x,r)构筑在可行域D外，随着惩罚因子r(k)的不断递增，生成一系列新目标函数(xk,r(k)，在可行域