工程设计中的优化方法教学课件PPT.ppt

第5章 工程设计中的优化方法,优化设计的基本概念和步骤 优化设计方法的种类和特点 优化设计方法的原理和应用,优化设计的数学模型和基本步骤 无约束优化方法,重点：,内容：,优化结构几何参数，使构件质量最轻或用料最省,优化材料配方或成分，使材料的性能最佳,优化工艺参数，使产品性能最佳,用成分不同的原料进行配料，设计成本最低的配料方案,5.1 最优化问题概述,0. 工程中的最优化设计问题,结构优化,材料优化,工艺优化,配料优化,注：所有设计都要在一定的约束条件下进行,1. 优化设计的涵义,一种新的设计方法，应用数学的一个分支。它能使一项设计在一定技术和物质条件下，获得一个技术经济指标最佳的设计方案，应用广泛.,在给定的技术、经济等客观条件下选择设计参数，使设计指标达到最优值 在一定约束条件下求多变量函数极值的方法,优化设计是研究和解决在一切可能方案中寻求最优方案的科学方法。,优化设计主要研究内容 建模理论和方法(从实际问题中抽象出最优数学模型)； 求解最优化问题的理论和方法。,优化设计的基本思想 从研究对象的整体来考察和解决问题，并从组成整体各个部分的相互联系、相互影响和相互制约中寻求最优方案。,优化设计的基本步骤 分析实际问题建立数学模型选择优化方法求解最优方案,2. 优化设计的数学模型,数学模型是优化设计的基础。要对一个实际设计问题进行优化，首先必须建立问题的数学模型。,优化设计问题的数学模型，是指用数学符号和公式描述优化设计问题的一种模型。,(1) 设计变量,一个设计方案可以用一组设计参数来表示。,需要在设计过程中优选的独立参数,根据设计要求事先给定的参数（值不变）,设计变量表示方法,设计空间：以设计变量为坐标轴所构成的空间 设计空间的维数：即设计变量的个数 n个设计变量即构成n维设计空间（记为XRn）。,设计空间及其维数,设计变量的数目,选择余地或影响不大的参数，根据经验定为常量。,设计变量个数应尽量减少。,选定原则：只把与问题本质有关、对结果影响大的参数定为设计变量。,连续变量：值能连续变化。 离散变量：值不能连续变化。,设计变量的类型,对于离散变量的优化设计问题，通常先按连续变量处理，找到最优解后，再按工艺规范或标准系列调整。,在优化设计中，用于评价设计变量好坏的函数，称为目标函数，记作,优化目标函数就是求目标函数的极小值或极大值，即 min f (X) 或 max f (X)。,(2)目标函数,对目标函数进行优化，就可以得到最优方案。,f (X)=f (x1, x2, ···, xn),用效果函数(如性能指标、利润等)作目标函数，则是求极大值； 用费用函数(如能源、材料、经费等)作目标函数，则求极小值。,单目标优化问题：只包含一个优化目标的问题 多目标优化问题：存在两个或两个以上优化目标的问题,单目标和多目标优化问题,一般来讲，目标函数越多，设计结果越趋完善，但优化设计的难度也相应加大。,实际中应尽量控制目标函数的数量，抓住问题的主要矛盾，保证重点要求的实现，其余要求可处理成设计约束来加以保证。,例如：一个结构应满足的强度和刚度等条件。,(3) 约束条件,约束条件的定义：对设计变量取值的限制条件。,约束条件的数目 约束条件愈接近实际，则最优解愈接近最优方案。但约束条件数增加时，可行方案数量将大大减少，计算工作量也会增大。,约束条件的类型 边界约束 设计变量的变化范围（如板材厚度范围） 性能约束 由某种性能设计要求导出的约束条件(如结构设计中，弯曲应力必须小于或等于许用弯曲应力等),hi(X)=hi(x1, x2, ···, xn)=0 i=1, 2, ···, m, mn,约束条件的类型,不等式约束,等式约束,同一个优化设计问题可同时含有等式和不等式约束。,对于不等式约束，0型和0型可互相转化。方法是改变约束条件的符号，即令 gj(X)= -gj(X),gj(X)=gj(x1, x2, ···, xn)0 或 0 j=1, 2, ···, p,约束条件把设计空间划分为两个区域：可行域和不可行域。,可行域和可行点,可行域 域内设计点（设计方案）满足所有约束条件。可行域内的设计点称为可行点。,约束优化设计中，最优点一般是约束区域的边界点，即设计点位于某个约束面上： gu(X)=0 (1up),优化设计的数学模型是实际设计的数学抽象。 任何一个优化设计问题可归结为如下描述： 在给定的约束条件下，选择适当的设计变量X，使其目标函数 f (X)达到最优值。,（4）数学模型,建立数学模型是解决优化设计的关键,其数学表达式(数学模型)为,优化设计数学模型的简化表示,s.t.“满足于”或“受约束于”；Rnn维欧氏空间,利用优化方法求解上述数学模型，可得到一组最优设计参数或一个最优设计方案,X*称为最优点，f(X*) 称为最优值。 最优点和最优值构成一个约束最优解。,X* = (x1*, x2*, ··· , xn*)T,优化设计问题的最优解,实际工程的优化设计问题：非线性约束优化问题,优化设计问题的类型,例5-1 已知箱形梁的长度l和载荷F1、F2，许用挠度 f = l /700。设梁高为x1，梁宽为x2，腹板厚度为x3，翼缘板的厚度为x4。 试设计该箱形梁，使其质量最轻。 (长度单位为mm，力的单位为N),设计变量 取箱形梁横截面待定尺寸x1，x2，x3及x4为设计变量，则,目标函数 优化目标为质量最轻。 梁的跨度已知，故可用梁的截面面积作为目标函数。截面面积之半可近似为,f (X) = x1x3 + x2x4,使质量最轻就是使f (X)的值最小。,X = x1, x2, x3, x4 T，XR4,（忽略了-2x3x4项,厚度的乘积）,约束条件 设计的箱形梁需满足一定的强度、刚度、稳定性以及几何要求。推导得,箱形梁优化设计的数学模型,属约束非线性规划问题。选用可行方向法求解。,表5-1 箱形梁设计结果比铰,优化结果：取出三种跨度的优化结果见表5-1。 所用数据为：F1=120kN， F2=12kN，=140MPa,3. 优化设计的计算方法,求解无约束优化问题,求解约束优化问题,解析法 用求导数或变分方法求出极值存在的必要条件，再求出它们的解析解。然后按照充分条件或问题的实际物理意义确定最优解。 仅适用于目标函数和约束条件较为简单明确的情况。,无约束优化方法,数值法 利用函数在某一局部区域的性质和一些己知点的数值，确定下一步的计算点，经过迭代搜索，最后达到最优点。可解决复杂的优化设计问题，是优化设计采用的主要方法。,无约束优化方法分为解析法和数值计算法两类。,根据处理问题的方法，约束优化方法可分为两大类：,约束优化方法,直接解法 直接从可行域中找出约束最优解X* 和 f (X*)。如： 网格法、随机试验法、随机方向搜索法、复合形法、可行方向法等。,间接解法 将约束优化设计求解问题，转换成求无约束极值问题。 可用于求解同时存在不等式约束和等式约束的优化设计问题。以惩罚函数法应用最为广泛。,无约束优化方法的特点和适用范围,约束优化方法的特点和适用范围,4. 优化设计的一般步骤,优化设计是一种规格化的设计。一般步骤为:,（1）分析设计问题，建立数学模型,对生产或试验数据进行统计分析，求出回归方程； 对不能实际试验的问题通过模拟建立数学模型； 把理论公式或经验公式作为数学模型； 根据物理概念和逻辑推理建立数学模型。,建模方法,回归设计是建立数学模型的有效方法。它利用正交表等编制试验方案，直接求出回归方程。 常用回归设计方法：多元线性回归设计、回归正交设计、回归旋转设计、D-最优设计、混料回归设计等。,编制调试计算程序,（2）选择优化方法，求解最优方案,正确选择优化方法,计算过程中，要随时注意计算结果。必要时要及时调整输入参数，使解不断得到改善。,选择原则：计算程序简单，满足精度要求，稳定可靠，计算效率高，节约时间,尽量利用现有优化程序。当需引用各种图表数据时，应编制查找和捡取这些数据的专门子程序。,这是优化设计极为重要的环节。,（3）分析计算结果，评价优化方案,检查最优点的合理性和可行性； 分析目标函数的最优值； 分析约束函数值、判断最优点位置； 分析设计变量的敏感度。,主要内容,排除计算机输出的不合理或不正确的结果； 分析判断优化方案优劣，作出圆满的最终决策。,主要任务,分析检查的内容,敏感度：设计变量微小变化引起目标函数值变化的程度,对结果分析作出肯定的结论后，一般即可按优化设计方案组织实施。,优化方案的实施,重要的工程设计问题 生产中不可控因素较多的问题 变量不能严格控制的问题,求最优点X* = x1*, x2*T 和最优值 f (X*) 。,5. 优化设计的几何解释和基本解法,(1) 几何解释,对于一个二维问题,设计变量X=x1,x2T 设计空间维数：2 不等式约束数：4 二维非线性规划 求极小值问题,最优解,二维非线性优化问题的几何解释,同心圆簇,(n+1)维立体图,约束最优设计点：可行域内目标函数值最小的点，它是约束边界与目标函数等值线的切点,数值解法的主要思想 从一个初始设计点X(k)出发，沿着某个搜索方向S(k)以适当步长hk的方式实现对X(k)的修改，以获得新点X(k+1)值。迭代公式为,（2）基本解法,求函数f (X)极值点的迭代算法,首先选定初始设计点X(0)，从X(0)出发沿某一规定方向S(0)求函数f (X)的极值点，设此点为X(1):,X (k+1)=X (k) +h(k) S (k),X (1)=X (0) +h (0) S (0),X(k+1)=X(k)+h(k)S(k),寻求极值点的搜索过程,再从X(1)出发沿某一规定方向S(1)求f (X)的极值点，设此点为X(2)。如此继续，···。,一般地，从点X出发，沿某一规定方向S(k)求函数f(X)的极值点X(k) (1, 2 , ···, n)。这样的搜索过程,组成了求n维函数f(X)极值的基本过程。,确定搜索方向S(k)； 计算最佳步长hk。,求极值的基本过程是通过一系列的搜索过程来完成的。其核心是：,搜索过程是逐步逼近最优点而获得近似解的过程，因此需要考虑： 优化问题解的收敛性 迭代过程的终止条件,求极值的核心问题,由此产生了各种优化方法,收敛性与终止条件,根据收敛条件，可以确定迭代终止准则。,迭代终止准则,点距准则 相邻两设计点（迭代点）的距离达到充分小时。若用向量模计算长度，则,函数下降量准则 当相邻两次迭代点函数值的下降量达到充分小时终止迭代。即,| X (k+1) X (k) |,：预先给定的迭代精度或允许误差,梯度准则 当某次迭代点目标函数梯度模达到充分小时终止迭代，即,| f (X (k) |,若上述准则之一满足，则认为目标函数值已收敛到最小值，这样即求得近似最优解： X*=X(k+1) 实际中常将点距和函数下降量准则结合起来使用，即要求两者同时满足。,最优解的确定,5.2 无约束最优化方法,目标函数或约束条件为非线性函数的规划问题属非线性规划。它是优化设计中最常见的数学形式.,中，有一个或多个函数是变量X的非线性函数，则此最优问题称为非线性规划。,1. 非线性规划,若在数学模型,min f (X) gi(X)0, ( i=1, 2, ···, m mn) hj(X) = 0, ( j=1, 2, ···, p) XRn,线性规划：f (X)、gi (X) 、hj (X)为线性函数时。 二次规划：f (X)为二次函数， gi (X) 、h j (X)为线性函数时。它是一种特殊的非线性规划。,应用最多的求解方法是将非线性规划转换成无约束最优问题来求解，即将有约束的最优化问题化为无约束最优问题。 对无约束问题的求解，具有十分重要的意义。,非线性规划问题的求解方法,函数的等值线：当函数f (X)的值依次等于一系列常数时，自变量取得一系列值的集合。,（1）函数的等值线（面）,2. 目标函数的无约束极值问题,当二维函数f(X)的值依次取不同的实数时，其相应的水平面与空间曲面的交线为一组椭圆，它们在x1ox2平面上的投影就是一族椭圆曲线。 同一曲线上任意点(x1,x2)所对应的函数f(X)值都相等，故称这族曲线为函数f(X)的等值线。,对于三维以上的函数（n维函数），具有共同函数值的点构成一族曲面，称函数f(X)的等值面族。,函数等值线在极值处聚成一点，并位于等值线族的中心。当该中心为极小值时，离中心越远函数值越大。,在极值点附近，n元函数的等值面一般为一族近似的椭球面，它们共同的中心就是n元函数的极值点。,求函数极值点亦即求函数最优点问题，可归结为求其等值线（面）同心椭圆（椭球面）族的中心。 根据求椭圆（椭球面）族中心的不同途径，就形成了各种不同的优化方法。,极值点附近等值线呈椭圆形，等值线较密的部位，目标函数值变化越迅速。目标函数非线性程度越严重，等值线形状越复杂，且可能存在多个极值点。,梯度定义：n元函数f (x1,x2, ···,xn)的梯度,即梯度是由函数 f (X)一阶偏导数组成的n维列向量。,(2) 函数的梯度,梯度的模,梯度方向：函数等值线（面）的法线方向,梯度与函数的等值线相互垂直，其方向沿函数等值线的法线指向函数值增加的一侧.,梯度正方向是函数值最速上升（增加最快）方向；梯度负方向或负梯度方向是函数值最速下降方向。,梯度f (X)是一个向量，其方向是函数f (X)具有最大变化率的方向。,梯度的主要特征,沿某点的梯度方向，函数值在该点附近增长最快。 反之，沿某点的负梯度方向，函数值在该点附近下降最快。,多元目标函数可用其在某点的泰勒展开式近似。,(3) 多元函数的泰勒展开式,多元函数f(X)在点X(k)的泰勒展开式（只取到二阶偏导数项）,xi、xj 变量x的第i、j个分量； n变量的个数,函数在X (k)点处对xi的一阶偏导,函数在X (k)点处对xi, xj的二阶偏导,即函数f (X)在点X (k)的一阶偏导数的列向量。,矩阵形式,函数f (X)在点X (k)的二阶偏导数，它是一个n×n阶的对称方阵，称为函数f (X)在点X (k)的海森(Hessian)矩阵。,梯度,多元函数在极值点附近的等值线簇为同心椭圆簇，即目标函数在极值点附近是二次函数。因此，多元函数常用其泰勒展开式的前三项近似表示（精度已足够），记为,与矩阵形式对应,多元函数的近似表达式,二元二次函数的表达形式,一般二元二次函数,f (X) = mx12 + nx22 + px1x2 + b1x1 + b2x2 + c,矩阵表达式,A函数的二阶偏导数矩阵，对称方阵。,二次函数的梯度,f (X) = AX+B,B函数一次项系数列向量。,补充知识,(4) 多元函数无约束极值条件,对于n元函数 f (x1, x2, ···, xn)的无约束极值问题,点X*为一个局部极值点的充分必要条件,一阶导数向量f(X *)=0，即,二阶导数矩阵2f (X*)，即海森矩阵H(X *)为正定或负定，且 当H(X *)为正定时X *为极小点； 当H(X *)为负定时X *为极大点。,min f (X) , XRn,若矩阵A各阶顺序主子式均大于零，即当A=aij时,则该矩阵A是正定的；,不符合正、负定条件的矩阵，是不定矩阵。对于这类矩阵，不可用上述方法判别点X*是否为极值点，而需用更高阶的导数来判定.,若各阶顺序主子式呈负、正交替变化，即一切偶数阶的主子式都是正数，一切奇数阶主子式都是负数，则该矩阵A是负定的。,判断矩阵A正定或负定的方法,3. 无约束最优问题的直接搜索解法,一维搜索法是多维搜索法的基础 多维寻优可转化为一维寻优问题求解,基本思想：在搜索过程中逐步缩小搜索区间，直至最优点存在的范围达到允许误差为止。,对单变量目标函数 f (x)寻优，即 min f (x)。 亦即 求函数 f (x)的极小点 x* 和极小值 f * = f (x*)。,（1）消去法,消去法是搜索单变量函数极值的有效方法。,时停止迭代，得到最优解为,再选一个x3，求出f3=f(x3) ，并比较f3和min(f1, f2) 如此继续下去，直到第n次迭代，满足,x* = xn ， f * = fn,数值迭代法求解过程 从一个初始点 x1开始，求出 f1=f (x1) 。 按一定规律，另选一个点 x2，求出 f2=f (x2) 。 比较 f1和 f2，去掉其中较大者。,f (x1) f (x2) 最优点x*在区间a, x2内，可将区间x2, b消去。令b=x2，得到已缩小的新搜索区间a, b 。,若目标函数f (x)的极小点x*在a, b闭区间内，则,消去法搜索过程,在 a, b内选取两个试点 x1和 x2（x1x2）分别代入目标函数，求出 f1=f(x1)和 f2=f(x2)。 比较 f (x1)和 f (x2)。可能有三种情况：,f(x1) f(x2) 最优点x*在x1, b内，可将区间a,x1消去，令a=x1，得到缩小的新搜索区间a, b。,f(x1) = f(x2) 最优点x*在x1, x2内，可消去两侧任意一个区间，如消去a, x1，则搜索范围缩小为a, b，a=x1。,在新的搜索区a, b内重新选试点，并重复计算。每迭代一次，搜索区就缩短一次。 经过 n 次迭代后，若满足|b-a|要求，则可认为最优解: x*=(a+b)/2，f *=f(x*) 。,需要解决的两个问题 初始搜索区间a, b的确定(区间内必须包含极小点)。 通常采用进退法确定。,测试点x1和x2的选取。可按黄金分割法选取，即,x1=a+(1-)(b-a)，x2=a+(b-a) =0.618（黄金分割数）,确定最优解所在区间的进退法（补充）,用数值法求一维函数f(x)的极小点x*，必须先确定极小值所在区间。确定该区间的算法，称为进退法。,一维函数最小值所在区间满足高-低-高的原则，边界是函数值高的两点。,只要区间内某点的函数值小于两边界点的函数值，此区间即为所求。,进退法定区间的步骤,任意给出自变量的一个初始值x1和前进步长h； 从x1出发，可求出x2=x1+h 及f(x1)、f(x2)。 比较f(x1)和f(x2) ：,f(x1)f(x2) 极值点在x1右边，h的方向正确，步幅可能较小，取h=2h，转入第步。,f(x1)f(x2) 函数极值点在x1左边，h增加方向错误，应取h = - h (后退)进行计算。 为减小计算工作量，将x1与x2、f(x1)与f(x2)的值互换。转入第步。, 计算新的试探点x3=x2+h和函数值f(x3)， 比较f(x2)和f(x3)：,f(x3)f(x2)，表明在x1,x2之间没有最小值，做代换x1=x2，x2=x3，f(x2)= f(x3)，继续计算x3。,注：初始步长h一般应取较小的值，如取收敛精度值的10倍左右。取值过大，有可能不收敛。,f(x3)f(x2)，表明在x1,x3 存在最小值，取a=min(x1,x3)，b=max(x1,x3)，输出a, b即得最小值所在的区间,f(x3)f(x2),f(x3)f(x2),进退法确定区间的算法框图,前进,输入初始自变量和步长x1,h,计算f(x1)和x2=x1+h,f(x2),h=-h x1与x2，f(x1)和f(x2)互换 x3=x2+h,计算f(x3),h=2h x3=x2+h 计算f(x3),x1=x2,x2=x3,f(x2)=f(x3) x3=x2+h，计算f(x3),x1,x3满足高-低-高 a=min(x1,x3),b=max(x1,x3),结束,f(x1)f(x2)?,f(x2)f(x3)?,N,N,Y,Y,后退,黄金分割法基本步骤,1) 给出初始搜索区间a，b和收敛精度。 2) 在区间a,b内插入两点x1和x2，并计算函数值f(x1)和f(x2)。,使用黄金分割法，相邻两次搜索区间的缩短率为0.618。,3) 比较f(x1)和f(x2)大小，缩短搜索区间，进行区间名称代换. 4) 检查区间是否缩短到足够小，或函数值收敛到足够接近。如果条件不满足，则到步骤5），否则到步骤6）。,x1=a+(1-)(b-a)，x2=a+(b-a) =0.618（黄金分割数）,5) 在保留区间中计算一个新测试点及相应函数值，转步骤3) 6) 取最后两次测试点的平均值作为极小点的数值近似解，并计算该点的函数值作为目标函数的最优解。,黄金分割法程序框图,a,b可用进退法确定,例题用黄金分割法求单变量函数f(x)=x2-7x + 10的极小点，初始搜索区间a,b=2,8,迭代精度=0.35。,解：在搜索区间a,b内取两试点x1和x2，计算它们的函数值：,x1=b-0.618(b-a)=8-0.618×(8-2)=4.292 f1=f(x1)=4.2922-7×4.292+10=-1.6227 x2=a+0.618(b-a)=2+0.618×(8-2)=5.708 f2=f(x2)=5.7082-7×5.708+10=2.6253,比较函数值f1和f2，缩短搜索区间,由于f1f2，消去右区间(x2,b，令 b=x2=5.708，x2=x1=4.292，f2=f1=-1.6227, x1=b-0.618(b-a)=5.708-0.618(5.708-2)=3.4165 f1=f(x1)=3.41652-7×3.4165+10=-2.2430,x*=(b-a)/2=(3.5971+3.2863)/2=3.4417,f*=f(x*)=-2.2466,判断迭代终止条件 b-a=5.708-2=3.708 不满足迭代终止条件。再取两试点x1和x2，并且比较函数值f1与f2，继续缩短搜索区间。,搜索区间经6次缩短后，区间长度为 b-a=3.5971-3.2863 可以终止迭代，得到近似极小点和最优值,利用若干点的函数值，构造一个低次的插值多项式P(x) ，去逼近要求极小值的函数f(x )； 用解析法求出P(x) 导数的根，作为目标函数f(x ) 极小值的近似位置。 重复应用这一方法进行迭代计算，直到得出符合要求的结果。,常用插值多项式有二次和三次的，因此分别称为二次插值法和三次插值法。,（2）插值法,基本思想,在目标函数f(x)的寻优区间a, b内任取三点x1、x2、x3，且x1x2x3，相应的函数值为f1=f(x1)、f2=f(x2)和f3=f(x3)。过此三点构造一条抛物线，并以此抛物线近似原目标函数。,二次插值法,构造的抛物线为二次方程,求待定系数 将x1、x2、x3代入上式，可求出系数a1和a2：,P(x) = a0a1 xa2 x2,令P(x)的导数为0，可求出近似抛物线的极小点x0，即,求极小点和极小值,代入目标函数，得,迭代求解 去掉 f1与 f2中较大者，将剩下的两个预选点和 x0 组成一个新的“三点组”，然后重复上述过程，进行二次迭代，直到满足允许误差的要求为止。,如果 | f2f0 | ，则选其小者为最优解。 若不满足收敛条件，则转下一步。,判断终止条件,注：首先要确定初始搜索区间a,b。,二次插值法收敛速度快，有效性好，但可靠性差，适用于多维优化的一维搜索迭代。,多维优化的一维搜索,在求多维目标函数的极值点时，大多数方法都要进行一系列的一维搜索。 多维搜索的迭代格式为 X(k+1)=X(k)+hS(k) (h为步长因子),搜索新点X(k+1)时，出发点X(k)和搜索方向S(k)均已确定。这样，问题就变成了过点X(k)沿S(k)方向求函数f(X)极小点X*的一维搜索问题。,沿S(k)方向求原函数f(X)的极小点X*，实际转化为求单变量函数f(h) =f(X(k)+hS(k)为极小值时的步长因子h，即,通过一维搜索求得的步长因子h，称为最优步长因子。,minf(X(k)+hS(k)=f(X(k)+h(k)S(k),将最优步长h代入迭代式中，即得新点： X(k+1)=X(k)+hS(k),多维优化一维搜索示意图,多维搜索法。其原理是将多维无约束最优化问题转化为一系列沿坐标轴方向的一维问题求解.而一维寻优问题可用消去法或插值法求解。,（3）坐标轮换法,（降维法）,首先沿x1方向搜索，即固定x2(0)，只改变x1。,h1为优化步长，可用一维寻优方法求得，即,第一轮搜索,目标函数转化为单变量x1的函数，可得目标函数沿x1方向的极小点，即,目标函数转化为单变量x2的函数，可得目标函数沿x2方向的极小点，即,再沿x2方向搜索，即固定x1(1)，只改变x2。,优化步长h2可用一维寻优方法求得，即,至此，第一轮结束（坐标轮换一周），得到两个目标函数值逐次下降的迭代点X1(1)和X2(1)。,X的上角码表示轮数，下角码i表示该轮中第i个迭代点,完成第一个轮计算后，如满足,则目标函数的极小点 X*X2(1)。否则，进行第二轮搜索。,以前一轮得到的第二个迭代点（如X2(1) ）为新起点进行搜索，进行k轮迭代得到迭代点X2(k),若此时满足精度，则X2(k)即为所求最优点X*。,第二轮以后的搜索,注意：每轮迭代都依次沿两个坐标方向进行一维搜索，且每轮搜索的次序应一致。,(本轮终点与始点的距离),先将n-1个变量固定不变，只对一个变量（一般先对x1）进行一维搜索，得到沿该坐标方向的一个目标函数极小点X1(1)；,然后再将x1轴固定在X1(1)点上，并使变量x3,x4, ···,xn固定不变，仅使x2变化，沿x2轴进行一维搜索，求沿该方向上的最小点X2(1)；依次类推。,n维函数的寻优,当分别沿坐标方向x1,x2, ···,xn进行一次搜索后，即完成一个轮计算， 得到最小点Xn(1) 。 判断是否满足精度要求，否则重复上述步骤。,总之，每次都固定n-1个变量不便，依次轮换地对一个变量进行一维搜索，这样就把一个n维优化问题转化为求解一系列的一维优化问题。,对于第 k 轮迭代，其迭代公式为,Xi-1(k)为第 k 轮第 i 次迭代初始点；Si(k) 为第 k 轮第 i 次搜索方向，它轮换地取 n 维坐标的单位向量，即,Si(k)=ei=0, ···,1, ···,0（第 i 个分量为1，其余为0）,hi(k)为第 k 轮第 i 次迭代步长因子，可正可负。一般采用一维优化方法确定，即,(1) 取初始点X(0)和收敛精度，并令k =1，同时置n个坐标方向矢量为单位坐标矢量e1=1 0 0 ··· 0T，e2=0 1 0 ··· 0T，···，en=0 0 0 ··· 1T。 (2) 按迭代公式计算Xi(k)，k为迭代轮数的序号，取k=1,2, ···，i为该轮中一维搜索的序号，依次取i=1, 2, ···,n。步长hi(k)通过一维优化方法求得。,迭代步骤,若上式成立，迭代终止，输出最优解X*=Xn(k) ，否则，令k=k+1，X0(k+1)Xn(k)返回步骤(2)，进行下一轮搜索.,(3) 按点距准则判断是否收敛：,开始,给定X(0),n,e1,k=1,x(k)=x(0),i=1,si(k)=ei,沿Si(k)方向一维搜索求得i(k) Xi(k)=Xi-1(k)+ hi(k) Si(k),i=n?,|Xn(k)-X0(k)|,输出X*=Xn(k+1) f*=f(X*),结束,i=i+1,k=k+1 X0(k)=Xn(k-1),坐标轮换法计算框图,N,N,坐标轮换法特点及应用 搜索路线较长，计算效率低。一般仅适用于n10的小型优化问题的求解。 此法的效能在很大程度上取决于目标函数的性质。 收敛速度慢，应用不普遍。,（4）共轭方向与鲍威尔法,鲍威尔（Powell）法又称方向加速法，它是利用共轭方向可以加快收敛速度的性质形成的一种搜索方法。 该法不用对目标函数求导，当目标函数的导数不连续时也能应用。因此，鲍威尔法是一种十分有效的直接搜索法。,搜索方向：共轭方向,设A为n阶实对称正定矩阵，若两个n维向量S1和S2满足,则称向量S1与S2对矩阵A共轭，共轭向量的方向称为共轭方向。,共轭方向的概念,S1T A S2 = 0,则称向量组S1、S2、···、Sk关于矩阵A共轭，即对于同一实对称正定矩阵A，可以根据需要取不同的对A共轭的方向组。,如果非零向量组S1、S2、Sk中任意两个向量关于n阶对称正定矩阵A共轭，既满足,SiT A Sj = 0 ij，i, j=1,2, ···, k,S1T I S2 = 0 即 S1T S2 = 0,此时的S1、S2为两正交向量，正交向量的方向称为正交方向。显然，正交是共轭的特例。,二次正定函数f (X)在坐标平面上的等值线是一族同心的椭圆。,共轭方向的几何意义,二次函数的共轭方向,设A为n×n阶实对称正定矩阵，S1,S2, ···,Sn为对A共轭的n个非零向量，则这组向量线性无关。 对于n维优化问题，共轭向量的个数最多等于n。 单位坐标向量系是一组线性无关的共轭向量，且它们也是正交向量系。,共轭向量的重要性质,设A为n×n阶实对称正定矩阵，Si（i=1,2, ···, n）是关于A的n个互相共轭的非零向量，对于正定二次函数f (X)的极小化寻优问题，从任何初始点出发，依次沿 Si 方向经n次一维搜索即可收敛到极小点X*=X(n)。（搜索次数）,二元二次正定函数等值线的中心就是函数的极小点。 任意两条平行线与椭圆两个切点X(1)和X(2)的连线必通过极小点。,二次函数极小值的搜索,X(0),S1 S2 X(0) X(1) X*,若以X(0)为起始点，分别沿S1、S2方向作两次一维搜索，即可到达二元二次正定函数的极小点.,将切线的方向记为S1，连线方向记为S2，则S1与S2为共轭方向。,对于n元二次正定函数，沿其n个共轭方向进行n次一维搜索就可到达目标函数的极小点。,鲍威尔法的基本算法,S(1)与等值线相切，再沿S(1)方向作一维搜索，求得极小点X3(1)。,选定一起始点X(0)，以坐标轴单位向量 e1=1,0T、e2= 0,1T作为初始搜索方向。,从X0(1)=X(0)出发，沿 x1轴作一维搜索，得到搜索点X1(1)；,再以X1(1)为新的初始点x2轴作一维搜索得到搜索点X2(1)；,连接X2(1)和X0(1)二点，其连线作为新的方向S(1)，即 S(1)=X2(1)-X0(1),X3(1),从X0(2)=X3(1)出发，舍去x1方向，沿x2方向作一维搜索，求得极小点X1(2)； 再以X1(2)为新的始点沿S2(2)=S(1)方向进行一维搜索，求得极小点X2(2)； 连X2(2)与X0(2)点，构成新的方向S(2)，则 S(2)=X2(2)-X0(2),再沿S(2)方向进行一维搜索，求得极小点X3(2)。,第 k 轮得到的共轭方向： S(k)=Xn(k)-X0(k) n为维数。,X3(2)相当于从X0(1)出发分别沿A的两个共轭方向S(1)、S(2)进行两次一维搜索而得到的点，所以 点X3(2)即为二维问题的极小点X *。,符号：X的上角码k表示轮数，下角码i表示该轮中第i个迭代点。 S的上角码表示轮数，下角码i表示该轮中第i次搜索方向。,从初始点出发时，也可先沿x2方向搜索，再沿x1方向搜索。,共轭方向法只适用于目标函数近似于椭圆簇的情况，通常远离极小点处，目标函数的等值线不能用椭圆簇来近似，所以计算机计算时，先用坐标轮换法搜索，然后再用共轭方向法进行精搜索的办法较为有效。,对于二维非二次目标函数，按泰勒公式可以用二次函数来逼近，等值线在极小点X*附近呈现近似的有心椭圆簇。 因此，X(2)不一定是目标函数的极小点，需要以X(2)为新起点，继续进行第二轮、第三轮迭代···，直到满足精度要求。,几点说明：,对于共轭方向法（初始鲍威尔法），有时新产生n个方向有可能出现线性相关或近似于线性相关的情况(就是向量平行或近似平行)，从而导致计算不能收敛。此法不实用。 修正的鲍威尔法：在形成新方向组时，有选择地去掉某一方向（不一定去掉前一轮的第一个搜索方向），以避免线性相关性。 按照这一原则重置方向就可保证算法是收敛的。这是一种实用的方法。,例5-3 设目标函数,从X(0)=(0,0)T出发搜索，求极小点。,该函数的极值点为 X* = (8,6)T, f (X*) = 8。,f (X)=x12+x22-x1x2-10x1-4x2+60,沿x2轴方向，按坐标轮换法进行一维搜索，求最优步长,令 X0(1)=X(0)=(0,0)T，S1(1)=(0,1)T，S2(1)=(1,0)T,第一轮迭代,沿x1轴方向进行一维搜索，求最优步长,X2(1)=X1(1) + h2S2(1)=(h2, 2)T,f (X2(1)=56-12h2+h22,df (X2(1)/dh2= -12+2h2=0,得 h2=2。于是 X2(1)=(6,2)T, f (X2(1)=20,沿X2(1)-X0(1)方向进行一维搜索。因 S3(1)为单位向量，则,df (X3(1)/dh3 = 0,得 h3=1.357。于是 X3(1)=(7.238, 2.429)T,第一轮迭代到此结束，共进行了三次迭代。,S3(1),X0(2),求步长h3和X3(1),以第一轮迭代的终点X3(1)作为起点，即令X0(2)=X3(1) 先沿x2(?)轴方向进行一维搜索，令S1(2)=S1(1)，求出最优步长。得到最优点,第二轮迭代,X1(2)=(7.286, 5.643)T,连接X0(2)和X2(2)，得向量X2(2)-X0(2)，此方向的单位向量S3(2) 。S3(2)是S3(1)和S2(2)两条平行线切点的连线方向，因此S3(2)和S3(1)对A共轭。,可见对二元二次函数，用共轭方向法经过两轮六次迭代即可获得最优点，即极小点,在每轮获得新方向Sn+1(k)后，在组成新方向组时，有选择地去掉前一轮方向组中某一个方向Sm(k)（1mn），以避免新产生的方向组中各方向出现线性相关的情形。,修正的鲍威尔法,用Sn+1(k)方向组成新的搜索方向组的判别条件：,同时成立，则用Sn+1(k)方向，并且挤掉Sm(k)；否则仍用原来的n个搜索方向。,若,f1= f (X0(k) 第 k 轮起始点函数值； f2 = f (Xn(k) 第k轮方向组一维搜索终点函数值； f3 = f (2Xn(k) - X0(k) X0(k)对Xn(k)的映射点函数值；,修正的鲍威尔法虽然计算稍微复杂一些，但它保证了非线性函数寻优计算可靠的收敛性。,第k轮方向组沿诸方向一维搜索所得的各函数下降量中最大者，其相对应的方向即是Sm(k)。,(1) 给定初始点X0和计算精度，令k=1，Si(k)= ei(i=1,2,···,n)，即取初始方向组为n个单位坐标向量；X0(1) =X0, i=1, k=1。,(3) 经计算求出共轭方向和影射点分别为,修正鲍威尔法的计算步骤,(4) 计算k轮中相邻两点目标函数值的下降量，并求出下降量最大者及其相应的方向：,若至少其中之一成立，则由Xn(k)出发沿S(k)方向进行一维搜索，求出目标函数f(X)的极小点X(k)，并作为k+1轮的初始点，即X0(k+1) X(k)， 然后进行第k+1轮搜索，其搜索方向为挤掉Sm(k)，并令S(k+1) S(k)，即,注: 新一轮的方向组是在前一轮的方向组中去掉Sm(k)，同时把S(k)放在方向组的最后构成。,(6) 若上述判断条件不满足，则置k+1轮的初始点和方向组为：,即此时k+1轮的n个搜索方向全部用第k轮的搜索方向。,计算框图,min(f(Xi-1(k)+iSi(k) =f(Xi-1(k)+hi(k)Si(k),4. 无约束问题的梯度解法,使用导数的间接寻优法 。 对于可以求得目标函数导数的多变量寻优问题，这类方法收敛速度快，应优先选用。,最