汽车优化设计.doc

汽车优化设计讲 稿课程名称：汽车优化设计课 型：选修课总 学 时：36学 分 数：2任课教师：陈 雷授课对象：2011级湖北文理学院第一章 优化设计（Optimal Design）第一节 优化设计的基本概念与数学模型引例例1 有一边长为6m的正方形钢板，四角各截去一个小的方块，加工成一个无盖的盒子，试确定截去的四个小方块的边长，使加工的盒子具有最大的容积。解：设截去的四个小方块的边长为x，则盒子的容积可表示成x的函数于是上述物理问题可描述为：求变量：x，使函数极大化。其中，x称为设计变量，f(x)称为目标函数由于目标函数是设计变量的一元三次函数，且没有附加的约束条件，因此该问题属于一元非线性无约束优化设计问题。根据一元函数的极值条件，令因为取x=3时,f(x)=0,无意义；故取x=1为极值点，记为所以，该设计问题的最优解为。例2 某工厂生产甲、乙两种产品，生产每种产品所需的材料、工时、电力和可获得的利润以及能够提供的材料、工时和电力见表1。试确定两种产品每天的产量，以使每天可获得的利润最大。表1 生产条件与供给数据产品材料/kg工时/h电力/kw.h利润/元甲93460乙4105120供应量360300200解：这是一个生产计划问题。归结为既满足各项生产条件，又使每天所能获得的利润达到最大的优化设计问题。设每天生产甲产品x1件，乙产品x2件，每天获得的利润可用函数f(x1, x2)表示，即：f(x1, x2)=60x1+120x2每天实际消耗的材料用函数g1(x1, x2)表示，即：g1(x1, x2)= 9x1+4x2每天实际消耗的工时用函数g2(x1, x2)表示，即：g2(x1, x2)= 3x1+10x2每天实际消耗的电力用函数g3(x1, x2)表示，即：g3(x1, x2)= 4x1+5x2由此上述生产计划问题，再考虑供应量可归结为下面设计问题的数学模型：求变量：x1，x2设计目标函数：使函数f(x1, x2)=60x1+120x2极大化约束函数为gi(x1, x2)不等式的约束条件满足条件：其中，x1，x2变量生产的件数必须大于或等于0。由于目标函数和所有约束函数均为设计变量的线性函数，因此该问题为线性约束优化问题，显然，这样的问题无法解决直接用于极值条件求解，须借助数值算法语言来计算。计算结果为：该设计问题的最优解为一、优化设计的概念从上面两例看出优化设计的工作分为两部分：一部分是将设计问题的物理模型转变为数学模型；另一部分是采用适当的优化方法求解数学模型。概念：优化设计是将工程设计问题转化为最优化问题，利用数学规划的方法，借助于计算机（高速度、高精度和大存储量）的处理，从满足设计要求的一切可行方案中，按照预定的目标自动寻找最优设计的一种设计方法。发展与应用：采用优化设计技术始于六十年代，早期的机械优化设计大多集中在机构学问题上，特别是结构运动参数的优化选择方面，以后才逐渐发展到机构运动学优化设计和机械零部件及机械产品的优化设计，包括优化设计的软件开发。优化设计的应用已被实践证明，可以有效的提高设计质量，降低产品成本，缩短设计周期，具有较为明显的经济效益。典型的代表是：1）美国。辛格采用优化设计方法设计了一种十级转速的机床主轴箱，使各轴的中心距总和比用传统设计方法所取得的结果减少16.55%，从而体积和重量相应的减少。2）意大利。扎罗蒂用优化设计方法对工程机械中的柴油机变速箱等作了最佳匹配设计，显著提高了其性能。3）中国。葛洲坝二号船闸人字门启闭机构经过优化设计，使驱动力矩由400t.m降为232.t.m；广州造船厂将优化方法船用螺旋桨的叶型及叶截面的设计中，并采用CAD技术直接绘出图形，从而节省了大量的人力和物力，取得了满意的结果。二、优化设计的数学模型优化设计的问题首先是建立数学模型，即把实际问题转化为数学模型的形式，一般包括三个方面：设计变量与设计空间、约束条件与目标函数。1设计变量与设计空间在机械设计中，每一个设计方案都可以用一组参数来表示，这些参数有几何参数和物理参数。几何参数如构件的长度、位置角、构件上点的坐标等；物理参数如质量、转动惯量、力及力矩等。这些参数中，在优化设计前根据要求预先给定的，称为设计常量；在优化设计中待选择的参数，也是变化的量，称为设计变量。设有n个设计变量，可用一个向量X表示。写成式中表示n维空间，它包括了所有的设计变量，称为设计空间，一个设计向量X代表着一个设计方案，它对应着n维空间的一个点，其中最优设计方案用表示，称为最优点或优化点。设计变量的数目称为维数，维数越多，优选方案越多，效果越好，但计算更复杂，难度增加。一般在优化设计中，不应过多地增加设计变量，应尽可能根据以往经验将一些参数确定为设计常量，而只将那些对设计指标影响比较大的设计参数定为设计变量。2约束条件与可行域约束条件：对任何设计都有若干不同的要求和限制，将对设计方案的要求和限制表示成设计变量的函数并写成一系列不等式和等式表达式，就构成了设计的约束条件简称约束。其作用是对设计变量的取值加以限制。根据形式的不同可分为不等式约束和等式约束，根据性质不同可分为边界约束和性能约束。可行域：任何一个不等式约束都把设计空间分为两部分，一部分是满足约束条件的称为可行域，另一部分是不满足约束条件的称为非可行域，这两部分分界是。在约束边界上的点称为边界点，两个以上约束的交点称为角点。在有约束的优化问题中，优化点常常是边界点或角点。又称为约束方程。因此，有约束优化设计的实质就是在可行域内寻求一组设计变量，使目标函数值最优。不等式约束和等式约束的几何意义：教材p6图14例2的5个约束方程分别是：对应的可行域：教材p6图15将以上约束条件用图表示，约束条件均满足的公共部分即为可行域，在可行域内的点称为可行点（在实际设计中为可行方案）。确定了设计变量和设计空间，提出了约束条件和可行域，下一步建立目标函数。3目标函数优化设计的任务是在许多可行的方案中找出最优的方案，所谓最优方案是在设计变量中能最好的满足所需追求的某些特点的目标，而这些目标又可表达为设计变量的函数，称为目标函数。目标函数可用来评价设计方案的好坏，所以又称为评价函数。常表示为：一般目标函数可用经济指标和性能指标来表示。经济指标如机器的寿命最长、重量最轻、体积最小、用料最省、所需功率最小等；性能指标主要是满足运动学与动力学的要求，如牛头刨床要求刨刀在工作行程上近似等速，港口起重机要求M点轨迹近似直线，凸轮机构要求压力角小于许用压力角等等。4优化设计的数学模型在明确了设计变量、约束条件和目标函数后，优化设计问题就可表示成规范的数学形式，称为数学模型。一般形式：求变量： 极小化（极大化）函数： 满足约束条件： 其中，称为不等式约束条件；称为等式约束条件。若用向量表示设计变量，表示向量X属于n维实欧氏空间，用“max、min”表示极大、极小化，用“s.t”表示“满足于”，“m、p”表示不等式约束与等式约束的个数，则表示如下形式：三、优化设计的分类（1） 按目标函数的多少可分为单目标优化和多目标优化；（2） 按所能求解的函数的维数可分为一维优化方法（称为一维搜索）和多维优化方法；（3） 按约束情况可分为无约束优化方法和约束优化方法；（4） 用数学模型表达的求有方法称为数学优化方法，包括数学规划法和最优控制法（最优控制问题的数值解法常可通过离散化等措施转化为数学规划问题，一般只讨论数学规划法。数学规划法按目标函数的特性分为线性与非线性、约束与无约束规划、动态整数与随机规划（5） 按求优的途径可分为：数值迭代法：利用已有信息及再生信息进行试探及迭代求优方法，是目前优化设计中广泛采用的方法。解析法：利用函数性态通过微分或变分求优；图解法：利用作图求优，主要用于不超过二维的优化问题。四、优化问题的图解法1等值线的概念要知道一个目标函数的最优点在设计空间中所处的位置，就需要了解目标函数的变化规律。对于简单的问题，等值线或等值面不仅可以直观地描绘函数的变化趋势，还可以直观地给出极值点的位置。以二维优化为例。设目标函数为，它的图形是三维空间中的一个曲面。用一个平面z=c(常数)去截这个曲面，其交线是空间中的一条曲线，在这条曲线上所有的点距平面xoy有同一高度，即具有相同的目标函数值，称这条曲线为等高线，为方便起见，往往将这条曲线投影到xoy平面，这条曲线称为该函数的等值线，不同的常数c1、c2,所截的平面曲线不同，得到不同的等值线。如果目标函数的图形是一个旋转曲面，则其等值线是一族同心圆，在同一个圆上函数值相同。求优的出发点：不同的圆函数值不同，各同心圆的中心即为目标函数的极值点。教材p7图19二维线性目标函数的等值线可以直接在设计平面上做出。如例2的等值线图。教材p7图182优化问题的图解法 简单的二维优化问题，可以在设计平面内直观地作出可行域，画出目标函数的一族等值线，并且可以根据等值线与可行域的相互关系确定出最优点的位置。这种求解优化问题的方法就是图解法。例2的图解法。教材p8图110将例2的可行域和等值线叠加在一起。最优点就是目标函数等值线在下降方向上与可行域的最后一个交点C（20，24），此时可得最大利润4080元。例3 用图解法求解 这是一个二维非线性优化问题。在设计平面上作出可行域如图所示。其等值线是一组以（2，0）为圆心的同心圆。教材p6图16，p9图111。目标函数的最优解是等值线在函数的下降方向上与可行域的最后一个交点，而且是一个切点。可以看出，最优点都是目标函数在下降方向上的等值线与可行域边界的最后一个交点。一般来说，非线性问题的最优点要么是一个内点，要么是一个边界点，而且此边界点必定是目标函数的一条等值线或一个等值面与可行域边界的一个切点；而线性问题的最优点则必定是，两个或两个以上约束边界的交点，这种交点称为可行域的顶点。或者说，线性优化问题的最优点必定在可行域的顶点上取得。图解法实用价值不大，但对于理解优化问题的一些概念、掌握最优解的存在条件和规律是十分重要的。本节思考题1. 优化设计模型的组成要素及其表示方法。2. 什么是可行域？什么是等值线（面）？3. 通过简单优化问题的图解法分析优化问题最优解的特点。第二节 优化问题的极值条件与数值迭代法一、 优化问题的数学基础1 方向导数导数作为描述函数变化率的数学量，在优化理论重具有重要的地位。一元函数在点的导数表示函数在该点的变化率。一阶导数大于0，说明函数在这一点随x的增大而增大，一阶导数小于0，说明函数在这一点随x的增大而下降。一阶导数等于0的点，称为函数的驻点。一元函数的极值往往在驻点取得。多元函数在某点对坐标变量的一阶偏导数仿照多元函数沿各坐标轴方向的导数，可以定义多元函数沿任意方向S的方向导数设方向S与各坐标轴正向夹角分别为，则有其中，为函数在点的梯度，为方向S上的单位向量，为方向余弦。2 梯度函数在点的梯度是由函数在该点的各个一阶偏导数组成的向量，即根据矢量代数的概念，方向导数可以写成其中：显然，当方向导数与梯度夹角为0时，方向导数取得最大值。也就是说，函数在某点沿任意方向S的方向导数等于该点的梯度在该方向上的投影。而梯度方向是函数在该点的方向导数最大的方向，或者说是函数值增长最快的方向。梯度具有如下性质：1） 函数在一点的梯度是一个向量。梯度的方向是该点函数值上升得最快的方向，梯度的大小就是它的模长；负梯度方则向是函数值下降得最快的方向。2） 一点的梯度方向与过该点的等值线或等值面的切线或切面垂直，或者说是该点等值线或等值面的法线方向。3） 梯度是一点函数在某点邻域内局部形态的描述。在某点上升得最快的方向，离开该邻域后不一定上升得最快，甚至可能下降。3 凸集、凸函数与凸规划（1） 凸集设D是n维欧式空间内的一个点集，即，若任意两点的连线上的一切点（），则称D为凸集。从直观上讲，凸集的内部没有空洞，边界上也没有凹陷部分。凸集的几何特征是：其任意两点连线上的一切点都位于这个几何内。（2） 凸函数设D为中的一个凸集，为定义在D上一个函数，若对D内任意两个点及任意，恒有则称为凸函数。凸函数的几何意义是：点的连线完全处在曲线或曲面的上方或在上。同理，可以定义凹函数。注意：这与高等数学中函数图形的凹凸性正好相反。（3） 凸规划对于非线性规划若其中和均为凸函数（对于约束则为凹函数），则这样的规划问题称为凸规划。凸规划的可行域为凸集。凸规划的局部极小点一定是全局极小点。二、 优化问题的极值条件1 无约束问题的极值条件多元函数在点取得极小值的条件是：函数在该点的梯度为0，二阶导数矩阵为正定，即同理，多元函数在点取得极大值的条件是：函数在该点的梯度为0，二阶导数矩阵为负定。（矩阵正定：该矩阵的各阶主子式均为正。奇数阶为负、偶数阶为正称为负定。）由于实际问题的目标函数比较复杂，二阶导数矩阵难以求出，即便求出，其正定性的判断也很困难，因此，具体优化计算中，只将函数梯度为0作为极值存在的判断准则。2 约束问题的极值条件约束问题的极值有多种状态：（1） 极值点为可行域的内点，此时目标函数的极小点也就是约束问题的极小点。此时，约束条件均不是起作用约束。（2） 当目标函数的极小点在可行域外时，约束问题的极小点是约束边界上的一点，该点是约束边界与目标函数的一条等值线（等值面）的切点。当极值点位于某约束边界上时，该约束被称为这个点的起作用约束。（起作用约束：若点位于约束条件形成的约束边界上（即），则约束条件成为点的起作用约束。）（3） 约束问题还可能有多个极值点。1） 等式约束的极值条件对于等式约束问题由高等数学可知，可以建立拉格朗日函数其中，为拉格朗日向量。令，得 （）这就是等式约束问题在点取得极值的必要条件。上式的含义是：在等式约束问题的极值点上，目标函数的负梯度等于诸约束函数在该点梯度的线性组合。2） 不等式约束的极值条件对于不等式约束问题可以通过引入m个松弛变量，将上面的不等式约束变成等式约束问题然后类似地，建立拉格朗日函数 式中，为松弛变量组成的向量。令这个拉格朗日函数的梯度等于0。即令 则可以得到若，这说明点X*在约束边界上，为点X*的起作用约束。约束条件形式为“”，所以，必有；若，则必有。设点X*的起作用约束有w个，即起作用约束为，则必有上式称为不等式约束的极值条件，又称为Kuhn-Tucker条件，简称kt条件。k-t条件的含义是：若点X*是函数的极值点，则要么，要么该点目标函数的负梯度等于起作用约束的函数梯度的非负线性组合。k-t条件是多元函数取得约束极值的必要条件，但不是充分条件。只有当优化问题为凸规划时，k-t条件才是约束优化问题最优解的充分必要条件。三、 数值迭代法1数值迭代法的基本思想从一个初始点出发，按照一个可行的搜索方向和适当的步长走一步，达到，再从出发，选一个可行的搜索方向和适当的步长走一步，达到，并保证每一步函数值必须是下降的，即，这样一步一步地重复进行数值计算，最终达到目标函数的极小点。（1） 无约束优化问题对于图中表示的二维函数求其无约束最优点时，只须任选一初始点，从点出发沿着某种优化方法采用的搜索方向，以初选的步长按下面的迭代公式求出一个新点，然后检查函数值是否有所下降，如果，就说明：点优于点，也即满足了适用性要求，于是接着以点作为起点，依据上述方法进行迭代搜索，得到，检查，若不成立，改变方向和步长，如此循环下去，直到求得所需的，此式即为迭代计算的基本公式。由于每次迭代求得的新点均为使函数值有所下降的适用点，（如果不是适用点，可改变方向和步长另行搜索适用点），则所得各点必将逐步向该函数的极值点逼近，最后总可求得非常接近该函数理论最优点的近似最优点。（国防工业出版社教材p22图110）（2） 有约束优化问题对于有约束的优化问题，除了检查每个新点的适用性外，还要检查其可行性，即是否满足的约束条件，如果适应性和可行性兼备，再仿照无约束优化方法进行下一次迭代，最终自然也能求得非常接近约束最优点的近似最优点。综上所述，采用数值法进行迭代求优时，除了选择初始点以外，如何确定迭代方向和步长成为非常重要的环节，他们将直接决定着搜索的效率，函数值逐步下降的稳定性和所需的时间等。2终止准则（收敛准则）用迭代法求优时，虽然所得各新点依次逐步向理论上的无约束或约束最优点靠拢，而且理论上可以无限的趋近，但又不会真正达到，另一方面，从工程实际需要和经济上的考虑，追求问题的精确解也是没有必要的，因此，就应根据不同的优化方法、迭代过程中产生的信息及所需的计算精度（足够小的正数），定出某个相应的终止准则，一旦满足终止准则，则可停止迭代，输出近似的最优解和。无约束优化问题常用的迭代终止准则有：（1） 点距准则：根据相邻两迭代点与间的距离足够小而建立的点距准则可表示为或；（2） 值差准则：根据相邻的两迭代点的函数值下降量足够小而建立的函数值下降量准则a) 当时，用绝对下降量准则b) 当时，用相对下降量准则（3） 梯度准则：一般来说，梯度等于0的点是极小点，根据这种思路，梯度近似于0的点就是近似极小点，因此根据迭代点的函数梯度模长达到足够小可以建立梯度准则或 上述三个准则都在一定程度上反映了逼近最优点的程度，均可以单独使用。但他们又都有一定的局限性，在实际应用中，可取一种、二种甚至三种同时满足作为收敛判断的条件。四、 数值迭代法分类优化过程就是求解各类优化问题的数值迭代过程，其算法的核心是如何选择搜索方向和步长因子。确定搜索方向和步长的方法有很多种，它同时也就定义了多种数值迭代的方法。如教材P22。自学教材P19例23。思考题：1 为什么说k-t条件只是约束问题极值条件的必要条件而不是充分条件？2 三个数值迭代终止准则各有什么局限性？第三节 一维搜索方法一、 概述1. 一维搜索的概念在数值迭代方法中，任一次迭代，总是从某个已知点出发，沿着给定的方向（用梯度法确定方向）搜索到目标函数的极小值点，这个过程称为一维搜索。（也有称一维搜索法就是一元函数极小化的数值迭代算法，其求解过程称为一维搜索），一维搜索法是构成非线性优化方法的基本算法，因为多元函数的迭代解法都可归结为在一系列逐步产生的下降方向上的一维搜索。2. 一维搜索的数学形式在任一次迭代中，使得，即，也就是说，一维搜索的每一次迭代过程都是寻找合适的步长因子，使得所得到的下一个点的函数值是该方向上所有可能点中最小的，即：从出发，沿着方向，求步长因子，使最小。此时的记为，称为最优步长因子。3. 一维搜索的几何意义从出发，沿方向一维搜索，就是求方向与目标函数等值线的切点，此时的步长因子即为最优步长因子。 4. 单峰区间对于所有的一维优化方法，首先遇到的共同问题是：如何确定一个初始搜索区间，使该区间内含有函数的极小点，且在该区间内函数有唯一的极小点，这个搜索区间就是单峰区间。（含且仅含一个目标函数极小点的区间就是单峰区间）用解析方法给单峰区间下个定义：设函数f(x)在区间内有定义，且（1） 在区间内存在极小点，即有；（2） 对区间上的任意自变量x，有；对区间上的任意自变量x，有；则称闭区间为函数f(x)的单峰区间。如下图所示函数曲线，区间就是该函数的单峰区间。在单峰区间内，在极小点的左边，函数是严格减少的，在的右边，函数是严格增加的。即函数的函数值在单峰区间具有高低高的特征，我们用这一特征来确定初始的搜索区间。讨论：如果函数f（x）在区间a,b上有多个极值点，则成为多峰函数，对于多峰函数f（x），只要适当划分区间，也可以使该函数f（x）在每一个子区间上是单峰的。5. 一维搜索的基本思想一维搜索就是要在初始单峰区间中求单峰函数的极小点。所以找初始单峰区间是一维搜索的第一步，然后将初始单峰区间逐步缩小，直至极小点存在的范围小于给定的一个正数，此称为收敛精度或迭代精度。此时，如区间为，即有可取该区间的中点作为极小点要使区间缩小可采用区间消去法，即在初始单峰区间内任取两点，计算和比较它们函数值的大小，消去大函数值一边的区间，剩下的区间中一定包含极小点。设初始单峰区间为，取两点，令（1） 如果，则缩小的区间为（2） 如果，则缩小的区间为（3） 如果，则缩小的区间为最优步长可通过求单变量函数的极小点来获得，即。这种在第k次迭代中求最优步长的过程，就是一维搜索过程，所用的方法就是一维优化方法。一维优化方法很多，介绍确定初始区间的进退法、黄金分割法和二次插值法。6. 确定初始区间的进退法进退算法的基本思路为：对单峰函数任选一个初始点及初始步长h，由此可确定两点。通过比较这两点函数值的大小，来决定第三点的位置，确定它们是否为“高低高”形态，如是，则说明已找到单峰区间，否则向前或向后继续寻求下一点，直到三点函数值形成“高低高”形态。设有一维函数f（x），给定初始点x0,初始步长h，求初始搜索区间的步骤如下：（1） 给定初始点x0，初始步长h，令；比较，此时有三种情况：(a) 如果，说明极小点必在的右方，应向右（前进）搜索，加大步长，令转步骤（2）； (b) 如果，说明极小点必在的左边，应向左（后退）搜索，交换的值并令，转步骤（2）； （交换后仍然是）(c) 如果，说明极小点必在点和之间，本身就是“高低高”的形态，也就是说已经找到单峰区间（2） 取下一个计算点，计算；（3） 比较的大小，这个时候可能有二种情况：(a) 如果，则已经形成了“高低高”的形态，初始单峰区间已经找到，当时，输出初始单峰区间；当时，输出初始单峰区间为。 (b) 如果，则说明应继续搜索。令、，转步骤（2）例1. 试用进退算法确定函数的初始搜索区间，设初始点，初始步长h=1。解：按前述步骤计算：1. 2 因为，说明极小点在右方，故作前进运算，设步长加倍，取第三试点为3 因为，说明极小点在右方，故继续作前进运算，步长加倍。令；，取第三点为4.此时，因为，即这个相邻三点的函数值为形成了高低高的特征，故寻得初始搜索区间为。确定了初始单峰区间后，就可以进行一维寻优，适用的一维寻优方法一般可分为消去法和近似法两种。注意选择不同的初始点和步长其单峰区间可能不同。消去法就是不断消去部分搜索区间，逐步缩小最优点存在的范围，最终寻得近似的最优点。黄金分割法就是一种消去法。近似法是用一个多项式来近似代替目标函数，并用这个多项式的极小点作为目标函数的近似最优点。二次插值法就是一种近似法。二、 黄金分割法1. 基本原理在搜索区间a,b内适当插入两个内分点x1和x2(x1 f(x2)时，极小点必在x1,b中；当f(x1)f(x2)时，极小点必在a, x2中，如图所示，无论发生在那种情况，都将包含极小点的区间缩小，即可删去最左段或最右段，然后在保留下来的区间上做同样的处理，如此迭代下去，将使搜索区间逐步减小，直到满足预先给定的精度（终止准则）时，即获得一维优化问题的近似最优解。黄金分割法要求在区间a,b中插入的两点位置是对称的，如图所示，。设区间长为L，插入的每一点把区间分成较长的一段和较短的一段，如图所示，这样，无论删去那一段，保留的区间长度总是，在每次迭代中，整个区间的长度与较长一段长度的比等于较长一段长度与较短长度的比。即：式中比例系数黄金分割法之所以这样取点，是因为这样才能使得函数值在计算同样次数的条件下，取件搜索的最快，由于内分点在区间0.618处，因此黄金分割法也称为0.618法。例2：试用黄金分割法求解优化问题：允许误差。解：已知搜索区间和精度要求。（若无搜索区间可设定初始点和步长求得）1.根据题意单峰区间为2.取内分点并计算函数值3.比较函数值大小：因为，故可知新区间为，删去最右端，（在中再取内分点，把原来的x2变为新的b，原来的x1变为新的x2，原来的f1变为新的f2,找新的x1内分点。）即：比较函数值大小：因为4.判断是否满足精度要求：b-a=1.944-(-3)=3.944因此需要继续迭代下去，进一步缩短区间。表1 各次循环迭代的计算结果见表所示Nabx1x2f1f20-3.0005.0000.0561.9440.1157.6671-3.0001.944-1.1110.056-0.9860.1152-3.0000.056-1.832-1.111-0.306-0.9873-1.8320.056-1.111-0.665-0.987-0.8884-1.832-0.665-1.386-1.111-0.851-0.9875-1.386-0.665-1.111-0.940-0.997-0.9966-1.111-0.665-0.940-0.835-0.966-0.9737-1.111-0.835-1.006-0.940-0.999-0.9968-1.111-0.940-1.046-1.006-0.996-0.999各次循环迭代的计算结果从表中可见，区间缩短8次后，故计算可结束。最优解为：2. 迭代步骤步骤：1）给定单峰区间a,b（ab）及允许误差；2）计算内分点及其函数值：3）比较函数值f1和f2的大小，有以下两种情况：a.若，则极小点在a与x2之间，故令；b. 若，则极小点在x1与b之间，故令；4).判断是否满足精度要求，若新区间已缩短至预定精度要求，则转第5）步，否则转第3）步，进行下一次迭代计算。5）最终区间的中点即为近似最优点，其对应的函数值即为最优值，他们组成的最优解为：计算框图。三、 二次插值法1. 二次插值法的基本思想二次插值法是一种近似法，其基本思想是用原目标函数在任意三点的函数值来构造一个二次插值多项式，并将这个多项式的极小点作为目标函数的近似极小点。设x1，x2，x3是一维目标函数f(x)在初始单峰区间a,b中的三点，且x1 x2 x3,他们的函数值分别为且，得到三点，现把一维函数f(x)的作为二次插值多项式的插值点，式中a，b，c是待定系数，显然，在插值点出二次插值函数与目标函数应具有相同的函数值，即二次插值多项式满足解此方程得a，b，c的值分别为于是，插值函数p(x)就成为一个确定的二次多项式，通常称为二次插值函数。如图所示，二次插值函数就是通过目标函数f(x)曲线上的三点画出的一条方程为的曲线。可以认为此曲线的极小点x*就是原目标函数的近似极小点x*，由图可以看出该插值函数曲线在目标函数的单峰区间是一条开口向上的抛物线，故二次插值法又称为抛物线插值法。对二次插值函数求导数，并令其为零，得：故此插值多项式p(x)的极小点为：将上面求得的系数a，b代入上式，则得插值函数的极小点为：就是目标函数f(x)极小点的一个近似点，当搜索区间充分小时，如，（是一个给定的小的正数），既可看作是f(x)在区间a，b上的近似最优点。否则，继续进行插值计算，重复多次地向目标函数最优点逼近，直至满足给定的精度为止。（以此点作为下一次缩小区间的一个中间插入点，无疑将使新的插入点向极小点逼近的过程加快，二次插值法的中间插入点包含了函数在三个已知点上的函数值信息，因此选择这样的插入点比较接近函数的极小点。二次插值法以两个中间插入点的距离充分小作为收敛准则，即成立时，把作为此次一维搜索的极小点。）2. 算法步骤1） 确定初始区间a，b和精度，在区间内选取三点x1，x2，x3。一般取x1，x3分别为初始区间的左右端点，x2为区间的一个内点，开始时可取，并取x1，x2，x3对应的目标函数值：；2） 构造二次插值多项式，按计算式计算p(x)的极小点；3） 收敛判断：判断是否满足精度要求。 a. 若，说明搜索区间已足够小，当时，结束一维搜索点。输出目标函数的最优解，；否则，输出目标函数最优解x2,f(x2)。b. 若则需比较点与x2在搜索区间的相对位置及其对应的目标函数值的大小，以便缩短搜索区间，得到新的三点（该三点仍以x1，x2，x3表示，他们应保持两端点x1和x3的函数值大，中间点x2小的性质）。然后按第二步继续进行插值计算。搜索区间的缩小分四种情况（如PPT图）。图中阴影部分为消去的区间，缩小后的新区间保持函数值两头大中间小的性质。例3：试用二次插值法求解目标函数的极小值。给定。解：1）确定初始单峰区间由于 ，因继续向前搜索，令由于，所以初始单峰区间已经找到，为2) 用二次插值法逼近极小点（a） 将第一步求出的代入二次插值公式，求得插值点及其函数值：由于，故新区间为作精度检验：由于，故因继续作二次插值计算。（b） 在新区间内，相邻的三点依次为，将它们代入二次插值公式计算，得由于，故新区间为作精度检验：由于故结束一维搜索，极小点为本节思考题1 为什么一维搜索要以单峰区间为基础？2 黄金分割法和二次插值法缩减区间的原则是什么？第四节 无约束优化方法一、 梯度法1. 基本思想由前所述，梯度方向是函数增加最快的方向，而负梯度方向是函数下降最快的方向，所以梯度法以负梯度方向为搜索方向，每次迭代都沿着负梯度方向一维搜索，直到满足精度要求为止，因此，梯度法又称为最速下降法。设在某次迭代中已取得迭代点，从该点出发，取负梯度方向：为搜索方向式中这样，第k+1次迭代计算所得的新点为：，此式即为梯度法迭代公式。因为为已知，故和易求出，只要知道步长后，就可以得到新点，且能保证，如此反复计算，直到达到最优点。为了使目标函数值在搜索方向上获得最多的下降，沿负梯度方向一维搜索，从而求得最优步长。2. 迭代步骤1） 任选初始点，计算精度，令k=0；2） 计算点的梯度及梯度的模，并令；3） 判断是否满足精度指标，一般情况下，若，则为近似最优点，迭代停止，输出最优解=和，若不满足，转下一步；4） 以为出发点，沿负梯度方向求最优步长，即沿进行一维搜索，求能使函数值下降最多的步长因子。5） 确定新的近似点，此点就是下次迭代的出发点，即，令k=k+1转步骤2），直到满足精度要求为止。3. 举例例：用梯度法求函数的极小值，初始点，计算精度。解：1）计算梯度：2）计算函数在点的梯度及梯度的模：3）因为，不满足精度指标，转入第4）步；4）从出发，沿着方向一维搜索，将代入目标函数并求其极小值式中为单变量的一维函数，令所以求得一维优化的最优步长5）新点6）计算目标函数在点的梯度及梯度的模 由于已满足精度要求，故停止迭代下去，得到最优解为：二、 牛顿法1. 基本思想设目标函数是连续二阶可微的，将函数在点按泰勒级数展开，并取到二次项：（上式展开后为 对X求导，故无X的求导后均为零。）其极值点必满足一阶导数为零，所以，上式与一维搜索公式比较，相当于搜索方向为：，而步长因子为。对于二次函数，则从初始点出发，一步就可以达到优化点。这个搜索方向称为牛顿方向。2. 举例例：用牛顿法求函数的极小值。解：1）取初始点 2）计算牛顿方向故3）极小点：数学分析表明，牛顿法具有很好的局部收敛性质，对二次函数来说，仅一步就达到优化点，但对一般函数来说在一定条件下，当初始点的选取充分接近目标函数的极小点时，有很快的收敛速度，但若初始点选取离最小点比较远，就难保证收敛；另外，牛顿法必须求一阶、二阶导数及求逆阵，这对较复杂的目标函数来说，是较困难的。三、 共轭方向法1. 椭圆的共轭方向如图1所示的椭圆中，任意一组平行弦的中点的连线必位于过椭圆中心O的直线S上，这些平行弦所组成的直线族的方向S1与中点连线方向S互称为共轭方向，即S1与S互为共轭方向。椭圆中的平行弦的极限情况是与椭圆相切的弦S0，根据一维搜索观点，该弦S0与椭圆的切点就是沿S0方向的一维搜索的优化点。共轭方向的代数含义是：设有两个向量Si与Sj及阶对称正定矩阵A，若满足，则称两向量Si与Sj对于矩阵A共轭。2. 共轭方向的基本思想设二元函数的极值点为，将函数在展开成泰勒级数，并取其二次项，若其海色矩阵为正定矩阵，则其目标函数的等值线的极值点附近是近似的同心椭圆族，根据椭圆的共轭方向，只要沿两个相互平行的方向S1进行一维搜索，找出目标函数沿该两个方向的极小点，然后沿与S共轭的方向进行一维搜索，就可以求得目标函数的优化点，也就是说共轭方向法是以椭圆的共轭方向作为搜索方向的。在n维空间中，用数学归纳法可以证明，对n维二次目标函数，从任意点出发，可以找到n个共轭的向量，依次对这些向量分别进行一维搜索，就可以找到n维二次目标函数f(X)的极小点，即应用这种算法通过有限次（即n步），可以得到目标函数的极小点。如果一种算法，从理论上讲经过有限步的搜索可以求出二次目标函数的极小点，则称这种算法具有二次收敛性，因此，共轭方向法具有二次收敛性。基于共轭方向的思想，发展起来了多种共轭方向法，在此介绍比较成熟的三种方法：变尺度法、共轭梯度法和Powell法。四、 变尺度法变尺度法是优化方法在最近二十几年来发展起来的最有影响的研究成果之一，它被公认为是求解无约束极值问题的最有效的算法之一，这种方法是在牛顿法基础上发展起来的一种共轭方向法，用得较多的是DFP变尺度法。1. DFP(Davidon-Fletcher-Powell)牛顿法虽比梯度法收敛的快，但必须求目标函数的二阶导数及逆阵，不仅困难且工作量大，因此在牛顿法基础上Davidon-Fletcher-Powell提出了用一个近似矩阵代替求二阶导数及逆阵，而且该矩阵在每一次迭代中都不同，所以称为变尺度矩阵；另外在一维搜索中最优步长因子，变尺度法的搜索方向为：迭代公式为：2. 迭代步骤1） 取初始点，计算精度；2） 令k=0, ,I为单位阵，搜索方向；3） 一维搜索，这一步就是梯度法；4） 计算（k+1）步梯度；5） 判别精度指标：如果，则为极小点，否则转下一步；6） 计算近似矩阵，构造新的搜索方向式中所以，令k=k+1，转步骤3），直到满足精度要求为止。3. 举例例：用变尺度法求函数的极小值。解：1）取初始点，一维搜索最优步长因子为：附：一维搜索最优步长因子的求解因为，将代入目标函数并求其极小值：上式中为单变量的一维函数，令，即，所以，一维搜索最优步长因子为：。2）一维搜索3） 如何求呢？可利用4）搜索方向一维搜索得：最优步长因子，方法同前。与牛顿法比较其结果非常接近，从本例中可以看出用近似矩阵代替二阶导数及逆阵是可行的。如何判断结束？因为，即，因此，为极小点。解决此类问题的关键是求解。五、 共轭梯度法1. 基本思想从初始点出发，沿着该点负梯度方向一维搜索到，如图所示，然后从出发，按照与上一次搜索方向相共轭的方向进行搜索，也就是，A为对称正定矩阵，根据共轭方向原理，沿着方向一维搜索，就可以直接达到优化点。2. 梯度的递推公式设梯度用g表示，k+1点的梯度可以由k点的梯度推算出来，设目标函数是n维二次函数，式中A对称正定矩阵，梯度为：。现从出发，沿方向一维搜索得，由一维搜索的几何描述可知，搜索方向是处等值线的切线，而点的梯度与该切点切线方向垂直，所以，。与的梯度由式可得：以上两式相减得：上式就是梯度递推公式。当已知时，可计算。若目标函数是非二次函数，则可将函数按泰勒级数展开，忽略三次方以上的项，然后用二次函数来逼近。3. 共轭梯度方向共轭梯度法的关键是如何构造梯度的共轭方向，由上图可以看出，的方向可以看成是和的线性组合，即，此式中只要求出，则就可以求出。由式梯度递推公式两边乘以得：因为根据共轭方向的含义，所以，把代入得： 展开上式可得：因为，代入上式得：则有4. 迭代步骤（以二维为例）1） 取初始点，计算精度；2） 计算梯度，从出发，沿方向一维搜索到；3） 由式计算，由式计算；则 4） 从出发，沿方向一维搜索，就可以达到优化点。5. 举例例：用共轭梯度法求函数的极小值。解:1)第一步是梯度法，取初始点，沿方向一维搜索得： 2）计算点的梯度：，由计算 3）计算搜索方向4）从出发，沿着的方向一维搜索，其最优步长，由此可得：5）判断是否达到精度要求，则为极小点。从以上可以看出，对同一个目标函数，采用共轭梯度法只需经过两次迭代便达到极值点，所以共轭梯度法比梯度法收敛的快很多。共轭梯度法与梯度法一样，必须求目标函数的梯度，这对于较复杂的工程实际问题来说是很困难的。本节思考题1 梯度法、牛顿法、变尺度法的搜索方向确定的理论依据分别是什么？2 梯度法、牛顿法、变尺度法之间有什么内在联系？3 梯度法、牛顿法、变尺度法各有什么优缺点？第五节 约束优化方法一、概述与无约束优化问题不同的是，约束优化问题的目标函数的最小值是函数在有约束条件所限定的可行域内的最小值，并不一定是目标函数的自然最小值。约束优化方法是用来求解如下非线性约束优化问题的数值迭代算法。根据处理约束条件的不同方式，求解这类问题的方法分为直接法和间接法。直接法：在迭代过程中逐点考察约束的可行域，并使迭代点始终局限于可行域之内的算法称为直接法。常用的直接法有：复合形法、可行方向法、约束坐标轮换法、网格法、随即方向搜索法、随机实验法等；间接法：把约束条件引入目标函数，是约束优化问题转化为相对简单的二次规划问题或线性规划问题求解的算法称为间接法，常用的间接法有消元法、拉格朗日乘子法、惩罚函数法和序列线性规划法等。二、可行方向法数学基础：梯度法、方向导数、kt条件（库恩塔克条件）适用条件：目标函数和约束函数均为n维一阶连续可微函数、可行域是连续闭集的情况、求解不等式约束的一种直接解法。可行方向法是用梯度去求解约束非线性最优化问题的一种有代表性的直接解法，适用于目标函数和约束函数都是n维空间的一阶连续可微的函数，且可行域是连续闭集的情况，它是求解大型约束优化问题的主要方法之一。其收敛速度快，效果好，但程序比较复杂，直接算法，计算困难且工作量大。1可行方向法的基本思路在可行域内选择一个初始点，当确定了一个可行方向S和适当步长后，按下式：，进行迭代计算，通过调整可行方向，使其既不超出可行域，又使目标函数值有所下降，经过若干次迭代，使迭代点逐步逼近约束最优点。2产生可行方向的条件1）可行条件可行条件是指沿该方向作微小移动后，所得到的新点应是可行点。如图所示，若点在J个约束面的交集上，要满足可行条件，方向应和这J个约束函数在点的梯度的夹角均大于等于900，若用向量关系式表示为：。2）下降条件方向下降条件是指沿该方向作微小移动后，所得新点的目标函数值是下降的，而且下降的愈快愈好，显然，如果负梯度方向是可行方向，那么沿负梯度方向进行移动最有利。满足下降条件的方向应和目标函数在点的梯度交成钝角。用向量关系式可.表示为：。综上所述，可行方向就是满足可行和下降条件，若用几何表示，见下图。可行下降方向区是位于点的约束曲线的切线与目标函数等值线的切线所围成的扇形区域内，用向量关系式表示为： 可行方向 下降条件满足上式的方向称为可行方向。由此确定的可行方向多，但是否最快最有呢？3）最佳下降可行方向在一个点的所有下降的可行方向中，使目标函数取得最大下降量的方向称为最佳可行方向，显然，当点处于可行域内时，目标函数的负梯度方向就是最佳下降可行方向，当点处于几个起作用约束的交点或交线上，即有： 时，只能提供下降可行方向的范围，而不能直接给出最佳下降可行方向，但是可以在满足上述可行条件的前提下，通过方向导数极小化（保证最佳）的求解得到最佳下降可行方向。考察目标函数在点的方向导数，由于梯度是常数向量，则方向导数是S的线性函数，故最佳下降可行方向的寻求可归结为以下线性规划问题。式中：为常数向量，用线性规划的单纯形解法可以方便地求出使目标函数下降最快的可行方向，即最佳下降可行方向S。问题：有约束是否可行应进行判断？3约束一维搜索所谓约束一维搜索是指求解一元函数约束极小点的算法，与前面讲的一维搜索相比，其特点在于，确定初始区间时，对产生的每一个探测点都进行可行性判断，如果违反了某个或某些约束条件，就必须减小步长因子，以使新的探测点落在最近的一个约束曲面上或约束曲面的一个允许的区间内，如下图所示。若得到的相邻三个探测点都是可行点，而且函数值呈“大小大”变化，则与前述一维搜索相同，两端点所决定的区间就是初始区间，接着缩小区间得到一维