重点 第二章优化设计

1、1第二章第二章 优化设计优化设计Optimal Design2说说 明：明：1. 优化设计的内容十分丰富，由于时间有限，只能讲解其中部优化设计的内容十分丰富，由于时间有限，只能讲解其中部分内容。分内容。2. 基本围绕教材讲解，补充讲解：多目标优化、基于智能计算基本围绕教材讲解，补充讲解：多目标优化、基于智能计算的优化问题求解方法。的优化问题求解方法。3. 不对有关数学推导过程进行详细讲解。不对有关数学推导过程进行详细讲解。4. 主要掌握：各种优化方法的基本思想、各自的优点和不足之主要掌握：各种优化方法的基本思想、各自的优点和不足之处、各种方法之间的内在联系。处、各种方法之间的内在联系。5. 多

2、练习，以熟练掌握和巩固所学的方法；同时结合上机实践，多练习，以熟练掌握和巩固所学的方法；同时结合上机实践，加深对所学方法的认识。加深对所学方法的认识。 3最优化问题：最优化问题： 人们做任何事情都希望用最少的付出得到最佳的效果，这就人们做任何事情都希望用最少的付出得到最佳的效果，这就是最优化问题，最优化问题习惯上被称为优化问题。是最优化问题，最优化问题习惯上被称为优化问题。最优化设计：最优化设计： 在工程设计中，设计者更是力求寻求一组合理的设计参数，在工程设计中，设计者更是力求寻求一组合理的设计参数，以使得由这组设计参数确定的设计方案既满足各种设计要求，以使得由这组设计参数确定的设计方案既满足

3、各种设计要求，又使其技术经济指标达到最佳，即实现最优化设计，最优化设又使其技术经济指标达到最佳，即实现最优化设计，最优化设计习惯上被称为优化设计。计习惯上被称为优化设计。 2.1 概概 述述1. 优化设计的概念优化设计的概念4 设计方案由一组设计参数表达和决定，不同的设计参数表达设计方案由一组设计参数表达和决定，不同的设计参数表达和决定了不同的设计方案。和决定了不同的设计方案。 “设计设计”一词本身就包含优化的概念。作为一项设计，不仅一词本身就包含优化的概念。作为一项设计，不仅要求方案可行、合理，而且应该是某些指标达到最优的理想方要求方案可行、合理，而且应该是某些指标达到最优的理想方案。案。

4、优化设计是一种典型的优化问题。优化设计是一种典型的优化问题。 优化设计的目标是在众多设计方案中寻找出最佳设计方案，优化设计的目标是在众多设计方案中寻找出最佳设计方案，因此优化设计在本质上可以理解为一个因此优化设计在本质上可以理解为一个搜索问题搜索问题，即在由所有，即在由所有设计方案组成的设计方案组成的搜索空间搜索空间中搜索最佳设计方案。中搜索最佳设计方案。 在产品开发过程中，优化设计的对象十分广泛：在产品开发过程中，优化设计的对象十分广泛： 对产品本身进行优化设计，如结构优化对产品本身进行优化设计，如结构优化 对产品的加工和制造等环节进行优化，如产品工艺方案优化、对产品的加工和制造等环节进行优

5、化，如产品工艺方案优化、生产计划优化、车间布局优化生产计划优化、车间布局优化 车间布局优化：为了有效地减少产品在车间中的传输时间，车间布局优化：为了有效地减少产品在车间中的传输时间，根据车间中的生产工件的工艺流程对设备进行优化布局。根据车间中的生产工件的工艺流程对设备进行优化布局。 5例例 有一块边长为有一块边长为6m的正方形铝板，四角各裁去一个小的方块，的正方形铝板，四角各裁去一个小的方块，做成一个无盖的盒子。试确定裁去的四个小方块的边长，以使做成一个无盖的盒子。试确定裁去的四个小方块的边长，以使做成的盒子具有最大的容积。做成的盒子具有最大的容积。 解：设裁去的四个小方块边长为解：设裁去的四

6、个小方块边长为x，盒子的容积可表示成，盒子的容积可表示成x的的函数函数f(x)= x(62 x )2。于是，上述问题可描述为。于是，上述问题可描述为: 数学模型：数学模型： 求变量求变量 x 使函数使函数 f(x)= x(62 x )2 极大化极大化 根据一元函数的极值条件，令根据一元函数的极值条件，令f (x)= 0，解得极值点和极值，解得极值点和极值分别为：分别为：x*1，f*16 2. 优化设计问题示例优化设计问题示例设计变量设计变量目标函数目标函数最优解最优解6例例 某工厂生产甲、乙两种产品。生产每种产品所需的材料、工某工厂生产甲、乙两种产品。生产每种产品所需的材料、工时、电力和可获得

7、的利润，以及能够提供的材料、工时和电力时、电力和可获得的利润，以及能够提供的材料、工时和电力见下表。试确定两种产品每天的产量，以使每天所获得的利润见下表。试确定两种产品每天的产量，以使每天所获得的利润最大。最大。 7解：这是一个解：这是一个生产计划问题生产计划问题，可归结为既满足各项生产条件，可归结为既满足各项生产条件，又使每天所能获得的利润达到最大的优化设计问题。又使每天所能获得的利润达到最大的优化设计问题。 设每天生产甲产设每天生产甲产x1件，乙产品件，乙产品x2件，每天获得的利润可用函件，每天获得的利润可用函数数 f(x1 , x2) 表示，即表示，即 f(x1 , x2)=60 x1+

8、120 x2 每天实际消耗的材料、工时和电力可分别用函数每天实际消耗的材料、工时和电力可分别用函数g1 (x1 , x2) 、 g2(x1 , x2)和和g3 (x1 , x2)表示，即表示，即8于是上述生产计划问题可归结为于是上述生产计划问题可归结为: 数学模型：数学模型： 求变量求变量 x1 , x2 使函数使函数 f(x1 , x2)=60 x1+120 x2极大化极大化 满足条件满足条件设计变量设计变量目标函数目标函数约束函数约束函数9 两个基本问题：数学模型的建立和数学模型的求解两个基本问题：数学模型的建立和数学模型的求解 数学模型的建立数学模型的建立 用数学表达式对优化问题进行数学

9、描述用数学表达式对优化问题进行数学描述 数学模型的求解数学模型的求解 利用合适的优化方法求解数学模型，得到最优解利用合适的优化方法求解数学模型，得到最优解 必须正确描述实际优化问题，否则会导致根据数学模型得到必须正确描述实际优化问题，否则会导致根据数学模型得到的计算结果偏离实际要求，得出与实际问题不一致甚至相互矛的计算结果偏离实际要求，得出与实际问题不一致甚至相互矛盾的结果。盾的结果。 3. 优化设计的基本问题优化设计的基本问题10 什么是优化问题求解？什么是优化问题求解？ 找到问题的最优解找到问题的最优解 对于优化设计问题，即找到最佳设计方案对于优化设计问题，即找到最佳设计方案 优化问题求解

10、方法，又可以叫优化方法优化问题求解方法，又可以叫优化方法 4. 优化问题求解方法优化问题求解方法11(1) 穷举法（枚举法）穷举法（枚举法）(2) 图解法图解法(3) 解析法：利用等式变换、微分求导、解方程等方法解析法：利用等式变换、微分求导、解方程等方法(4) 启发式方法：利用启发式信息进行搜索启发式方法：利用启发式信息进行搜索 启发式信息：关于问题的信息，这些信息能够对问题的求解启发式信息：关于问题的信息，这些信息能够对问题的求解提供启发或参考。提供启发或参考。12旅行商问题旅行商问题(traveling salesman problem, TSP) 著名的优化问题著名的优化问题 设有设有

11、n个城市，城市个城市，城市i和城市和城市j之间的距离为之间的距离为d(i，j)，其中，其中i，j1, , n。现要寻找使访问每个城市恰好一次的一条回路，。现要寻找使访问每个城市恰好一次的一条回路，且其路径总长为最短。且其路径总长为最短。一条启发式信息：一条启发式信息： 每次选取与当前城市距离最近的城市作为下一个访问的城市每次选取与当前城市距离最近的城市作为下一个访问的城市注意：依据这条启发式信息，不一定能够找到注意：依据这条启发式信息，不一定能够找到TSP问题的最优解。问题的最优解。启发式方法启发式方法奥运火炬奥运火炬传递问题传递问题13 依据启发式信息进行搜索，可以得到依据启发式信息进行搜索

12、，可以得到近似最优方案近似最优方案，但是一般不能得到最优方案。但是一般不能得到最优方案。 关键是构造启发式信息关键是构造启发式信息u 可以构造不同的启发式是信息可以构造不同的启发式是信息u 启发式信息决定最优解的质量和搜索速度启发式信息决定最优解的质量和搜索速度启发式方法启发式方法14 启发式方法包括分枝定界法、动态规划法等启发式方法包括分枝定界法、动态规划法等 分枝定界法的基本思想：分枝定界法的基本思想： 首先将整个搜索空间组织成树状结构首先将整个搜索空间组织成树状结构 树的每一个节点就是优化问题的一个可能的解树的每一个节点就是优化问题的一个可能的解 然后依据启发式信息，剪去那些我们不感兴趣

13、的分枝（最优然后依据启发式信息，剪去那些我们不感兴趣的分枝（最优解不可能存在的分枝），从而减小搜索空间，加快搜索速度，解不可能存在的分枝），从而减小搜索空间，加快搜索速度，提高搜索效率。提高搜索效率。 逐步剪去分枝，找到最优解逐步剪去分枝，找到最优解 基于基于“树树”的搜索方法是人工智能中的一种常用方法的搜索方法是人工智能中的一种常用方法启发式方法启发式方法15(5) 传统优化方法传统优化方法 对初始设计方案不断进行改进，逐步使设计方案趋于完善对初始设计方案不断进行改进，逐步使设计方案趋于完善只是只是“被动地被动地”重复分析产品的性能，而不是重复分析产品的性能，而不是“主动地主动地”设计设计产

14、品的参数。从这个意义上讲，它没有真正体现产品的参数。从这个意义上讲，它没有真正体现“设计设计”的含的含义。义。(6) 现代优化方法现代优化方法 数值迭代方法数值迭代方法 基本迭代公式，即解的改进公式基本迭代公式，即解的改进公式 智能计算方法智能计算方法优化问题的求解方法优化问题的求解方法165. 优化设计问题的数学模型优化设计问题的数学模型统一形式统一形式不等式约束不等式约束 用向量用向量X=x1 , x2 , , xnT表示设计变量，表示设计变量，XRn表示向量表示向量X属于属于n维实欧氏空间，用维实欧氏空间，用min、max表示极小化和极大化，表示极小化和极大化，s.t. (subject

15、 to)表示表示“满足于满足于”。可以省略可以省略等式约束等式约束数学模型的组成要素：设计变量、目标函数、约束条件数学模型的组成要素：设计变量、目标函数、约束条件17说明：说明： 当设计问题要求极大化目标函数当设计问题要求极大化目标函数f(X)时，只要将目标函数改时，只要将目标函数改写为写为f(X)即可，因为即可，因为min f(X)和和max f(X)具有相同的解。具有相同的解。 当不等式约束条件中的不等号为当不等式约束条件中的不等号为“0”时，只要将不等式两时，只要将不等式两端同乘以端同乘以“一一1”，即可得到，即可得到“0”的一般形式。的一般形式。 18 最优化问题也称为数学规划问题最优

16、化问题也称为数学规划问题最优化问题的分类：最优化问题的分类： 根据数学模型中是否包含约束条件，分为根据数学模型中是否包含约束条件，分为无约束优化问题和约束优化问题无约束优化问题和约束优化问题； 根据设计变量的多少，可分为根据设计变量的多少，可分为单变量优化和多变量优化问题单变量优化和多变量优化问题； 根据目标函数和约束函数的性质，可分为根据目标函数和约束函数的性质，可分为线性规划和非线性规划问题线性规划和非线性规划问题u 当数学模型中的目标函数和约束函数均为设计变量的线性函数时，称此设计当数学模型中的目标函数和约束函数均为设计变量的线性函数时，称此设计问题为线性优化问题或线性规划问题。问题为线

17、性优化问题或线性规划问题。u 当目标函数和约束函数中至少有一个为非线性函数时，称为非线性优化问题当目标函数和约束函数中至少有一个为非线性函数时，称为非线性优化问题或非线性规划问题。或非线性规划问题。u 线性规划和非线性规划是数学规划的两个重要分支。生产计划和经济管理方线性规划和非线性规划是数学规划的两个重要分支。生产计划和经济管理方面的问题一般属于线性规划问题，而工程设计问题则属于非线性规划问题。面的问题一般属于线性规划问题，而工程设计问题则属于非线性规划问题。19非线性？一个和尚挑水吃；一个和尚挑水吃；两个和尚抬水吃；两个和尚抬水吃；三个和尚没水吃！三个和尚没水吃！20线性与非线性21 设计

18、变量的选择：设计变量的选择： 应该选择那些与目标函数和约束函数密切相关的、能够表应该选择那些与目标函数和约束函数密切相关的、能够表达设计对象特征的达设计对象特征的独立独立参数和尺寸。参数和尺寸。 兼顾求解的精度和复杂性方面的要求。一般说来，设计变兼顾求解的精度和复杂性方面的要求。一般说来，设计变量的个数越多，数学模型越复杂，求解越困难。量的个数越多，数学模型越复杂，求解越困难。 设计变量与设计空间设计变量与设计空间22 设计变量有连续变量和离散变量之分，由此产生设计变量有连续变量和离散变量之分，由此产生连续变量优连续变量优化问题化问题和和离散变量优化问题离散变量优化问题。 目前，关于离散变量优

19、化问题的理论和方法还很不完善。因目前，关于离散变量优化问题的理论和方法还很不完善。因此，对于各种包含离散变量的优化问题，一般先将离散变量当此，对于各种包含离散变量的优化问题，一般先将离散变量当作连续变量，求出连续变量最优解后，再作适当的离散化处理。作连续变量，求出连续变量最优解后，再作适当的离散化处理。 设计变量与设计空间设计变量与设计空间23 若若n个设计变量个设计变量x1 , x2 , , xn相互独立，则由它们形成的向相互独立，则由它们形成的向量量X=x1 , x2 , , xnT 的全体集合构成一个的全体集合构成一个n维实欧氏空间，称维实欧氏空间，称为为设计空间设计空间，记作，记作Rn

20、 。 一组设计变量构成一个设计方案，可看作设计空间中的一个一组设计变量构成一个设计方案，可看作设计空间中的一个点，称点，称设计点设计点。 所有设计点的集合构成一个设计空间。所有设计点的集合构成一个设计空间。 优化设计就是要对设计空间进行搜索，得到最优设计点，即优化设计就是要对设计空间进行搜索，得到最优设计点，即最优解，也即最佳设计方案。最优解，也即最佳设计方案。设计变量与设计空间设计变量与设计空间24 对任何设计都有若干不同的要求和限制，将这些要求和限制表示成设计对任何设计都有若干不同的要求和限制，将这些要求和限制表示成设计变量的函数并写成一系列不等式和等式表达式，就构成了设计的约束条件，变量

21、的函数并写成一系列不等式和等式表达式，就构成了设计的约束条件，简称约束。简称约束。约束条件的作用：约束条件的作用：对设计变量的取值加以限制。对设计变量的取值加以限制。约束条件的分类：约束条件的分类： 根据形式不同，可分为根据形式不同，可分为不等式约束不等式约束和和等式约束等式约束 根据性质，可分为根据性质，可分为边界约束边界约束和和性能约束性能约束u 边界约束是对设计变量本身所加的直接限制边界约束是对设计变量本身所加的直接限制u 性能约束在形式上是对某些技术性能指标或参数所加的限制，实际上同性能约束在形式上是对某些技术性能指标或参数所加的限制，实际上同样是对设计变量所加的间接限制样是对设计变量

22、所加的间接限制 根据设计点是否在约束边界上，分为根据设计点是否在约束边界上，分为起作用约束起作用约束和和不起作用约束不起作用约束u 约束表示了设计变量的限定范围，范围的边界就是约束边界约束表示了设计变量的限定范围，范围的边界就是约束边界约束条件与可行域约束条件与可行域约束条件约束条件25 每一个不等式或等式约束都将设计空间分为两个部分，满足每一个不等式或等式约束都将设计空间分为两个部分，满足所有约束的部分形成一个所有约束的部分形成一个交集交集，该交集称为此约束问题的可行域。，该交集称为此约束问题的可行域。 可行域也可看作满足所有约束条件的设计点的集合。可行域也可看作满足所有约束条件的设计点的集

23、合。 可行域由约束边界围成。可行域由约束边界围成。 根据是否满足约束条件，可把设计点分为根据是否满足约束条件，可把设计点分为可行点可行点(也称内点也称内点)和和非可行点非可行点(也称外点也称外点)。 约束条件与可行域约束条件与可行域可行域可行域26约束可行域是由约束可行域是由5条约束边界线围成的封闭五边形条约束边界线围成的封闭五边形ABCDO27 根据设计点是否在约束边界上，约束分为起作用约束和不起根据设计点是否在约束边界上，约束分为起作用约束和不起作用约束。作用约束。 可行点与非可行点可行点与非可行点28 目标函数的作用目标函数的作用u 目标函数是关于设计变量的函数，目标函数是关于设计变量的

24、函数，是用于衡量设计方案优劣是用于衡量设计方案优劣的定量标准。的定量标准。u 对极小化问题来说，目标函数的值越小，对应的设计方案越对极小化问题来说，目标函数的值越小，对应的设计方案越好，目标函数的最小值及其对应的设计变量的取值称为设计问好，目标函数的最小值及其对应的设计变量的取值称为设计问题的最优解。题的最优解。 目标函数的选择：目标函数的选择： 不同的设计问题有不同的方案评价标准，甚至一个问题可能不同的设计问题有不同的方案评价标准，甚至一个问题可能存在几个不同的评价标准。因此，必须针对具体问题，选择那存在几个不同的评价标准。因此，必须针对具体问题，选择那些些主要的技术经济指标主要的技术经济指

25、标作为设计的目标函数。作为设计的目标函数。 根据目标函数的个数，优化为题分为根据目标函数的个数，优化为题分为单目标优化问题单目标优化问题和和多目多目标优化问题标优化问题目标函数与等值线目标函数与等值线/ /等值面等值面 29 要知道一个目标函数的最优点在设计空间中所处的位置，要知道一个目标函数的最优点在设计空间中所处的位置，就需要了解就需要了解目标函数的变化规律目标函数的变化规律。对于简单的问题，等值线或。对于简单的问题，等值线或等值面不仅可以直观地描绘函数的变化趋势，而且还可以直观等值面不仅可以直观地描绘函数的变化趋势，而且还可以直观地给出极值点的位置。地给出极值点的位置。 等值线簇是以点等

26、值线簇是以点X2, 0T为圆心为圆心的一组同心圆，显然圆心的一组同心圆，显然圆心X2, 0T就是函数的极小点。就是函数的极小点。30 “约束优化约束优化”与与“无约束优化无约束优化” “单变量优化单变量优化”与与“多变量优化多变量优化” “线性优化线性优化”与与“非线性优化非线性优化” “连续优化连续优化”与与“离散优化离散优化” “单目标优化单目标优化”与与“多目标优化多目标优化” 6. 优化问题的分类优化问题的分类317. 优化设计的一般过程优化设计的一般过程32对于简单的二维优化问题，可用图解法求解。对于简单的二维优化问题，可用图解法求解。 图解法一般步骤：图解法一般步骤：(1) 确定设

27、计空间确定设计空间(2) 作出约束可行域作出约束可行域(3) 画出目标函数的一簇等值线画出目标函数的一簇等值线(4) 最后判断确定最优点最后判断确定最优点 2.2 优化问题的图解法优化问题的图解法33例例 用图解法求解：用图解法求解：可行域可行域目标函数等值线目标函数等值线起作用约束不起作用约束340)(0)X(. t . s)(min12221121xXgxxgxxXf35 极值点位置规律极值点位置规律 如果有最优解的话，最优点必定位于可行域内目标函数在下如果有最优解的话，最优点必定位于可行域内目标函数在下降方向上的等值线与可行域边界的最后一个交点。降方向上的等值线与可行域边界的最后一个交点

28、。 可能出现的情况可能出现的情况u位于一条约束边界上位于一条约束边界上u位于几条约束边界的交点上位于几条约束边界的交点上 极值点位置极值点位置36 图解法只适用于一些简单的优化问题，没有实用价值图解法只适用于一些简单的优化问题，没有实用价值 图解法对于理解优化问题的诸多基本概念，掌握最优解的存图解法对于理解优化问题的诸多基本概念，掌握最优解的存在条件和规律是十分重要的。在条件和规律是十分重要的。 图解法作用图解法作用37 优化设计问题实际上就是极值问题。优化设计问题实际上就是极值问题。 工程设计一般可归结为工程设计一般可归结为多变量、多约束的非线性优多变量、多约束的非线性优化问题化问题。高等数

29、学中的极值理论是求解这种问题的基。高等数学中的极值理论是求解这种问题的基础，但是却不能用来直接求出它们的最优解。础，但是却不能用来直接求出它们的最优解。2.3 优化方法的数学基础优化方法的数学基础38 导数导数 偏导数偏导数 方向导数方向导数 梯度梯度 一元函数、多元函数的泰勒展开一元函数、多元函数的泰勒展开 二次函数二次函数 优化问题的极值条件优化问题的极值条件2.3 优化方法的数学基础优化方法的数学基础39导数的定义导数的定义 对于函数对于函数 ，如果极限，如果极限 存在，则称此极限值为函数在存在，则称此极限值为函数在x0点处的导数，记为点处的导数，记为 ，或者，或者 导数的含义导数的含义

30、 导数表示当自变量变化时所引起的函数变化的快慢程度，即导数表示当自变量变化时所引起的函数变化的快慢程度，即函数的变化率。函数的变化率。 1. 导数及其含义导数及其含义)(xfy 自变量增量函数增量xxfxxfxyxx)()(limlim00000ddxxxy)(0 xf 40 从一元函数的变化率引入了一元函数的导数概念，对于多元函数也有类从一元函数的变化率引入了一元函数的导数概念，对于多元函数也有类似的问题。似的问题。偏导数的定义偏导数的定义（以二元函数为例）（以二元函数为例） 对于函数对于函数 ，如果极限，如果极限 存在，存在，则称此极限值为函数则称此极限值为函数 在点在点 处对处对x 的偏

31、导数，记的偏导数，记为为 ，或者，或者 对于函数对于函数 ，如果极限，如果极限 存在，存在，则称此极限值为函数则称此极限值为函数 在点在点 处对处对y的偏导数，记的偏导数，记为为 ，或者，或者偏导数的含义偏导数的含义 二元函数的偏导数反映的是二元函数沿平行于二元函数的偏导数反映的是二元函数沿平行于x轴方向或者沿平行于轴方向或者沿平行于y轴轴方向的变化率。方向的变化率。 2. 偏导数、方向导数、梯度及其性质偏导数、方向导数、梯度及其性质 ),(yxfz xyxfyxxfxzxxx),(),(limlim000000),(00yx),(yxfz ),(00yxfx),(00yxxf),(yxfz

32、yyxfyyxfyzyyy),(),(limlim000000),(yxfz ),(00yx),(00yxfy),(00yxyf偏导数偏导数41 偏导数反映的是函数沿平行于坐标轴方向的变化率。但是在偏导数反映的是函数沿平行于坐标轴方向的变化率。但是在许多实际问题中，往往要研究函数沿某一特定方向的变化率，许多实际问题中，往往要研究函数沿某一特定方向的变化率，因而引入了方向导数的概念。因而引入了方向导数的概念。方向导数的定义方向导数的定义 对于函数对于函数 ，设，设P0为函数定义域内的一点，如果为函数定义域内的一点，如果L为从为从P0出发的一根射线的方向矢量，出发的一根射线的方向矢量，P为射线上且

33、属于函数定为射线上且属于函数定义域的任一点，以义域的任一点，以 表示表示P与与P0两点间的距离，如果极限两点间的距离，如果极限 存在，则称此极限值为函数存在，则称此极限值为函数 在在P0点沿方向点沿方向L的方向的方向导数，记为导数，记为 ，或者，或者 偏导数是方向导数的一种特殊情况偏导数是方向导数的一种特殊情况 方向导数方向导数),(zyxfu )()(lim00PfPf),(zyxfu ),(000zyxfL),(000zyxLf42梯度梯度 与方向导数相关联的一个概念是函数的梯度。我们知道，与方向导数相关联的一个概念是函数的梯度。我们知道，过空间一点可以引无穷多条射线，即有无穷多个不同的方

34、向。过空间一点可以引无穷多条射线，即有无穷多个不同的方向。一般来说，函数沿不同方向的方向导数是不相同的，那么函数一般来说，函数沿不同方向的方向导数是不相同的，那么函数沿哪个方向变化最快呢？梯度方向是函数变化最快的方向。沿哪个方向变化最快呢？梯度方向是函数变化最快的方向。 梯度的定义：梯度的定义： 43梯度与方向导数的关系梯度与方向导数的关系 函数在一点沿某一方向的方向导数就等于函数在这点的梯度函数在一点沿某一方向的方向导数就等于函数在这点的梯度在该方向上的投影。在该方向上的投影。 设函数在点设函数在点P0的梯度为的梯度为g，在该点沿方向，在该点沿方向L的单位矢量为的单位矢量为则：则：cos,c

35、os,cos0L00)(LgPfL44梯度的性质梯度的性质45函数泰勒展开的作用函数泰勒展开的作用 一元函数的泰勒展开一元函数的泰勒展开 如果取泰勒展开的前两项，则将原来的函数简化为线性函数如果取泰勒展开的前两项，则将原来的函数简化为线性函数 如果取泰勒展开的前三项，则将原来的函数简化为二次函数如果取泰勒展开的前三项，则将原来的函数简化为二次函数3. 一元函数和多元函数的泰勒展开一元函数和多元函数的泰勒展开 46多元函数的泰勒展开多元函数的泰勒展开47二次函数的形式二次函数的形式 二次型矩阵的正定问题二次型矩阵的正定问题 4. 二次函数二次函数48正定二次函数正定二次函数 对于二次函数对于二次

36、函数正定二次函数在优化理论中具有特殊作用正定二次函数在优化理论中具有特殊作用49正定二次函数性质正定二次函数性质 50 优化设计问题实际上就是极值问题。无约束优化问题就是数优化设计问题实际上就是极值问题。无约束优化问题就是数学上的无条件极值问题，而约束优化问题就是数学上的条件极学上的无条件极值问题，而约束优化问题就是数学上的条件极值问题。值问题。 优化问题的极值条件就是指目标函数取得极小值时极值点所优化问题的极值条件就是指目标函数取得极小值时极值点所应满足的条件。应满足的条件。 优化问题的极值条件分为三种情况：优化问题的极值条件分为三种情况： 无约束优化问题的极值条件无约束优化问题的极值条件

37、等式约束优化问题的极值条件等式约束优化问题的极值条件 不等式约束优化问题的极值条件不等式约束优化问题的极值条件 （K-T条件，库恩条件，库恩-塔克条件）塔克条件）5. 优化问题的极值条件优化问题的极值条件 51(1) 一元函数的极值条件一元函数的极值条件 无约束优化问题的极值条件无约束优化问题的极值条件52(2) 二元函数的极值条件二元函数的极值条件必要条件：必要条件：充分条件：充分条件： 53(3) 多元函数的极值条件多元函数的极值条件必要条件：必要条件：函数的极值在驻点取得，即在函数的极值点处，函函数的极值在驻点取得，即在函数的极值点处，函数对各个坐标的偏导数都为数对各个坐标的偏导数都为0

38、。充分条件：充分条件：函数在某点处取得极值的充分条件是要求在该点处函数在某点处取得极值的充分条件是要求在该点处的海赛矩阵正定，即海赛矩阵（二阶导数矩阵）的各阶顺序主的海赛矩阵正定，即海赛矩阵（二阶导数矩阵）的各阶顺序主子式均大于零。子式均大于零。542.4 数值迭代法概述数值迭代法概述55通用迭代公式通用迭代公式 56数值迭代方法（下降迭代方法）的基本过程数值迭代方法（下降迭代方法）的基本过程：57算法的收敛性算法的收敛性 如果算法最终收敛于函数极小值，则称算法具有收敛性。如果算法最终收敛于函数极小值，则称算法具有收敛性。算法的收敛速度算法的收敛速度 算法收敛于极小值的速度，或者说算法逼近于极

39、小值的速度。算法收敛于极小值的速度，或者说算法逼近于极小值的速度。 一种好的优化算法必须具有较好的收敛性（即收敛于极小一种好的优化算法必须具有较好的收敛性（即收敛于极小值或者近似极小值）和较快的收敛速度。值或者近似极小值）和较快的收敛速度。 58常用收敛准则常用收敛准则 （数值迭代优化方法的迭代终止准则（数值迭代优化方法的迭代终止准则 ）59一维搜索的含义一维搜索的含义 在搜索方向在搜索方向 S(k)上寻求最优步长上寻求最优步长的方法称一维搜索法。的方法称一维搜索法。 一维搜索法就是一元函数极小化的数值迭代算法，其求解过一维搜索法就是一元函数极小化的数值迭代算法，其求解过程称一维搜索。程称一维

40、搜索。一维搜索的重要性一维搜索的重要性 一维搜索法是构成非线性优化方法的基本算法，因为多元一维搜索法是构成非线性优化方法的基本算法，因为多元函数的迭代解法都可归结为在一系列逐步产生的下降方向上的函数的迭代解法都可归结为在一系列逐步产生的下降方向上的一维搜索。一维搜索。 2.5 一维搜索方法一维搜索方法 1. 概述概述60 一维搜索的数值解法的基本思路一维搜索的数值解法的基本思路(分两步进行分两步进行)： 首先，在搜索方向首先，在搜索方向 S(k)上确定一个包含极小点的初始区间（搜上确定一个包含极小点的初始区间（搜索区间）；索区间）； 然后，根据然后，根据区间消去原理区间消去原理不断缩小搜索区间

41、，从而得到极小点。不断缩小搜索区间，从而得到极小点。612. 确定搜索区间的进退法确定搜索区间的进退法 搜索区间的特征搜索区间的特征 确定搜索区间的基本思路确定搜索区间的基本思路 62进退法的基本步骤进退法的基本步骤 (4)产生新的探测点产生新的探测点x3=x0+h，令，令f3=f(x3)。63(5)判断判断h0？h0，比较，比较f2和和f3若若f2f3，则继续向前探测，即令，则继续向前探测，即令x1=x2, x2=x3，且加大步长，且加大步长，令令h=2h，转，转(6)若若f2f3，则搜索区间，则搜索区间a, b=x1, x3，算法结束，算法结束如果如果hf3，则继续向后探测，即令，则继续向

42、后探测，即令x1=x1, x2=x3，且加大步长，且加大步长，令令h=2h，转，转(6)若若f1f3，则搜索区间，则搜索区间a, b=x3, x2，算法结束，算法结束以上步骤：以上步骤：确定向前搜索还是向后搜索确定向前搜索还是向后搜索以下步骤：以下步骤：在确定了的搜索方向（向前或向后）上进行搜索在确定了的搜索方向（向前或向后）上进行搜索不论是向前搜索还是向后搜索，在搜索方向上的不论是向前搜索还是向后搜索，在搜索方向上的3个探测点的顺个探测点的顺序都依次为：序都依次为：x1、x2、x3 64(6)产生新的探测点产生新的探测点x3=x0+h，令，令f3=f(x3) （同第（同第(4)步）步）(7)

43、 教材上的步骤有一点小问题！教材上的步骤有一点小问题！65 x1和x2互换 f1和f2互换 x3和f3在这里仅作为临时变量，临时存放x1和f2的值初始区间的中间点6612)(2xxXfxxXf6)(31, 20hx1267 以初始步长开始向前探测。如果函数值上升，则步长变号，以初始步长开始向前探测。如果函数值上升，则步长变号，即改变探测方向，向后探测。如果函数值下降，则维持搜索即改变探测方向，向后探测。如果函数值下降，则维持搜索的探测方向，并将步长加倍。（即：先要确定探测方向，是的探测方向，并将步长加倍。（即：先要确定探测方向，是向前探测还是向后探测，找到函数下降的方向；探测方向确向前探测还是

44、向后探测，找到函数下降的方向；探测方向确定后，沿探测方向进行探测，并且每次探测时步长加倍）定后，沿探测方向进行探测，并且每次探测时步长加倍） 每次探测时，区间的始点、中间点依次沿探测方向移动一步，每次探测时，区间的始点、中间点依次沿探测方向移动一步，一直进行到得到三个点，形成函数值一直进行到得到三个点，形成函数值“高低高高低高”的趋势，的趋势，从而得到搜索区间的始点、中间点和终点。从而得到搜索区间的始点、中间点和终点。 进退法的基本思想进退法的基本思想683.区间消去原理区间消去原理 69 由区间消去原理可知，为了缩短区间，只需要在区间内再插由区间消去原理可知，为了缩短区间，只需要在区间内再插

45、入一点并计算其函数值。然而，对于入一点并计算其函数值。然而，对于插入点的位置，可以用不插入点的位置，可以用不同的方法来确定同的方法来确定，这样就形成了不同的一维搜索方法。概括起，这样就形成了不同的一维搜索方法。概括起来，可以将一维搜索方法分成两大类。来，可以将一维搜索方法分成两大类。 试探法试探法 按某种给定的规律来确定区间内插入点的位置。插入点位置按某种给定的规律来确定区间内插入点的位置。插入点位置的确定不顾及函数值的分布关系。的确定不顾及函数值的分布关系。 如：黄金分割法、裴波纳契法等如：黄金分割法、裴波纳契法等 插值法（函数逼近法插值法（函数逼近法） 根据某些函数点处的某些信息，如函数值

46、、一阶导数、二阶根据某些函数点处的某些信息，如函数值、一阶导数、二阶导数等，构造一个插值函数来逼近原来函数，用插值函数的极导数等，构造一个插值函数来逼近原来函数，用插值函数的极小点作为区间的插入点。小点作为区间的插入点。 属于插值法一维搜索的有：二次插值法、三次插值法等属于插值法一维搜索的有：二次插值法、三次插值法等 4. 一维搜索方法的分类一维搜索方法的分类 70 设区间设区间a, b内的两个中间插入点由以下方式产生：内的两个中间插入点由以下方式产生： 若缩小一次后的新区间为若缩小一次后的新区间为a, x2，则如图，则如图512所示。由于新旧区间内中所示。由于新旧区间内中间插入点应具有相同的

47、位置关系，原区间内的点间插入点应具有相同的位置关系，原区间内的点x1和新区间内的点和新区间内的点x2 实际上实际上是同一个点，故有是同一个点，故有 黄金分割法亦称黄金分割法亦称0.618法，法，它是按照对称原则选取中间插入点而缩小区间它是按照对称原则选取中间插入点而缩小区间的一种一维搜索算法。的一种一维搜索算法。5. 黄金分割法黄金分割法71收敛准则收敛准则 （迭代终止条件）（迭代终止条件） 黄金分割法以区间长度是否充分小作为收敛准则，并以收敛黄金分割法以区间长度是否充分小作为收敛准则，并以收敛区间的中点作为一维搜索的极小点，即当区间的中点作为一维搜索的极小点，即当b-a时，取时，取 不难看出

48、，黄金分割法每次区间缩小的比率是完全相等的。不难看出，黄金分割法每次区间缩小的比率是完全相等的。如果将新区间的长度和原区间的长度之比称作如果将新区间的长度和原区间的长度之比称作区间缩小率区间缩小率，则，则黄金分割法的区间缩小率黄金分割法的区间缩小率等于常数等于常数0.618。如果给定收敛精度。如果给定收敛精度 ，初始区间长度初始区间长度b-a ，则完成一维搜索所需缩小区间的次数，则完成一维搜索所需缩小区间的次数n可以可以由下式求出：由下式求出：72黄金分割法的计算步骤：黄金分割法的计算步骤：按照区间消去按照区间消去原理缩小区间原理缩小区间7374 相同之处：相同之处： 都是利用区间消去原理将初

49、始搜索区间不断缩短，从而求得都是利用区间消去原理将初始搜索区间不断缩短，从而求得极小点的数值近似解。极小点的数值近似解。 不同之处：不同之处： 在在试探法试探法中试验点位置是由中试验点位置是由某种给定的规律某种给定的规律确定的，它不考确定的，它不考虑函数值的分布。例如，黄金分割法是按等比例虑函数值的分布。例如，黄金分割法是按等比例0.618缩短率确缩短率确定的。试探法仅仅利用了定的。试探法仅仅利用了试验点函数值大小的比较试验点函数值大小的比较。 插值法插值法则是利用函数则是利用函数在已知试验点的值（或导数值）在已知试验点的值（或导数值）来确定来确定新试验点的位置。新试验点的位置。 由于试探法仅

50、对试验点函数值的大小进行比较，而由于试探法仅对试验点函数值的大小进行比较，而函数值本函数值本身的特性没有得到充分利用身的特性没有得到充分利用，这样即使对一些简单的函数，例，这样即使对一些简单的函数，例如二次函数，也不得不象一般函数那样进行同样多的函数值计如二次函数，也不得不象一般函数那样进行同样多的函数值计算，算，因此算法收敛较慢，效率较低因此算法收敛较慢，效率较低。6. 二次插值法二次插值法试探法和插值法比较试探法和插值法比较 75 多项式是函数逼近的一种常用工具。在搜索区间内，我们可多项式是函数逼近的一种常用工具。在搜索区间内，我们可以利用若干试验点处的函数值来构造低次多项式，用它作为函以

51、利用若干试验点处的函数值来构造低次多项式，用它作为函数的近似表达式，并用这个多项式的极小点作为原函数极小点数的近似表达式，并用这个多项式的极小点作为原函数极小点的近似。的近似。 常用的插值多项式为二次多项式。两种用二次函数逼近原函常用的插值多项式为二次多项式。两种用二次函数逼近原函数的方法：数的方法： 牛顿迭代法（切线法）：牛顿迭代法（切线法）：利用一点的函数值、一阶导数值和利用一点的函数值、一阶导数值和二阶导数值来构造二次函数。二阶导数值来构造二次函数。 二次插值法（抛物线法）：二次插值法（抛物线法）：利用三个点的函数值形成一个抛利用三个点的函数值形成一个抛物线来构造二次函数。物线来构造二次

52、函数。插值法插值法76牛顿法牛顿法)()(1kkkkxfxfxx 牛顿迭代公式：牛顿迭代公式： （利用了一阶导数值和二阶导数值）（利用了一阶导数值和二阶导数值）77 二次插值法又称抛物线法，它是以目标函数的二次插值函数的极小点作二次插值法又称抛物线法，它是以目标函数的二次插值函数的极小点作为新的中间插入点，进行区间缩小的一维搜索算法。为新的中间插入点，进行区间缩小的一维搜索算法。 二次插值法二次插值法78 由上式求出的由上式求出的xp，是插值函数式，是插值函数式(5.14)的极小点，也是原目的极小点，也是原目标函数的一个近似极小点。以此点作为下一次缩小区间的一个标函数的一个近似极小点。以此点作

53、为下一次缩小区间的一个中间插入点，无疑将使新的插入点向极小点逼近的过程加快。中间插入点，无疑将使新的插入点向极小点逼近的过程加快。 79 二次插值法的中间插入点包含了函数在三个点上的函数值信二次插值法的中间插入点包含了函数在三个点上的函数值信息，因此这样的插入点比较接近函数的极小点。息，因此这样的插入点比较接近函数的极小点。收敛准则：收敛准则： 二次插值法以两个中间插入点的距离充分小作为收敛准则，二次插值法以两个中间插入点的距离充分小作为收敛准则，即当即当|xp-x2|成立时，把成立时，把xp作为此次一维搜索的极小点。作为此次一维搜索的极小点。 80二次插值法的计算步骤二次插值法的计算步骤:

54、818 . 082838485二次插值法的收敛速度比黄金分割法快得多二次插值法的收敛速度比黄金分割法快得多86作业：作业：P1865.25.3 (3) (4)5.7 x0=25.8 (1) =0.35.9 (1) =0.35.10(1)5.11(1)上机作业：上机作业：P1875.8 (1) =0.15.9 (1) =0.15.10(1)87 根据设计变量的多少，可将优化问题分为单变量优化和多变根据设计变量的多少，可将优化问题分为单变量优化和多变量优化。量优化。 单变量优化即一元函数优化，其极小化的数值迭代过程称为单变量优化即一元函数优化，其极小化的数值迭代过程称为一维搜索。一维搜索。 多维优

55、化方法是进行多变量优化设计的数值迭代法，是多元多维优化方法是进行多变量优化设计的数值迭代法，是多元函数的优化方法。函数的优化方法。 多维优化方法分为无约束优化方法和约束优化方法两种多维优化方法分为无约束优化方法和约束优化方法两种2.6 无约束优化方法无约束优化方法 88无约束优化方法的基本思想：无约束优化方法的基本思想： 无约束优化方法是构成约束优化方法的基础算法无约束优化方法是构成约束优化方法的基础算法，无约束优无约束优化问题的基本问题是不断构造搜索方向，并在此基础上进行一化问题的基本问题是不断构造搜索方向，并在此基础上进行一维搜索，以寻求最优解。维搜索，以寻求最优解。 无约束优化方法就是要

56、将原多维优化问题转化为一系列的一无约束优化方法就是要将原多维优化问题转化为一系列的一维搜索。维搜索。 89 根据根据搜索方向的不同构成形式搜索方向的不同构成形式，无约束优化方法可分成两类。，无约束优化方法可分成两类。 一类是利用目标函数的一阶和二阶导数的信息构造搜索方向一类是利用目标函数的一阶和二阶导数的信息构造搜索方向的算法，称为的算法，称为导数法导数法，如梯度法和共轭梯度法如梯度法和共轭梯度法。 特点：特点：由于导数是函数变化率的具体描述，因此导数法的收由于导数是函数变化率的具体描述，因此导数法的收敛性和收敛速度都比较好。敛性和收敛速度都比较好。 另一类是通过几个已知点上函数值的比较构造搜

57、索方向的算另一类是通过几个已知点上函数值的比较构造搜索方向的算法，称为法，称为模式法模式法，如鲍威尔法如鲍威尔法。特点：特点： 由于构成搜索方向的信息仅仅是几个有限点上的函数值，因由于构成搜索方向的信息仅仅是几个有限点上的函数值，因此难以得到较理想的搜索方向；此难以得到较理想的搜索方向； 但该方法免去了对目标函数求导，对于较复杂的目标函数优但该方法免去了对目标函数求导，对于较复杂的目标函数优化是有利的。化是有利的。 90 梯度法是一种古老的优化方法，它的迭代方向是由迭代点的梯度法是一种古老的优化方法，它的迭代方向是由迭代点的负梯度方向负梯度方向构成的。由于负梯度方向是函数值下降得最快的方构成的

58、。由于负梯度方向是函数值下降得最快的方向，故此法也称最快速下降法。向，故此法也称最快速下降法。 梯度法的迭代算式为：梯度法的迭代算式为：最佳步长因子的确定最佳步长因子的确定 对于复杂的问题，由最佳步长因子由一维搜索方法（进退法确定搜索区对于复杂的问题，由最佳步长因子由一维搜索方法（进退法确定搜索区间、黄金分割法间、黄金分割法/二次插值法缩小区间）得到。二次插值法缩小区间）得到。 1. 梯度法梯度法91牛顿法迭代特点：牛顿法迭代特点： 相邻两迭代点的梯度是彼相邻两迭代点的梯度是彼此正交的。此正交的。 在梯度的迭代过程中，相在梯度的迭代过程中，相邻的搜索方向相互垂直。邻的搜索方向相互垂直。 梯度法

59、向极小点的逼近路梯度法向极小点的逼近路径是一条曲折的锯齿形路线，径是一条曲折的锯齿形路线，而且越接近极小点，锯齿越而且越接近极小点，锯齿越细，前进细，前进速度越慢。速度越慢。 92 梯度法的迭代特点是由梯度的性质决定的，因为梯度是函数梯度法的迭代特点是由梯度的性质决定的，因为梯度是函数在一点邻域内在一点邻域内局部变化率局部变化率的数学描述。沿一点的负梯度方向前的数学描述。沿一点的负梯度方向前进时，在该点邻域内函数下降得最快，但是离开该邻域后，函进时，在该点邻域内函数下降得最快，但是离开该邻域后，函数就不一定继续下降得快，甚至不再下降。数就不一定继续下降得快，甚至不再下降。 以负梯度作为搜索方向

60、，从局部看都下降得快，但从全局看以负梯度作为搜索方向，从局部看都下降得快，但从全局看却走了许多弯路，故总的计算速度较慢。梯度法只具有线性收却走了许多弯路，故总的计算速度较慢。梯度法只具有线性收敛速度。敛速度。 梯度法又叫最快速下降法，是指在某一点的邻域内梯度方向梯度法又叫最快速下降法，是指在某一点的邻域内梯度方向是函数值下降最快的方向，而不是指这种方法在所有方法中收是函数值下降最快的方向，而不是指这种方法在所有方法中收敛速度最快。敛速度最快。93 在梯度法的迭代过程中，离极小点较远时，一次一维搜索得在梯度法的迭代过程中，离极小点较远时，一次一维搜索得到的函数下降量较大。或者说，梯度法在远离极小