工程设计中的优化方法教学课件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，则，则

6、x = (x1, x2, , xn)t xrn 设计空间：以设计变量为坐标轴所构成的空间设计空间：以设计变量为坐标轴所构成的空间 设计空间的设计空间的维数维数：即设计变量的即设计变量的个数个数 n个设计变量即构成个设计变量即构成n维设计空间维设计空间（记为（记为xrn）。 设计空间及其维数设计空间及其维数 设计变量、设计空间和设计方案之间的关系 一组设 计变量 设计空 间一点 一个设 计方案 p x1 x2 x3 三维设计空间r3 设计变量的数目设计变量的数目 选择余地或影响不大的参数，根据经验定为常量。选择余地或影响不大的参数，根据经验定为常量。 设计变量个数应尽量减少设计变量个数应尽量减少

7、。 选定原则：只把与问题本质有关、对结果影响选定原则：只把与问题本质有关、对结果影响 大的参数定为设计变量。大的参数定为设计变量。 连续变量：值能连续变化。连续变量：值能连续变化。 离散变量：值不能连续变化。离散变量：值不能连续变化。 设计变量的类型设计变量的类型 对于离散变量的优化设计问题，通常先按连续变量处对于离散变量的优化设计问题，通常先按连续变量处 理，找到最优解后，再按工艺规范或标准系列调整。理，找到最优解后，再按工艺规范或标准系列调整。 在优化设计中，用于评价设计变量好坏的函数，在优化设计中，用于评价设计变量好坏的函数， 称为目标函数，记作称为目标函数，记作 优化目标函数就是求目标

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

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

10、 约束条件约束条件 n 约束条件的定义：对设计变量取值的限制条件。约束条件的定义：对设计变量取值的限制条件。 n 约束条件的数目约束条件的数目 约束条件愈接近实际，则最优解愈接近最优约束条件愈接近实际，则最优解愈接近最优 方案。但约束条件数增加时，可行方案数量将方案。但约束条件数增加时，可行方案数量将 大大减少，计算工作量也会增大。大大减少，计算工作量也会增大。 n 约束条件的类型约束条件的类型 边界约束边界约束 设计变量的变化范围设计变量的变化范围（如板材厚度范围）（如板材厚度范围） 性能约束性能约束 由某种性能设计要求导出的约束条由某种性能设计要求导出的约束条 件件(如结构设计中，弯曲应力

11、必须小于或等于许用弯曲应力等如结构设计中，弯曲应力必须小于或等于许用弯曲应力等) hi(x)=hi(x1, x2, , xn)=0 i=1, 2, , m, mn n 约束条件的类型约束条件的类型 不等式约束不等式约束 等式约束等式约束 同一个优化设计问题可同时含有等式和不等式同一个优化设计问题可同时含有等式和不等式 约束。约束。 对于不等式约束，对于不等式约束，0型和型和0型可互相转化。方型可互相转化。方 法是改变约束条件的符号，即令法是改变约束条件的符号，即令 gj(x)= -gj(x) gj(x)=gj(x1, x2, , xn)0 或或 0 j=1, 2, , p m，p 等式约束数和

12、不等式约束数。等式约束数和不等式约束数。 hi(x)， gj(x)约束函数约束函数； 约束条件把设计空间划分为两个区域：可行域约束条件把设计空间划分为两个区域：可行域 和不可行域。和不可行域。 n 可行域和可行点可行域和可行点 可行域可行域 域内设计点（设计域内设计点（设计 方案）满足所有约束条件。方案）满足所有约束条件。 可行域内的设计点称为可行域内的设计点称为可行点可行点。 约束优化设计中，约束优化设计中，最优点一般是约束区域的边界点最优点一般是约束区域的边界点， 即设计点位于某个约束面上：即设计点位于某个约束面上： gu(x)=0 (1up) 不可行域 可行域 gu(x)=0 设计空间

13、不可行域不可行域 域内的设计点域内的设计点 不不满足或不全满足约束条件。满足或不全满足约束条件。不可行域内的设计点不可行域内的设计点 称为称为不可行点不可行点，一般是工程实际，一般是工程实际不能接受的方案不能接受的方案。 优化设计的数学模型是实际设计的数学抽象。优化设计的数学模型是实际设计的数学抽象。 任何一个优化设计问题可归结为如下描述：任何一个优化设计问题可归结为如下描述： 在给定的约束条件下，选择适当的设计变量在给定的约束条件下，选择适当的设计变量x， 使其目标函数使其目标函数 f (x)达到最优值。达到最优值。 （4）数学模型）数学模型 建立数学模型是解决优化设计的关键 设计变量设计变

14、量 在满足约束方程在满足约束方程 的条件下，求目标函数的条件下，求目标函数f (x)的最优值。的最优值。 x= (x1, x2, , xn)t xrn hi(x)=0, i=1, 2, , m gj(x)0, j=1, 2, , p 其数学表达式其数学表达式(数学模型数学模型)为为 n 优化设计数学模型的简化表示优化设计数学模型的简化表示 s.t.“满足于满足于”或或“受约束于受约束于”；rnn维欧氏空间维欧氏空间 利用优化方法求解上述数学模型，可得到一组最优设利用优化方法求解上述数学模型，可得到一组最优设 计参数或一个最优设计方案计参数或一个最优设计方案 x*称为称为最优点最优点，f(x*)

15、 称为称为最优值最优值。 最优点和最优值构成一个最优点和最优值构成一个约束最优解约束最优解。 min f (x), xrn hi(x)=0, i=1, 2, , m gj(x)0, j=1, 2, , p s.t. x* = (x1*, x2*, , xn*)t n 优化设计问题的最优解优化设计问题的最优解 实际工程的优化设计问题：实际工程的优化设计问题：非线性约束优化问题非线性约束优化问题 n 优化设计问题的类型优化设计问题的类型 线性规划问题线性规划问题 优化问题的目标函数和优化问题的目标函数和 约束函数都是设计变量的线性函数约束函数都是设计变量的线性函数 非线性规划问题非线性规划问题 目

16、标函数和约束函数目标函数和约束函数 不全是设计变量的线性函数不全是设计变量的线性函数 函数与函数与 变量间变量间 的关系的关系 无约束优化问题无约束优化问题 只有目标函数而无约只有目标函数而无约 束条件的优化问题束条件的优化问题 约束优化问题约束优化问题 有约束条件的优化问题有约束条件的优化问题 有无约有无约 束条件束条件 例例5-1 已知箱形梁的长度已知箱形梁的长度l和载荷和载荷f1、f2， 许用挠度许用挠度 f = l /700。设梁高为。设梁高为x1，梁宽为，梁宽为x2， 腹板厚度为腹板厚度为x3，翼缘板的厚度为，翼缘板的厚度为x4。 试设计该箱形梁，使其试设计该箱形梁，使其质量最轻质量

17、最轻。 (长度单位为长度单位为mm，力的单位为，力的单位为n) x1 x2 x3 x4 箱形截面梁计算简图 f1 f2 l l / 2 设计变量设计变量 取箱形梁横截面待定尺寸取箱形梁横截面待定尺寸x1，x2， x3及及x4为设计变量，则为设计变量，则 目标函数目标函数 优化目标为优化目标为质量最轻质量最轻。 梁的跨度已知，故可用梁的梁的跨度已知，故可用梁的截面面积截面面积作为目作为目 标函数。截面面积之半可近似为标函数。截面面积之半可近似为 f (x) = x1x3 + x2x4 使质量最轻就是使使质量最轻就是使f (x)的值最小。的值最小。 x = x1, x2, x3, x4 t，xr4

18、 （忽略了-2x3x4项,厚度的乘积） 约束条件约束条件 设计的箱形梁需满足一定的设计的箱形梁需满足一定的强度、强度、 刚度、稳定性以及几何要求刚度、稳定性以及几何要求。推导得。推导得 式中，k1=3l/4；w=x1x3+x2x4, k2=f1l3/(16.810-5)。 强度条件 刚度条件(梁跨中挠度限制) 翼缘板局部稳定性条件 腹板局部稳定性条件 几何约束条件（板厚不得小于5mm） 0 33 10000/8 . 7 )( 4 2 2321 2 3 2 1421 1 11 xxxxx f xxxxx wlf kxg 0 3 )( 3 3 142 2 1 2 2 f xxxxx k xg 06

19、0)( 4 2 3 x x xg 0160)( 3 1 4 x x xg 05)( 35 xxg 05)( 46 xxg f f （厚度与宽度之比） 箱形梁优化设计的数学模型箱形梁优化设计的数学模型 属约束非线性规划问题属约束非线性规划问题。选用。选用可行方向法可行方向法求解。求解。 跨度 l(cm) 常规设计（mm）优化设计(mm)减轻自 重 （%） x1x2x3x4x1x2x3x4 1050 1350 1650 760 880 1010 340 390 440 6 6 6 10 10 10 790 870 1020 310 380 370 5 6 6 8 6 8 19.8 18.8 13.

20、7 表5-1 箱形梁设计结果比铰 min f (x), xr4 gj(x)0, j=1, 2, , 6s.t. 优化结果优化结果：取出三种跨度的优化结果见表：取出三种跨度的优化结果见表5-1。 所用数据为：所用数据为：f1=120kn， f2=12kn，=140mpa 3. 优化设计的计算方法优化设计的计算方法 无约束优化方法无约束优化方法约束优化方法约束优化方法 优化方法优化方法 解析法解析法数值法数值法直接法直接法间接法间接法 无约束优化方法是优化设计的基础无约束优化方法是优化设计的基础 许多约束优化问题可转化为无约束优化问题求解许多约束优化问题可转化为无约束优化问题求解 求解无 约束优

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

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

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

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

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

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

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

28、x* 二维函数f(x)的等值线 x1 x2 f(x)f(x) a b c d 对于三维以上的函数（对于三维以上的函数（n维函数），具有共同函数值维函数），具有共同函数值 的点构成一族曲面，称函数的点构成一族曲面，称函数f(x)的的等值面等值面族。族。 函数等值线在极值处聚成一点，并位函数等值线在极值处聚成一点，并位 于等值线族的中心。于等值线族的中心。当该中心为极小当该中心为极小 值时，离中心越远函数值越大。值时，离中心越远函数值越大。 在极值点附近，在极值点附近，n元函数的等值面一般为一族近似的元函数的等值面一般为一族近似的 椭球面，它们共同的中心就是椭球面，它们共同的中心就是n元函数的极值

29、点。元函数的极值点。 求函数极值点亦即求函数最优点问题，可归结为求其 等值线（面）同心椭圆（椭球面）族的中心。 根据求椭圆（椭球面）族中心的不同途径，就形成了根据求椭圆（椭球面）族中心的不同途径，就形成了 各种不同的优化方法。各种不同的优化方法。 极值点附近等值线呈椭圆形，等值线较密的部位，目标函数值变化越迅速。极值点附近等值线呈椭圆形，等值线较密的部位，目标函数值变化越迅速。 目标函数非线性程度越严重，等值线形状越复杂，且可能存在多个极值点。目标函数非线性程度越严重，等值线形状越复杂，且可能存在多个极值点。 极值点极值点 驻点驻点 二维目标函数等值线二维目标函数等值线 f(x)=x24-2x

30、2x12+x22+x12-2x1+5f(x)=4+4.5x1-4x2+x12+2x22-2x1x2+x14-2x12x2 n 梯度定义：梯度定义：n元函数元函数f (x1,x2, ,xn)的梯度的梯度 即梯度是由函数即梯度是由函数 f (x)一阶偏导数组成的一阶偏导数组成的n维列向量维列向量。 (2) 函数的梯度函数的梯度 n 梯度的模梯度的模 n 梯度方向：函数等值线（面）的法线方向梯度方向：函数等值线（面）的法线方向 梯度梯度与函数的等值线相互垂与函数的等值线相互垂 直，直，其方向沿函数等值线的其方向沿函数等值线的 法线指向函数值增加的一侧法线指向函数值增加的一侧. x1 函数的负梯度方向

31、 s -s x2 梯度正方向是函数值最速上升（增加最快）方向；梯度正方向是函数值最速上升（增加最快）方向； 梯度负方向或梯度负方向或负梯度方向是函数值最速下降方向负梯度方向是函数值最速下降方向。 梯度梯度f (x)是一个向量，其方向是函数是一个向量，其方向是函数f (x)具有最具有最 大变化率的方向。大变化率的方向。 n 梯度的主要特征梯度的主要特征 沿某点的梯度方向，函数值在该沿某点的梯度方向，函数值在该 点附近增长最快。点附近增长最快。 反之，反之，沿某点的负梯度方向，函沿某点的负梯度方向，函 数值在该点附近下降最快。数值在该点附近下降最快。 多元目标函数可用其在某点的泰勒展开式近似。多元

32、目标函数可用其在某点的泰勒展开式近似。 (3) 多元函数的泰勒展开式多元函数的泰勒展开式 多元函数多元函数f(x)在点在点x(k)的泰勒展开式（的泰勒展开式（只取到二阶偏导数项）只取到二阶偏导数项） xi、xj 变量变量x的第的第i、j个分量；个分量； n变量的个数变量的个数 函数在函数在x (k)点处对点处对 xi的一阶偏导的一阶偏导 函数在函数在x (k)点处对点处对 xi, xj的二阶偏导的二阶偏导 )( )( 2 1 )( )( )()( )()( 1, )(2 )( 1 )( )(k jj k ii n ji ji k k ii n i i k k xxxx xx xf xx x x

33、f xfxf 即函数即函数f (x)在点在点x (k)的一阶偏导数的列向量。的一阶偏导数的列向量。 n 矩阵形式矩阵形式 函数函数f (x)在点在点x (k)的二阶偏导数，它是一个的二阶偏导数，它是一个nn阶的对称方阶的对称方 阵，称为函数阵，称为函数f (x)在点在点x (k)的的海森海森(hessian)矩阵矩阵。 )( )()()( )()()( )()()( )( )( 2 )(2 2 )(2 1 )(2 2 )(2 2 2 )(2 12 )(2 1 )(2 21 )(2 2 1 )(2 )(2k n k n k n k n kkk n kkk k xh x xf xx xf xx x

34、f xx xf x xf xx xf xx xf xx xf x xf xf t n kkk k x xf x xf x xf xf )( , )( , )( )( )( 2 )( 1 )( )( )()( 2 1 )()()()( )()(2t)()( t )()(kkkkkk xxxfxxxxxfxfxf 梯度梯度 多元函数在极值点附近的等值线簇为同心椭圆多元函数在极值点附近的等值线簇为同心椭圆 簇，即簇，即目标函数在极值点附近是二次函数目标函数在极值点附近是二次函数。因。因 此，多元函数常用其泰勒展开式的前三项近似此，多元函数常用其泰勒展开式的前三项近似 表示（精度已足够），记为表示（精

35、度已足够），记为 与矩阵形式对应 n 多元函数的近似表达式多元函数的近似表达式 cxbaxxxf tt 2 1 )( 一般二元二次函数一般二元二次函数 f (x) = mx12 + nx22 + px1x2 + b1x1 + b2x2 + c 矩阵表达式矩阵表达式 x = x1 x2 b = b1 b2 a = = a11 a12 a21 a22 2m p p 2n a函数的二阶偏导数矩阵，对称方阵。函数的二阶偏导数矩阵，对称方阵。 二次函数的梯度二次函数的梯度 f (x) = ax+b b函数一次项系数列向量。函数一次项系数列向量。 补充知识 对于对于n元函数元函数 f (x1, x2, ,

36、 xn)的无约束极值问题的无约束极值问题 n 点点x*为一个局部极值点的充分必要条件为一个局部极值点的充分必要条件 一阶导数向量一阶导数向量f(x *)=0，即，即 二阶导数矩阵二阶导数矩阵2f (x*)，即海森矩阵，即海森矩阵h(x *) 为为正定或负定正定或负定，且，且 当当h(x *)为正定时为正定时x *为极小点；为极小点； 当当h(x *)为负定时为负定时x *为极大点。为极大点。 min f (x) , xrn ni x xf i , 2 , 1, 0 *)( 若矩阵若矩阵a各阶顺序主子式均大于零，即当各阶顺序主子式均大于零，即当a=aij时时 则该矩阵则该矩阵a是正定的是正定的；

37、 不符合正、负定条件的矩阵，是不符合正、负定条件的矩阵，是不定矩阵不定矩阵。对于这类矩阵，不可。对于这类矩阵，不可 用上述方法判别点用上述方法判别点x x* *是否为极值点，而需用更高阶的导数来判定是否为极值点，而需用更高阶的导数来判定. . 若各阶顺序主子式呈若各阶顺序主子式呈负、正交替变化负、正交替变化，即一切，即一切 偶数阶的主子式都是正数，一切奇数阶主子式偶数阶的主子式都是正数，一切奇数阶主子式 都是负数，则该矩阵都是负数，则该矩阵a是是负定负定的。的。 n 判断矩阵判断矩阵a正定或负定的方法正定或负定的方法 3. 无约束最优问题的直接搜索解法无约束最优问题的直接搜索解法 消去法消去法

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

39、。直至最优点存在的范围达到允许误差为止。 对单变量目标函数对单变量目标函数 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- fn-1 |

40、 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闭区间内，则闭区间内，则 消去法搜索过

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

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

43、应取误，应取h = - h (后退后退)进行计算。进行计算。 为减小计算工作量，将为减小计算工作量，将x1与与x2、f(x1) 与与f(x2)的值互换。转入第的值互换。转入第步。步。 x 0 f(x) f(x1) x1x2 f(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即得最小值所在的区间即得最小值所在的区间 x 0 f(x) f(x2) x2 x1

44、x3 f(x3) f(x1) x 0 f(x) f(x2) x2 x1 x3 f(x3) f(x1) 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

45、 y 后退 n黄金分割法基本步骤黄金分割法基本步骤 1) 给出初始搜索区间给出初始搜索区间a，b和收敛精度和收敛精度。 2) 在区间在区间a,b内插入两点内插入两点x1和和x2，并计算函数值，并计算函数值f(x1)和和f(x2)。 使用黄金分割法，相邻两次搜索区间的缩短率为使用黄金分割法，相邻两次搜索区间的缩短率为0.6180.618。 3) 比较比较f(x1)和和f(x2)大小，缩短搜索区间，进行区间名称代换大小，缩短搜索区间，进行区间名称代换. 4) 检查区间是否缩短到足够小，或函数值收敛到足够接近。检查区间是否缩短到足够小，或函数值收敛到足够接近。 如果条件不满足，则到步骤如果条件不满足

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

47、x2, x2=x1, f2= f1 x1=a+0.382(b-a), f1=f(x1) a = x1, x1= x2, f1= f2 x2=a+0.618(b-a), f2=f(x2) | b-a |? x*=(a+b)/2, f*=f (x*) 结束结束 yn y n a,b可用进退法确定可用进退法确定 例题例题用黄金分割法求单变量函数用黄金分割法求单变量函数f(x)=x2-7x + 10的极小点，初始搜索区间的极小点，初始搜索区间a,b=2,8,迭代精迭代精 度度=0.35。 解：在搜索区间解：在搜索区间a,b内取两试点内取两试点x1和和x2，计算，计算 它们的函数值：它们的函数值： x1

48、=b-0.618(b-a)=8-0.618(8-2)=4.292 f1=f(x1)=4.2922-74.292+10=-1.6227 x2=a+0.618(b-a)=2+0.618(8-2)=5.708 f2=f(x2)=5.7082-75.708+10=2.6253 比较函数值比较函数值f1和和f2，缩短搜索区间，缩短搜索区间 由于由于f1 不满足迭代终止条件。再取两试点不满足迭代终止条件。再取两试点x1和和x2，并且比较函，并且比较函 数值数值f1与与f2，继续缩短搜索区间。，继续缩短搜索区间。 搜索区间经搜索区间经6次缩短后，区间长度为次缩短后，区间长度为 b-a=3.5971-3.28

49、63 可以终止迭代，得到近似极小点和最优值可以终止迭代，得到近似极小点和最优值 利用若干点的函数值，构造一个低次的插值多利用若干点的函数值，构造一个低次的插值多 项式项式p(x) ，去逼近要求极小值的函数，去逼近要求极小值的函数f(x )； 用解析法求出用解析法求出p(x) 导数的根，作为目标函数导数的根，作为目标函数 f(x ) 极小值的近似位置。极小值的近似位置。 重复应用这一方法进行迭代计算，直到得出符重复应用这一方法进行迭代计算，直到得出符 合要求的结果。合要求的结果。 常用插值多项式有二次和三次的，因此分别常用插值多项式有二次和三次的，因此分别 称为称为二次插值法二次插值法和三次插值

50、法。和三次插值法。 （2）插值法）插值法 n 基本思想基本思想 在目标函数在目标函数f(x)的寻优区间的寻优区间a, b内任取三点内任取三点x1、 x2、x3，且，且x1x2x3，相应的函数值为，相应的函数值为f1=f(x1)、 f2=f(x2)和和f3=f(x3)。过此三点构造一条抛物线，。过此三点构造一条抛物线， 并以此抛物线近似原目标函数。并以此抛物线近似原目标函数。 n 二次插值法二次插值法 构造的抛物线为二次方程构造的抛物线为二次方程 求待定系数求待定系数 将将x1、x2、x3 代入上式，可求出系数代入上式，可求出系数a1和和 a2： p(x) = a0a1 xa2 x2 x0 p(

51、x) 二次插值法 xx1x*x3 f(x) f(x) x2 1 2 3 ab )()( )()()( )()( )()()( 133221 321213132 2 133221 3 2 2 2 12 2 1 2 31 2 3 2 2 1 xxxxxx fxxfxxfxx a xxxxxx fxxfxxfxx a 令令p(x)的导数为的导数为0，可求出近似抛物线的极小点，可求出近似抛物线的极小点x0，即，即 02 )( 021 0 xaa dx xdp xx 321213132 3 2 2 2 12 2 1 2 31 2 3 2 2 2 1 0 )()()( )()()( 2 1 2fxxfxx

52、fxx fxxfxxfxx a a x 求极小点和极小值求极小点和极小值 代入目标函数，得代入目标函数，得)( 00 xff 迭代求解迭代求解 去掉去掉 f1与与 f2中较大者，将剩下的两个预选点中较大者，将剩下的两个预选点 和和 x0 组成一个新的组成一个新的“三点组三点组”，然后重复，然后重复 上述过程，进行二次迭代，直到满足允许误上述过程，进行二次迭代，直到满足允许误 差的要求为止。差的要求为止。 如果如果 | f2f0 | ，则选其小者为最优解。，则选其小者为最优解。 若不满足收敛条件，则转下一步。若不满足收敛条件，则转下一步。 判断终止条件判断终止条件 注：首先要确定初始搜索区间首先

53、要确定初始搜索区间a,b。 二次插值法收敛速度快，有效性好，但可靠性差，二次插值法收敛速度快，有效性好，但可靠性差， 适用于多维优化的一维搜索迭代。适用于多维优化的一维搜索迭代。 n多维优化的一维搜索多维优化的一维搜索 在求多维目标函数的极值点时，大多数方法在求多维目标函数的极值点时，大多数方法 都要进行一系列的一维搜索。都要进行一系列的一维搜索。 多维搜索的迭代格式为多维搜索的迭代格式为 x(k+1)=x(k)+hs(k) (h为步长因子为步长因子) 搜索新点搜索新点x(k+1)时，出发点时，出发点x(k)和搜索方向和搜索方向s(k) 均已确定。这样，问题就变成了过点均已确定。这样，问题就变

54、成了过点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) 多维优化一维搜索示意

55、图多维优化一维搜索示意图 最优步长因子 x(k)hs(k) x(k+1) s(k)方向极小点 minf(x(k)+hs(k) f(x(k) 旧点 新点 搜索方向 s(k) 所在平面 目标函数 f(x)曲面 f(x) o x2 x1 x(0) 二维问题坐标轮换法搜索过程 x* x1 x2 s1 s2 多维搜索法。其原理是将多维无约束最优化问多维搜索法。其原理是将多维无约束最优化问 题转化为一系列题转化为一系列沿坐标轴方向沿坐标轴方向的一维问题求解的一维问题求解. 而一维寻优问题可用消去法或插值法求解。而一维寻优问题可用消去法或插值法求解。 （3）坐标轮换法）坐标轮换法（降维法） 设目标函数为二元

56、函数设目标函数为二元函数 f(x1, x2)。搜索过程为：。搜索过程为： 从初始点从初始点x(0)出发，分别沿出发，分别沿 两个坐标轴方向搜索两个坐标轴方向搜索。 初始点：初始点：x(0)=x1(0),x2(0)t 搜索方向：搜索方向：s1=1,0t，s2=0,1t x1，x2方向的单位向量方向的单位向量 首先沿首先沿x1方向搜索，即固定方向搜索，即固定x2(0)，只改变，只改变x1。 11 )0()1( 1 shxx h1为优化步长，可用一维为优化步长，可用一维 寻优方法求得，即寻优方法求得，即 )()(min 11 )0( 1 )0( shxfhsxf n 第一轮搜索第一轮搜索 目标函数转

57、化为单变量目标函数转化为单变量x1的函数，可得目标函的函数，可得目标函 数沿数沿x1方向的极小点，即方向的极小点，即 h1 x1(1) x(0) 坐标轮换法搜索过程 x* x1 x2 s1 x2(0) 目标函数转化为单变量目标函数转化为单变量x2的函数，可得目标函的函数，可得目标函 数沿数沿x2方向的极小点，即方向的极小点，即 再沿再沿x2方向搜索，即固定方向搜索，即固定x1(1)，只改变，只改变x2。 22 )1( 1 )1( 2 shxx 优化步长优化步长h2 2可用一维寻优可用一维寻优 方法求得，即方法求得，即 )()(min 22 )1( 12 )1( 1 shxfhsxf 坐标轮换法

58、搜索过程 x1(0) x(0) x1(1) x2(0) x2(1) x1(1) x2(1) x* x1 x2 至此，第一轮结束（坐标轮换一至此，第一轮结束（坐标轮换一 周），得到两个目标函数值逐次周），得到两个目标函数值逐次 下降的迭代点下降的迭代点x1(1)和和x2(1)。 x的上角码表示轮数，下角的上角码表示轮数，下角 码码i表示该轮中第表示该轮中第i个迭代点个迭代点 完成第一个轮计算后，如满足完成第一个轮计算后，如满足 )0()1 ( 2 xx 则目标函数的极小点则目标函数的极小点 x*x2(1)。否则，进行第。否则，进行第 二轮搜索。二轮搜索。 以前一轮得到的第二个迭代点（如以前一轮得

59、到的第二个迭代点（如x2(1) ）为新）为新 起点进行搜索，起点进行搜索，进行进行k轮迭代得到迭代点轮迭代得到迭代点x2(k), 若此时若此时满足精度，则满足精度，则x2(k)即为所求最优点即为所求最优点x*。 n 第二轮以后的搜索第二轮以后的搜索 注意：每轮迭代都依次沿两个坐标方向进行一维搜索，注意：每轮迭代都依次沿两个坐标方向进行一维搜索， 且每轮搜索的次序应一致。且每轮搜索的次序应一致。 ( (本轮终点与始点的距离本轮终点与始点的距离) ) 先将先将n-1个变量固定不变，只对一个变量（一般先对个变量固定不变，只对一个变量（一般先对x1） 进行一维搜索，得到沿该坐标方向的一个目标函数极进行

60、一维搜索，得到沿该坐标方向的一个目标函数极 小点小点x1(1)； 然后再将然后再将x1轴固定在轴固定在x1(1)点上，并使变量点上，并使变量x3,x4, ,xn 固定不变，仅使固定不变，仅使x2变化，沿变化，沿x2轴进行一维搜索，求沿轴进行一维搜索，求沿 该方向上的最小点该方向上的最小点x2(1)；依次类推。；依次类推。 n n维函数的寻优维函数的寻优 当分别沿坐标方向当分别沿坐标方向x1,x2, ,xn进行一次搜索后，即完成进行一次搜索后，即完成 一个轮计算，一个轮计算， 得到最小点得到最小点xn(1) 。 判断是否满足精度要求，否则重复上述步骤。判断是否满足精度要求，否则重复上述步骤。 总