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

1、第第5章章 工程设计中的优化方法工程设计中的优化方法n 优化设计的基本概念和步骤优化设计的基本概念和步骤n 优化设计方法的优化设计方法的种类种类和特点和特点n 优化设计方法的原理和优化设计方法的原理和应用应用l 优化设计的数学模型和基本步骤优化设计的数学模型和基本步骤l 无约束优化方法无约束优化方法重点：重点：内容：内容：优化结构几何参数，使构件质量优化结构几何参数，使构件质量最轻或用料最省最轻或用料最省优化材料配方或成分，使材料的优化材料配方或成分，使材料的性能最佳性能最佳优化工艺参数，使产品性能最佳优化工艺参数，使产品性能最佳用成分不同的原料进行配料，设用成分不同的原料进行配料，设计成本最

2、低的配料方案计成本最低的配料方案5.1 最优化问题概述最优化问题概述0. 工程中的最优化设计问题工程中的最优化设计问题 结构优化结构优化 材料优化材料优化 工艺优化工艺优化 配料优化配料优化注：所有设计都要在一定的约束条件下进行注：所有设计都要在一定的约束条件下进行一种新的设计方法，应用数学的一个分支。它一种新的设计方法，应用数学的一个分支。它能使一项设计在一定技术和物质条件下，获得能使一项设计在一定技术和物质条件下，获得一个技术经济指标最佳的设计方案，应用广泛一个技术经济指标最佳的设计方案，应用广泛. 在给定的技术、经济等客观条件下选择设计在给定的技术、经济等客观条件下选择设计参数，使设计指

3、标达到最优值参数，使设计指标达到最优值 在一定约束条件下求多变量函数极值的方法在一定约束条件下求多变量函数极值的方法优化设计是研究和解决优化设计是研究和解决在一切可能方案中寻求在一切可能方案中寻求最优方案最优方案的科学方法。的科学方法。n 优化设计主要研究内容优化设计主要研究内容 建模理论和方法建模理论和方法(从实际问题中抽象出最优数学模型从实际问题中抽象出最优数学模型)； 求解最优化问题的理论和方法。求解最优化问题的理论和方法。n 优化设计的基本思想优化设计的基本思想 从研究对象的整体来考察和解决问题，并从从研究对象的整体来考察和解决问题，并从组成整体各个部分的相互联系、相互影响和组成整体各

4、个部分的相互联系、相互影响和相互制约中寻求最优方案。相互制约中寻求最优方案。n 优化设计的基本步骤优化设计的基本步骤 分析实际问题分析实际问题建立建立数学模型数学模型选择选择优化方优化方法法求解最优方案求解最优方案2. 优化设计的数学模型优化设计的数学模型 数学模型是优化设计的基础。要对一个实际设计数学模型是优化设计的基础。要对一个实际设计问题进行优化，首先必须建立问题的数学模型。问题进行优化，首先必须建立问题的数学模型。优化设计问题的数学模型，是指用数学符号和公优化设计问题的数学模型，是指用数学符号和公式描述优化设计问题的一种模型。式描述优化设计问题的一种模型。 设计变量设计变量 目标函数目

5、标函数 约束条件约束条件该数学模型包含三个要素：该数学模型包含三个要素：(1) 设计变量设计变量一个设计方案可以用一组设计参数来表示。一个设计方案可以用一组设计参数来表示。设计参数设计参数设计常量设计常量设计变量设计变量 需要在设计过程中优选需要在设计过程中优选的独立参数的独立参数根据设计要求事先给定根据设计要求事先给定的参数的参数（值不变）（值不变） 设计变量表示方法设计变量表示方法Xn维列向量，维列向量，T转置符，转置符，Rnn维设计空间维设计空间设有设有n个设计变量个设计变量x1，x2，xn，则，则X = (x1, x2, , xn)T XRn设计空间：以设计变量为坐标轴所构成的空间设计

6、空间：以设计变量为坐标轴所构成的空间设计空间的设计空间的维数维数：即设计变量的即设计变量的个数个数 n个设计变量即构成个设计变量即构成n维设计空间维设计空间（记为（记为XRn）。设计空间及其维数设计空间及其维数设计变量、设计空间和设计方案之间的关系一组设计变量设计空间一点一个设计方案Px1x2x3 三维设计空间R3设计变量的数目设计变量的数目选择余地或影响不大的参数，根据经验定为常量。选择余地或影响不大的参数，根据经验定为常量。设计变量个数应尽量减少设计变量个数应尽量减少。选定原则：只把与问题本质有关、对结果影响选定原则：只把与问题本质有关、对结果影响大的参数定为设计变量。大的参数定为设计变量

7、。连续变量：值能连续变化。连续变量：值能连续变化。离散变量：值不能连续变化。离散变量：值不能连续变化。设计变量的类型设计变量的类型对于离散变量的优化设计问题，通常先按连续变量处对于离散变量的优化设计问题，通常先按连续变量处理，找到最优解后，再按工艺规范或标准系列调整。理，找到最优解后，再按工艺规范或标准系列调整。在优化设计中，用于评价设计变量好坏的函数，在优化设计中，用于评价设计变量好坏的函数，称为目标函数，记作称为目标函数，记作 优化目标函数就是求目标函数的极小值或极大优化目标函数就是求目标函数的极小值或极大值值，即，即min f (X) 或或 max f (X)。(2)目标函数目标函数对目

8、标函数进行优化，就可以得到最优方案。对目标函数进行优化，就可以得到最优方案。f (X)=f (x1, x2, , xn) 用用效果函数效果函数( (如性能指标、利润等如性能指标、利润等) )作目标函数，则是作目标函数，则是求极大值求极大值； 用用费用函数费用函数( (如能源、材料、经费等如能源、材料、经费等) )作目标函数，则作目标函数，则求极小值求极小值。 单目标优化问题：只包含一个优化目标的问题单目标优化问题：只包含一个优化目标的问题多目标优化问题：存在两个或两个以上优化目多目标优化问题：存在两个或两个以上优化目标的问题标的问题n 单目标和多目标优化问题单目标和多目标优化问题一般来讲，目标

9、函数越多，设计结果越趋完善，一般来讲，目标函数越多，设计结果越趋完善，但优化设计的难度也相应加大。但优化设计的难度也相应加大。实际中实际中应尽量控制目标函数的数量应尽量控制目标函数的数量，抓住问题，抓住问题的主要矛盾，保证重点要求的实现，其余要求的主要矛盾，保证重点要求的实现，其余要求可处理成设计约束来加以保证。可处理成设计约束来加以保证。 例如：一个结构应满足的强度和刚度等条件。例如：一个结构应满足的强度和刚度等条件。(3) 约束条件约束条件n 约束条件的定义：对设计变量取值的限制条件。约束条件的定义：对设计变量取值的限制条件。n 约束条件的数目约束条件的数目 约束条件愈接近实际，则最优解愈

10、接近最优约束条件愈接近实际，则最优解愈接近最优方案。但约束条件数增加时，可行方案数量将方案。但约束条件数增加时，可行方案数量将大大减少，计算工作量也会增大。大大减少，计算工作量也会增大。n 约束条件的类型约束条件的类型 边界约束边界约束 设计变量的变化范围设计变量的变化范围（如板材厚度范围）（如板材厚度范围） 性能约束性能约束 由某种性能设计要求导出的约束条由某种性能设计要求导出的约束条件件(如结构设计中，弯曲应力必须小于或等于许用弯曲应力等如结构设计中，弯曲应力必须小于或等于许用弯曲应力等) hi(X)=hi(x1, x2, , xn)=0 i=1, 2, , m, mnn 约束条件的类型约

11、束条件的类型 不等式约束不等式约束 等式约束等式约束 同一个优化设计问题可同时含有等式和不等式同一个优化设计问题可同时含有等式和不等式约束。约束。 对于不等式约束，对于不等式约束，0型和型和0型可互相转化。方型可互相转化。方法是改变约束条件的符号，即令法是改变约束条件的符号，即令gj(X)= -gj(X)gj(X)=gj(x1, x2, , xn)0 或或 0 j=1, 2, , pm，p 等式约束数和不等式约束数。等式约束数和不等式约束数。 hi(X)， gj(X)约束函数约束函数；约束条件把设计空间划分为两个区域：可行域约束条件把设计空间划分为两个区域：可行域和不可行域。和不可行域。n 可

12、行域和可行点可行域和可行点 可行域可行域 域内设计点（设计域内设计点（设计方案）满足所有约束条件。方案）满足所有约束条件。可行域内的设计点称为可行域内的设计点称为可行点可行点。约束优化设计中，约束优化设计中，最优点一般是约束区域的边界点最优点一般是约束区域的边界点，即设计点位于某个约束面上：即设计点位于某个约束面上： gu(X)=0 (1up)不可行域可行域gu(X)=0设计空间 不可行域不可行域 域内的设计点域内的设计点不不满足或不全满足约束条件。满足或不全满足约束条件。不可行域内的设计点不可行域内的设计点称为称为不可行点不可行点，一般是工程实际，一般是工程实际不能接受的方案不能接受的方案。

13、优化设计的数学模型是实际设计的数学抽象。优化设计的数学模型是实际设计的数学抽象。任何一个优化设计问题可归结为如下描述：任何一个优化设计问题可归结为如下描述：在给定的约束条件下，选择适当的设计变量在给定的约束条件下，选择适当的设计变量X，使其目标函数使其目标函数 f (X)达到最优值。达到最优值。（4）数学模型）数学模型建立数学模型是解决优化设计的关键设计变量设计变量 在满足约束方程在满足约束方程 的条件下，求目标函数的条件下，求目标函数f (X)的最优值。的最优值。X= (x1, x2, , xn)T XRnhi(X)=0, i=1, 2, , mgj(X)0, j=1, 2, , p其数学表

14、达式其数学表达式(数学模型数学模型)为为 n 优化设计数学模型的简化表示优化设计数学模型的简化表示s.t.“满足于满足于”或或“受约束于受约束于”；Rnn维欧氏空间维欧氏空间利用优化方法求解上述数学模型，可得到一组最优设利用优化方法求解上述数学模型，可得到一组最优设计参数或一个最优设计方案计参数或一个最优设计方案X*称为称为最优点最优点，f(X*) 称为称为最优值最优值。最优点和最优值构成一个最优点和最优值构成一个约束最优解约束最优解。min f (X), XRnhi(X)=0, i=1, 2, , mgj(X)0, j=1, 2, , ps.t.X* = (x1*, x2*, , xn*)T

15、n 优化设计问题的最优解优化设计问题的最优解实际工程的优化设计问题：实际工程的优化设计问题：非线性约束优化问题非线性约束优化问题 n 优化设计问题的类型优化设计问题的类型 线性规划问题线性规划问题 优化问题的目标函数和优化问题的目标函数和约束函数都是设计变量的线性函数约束函数都是设计变量的线性函数 非线性规划问题非线性规划问题 目标函数和约束函数目标函数和约束函数不全是设计变量的线性函数不全是设计变量的线性函数函数与函数与变量间变量间的关系的关系 无约束优化问题无约束优化问题 只有目标函数而无约只有目标函数而无约束条件的优化问题束条件的优化问题 约束优化问题约束优化问题 有约束条件的优化问题有

16、约束条件的优化问题有无约有无约束条件束条件例例5-1 已知箱形梁的长度已知箱形梁的长度l和载荷和载荷F1、F2，许用挠度许用挠度 f = l /700。设梁高为。设梁高为x1，梁宽为，梁宽为x2，腹板厚度为腹板厚度为x3，翼缘板的厚度为，翼缘板的厚度为x4。试设计该箱形梁，使其试设计该箱形梁，使其质量最轻质量最轻。(长度单位为长度单位为mm，力的单位为，力的单位为N)x1x2x3x4箱形截面梁计算简图F1F2ll / 2设计变量设计变量 取箱形梁横截面待定尺寸取箱形梁横截面待定尺寸x1，x2，x3及及x4为设计变量，则为设计变量，则目标函数目标函数 优化目标为优化目标为质量最轻质量最轻。 梁的

17、跨度已知，故可用梁的梁的跨度已知，故可用梁的截面面积截面面积作为目作为目标函数。截面面积之半可近似为标函数。截面面积之半可近似为 f (X) = x1x3 + x2x4 使质量最轻就是使使质量最轻就是使f (X)的值最小。的值最小。X = x1, x2, x3, x4 T，XR4 （忽略了-2x3x4项,厚度的乘积）约束条件约束条件 设计的箱形梁需满足一定的设计的箱形梁需满足一定的强度、强度、刚度、稳定性以及几何要求刚度、稳定性以及几何要求。推导得。推导得式中，k1=3l/4；W=x1x3+x2x4, k2=F1l3/(16.810-5)。强度条件刚度条件(梁跨中挠度限制)翼缘板局部稳定性条件

18、腹板局部稳定性条件几何约束条件（板厚不得小于5mm）03310000/8 . 7)(4223212321421111xxxxxFxxxxxWlFkXg03)(331422122fxxxxxkXg060)(423xxXg0160)(314xxXg05)(35xXg05)(46xXgf f （厚度与宽度之比）箱形梁优化设计的数学模型箱形梁优化设计的数学模型属约束非线性规划问题属约束非线性规划问题。选用。选用可行方向法可行方向法求解。求解。跨度l(cm)常规设计（mm）优化设计(mm)减轻自重（%）x1x2x3x4x1x2x3x410501350165076088010103403904406661

19、01010790870102031038037056686819.818.813.7表5-1 箱形梁设计结果比铰 min f (X), XR4gj(X)0, j=1, 2, , 6s.t.优化结果优化结果：取出三种跨度的优化结果见表：取出三种跨度的优化结果见表5-1。所用数据为：所用数据为：F1=120kN， F2=12kN，=140MPa3. 优化设计的计算方法优化设计的计算方法 无约束优化方法无约束优化方法约束优化方法约束优化方法优化方法优化方法解析法解析法数值法数值法直接法直接法间接法间接法无约束优化方法是优化设计的基础无约束优化方法是优化设计的基础许多约束优化问题可转化为无约束优化问题

20、求解许多约束优化问题可转化为无约束优化问题求解求解无约束优化问题求解约束优化问题解析法解析法 用求导数或变分方法求出极值存在的用求导数或变分方法求出极值存在的必要条件，再求出它们的解析解。然后按照充必要条件，再求出它们的解析解。然后按照充分条件或问题的实际物理意义确定最优解。分条件或问题的实际物理意义确定最优解。 仅适用于目标函数和约束条件较为简单明确的情况。仅适用于目标函数和约束条件较为简单明确的情况。n 无约束优化方法无约束优化方法数值法数值法 利用函数在某一局部区域的性质和一利用函数在某一局部区域的性质和一些己知点的数值，确定下一步的计算点，经过些己知点的数值，确定下一步的计算点，经过迭

21、代搜索，最后达到最优点。迭代搜索，最后达到最优点。可解决复杂的优可解决复杂的优化设计问题，是化设计问题，是优化设计采用的主要方法优化设计采用的主要方法。 无约束优化方法分为解析法和数值计算法两类。无约束优化方法分为解析法和数值计算法两类。根据处理问题的方法，约束优化方法可分为两大类：根据处理问题的方法，约束优化方法可分为两大类：n 约束优化方法约束优化方法直接解法直接解法 直接从可行域中找出约束最优解直接从可行域中找出约束最优解X* 和和 f (X*)。如：如： 网格法、随机试验法、随机方向搜索法、复网格法、随机试验法、随机方向搜索法、复合形法、可行方向法等。合形法、可行方向法等。间接解法间接

22、解法 将约束优化设计求解问题，转换成将约束优化设计求解问题，转换成求无约束极值问题。求无约束极值问题。 可用于求解同时存在不等式约束和等式约束的可用于求解同时存在不等式约束和等式约束的优化设计问题。优化设计问题。以惩罚函数法应用最为广泛。以惩罚函数法应用最为广泛。计算方法特点及适用范围直接搜索法消去法黄金分割法 黄金分割法计算过程简单，收敛较快，应用较广Fibonacci插值法二次插值法 二次插值法算法成熟，收敛较快，应用广。函数性态较好时，其效果比消去法好三次插值法爬山法-非导数法坐标轮换法 计算简单，占内存少，收敛慢，可靠性差，适用于维数n10共轭方向法 收敛较快，可靠性较好，占用内存少，

23、特别适用于n1| f (X(k+1) f (X(k) | f (X (k+1) 1 梯度准则梯度准则 当某次迭代点目标函数梯度模达到当某次迭代点目标函数梯度模达到充分小时终止迭代，即充分小时终止迭代，即| f (X (k) |若上述准则之一满足，则认为目标函数值已收若上述准则之一满足，则认为目标函数值已收敛到最小值，这样即求得敛到最小值，这样即求得近似最优解近似最优解：X*=X(k+1)实际中常将点距和函数下降量准则结合起来使实际中常将点距和函数下降量准则结合起来使用，即要求两者同时满足。用，即要求两者同时满足。最优解的确定最优解的确定5.2 无约束最优化方法无约束最优化方法目标函数或约束条件

24、为非线性函数的规划问题属目标函数或约束条件为非线性函数的规划问题属非线性规划。它是优化设计中最常见的数学形式非线性规划。它是优化设计中最常见的数学形式.中，中，有一个或多个函数是变量有一个或多个函数是变量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)为二次函数，为二次

25、函数， gi (X) 、h j (X)为为线性函数时。它是一种特殊的非线性规划。线性函数时。它是一种特殊的非线性规划。 应用最多的求解方法是将非线性规划转换成无应用最多的求解方法是将非线性规划转换成无约束最优问题来求解，约束最优问题来求解，即将有约束的最优化问即将有约束的最优化问题化为无约束最优问题。题化为无约束最优问题。对无约束问题的求解，具有十分重要的意义。对无约束问题的求解，具有十分重要的意义。n 非线性规划非线性规划问题的求解方法问题的求解方法函数的等值线：当函数函数的等值线：当函数f (X)的值依次等于一系的值依次等于一系列常数时，自变量取得一系列值的集合。列常数时，自变量取得一系列

26、值的集合。（1）函数的等值线（面）函数的等值线（面）2. 目标函数的无约束极值问题目标函数的无约束极值问题 当二维函数当二维函数f(X)的值依次取不同的的值依次取不同的实数时，其相应的水平面与空间曲实数时，其相应的水平面与空间曲面的交线为一组椭圆，它们在面的交线为一组椭圆，它们在x1ox2平面上的投影就是一族椭圆曲线。平面上的投影就是一族椭圆曲线。同一曲线上任意点同一曲线上任意点(x1,x2)所对应的函所对应的函数数f(X)值都相等，故称这族曲线为值都相等，故称这族曲线为函数函数f(X)的的等值线等值线。x*二维函数f(x)的等值线x1x2f(x)f(x)abcd 对于三维以上的函数（对于三维

27、以上的函数（n维函数），具有共同函数值维函数），具有共同函数值的点构成一族曲面，称函数的点构成一族曲面，称函数f(X)的的等值面等值面族。族。 函数等值线在极值处聚成一点，并位函数等值线在极值处聚成一点，并位于等值线族的中心。于等值线族的中心。当该中心为极小当该中心为极小值时，离中心越远函数值越大。值时，离中心越远函数值越大。 在极值点附近，在极值点附近，n元函数的等值面一般为一族近似的元函数的等值面一般为一族近似的椭球面，它们共同的中心就是椭球面，它们共同的中心就是n元函数的极值点。元函数的极值点。 求函数极值点亦即求函数最优点问题，可归结为求其等值线（面）同心椭圆（椭球面）族的中心。根据求

28、椭圆（椭球面）族中心的不同途径，就形成了根据求椭圆（椭球面）族中心的不同途径，就形成了各种不同的优化方法。各种不同的优化方法。 极值点附近等值线呈椭圆形，等值线较密的部位，目标函数值变化越迅速。极值点附近等值线呈椭圆形，等值线较密的部位，目标函数值变化越迅速。目标函数非线性程度越严重，等值线形状越复杂，且可能存在多个极值点。目标函数非线性程度越严重，等值线形状越复杂，且可能存在多个极值点。极值点极值点驻点驻点二维目标函数等值线二维目标函数等值线f(X)=x24-2x2x12+x22+x12-2x1+5f(X)=4+4.5x1-4x2+x12+2x22-2x1x2+x14-2x12x2n 梯度定

29、义：梯度定义：n元函数元函数f (x1,x2, ,xn)的梯度的梯度即梯度是由函数即梯度是由函数 f (X)一阶偏导数组成的一阶偏导数组成的n维列向量维列向量。(2) 函数的梯度函数的梯度n 梯度的模梯度的模n 梯度方向：函数等值线（面）的法线方向梯度方向：函数等值线（面）的法线方向 梯度梯度与函数的等值线相互垂与函数的等值线相互垂直，直，其方向沿函数等值线的其方向沿函数等值线的法线指向函数值增加的一侧法线指向函数值增加的一侧. x1函数的负梯度方向S-Sx2 梯度正方向是函数值最速上升（增加最快）方向；梯度正方向是函数值最速上升（增加最快）方向；梯度负方向或梯度负方向或负梯度方向是函数值最速

30、下降方向负梯度方向是函数值最速下降方向。 梯度梯度f (X)是一个向量，其方向是函数是一个向量，其方向是函数f (X)具有最具有最大变化率的方向。大变化率的方向。n 梯度的主要特征梯度的主要特征 沿某点的梯度方向，函数值在该沿某点的梯度方向，函数值在该点附近增长最快。点附近增长最快。 反之，反之，沿某点的负梯度方向，函沿某点的负梯度方向，函数值在该点附近下降最快。数值在该点附近下降最快。多元目标函数可用其在某点的泰勒展开式近似。多元目标函数可用其在某点的泰勒展开式近似。(3) 多元函数的泰勒展开式多元函数的泰勒展开式多元函数多元函数f(X)在点在点X(k)的泰勒展开式（的泰勒展开式（只取到二阶

31、偏导数项）只取到二阶偏导数项）xi、xj 变量变量x的第的第i、j个分量；个分量； n变量的个数变量的个数函数在函数在X (k)点处对点处对xi的一阶偏导的一阶偏导函数在函数在X (k)点处对点处对xi, xj的二阶偏导的二阶偏导)()(21)()()()()()(1,)(2)(1)()(KjjKiinjijiKKiiniiKKxxxxxxXfxxxXfXfXf即函数即函数f (X)在点在点X (k)的一阶偏导数的列向量。的一阶偏导数的列向量。n 矩阵形式矩阵形式函数函数f (X)在点在点X (k)的二阶偏导数，它是一个的二阶偏导数，它是一个nn阶的对称方阶的对称方阵，称为函数阵，称为函数f

32、(X)在点在点X (k)的的海森海森(Hessian)矩阵矩阵。)()()()()()()()()()()()(2)(22)(21)(22)(222)(212)(21)(221)(221)(2)(2KnKnKnKnKKKnKKKKXHxXfxxXfxxXfxxXfxXfxxXfxxXfxxXfxXfXfTnKKKKxXfxXfxXfXf)(,)(,)()()(2)(1)()()()(21)()()()()()(2T)()(T)()(KKKKKKXXXfXXXXXfXfXf梯度梯度多元函数在极值点附近的等值线簇为同心椭圆多元函数在极值点附近的等值线簇为同心椭圆簇，即簇，即目标函数在极值点附近是二

33、次函数目标函数在极值点附近是二次函数。因。因此，多元函数常用其泰勒展开式的前三项近似此，多元函数常用其泰勒展开式的前三项近似表示（精度已足够），记为表示（精度已足够），记为与矩阵形式对应n 多元函数的近似表达式多元函数的近似表达式CXBAXXXfTT21)(一般二元二次函数一般二元二次函数f (X) = mx12 + nx22 + px1x2 + b1x1 + b2x2 + c 矩阵表达式矩阵表达式X =x1x2B =b1b2A = =a11 a12a21 a222m p p 2nA函数的二阶偏导数矩阵，对称方阵。函数的二阶偏导数矩阵，对称方阵。 二次函数的梯度二次函数的梯度f (X) = A

34、X+BB函数一次项系数列向量。函数一次项系数列向量。补充知识对于对于n元函数元函数 f (x1, x2, , xn)的无约束极值问题的无约束极值问题n 点点X*为一个局部极值点的充分必要条件为一个局部极值点的充分必要条件一阶导数向量一阶导数向量f(X *)=0，即，即二阶导数矩阵二阶导数矩阵2f (X*)，即海森矩阵，即海森矩阵H(X *)为为正定或负定正定或负定，且，且 当当H(X *)为正定时为正定时X *为极小点；为极小点； 当当H(X *)为负定时为负定时X *为极大点。为极大点。min f (X) , XRnnixXfi, 2 , 1, 0*)(若矩阵若矩阵A各阶顺序主子式均大于零，

35、即当各阶顺序主子式均大于零，即当A=aij时时则该矩阵则该矩阵A是正定的是正定的；不符合正、负定条件的矩阵，是不符合正、负定条件的矩阵，是不定矩阵不定矩阵。对于这类矩阵，不可。对于这类矩阵，不可用上述方法判别点用上述方法判别点X X* *是否为极值点，而需用更高阶的导数来判定是否为极值点，而需用更高阶的导数来判定. .若各阶顺序主子式呈若各阶顺序主子式呈负、正交替变化负、正交替变化，即一切，即一切偶数阶的主子式都是正数，一切奇数阶主子式偶数阶的主子式都是正数，一切奇数阶主子式都是负数，则该矩阵都是负数，则该矩阵A是是负定负定的。的。n 判断矩阵判断矩阵A正定或负定的方法正定或负定的方法3. 无

36、约束最优问题的直接搜索解法无约束最优问题的直接搜索解法 消去法消去法插值法等插值法等坐标轮换法坐标轮换法共轭方向法等共轭方向法等梯度法梯度法牛顿法牛顿法共轭梯度法等共轭梯度法等一维搜索法一维搜索法单变量函数寻优单变量函数寻优多维搜索法多维搜索法多变量函数寻优多变量函数寻优无约无约束优束优化法化法直接寻优法直接寻优法( (不用导数不用导数) )间接寻优法间接寻优法 ( (使用导数使用导数) )一维搜索法是多维搜索法的基础一维搜索法是多维搜索法的基础多维寻优可转化为一维寻优问题求解多维寻优可转化为一维寻优问题求解基本思想：在搜索过程中基本思想：在搜索过程中逐步缩小搜索区间逐步缩小搜索区间，直至最优

37、点存在的范围达到允许误差为止。直至最优点存在的范围达到允许误差为止。对单变量目标函数对单变量目标函数 f (x)寻优，即寻优，即 min f (x)。亦即亦即求函数求函数 f (x)的极小点的极小点 x* 和极小值和极小值 f * = f (x*)。（1）消去法）消去法消去法是搜索消去法是搜索单变量函数单变量函数极值的有效方法。极值的有效方法。时停止迭代，得到最优解为时停止迭代，得到最优解为再选一个再选一个x3，求出，求出f3=f(x3) ，并比较，并比较f3和和min(f1, f2)如此继续下去，直到第如此继续下去，直到第n次迭代，满足次迭代，满足| xn-xn-1 | 或或 | fn- f

38、n-1 | x* = xn ， f * = fn数值迭代法求解过程数值迭代法求解过程 从一个初始点从一个初始点 x1开始，求出开始，求出 f1=f (x1) 。 按一定规律，另选一个点按一定规律，另选一个点 x2，求出，求出 f2=f (x2) 。 比较比较 f1和和 f2，去掉其中较大者。，去掉其中较大者。b f (x1) f (x2) 最优点最优点x*在区间在区间a, x2内，内，可将区间可将区间x2, b消去。令消去。令b=x2，得到已缩小的新搜，得到已缩小的新搜索区间索区间a, b 。若目标函数若目标函数f (x)的极小点的极小点x*在在a, b闭区间内，则闭区间内，则 消去法搜索过程

39、消去法搜索过程在在 a, b内选取两个试点内选取两个试点 x1和和 x2（x1x2）分别代）分别代入目标函数，求出入目标函数，求出 f1=f(x1)和和 f2=f(x2)。比较比较 f (x1)和和 f (x2)。可能有三种情况：。可能有三种情况：xax*bf(x)f(x1) f(x2) 最优点最优点x*在在x1, b内，可将内，可将区间区间a,x1消去，令消去，令a=x1，得，得到缩小的新搜索区间到缩小的新搜索区间a, b。 f(x1) = f(x2) 最优点最优点x*在在x1, x2内，可消内，可消去两侧任意一个区间，如去两侧任意一个区间，如消去消去a, x1，则搜索范围缩，则搜索范围缩小

40、为小为a, b，a=x1。xax*bf(x)f(x1) f(x2) x2x1f(x1) = f(x2) xax*bf(x)x2x1在新的搜索区在新的搜索区a, b内重新选试点，并重复计内重新选试点，并重复计算。每迭代一次，搜索区就缩短一次。算。每迭代一次，搜索区就缩短一次。经过经过 n 次迭代后，若满足次迭代后，若满足|b-a|f(x2) 极值点在极值点在x1右边，右边，h的方向正确，步的方向正确，步幅可能较小，取幅可能较小，取h=2h，转入第，转入第步。步。 f(x1)f(x2) 函数极值点在函数极值点在x1左边，左边，h增加方向错增加方向错误，应取误，应取h = - h (后退后退)进行计

41、算。进行计算。 为减小计算工作量，将为减小计算工作量，将x1与与x2、f(x1)与与f(x2)的值互换。转入第的值互换。转入第步。步。x0f(x)f(x1) x1x2f(x2)f(x1)f(x2) 计算新的试探点计算新的试探点x3=x2+h和函数值和函数值f(x3)， 比较比较f(x2)和和f(x3)： f(x3)f(x2)，表明在，表明在x1,x3 存在最小值，存在最小值，取取a=min(x1,x3)，b=max(x1,x3)，输出，输出a, b即得最小值所在的区间即得最小值所在的区间x0f(x)f(x2) x2x1x3f(x3)f(x1)x0f(x)f(x2) x2x1x3f(x3)f(x

42、1)f(x3)f(x2)进退法确定区间的算法框图进退法确定区间的算法框图前进输入初始自变量和步长x1,h计算f(x1)和x2=x1+h,f(x2)h=-hx1与x2，f(x1)和f(x2)互换x3=x2+h,计算f(x3)h=2hx3=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)?NNYY后退n黄金分割法基本步骤黄金分割法基本步骤1) 给出初始搜索区间给出初始搜索区间a，b和收敛精度和收敛精度。2) 在区间在区间a,b内插

43、入两点内插入两点x1和和x2，并计算函数值，并计算函数值f(x1)和和f(x2)。使用黄金分割法，相邻两次搜索区间的缩短率为使用黄金分割法，相邻两次搜索区间的缩短率为0.6180.618。3) 比较比较f(x1)和和f(x2)大小，缩短搜索区间，进行区间名称代换大小，缩短搜索区间，进行区间名称代换.4) 检查区间是否缩短到足够小，或函数值收敛到足够接近。检查区间是否缩短到足够小，或函数值收敛到足够接近。如果条件不满足，则到步骤如果条件不满足，则到步骤5），否则到步骤），否则到步骤6）。）。x1=a+(1-)(b-a)，x2=a+(b-a) =0.618（黄金分割数）（黄金分割数）5) 在保留区

44、间中计算一个新测试点及相应函数值，转步骤在保留区间中计算一个新测试点及相应函数值，转步骤3)6) 取最后两次测试点的平均值作为极小点的数值近似解，并取最后两次测试点的平均值作为极小点的数值近似解，并计算该点的函数值作为目标函数的最优解。计算该点的函数值作为目标函数的最优解。黄金分割法程序框图输入输入 a,b,x1=a+0.382(b-a), f1=f(x1)x2=a+0.618(b-a), f2=f(x2)f1f2?b=x2, x2=x1, f2= f1x1=a+0.382(b-a), f1=f(x1)a = x1, x1= x2, f1= f2x2=a+0.618(b-a), f2=f(x2

45、)| b-a |?x*=(a+b)/2, f*=f (x*)结束结束YNYNa,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.292f1=f(x1)=4.2922-74.292+10=-1.6227x2=a+0.618(b-a)=2+0.618(8-2)=5.708f2=f

46、(x2)=5.7082-75.708+10=2.6253比较函数值比较函数值f1和和f2，缩短搜索区间，缩短搜索区间由于由于f1不满足迭代终止条件。再取两试点不满足迭代终止条件。再取两试点x1和和x2，并且比较函，并且比较函数值数值f1与与f2，继续缩短搜索区间。，继续缩短搜索区间。搜索区间经搜索区间经6次缩短后，区间长度为次缩短后，区间长度为b-a=3.5971-3.2863可以终止迭代，得到近似极小点和最优值可以终止迭代，得到近似极小点和最优值利用若干点的函数值，构造一个低次的插值多利用若干点的函数值，构造一个低次的插值多项式项式P(x) ，去逼近要求极小值的函数，去逼近要求极小值的函数f

47、(x )；用解析法求出用解析法求出P(x) 导数的根，作为目标函数导数的根，作为目标函数f(x ) 极小值的近似位置。极小值的近似位置。重复应用这一方法进行迭代计算，直到得出符重复应用这一方法进行迭代计算，直到得出符合要求的结果。合要求的结果。常用插值多项式有二次和三次的，因此分别常用插值多项式有二次和三次的，因此分别称为称为二次插值法二次插值法和三次插值法。和三次插值法。（2）插值法）插值法n 基本思想基本思想在目标函数在目标函数f(x)的寻优区间的寻优区间a, b内任取三点内任取三点x1、x2、x3，且，且x1x2x3，相应的函数值为，相应的函数值为f1=f(x1)、f2=f(x2)和和f

48、3=f(x3)。过此三点构造一条抛物线，。过此三点构造一条抛物线，并以此抛物线近似原目标函数。并以此抛物线近似原目标函数。n 二次插值法二次插值法构造的抛物线为二次方程构造的抛物线为二次方程求待定系数求待定系数 将将x1、x2、x3代入上式，可求出系数代入上式，可求出系数a1和和a2：P(x) = a0a1 xa2 x2x0P(x)二次插值法xx1x*x3f(x)f(x)x2123ab)()()()()()()()()()(13322132121313221332213222122123123221xxxxxxfxxfxxfxxaxxxxxxfxxfxxfxxa令令P(x)的导数为的导数为0，

49、可求出近似抛物线的极小点，可求出近似抛物线的极小点x0，即，即02)(0210 xaadxxdPxx321213132322212212312322210)()()()()()(212fxxfxxfxxfxxfxxfxxaax 求极小点和极小值求极小点和极小值代入目标函数，得代入目标函数，得)(00 xff迭代求解迭代求解 去掉去掉 f1与与 f2中较大者，将剩下的两个预选点中较大者，将剩下的两个预选点和和 x0 组成一个新的组成一个新的“三点组三点组”，然后重复，然后重复上述过程，进行二次迭代，直到满足允许误上述过程，进行二次迭代，直到满足允许误差的要求为止。差的要求为止。如果如果 | f2

50、f0 | ，则选其小者为最优解。，则选其小者为最优解。若不满足收敛条件，则转下一步。若不满足收敛条件，则转下一步。判断终止条件判断终止条件注：首先要确定初始搜索区间首先要确定初始搜索区间a,b。二次插值法收敛速度快，有效性好，但可靠性差，二次插值法收敛速度快，有效性好，但可靠性差，适用于多维优化的一维搜索迭代。适用于多维优化的一维搜索迭代。n多维优化的一维搜索多维优化的一维搜索在求多维目标函数的极值点时，大多数方法在求多维目标函数的极值点时，大多数方法都要进行一系列的一维搜索。都要进行一系列的一维搜索。多维搜索的迭代格式为多维搜索的迭代格式为X(k+1)=X(k)+hS(k) (h为步长因子为