工程优化 硕士研究生课程 教材： 《最优化计算方法》陈开周 参考书：《最优化理论与算法》 陈宝林 任课教师：叶峰 时间： 周2, 5晚

Presentation on theme: "工程优化 硕士研究生课程 教材： 《最优化计算方法》陈开周 参考书：《最优化理论与算法》 陈宝林 任课教师：叶峰 时间： 周2, 5晚"— Presentation transcript:

1 工程优化 硕士研究生课程 教材： 《最优化计算方法》陈开周 参考书：《最优化理论与算法》 陈宝林 任课教师：叶峰 时间： 周2, 5晚
工程优化 硕士研究生课程 教材： 《最优化计算方法》陈开周 参考书：《最优化理论与算法》 陈宝林 任课教师：叶峰 时间： 周2, 5晚 考核方式： 平时成绩(20%含作业和考勤)+期末闭卷考试(80%)! 作业：按章交作业——每章结束的下一次课交作业. 注：1)以活页纸方式提交，写清楚姓名、学号、院系专业. 2) 作业原件留作记录成绩依据，不发还，请自行复印留底. 3) 合适时间课堂讲解作业或公布答案(建议大家课间答疑).

2 第一章 基础知识 背景知识 最优化问题举例 优化问题的数学模型及其分类 最优解与极值点

3 §1 背景知识 将达到最优目标的方案称为最优方案或最优决策，搜寻最优方案的方法称为最优化方法，关于最优化方法的数学理论称为最优化理论。
§1 背景知识 最优化技术是一门较新的学科分支。它是在本世纪五十年代初在电子计算机广泛应用的推动下才得到迅速发展，并成为一门直到目前仍然十分活跃的新兴学科。最优化所研究的问题是在一定的限制条件下，在众多的可行方案中怎样选择最合理的一种方案以达到最优目标。 将达到最优目标的方案称为最优方案或最优决策，搜寻最优方案的方法称为最优化方法，关于最优化方法的数学理论称为最优化理论。 最优化问题至少有两要素：一是可能的方案；二是要追求的目标。后者是前者的函数。如果第一要素与时间无关就称为静态最优化问题，否则称为动态最优化问题。 本科程专门讲授静态最优化问题。

4 最优化技术应用范围十分广泛，在我们日常生活中，在工农业生产、社会经济、国防、航空航天工业中处处可见其用途。
比如：结构最优设计、电子器件最优设计、光学仪器最优设计、化工工程最优设计、运输方案、机器最优配备、油田开发、水库调度、饲料最优配方、食品结构优化等等。 最优化技术工作被分成两个方面，一是由实际产生或科技问题形成最优化的数学模型，二是对所形成的数学问题进行数学加工和求解。对于第二方面的工作，目前已有一些较系统成熟的资料，但对于第一方面工作即如何由实际问题抽象出数学模型，目前很少有系统的资料，而这一工作在应用最优化技术解决实际问题时是十分关键的基础，没有这一工作，最优化技术将成为无水之源，难以健康发展。

5 数学模型: 对现实事物或问题的数学抽象或描述。
因此，在学习本科程时要尽可能了解如何由实际问题形成最优化的数学模型。 为了便于大家今后在处理实际问题时建立最优化数学模型，下面我们先把有关数学模型的一些事项作一些说明。 数学模型: 对现实事物或问题的数学抽象或描述。 建立数学模型时要尽可能简单，而且要能完整地描述所研究的系统，但要注意到过于简单的数学模型所得到的结果可能不符合实际情况，而过于详细复杂的模型又给分析计算带来困难。因此，具体建立怎样的数学模型需要丰富的经验和熟练的技巧。即使在建立了问题的数学模型之后，通常也必须对模型进行必要的数学简化以便于分析、计算。

6 一般的模型简化工作包括以下几类： （1）将离散变量转化为连续变量。 （2）将非线性函数线性化。 （3）删除一些非主要约束条件。

7 建立最优化问题数学模型的三要素： （1）决策变量和参数。 决策变量是由数学模型的解确定的未知数。参数表示系统的控制变量，有确定性的也有随机性的。 （2）约束或限制条件。 由于现实系统的客观物质条件限制，模型必须包括把决策变量限制在它们可行值之内，即约束条件，而这通常是用约束的数学函数形式来表示的。 （3）目标函数。 这是作为系统决策变量的一个数学函数来衡量系统的效率，即系统追求的目标。

8 优化建模（modeling）：识别出给定问题的目标、 变量和约束的过程。
建立恰当模型：第一步、最重要的一步（太简单—不能给实际问题提供有用的信息；太复杂—不易求解） 选择特定算法：很重要—决定求解速度及质量（无通用优化算法，有求解特定类型优化问题的算法）

9 §2 最优化问题举例 最优化在物质运输、自动控制、机械设计、采矿冶金、经济管理等科学技术各领域中有广泛应用。下面举几个专业性不强的实例。
例1.把半径为1的实心金属球熔化后，铸成一个实心圆柱体，问圆柱体取什么尺寸才能使它的表面积最小？ 解：决定圆柱体表面积大小有两个决策变量：圆柱体底面半径r、高h。 问题的约束条件是所铸圆柱体重量与球重相等。即

10 即 , 即 问题追求的目标是圆柱体表面积最小。即 min 则得原问题的数学模型： s.t Subject to.(以…为条件) 利用在高等数学中所学的Lagrange乘子法可求解本问题 分别对r, h,λ求偏导数,并令其等于零. 有:

11 此时圆柱体的表面积为 例2. 多参数曲线拟合问题 已知两个物理量x和y之间的依赖关系为: 其中 和 待定参数,为确定这些参数,

12 对x，y测得m个实验点: 试将确定参数的问题表示成最优化问题. 解:很显然对参数 和 任意给定的一组数值,就由上式确定了 y关于x的一个函数关系式,在几何上它对应一条曲线,这条曲线不一定通过那m个测量点，而要产生“偏差”. 将测量点沿垂线方向到曲线的距离的 平方和作为这种“偏差”的度量.即 显然偏差S越小,曲线就拟合得越好,说明参数值就选择得越好，从而我们的问题就转化为5维无约束最优化问题。即：

13 例3：旅游售货员问题 旅游线路安排 预定景点走且只走一次 路上时间最短 配送线路—货郎担问题 送货地到达一次 总路程最短

14 模型： 有一旅行团从 出发要遍游城市 ，已知从 到 的旅费为 ，问应如何安排行程使总费用最小？ 变量—是否从i第个城市到第j个城市
有一旅行团从 出发要遍游城市 ，已知从 到 的旅费为 ，问应如何安排行程使总费用最小？ 模型： 变量—是否从i第个城市到第j个城市 约束—每个城市只能到达一次、离开一次

15 目标—总费用最小

16 例4. （混合饲料配合）以最低成本确定满足动物所需营养的最优混合饲料。设每天需要混合饲料的批量为100磅，这份饲料必须含：至少达到0
例4.（混合饲料配合）以最低成本确定满足动物所需营养的最优混合饲料。设每天需要混合饲料的批量为100磅，这份饲料必须含：至少达到0.8%而不超过1.2%的钙;至少22%的蛋白质;至多5%的粗纤维。假定主要配料包括石灰石、谷物、大豆粉。这些配料的主要营养成分为： 每磅配料中的营养含量 每磅成本（元） 配料 钙 蛋白质 纤维 石灰石 谷物 大豆粉 0.0164 0.0463 0.1250

17 解:根据前面介绍的建模要素得出此问题的数学模型如下:
设 是生产100磅混合饲料所须的石灰石、谷物、大豆粉的量（磅）。

18 例5.(运输问题)已知有m个生产地点Ai, i=1,2,…，m。可供应某种物资，其供应量(产量)分别为ai，i=1，2，…，m，有n个销地Bj，j=1,2,…,n，其需要量分别为bj，j=1,2,…,n，从Ai到Bj运输单位物资的运价(单价)为cij，且 求最优运输方案。 供应地 运价 需求地 运输问题网络图举例 1 d1=22 需求量 6 s1=14 1 7 供应量 5 3 2 d2=13 8 4 s2=27 2 2 7 5 3 d3=12 9 s3=19 3 10 6 4 d4=13

19 若用xij表示从Ai到Bj的运量，那么在产销平衡的条件下，要求得总运费最小的调运方案，数学模型:
不平衡怎么描述？

20 练习推广 特殊运输问题——转运问题 工厂A, B, C要运送某种货物到仓库d, e, f去, 运输表如下. 但现在所有这些工厂或仓库又都可以作为转运点, 如 : A可运往B再运往各仓库, 工厂与仓库间地运费如下表. 试建立模型求解费用最小的调运方案. 提示： 假设：1) 沿相反方向的同线路运费相同;2) 设定合理的转运量(如总产量)； 建模：将工厂及仓库既作为供应点也作为需求点建立运输表; d e f 供量 A 70 40 80 B 60 30 90 C 50 20 100 需量 平衡 要求：写出规划模型; 推广到一般情形; 推广到混合型问题(含纯发/纯收/可收可发类问题. 转运1 A B C 20 30 25 转运2 d e f 20 15

21 例6.（多波信号发生仪中正弦波形逼近的优化设计）要在 上找出n个分点 （n固定），使这 些分点对应的正弦曲线的折线，逼近正弦曲线的误差达到最小。

22 容易计算出正弦曲线与折线间的面积（以此作为衡量误差的大小）为
因此可得该问题的数学模型为 详细问题及求解过程参阅课本P ！

23 §3. 优化问题的数学模型及其分类 n维欧氏空间 ， 向量 向量变量实值函数： §3. 1 根据优化问题的不同特点分类 无约束最优化问题：
§3. 1 根据优化问题的不同特点分类 无约束最优化问题： 约束最优化问题 其中 均为向量x 的实值连续函数，有二阶连续偏导数

24 采用向量表示法即为： 其中 这就是最优化问题的一般形式，又称非线性规划。 注意:等式约束通常可用不等式约束表示出来，有时

25 定义：称满足所有约束条件的向量x为容许解或可行解，容许点的集合称为容许集或可行集。
在容许集中找一点 ，使目标函数 在该点取最小值，即满足： 的过程即为最优化的求解过程。 称为问题的最优点， 称为最优值， 称为最优解。 最优化问题模型统一化： 在上述最优化问题的一般式中只是取极小值，如果遇到极大化问题，只须将目标函数反号就可以化为求极小的问题。 例如：函数 在 有极大值 ， 将它改变符号后， 在同一点 处 有极小值 由此可见： 有相同最优点。

26 因此后面专门研究最小化问题。 如果约束条件中有“小于等于“的，即 则转化为 ，另外，等式约束 可以由下面两个不等式来代替： 因而最优化问题的一般形式又可写成： 可行域记为

27 §3. 2 根据函数的类型分类 线性规划： 目标函数和约束函数皆为线性函数 二次规划 目标函数为二次函数，约束函数为线性函数 非线性规划 目标函数不是一次或二次函数，或者约束函数不全是线性函数

28 对于最优化问题一般可作如下分类： 其中求解一维无约束问题的方法称为一维搜索或直线搜索，这在最优化方法中起十分重要的作用。

29 §4 最优解与极值点 极小点概念： f 例如：图中一元函数 f 定义在区间[a , b] 上, 为严格局部极小点， 为
上, 为严格局部极小点， 为 非严格局部极小点 x a为全局严格极小点 。 a b §4 最优解与极值点

30 定义1: 对 满足不等式 的点x的集合称为 的邻域。记为： 定义2： 设 若 使 （1） 均有： 则称 为f的非严格局部极小点。 （2） ,且 , 有 则称 为 f 的严格局部极小点。 定义3： 设 若 使 （1） 均有 则称 为f 在 D上的非严格全局极小点。 （2） , 有 则称 为 f 在 D 上的严格全局极小点。

31 对如下问题 由定义可知有如下两个定理（练习自证） 定理1：最优化问题的任意全局极小点必为局部极小值点. 定理2：若 为定义在 上的连 续函数,则 （1）以上问题的可行解的集合D为闭集 （2）以上问题的最优解的集合为闭集. 作业：P8, 1.1

32 作业 P8 1.1

33 第二章 基础知识 范数及其相关不等式 多元函数中值公式及其极值 二次函数

34 范数及其相关不等式 1.向量的几种范数: 范数常见不等式 l2范数 l1范数 l∞范数 lp范数 椭球范数(A正定)

35 2. 矩阵范数: (||.||为某一向量范数) 特别对方阵有 l1范数(列和的最大者 ) l∞范数(行和的最大者 ) l2范数也称谱范数
2. 矩阵范数: (||.||为某一向量范数) 特别对方阵有 l1范数(列和的最大者 ) l∞范数(行和的最大者 ) l2范数也称谱范数 (ATA最大特征值开平方) 性质:

36 3. 向量内积：x , y  Rn x , y 的内积:<x, y> = xT y = xiyi = x1y1+ x2y2+ …+ xnyn x , y 的距离： ||x-y||= [(x-y)T(x-y)](1/2) x 的长度： ||x||= [ xTx ](1/2) 三角不等式： ||x + y ||≤||x||＋||y||

37 4. 矩阵正定性: 定义：设Q为n×n对称矩阵,若 ，均有 则称矩阵Q是正 定的。若 ，均有 ，则 称矩阵Q是半正定的。若 ，均有 ，则
4. 矩阵正定性: 定义：设Q为n×n对称矩阵,若 ，均有 则称矩阵Q是正 定的。若 ，均有 ，则 称矩阵Q是半正定的。若 ，均有 ，则 称Q是负定的。若 , 均有 ,则称Q是半负定的. 回忆线性代数中正定二次型的讨论！

38 判定一个对称矩阵Q是不是正定的，可用Sylvester定理判定。
Sylvester定理：一个n×n对称矩阵Q是正定矩阵的充要条件 是矩阵Q的各阶主子式都是正的。 A是正定矩阵的等价条件 1) 存在非奇异矩阵G，使得A=GGT; 2) A的所有特征根大于零; 3) A的所有(顺序)主子式＞0; A是半正定矩阵等价条件 1) 存在矩阵G，使得A=GGT; 2) A的所有特征根非负; 3) A的所有(顺序)主子式非负;

39

40

41

42 定理：设A为 n 阶对称正定矩阵，m与M分别为A的最小
与最大特征值，则 ，恒有 定理：设A为 n 阶对称正定矩阵， m与M分别为A的最小与最大特征值，则 ，恒有

43 多元函数中值公式及其极值 多元函数 记 f(x)的Hesse矩阵定义为: 则f(x)的梯度定义为:

44 一、可微及中值公式 定义：f(x)在x处可微 定理：f(x)在x处可微，则 1) 定理：f(x)在x处二次可微，则 2)中值公式1
3)中值公式2 定理：f(x)在x处二次可微，则

45 二、多元函数的极值 二元函数：(高等数学已有结论) 定理1(必要条件)：f(x,y)在(x0,y0)处可微且取得极值，则

46 定理2 (充分条件) 若函数 的某邻域内具有一阶和二阶连续偏导数, 且 令 A<0 时取严格极大值; 则: 1) 当 时, 具有极值 A>0 时取严格极小值. 2) 当 时, 没有极值(称(x0,y0)为函数的鞍点). 3) 当 时, 不能确定 , 需另行讨论.

47 多元函数： 定理3(必要条件)： 定理4(充分条件)：

48 三、等高线

49

50 唯一极小 (全局极小) 多局部极小

51 性质: 极值点附近二元函数的等高线是一族同心椭圆.
原因: 多元函数——等值面(等高线). 性质: 极值点附近多元函数的等直面线是一族同心超椭圆面.

52 四、 梯度的性质 设 f(x) 在定义域内有连续偏导数，即有连续梯度 ，则其有以下两个重要性质： 性质1: 函数在某点的梯度不为零，则必与过该点的等值面垂直(法向量). 性质2: 梯度方向是函数具有最大变化率的方向。 性质1的说明: 过点 的等值面方程为： 设 是过点 同时又完全在该等值面上的任一条光滑曲线L的方程,θ为参数.点 对应的参数是 ，则有

53 梯度方向也称为法方向. 两边同时在 处关于θ求导数有： 向量 恰为曲线L在 处的切向量，于是
两边同时在 处关于θ求导数有： 向量 恰为曲线L在 处的切向量，于是 即函数f(x) 在 处的梯度 与过该点在等值面上的任一条曲线L在此点的切线垂直。从而与过该点的切平面垂直，从而性质一成立。 梯度方向也称为法方向.

54 定义3: 设 在点x处可微，给定单位向量h，则函数f(x) 在x沿 h方向的方向导数定义为：
若 ，则 时， 取最大值 ； 则 时， 取最小值 ；

55 最速下降方向 几个常用的梯度公式：

56 下面几个Hesse矩阵计算公式是今后常用到的：

57 例1：试求目标函数 在点 处的最速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。
解： 处的最速下降方向 这个方向上的单位向量是： 移动一个单位的新点

58

59

60

61 3.二次函数 在n元函数中，除了线性函数： 或 之外，最简单最重要的一类就是二次函数。

62 二次函数的一般形式为 其中 均为常数。 其向量矩阵表示形式是： 其中 Q 为对称矩阵 在代数学中将特殊的二次函数 称为二次型。 对于二次函数，我们更关心的是Q为正定矩阵的情形。 定义：设Q为n×n对称矩阵,若 ，均有 则称矩阵Q是正 定的。若 ，均有 ，则 称矩阵Q是半正定的。若 ，均有 ，则 称Q是负定的。若 , 均有 ,则称Q是半负定的.

63 判定一个对称矩阵Q是不是正定的，可用Sylvester定理判定。
Sylvester定理：一个n×n对称矩阵Q是正定矩阵的充要条件 是矩阵Q的各阶主子式都是正的。 A是正定矩阵的等价条件 1) 存在非奇异矩阵G，使得A=GGT; 2) A的所有特征根大于零; 3) A的所有(顺序)主子式＞0; A是半正定矩阵等价条件 1) 存在矩阵G，使得A=GGT; 2) A的所有特征根非负; 3) A的所有(顺序)主子式非负;

64 例：判定矩阵 是否正定. 解：对称矩阵Q的三个顺序主子式依次为：

65 定理： 若二次函数 中Q正定，则它的等值面是同心椭球面族，且中心为
证明：作变换 ,代入二次函数式中： 根据解析几何知识，Q为正定矩阵的二次型 的等值面是以坐标原点 为中心的同心椭球面族。由于上式中的 是常数，所以 的等值面也是以 为中心的

66 同心椭球面族，回到原坐标系中去，原二次函数就是以 为中心的同心椭球面族。
注意: (1) 这族椭球面的中心 恰是二次目标函数的唯一极小点。 (2) 前面已说过，一般目标函数的等值面在极小点附近近似地呈现为椭球面族。由此可见对于二次目标函数有效的求极小点的算法，当用于一般目标函数时，至少在极小点附近同样有效。因此在最优化理论中判定一个算法好坏的标准之一，是把该算法用于Q为正定的二次目标函数，如能迅速找到极小点，就是好算法；否则就不是太好的算法。 (3) 特别地若算法对于Q为正定的二次目标函数能在有限步内找出极小点来，就称此算法为二次收敛算法，或具有二次收敛性。

67 例：把二次函数 化为矩阵向量形式并检验Q是否正定. 如正定, 试用公式 求这个函数的极小点.
注意到： 由上例知Q正定，且

68 作业 P38 2.1, 2.2, 2.4, ,2.19, 2.20(后),2.32, 2.36