工程优化课件

1、工程优化课件穆学文 2010，91背景知识（续）Ø 1935-38年，英国为了正确地运用新研制的系统来对付德国飞机的空袭，在中组织了一批科学家， 进行新战术试验和战术效率评价的研究，并取得了满意的效果。他们把从事的这种工作命名为“Operational Research”(运筹学，或直译为研究)。Ø 1939年， 的. 总结了他对生产组织的研究，写了生产组织与计划中的数学方法一书，是线性 应用于工业生产 的经典著作Ø 1947年,G.B.Dantzig提出了单纯形 后，线性 便迅速形成为一个 的分支。 并逐级发展起来。§1背景知识 运筹学理论的一部分 最

2、早于中国古代Ø 公元前6世纪所著的孙子兵法Ø “斗马术”，田忌与齐王赛马，博弈论Ø 运筹帷幄之中，决胜千里之外”。这千古名句也可以说是对运筹思想的赞颂和褒奖。 国外与发展Ø 1896年，V.Pareto首次从数学角度提出多目标优化问题，引进了Pareto最优的概念。第一章 基础知识 背景知识 基本概念及其应用 最优化举例 优化的数学模型及其分类 最优解与极值点 常用的数学 到课率+作业+期末 课件地址邮箱：：xd123456及其参考书目计划学时数：46学时：1 最优化计算.，西安电子科技大学，1985。2 最优化理论与算法. 陈宝林.

3、，2003。主要参考书目：1最优化理论与.,. 科学，1997。 2最优化.,. 大连理工大学，1985。3非线性数值.，上海科学技术，1993工程优化课程理学院数学系：穆学文:mxw1334工程优化课件穆学文 2010，92背景知识（续）Ø 1965年起，和他的小分队在工业部门开始普 及推广统筹法的群众运动。在此后的二十年中，为普及 推广（统筹法与从1970年开始普及推广的优选法）， 他们走访了23个省市中几百个城市的几千个工厂， 并百万人开设讲座开展工作，取得了巨大的效 益和效益。Ø 1965年统筹平话及其补充一书由中国工业。Ø 1970年起，和他的小分队开始

4、在范围内普及推广优选法的群众运动。从此，统筹与优选变得家，的普及推广也取得了极为可观的、经济效益。Ø 优选法平话及其补充一书由国防工业。背景知识（续）Ø 1959年2月，山东大学在数学系中设置了国内最早的一个运筹学专门化，由同与郑汉鼎执教。自当年暑假开始，每年运筹学方向的学生毕业，为我国运筹学事业的发展作出了重要贡献。Ø 1959年，中国数学了运筹学研究室， 研究所内其它室组调入。定任研究室， 该室最早的一批研究有排队论组的、煇、；对策论组的、施闺芳； 数学组的、凌开诚等。与 此同时，范围内很多高校也有大批教师转入运筹学 领域。背景知识（续） 运筹学理论在中国的研

5、究与发展Ø 1957年，经中国力学的倡导， 在该所了由的国内第一个运筹学研究组(后)。张、桂湘云等是该组最早的一批研究，从此在我国开始了现代运筹学的研究。当年秋季，又有大学毕业生、陈锡康、等分配进入该组。Ø 1958年，中国 数学率领广大研究 ， 、 、 先、 等在内， 也开展了运筹学应用课题的研究，并影响和带动了范围内、各高校的运筹学应用和推广工作。 和农业等部门的“图上作业法”、“打麦场设计”、“中国邮递员”是典型的成果。背景知识（续）Ø 1959年1月1日，国际运筹学会 会(1FORS)正式宣告，当时的 会只 英、美、法三个 的运筹学会，首任（1959-61

6、年） （当 为 ，到1968 年第四届 改称 ）为英国的Charles Goodeve。背景知识（续）Ø 1952年5月美国运筹学会，并创刊Operations Research。Ø 1953年,R.Bellman提出动态 的名称，并阐述了最优化原理。Ø 1954年，D.R.Dantzig等研究旅行 时提出了分解的思想，成为整数 中两大 割平面法与分枝定界法的萌芽。Ø 1955年,G.Dantzig首先考虑出现随 量的线性 问题，这是最早提出的随机 中的有补偿 。Ø 1956年, L.R.Ford,Jr.与 D.R.Fulkerson提出并解决

7、了网络最大流，加强了图论与线性的，促进了优化理论的研究。背景知识（续）Ø 英国运筹学会1948年 （1948-53年是运筹学 ，1953年11月起改名为学会）。 。Ø 二次大战胜利后，美英各国不但在军事部门继续保留了运筹学的研究 ，而且在研究 、组织的配备及研究范围和水平上，都得到了进一步的扩大和发展，同时运筹学 也向 和工业等部门扩展。Ø 1951年了新版（1946年的原版是的，1948年才 撤销）的P.M.Morse和G.E.Kimball的运筹学（Methods of Operations Research），这是二战结束后， 对 整个运筹学工作做系统的专业

8、叙述的一本著作。Ø 1951年,H.W.Kuhn与A.W.Tucker提出了Kuhn-Tucker条件，标志着非线性理论的初步形成。工程优化课件穆学文 2010，93因此，我们在学习本科要尽可能了 解如何由实际形成最优化的数学模型。 为了便于大家今后在处理实际时建立最优化数学模型，下面我们先把有关数学模型的一些事项作一些说明。数学模型: 对现实事物或的数学抽象或描述。最优化技术工作被分成两个方面，一是由实际生产或科技 形成最优化的数学模型，二是对所形成的数学 进行数学 和求解。对于第二方面的工作，目前已有一些较系统成 资料，但对于第一方面工作即如何由实际 抽象出数学模型，目前很少 的

9、资料，而这一工作在应用最优化技术解决实际 时是十分关键的基础，没有这一工作，最优化技术将成为无水之源，难以健康发展。最优化技术应用范围十分广泛，在我们日常生活中，在工农业生产、 、国防、航空航天工业中处处可见其用途。如结构最优设计、电子器件最优设计、光学仪器最优设计、化工工程最优设计、标腔最优配方、 方案、 最优配备、油田开发、水库调度、饲料最优配方、食品结构优化等等。最优化 至少有两要素：一是可能的方案；二是要追求的目标。后者是前者的函数。如果第一要素与时间无关就称为静态最优化 ，否则称为动态最优化 。本科程专门讲授静态最优化。§2 基本概念及其应用最优化技术是一门较新的学科分支。

10、它是在本世纪五十年代初在电子计算机广泛应用的推动下才得到迅速发展，并成为一门直到目前仍然十分活跃的新兴学科。最优化所研究的 是在众多的可行方案中怎样选择最合理的一种以达到最优目标。将达到最优目标的方案称为最优方案或最优决策，搜寻最优方案的称为最优化，关于最优化的论称为最优化理论。背景知识（续）Ø 1980年4月22-26日在山东济南，召开了中国数学会运筹学会 暨第一届 。中国运筹学倡导者之一， 中国 副院长 主持了会议，有来自各地科研机构、高等院校、军事部门、工交企业等有关 的82 名代表出席。 在大会开幕式与闭幕式上均 了，回顾了他在 范围普及推广“ ”的经验和成果，勉励大家以克敌

11、攻坚的进取精神积极开展运筹学研究。会议作了12个专题学术报告和个人成果的几十个分组报告。中国数学会理事长 被推选兼任运筹学会理事长， 、 、余潜修为副理事长，桂湘云为 长，推选常务理事11名，理事42名。会议决定学会挂靠在 应用数学所工程优化课件穆学文 2010，94追求的目标是圆柱体表面积最小。即minimize(min)2p rh + 2p r 2则得原的数学模型：min 2p rh + 2p r2s t.r 2 - 4 = 03s.t.Subject to.固定.解:(1) 决定圆柱体表面积大小有两个决策变量： 圆柱体底面半径 r、高 h。(2) 的约束条件是所铸圆柱体重量与球重相等。即

12、p r 2 × h × r = 4 p R3 × r3即r 2h - 4 = 03§2 最优化举例最优化在、自动、机械设计、采矿冶金、管理等科学技术各领域中有广 泛应用。下面举几个实例。例1: 把半径为1的实心 熔化后，铸成一个实心圆柱体，问圆柱体取什么 才能使它的表面积最小？（3） 目标函数。这是作为系统决策变量的一个数学函数来衡量系统的效率，即系统追求的目标。一般的模型简化工作以下几类：（1） 将离散变量转化为连续变量。（2） 将非线性函数线性化。（3） 删除一些非主要约束条件。建立最优化数学模型的三要素：（1） 决策变量和参数。决策变量是由数学模型

13、 的解确定的未知数。参数表示系统的变量，有确定性的也有随机性的。（2） 约束或限制条件。 由于现实系统的客观物质条件限制，模型必须把决策变量限制在它们可行值之内的约束条件，而这通常是用约束的数学函数形式来表示的。建立数学模型时要尽可能简单，而且要能完整地描述所研究的系统，但要注意到过于简单的数学模型所得到的结果可能不符合实际情况，而过于详细复杂的模型又给分析计算带来。因此，具体建立怎样的数学模型需要丰富的经验和熟练的技巧。即使在建立了 的数学模型之后，通常也必须对模型进行必要的数学简化以便于分析、计算。工程优化课件穆学文 2010，95l 旅行团从 v0 出发要遍游城市 v1 , v2 ,.,

14、 vn ， 已知从 vi 到 v j 的旅费为 cij ，问应如何安排行程使总费用最小？ 模型：l 变量是否从 i 第个城市到第 j 个城市xij = 1, 0;l 约束每个城市只能到达一次、离开一次xij = 1, 0; 例3：旅游售货员l 旅游线路安排预定景点走且只走一次路上时间最短l 配送线路货郎担送货地到达一次总路程最短显然偏差S越小,曲线就拟合得越好,说明参数值就选择得越好，从而我们的 就转化为5维无约束最优化 。即：éæöù2êç÷úmin åm ê y - ç a +a

15、2÷úê i ç 1æö ÷úi =1 êç1+ a ln 1+ exp xi - x4 ÷úêëè3 ça ÷ øûè5 ø ú解: 很显然对参数a1 , a2 , a3 , a4 和 a5 任意给定的一组数值, 就由上式确定了 y 关于 x 的一个函数关系式, 在几何上它对应一条曲线, 这条曲线不一定通过那m个测量点, 而要产生“偏差”.将测量点沿垂线方向到曲线的距离的平方

16、和作为这种“偏差”的度量.即éæöù2 yêç÷úmS = åê y - ç a +a2÷úê i ç 1æx - a ö ÷úi=1 êç1+ a ln 1+ exp i4 ÷úêëè3 ça ÷ úxè5 ø øû例2: 多参数曲线拟合已知两个物理量 x 和 y 之

17、间的依赖为:y = a +a21æx - a ö1+ a3 ln ç1+ exp4 ÷èa5 ø其中 a1 , a2 , a3 , a4 和 a5 是待定参数, 为确定这些参数, 对x, y 测得m 个实验点:( x1, y1 ), ( x2, y2 ),"( xm , ym )试将确定参数的表示成最优化.利用在高等数学中所学的Lagrange乘子法可求解本, 分别对r, h,求偏导数,并令其等于零.有:L (r.h l ) = 2p rh + 2p r 2 - l(r 2h - 4)3ì¶L = 2p

18、h + 4p r - 2rhl = 0ï ¶rh = 2rÞ ï¶L22ï2í¶h = 2p r - lr = 0Þ r = 3 , h = 23ï33ï ¶L = -r 2h + 4 = 0î¶l32此时圆柱体的表面积为 6p æ 2 ö3ç 3 ÷è ø工程优化课件穆学文 2010，96打点行李，现有三个旅行包， 容积大小分别为1000毫升、1500毫升和2000毫 升，根据需要列出需带物品，

19、其中一些物 品是必带物品共有7件，其体积大小分别为400、300、150、250、450、760、190（毫升）。尚有10件可带可不带物品，如果不带将在目的 地，通过可以得知其在目的地的 价格（）。这些物品的容量及价格分 别见下表，试给出一个合理的安排方案把物品 放在三个旅行包里。例5：背包 邮递包裹把形状可变的包裹用尽量少的车辆运走 旅行背包容量一定的背包里装尽可能的多的物品 装箱解:根据前面 的建模要素得出此 的数学模型如下:设 x3 是生产100磅混合饲料所须的石灰石、谷物、大豆粉的量（磅）。ìmin 0.0164x3ïs t.= 100ï3ï0.

20、380x3 £ 0.012 ´100ï0.380x ³ 0.008´100í3ï0.09x + 0.50x ³ 0.22 ´100ï23ï0.02x2 + 0.08x3 £ 0.05´100ïx ³ 0î3配料每磅配料中的营养含量每磅成本（元）钙蛋白质石灰石谷物 大豆粉0 3800 000 000 0010 090 020 0020 500 080 01640 04630 1250例4：（混合饲料配合）以最低成本确定满 足动物所需营养的

21、最优混合饲料。设每天需要混合饲料的批量为100磅，这份饲料必须 含：至少0.8%而不超过1.2%的钙;至少22% 的蛋白质;至多5%的粗。假定主要配料石灰石、谷物、大豆粉。这些配料的主要营养成分为：n nl 目标总费用最小 åå cij xiji =0 j =0n nmin åå cij xiji=0 j =0ìån x = 1; i = 1, 2, , nïijï j =0ï nst íå xij = 1; j = 1, 2, , nï i =0ï xij = 1

22、, 0, i = 1, 2, , n, j = 1, 2, , nïî工程优化课件穆学文 2010，97§3. 优化的数学模型及其分类n维空间 Rn ，x Î Rn( , ," x )T2n变量实值函数：f : Rn ® R13. 1 根据优化的不同特点分类 无约束最优化：min f ( x) xÎRn模型：xij = 1, 0;17å ci xij £ rj ; j = 1, 2, 3i =13å xij = 1; i = 1, 2., 7j =13å xij £ 1; i

23、 = 8, 2.,17j =1xij = 1, 0; i = 1, 2.,17, j = 1, 2, 3l 目标函数未带物品费用最小173å pi (1 - å xij )i =8j =131 - å xij ; i = 8, 9.,17j =1 约束17包裹容量限制： å ci xij £ rj ; j = 1, 2, 3i =13必带物品限制： å xij = 1; i = 1, 2, 7j =1n n选带物品限制：åå cij xiji =0 j =0分析： 变量对每个物品要确定是否带同时要确定 放在哪个包裹

24、里，如果增加一个虚拟的包裹把不带的物品放在里面，则 就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为第 i 个物品是否放在第j个包裹中xij = 1, 0; i = 1, 2.,17, j = 1, 2, 3物品12345678910体积200350500430320120700420250100价格75200902030工程优化课件穆学文 2010，983. 2 根据函数的类型分类 线性：目标函数和约束函数皆为线性函数 二次(凸二次，非凸的二次)目标函数为二次函数，约束函数为线性函数 非线性目标函数不

25、是一次或二次函数，或者约束函数不线性函数如果约束条件中有“小于等于“的，即G ( x) £ 0则转化为 -G ( x) ³ 0 ，另外，等式约束 H ( x) = 0 可以由下面两个不等式来代替：H ( x) ³ 0, -H ( x) ³ 0因而最优化的一般形式又可写成：min f ( x) st G ( x) ³ 0可行域记为 D = x G(x) ³ 0最优化模型统一化：在上述最优化的一般式中只是取极小值， 如果遇到极大化，只须将目标函数反号就可以化为求极小的。fx因此后面只研究最化。- f ( x) 4- f ( x* )小f

26、( x* )f ( x)定义：称满足所有约束条件的x为容许可行解，容许点的集合称为容许集或可行集。在容许集中找一点 x* ，使目标函数 f ( x) 在该点取最小值，即满足：f (x* ) = min f ( x)s tS (x* ) ³ 0H (x* ) = 0的过程即为最优化的求解过程。x* 称为的最优解，f (x* ) 称为最优值，(x* , f (x* )称为最优点。采用表示法即为：min f ( x) ®目标函数stG ( x) ³ 0 ® 不等式约束H ( x) = 0 ® 等式约束其中 G ( x) = ( g ( x), g (

27、 x)," g ( x)T ,12mH (x) = éëh ( x), h ( x),"h ( x)ùûT12l这就是最优化的一般形式，又称非线性。 约束最优化min f ( x) s tgi ( x) ³ 0i = 1, 2,", m hj ( x) = 0j = 1, 2,", l其中 f , gi , hj 均为x 的实值连续函数，有连续偏导数工程优化课件穆学文 2010，99§5 常用数学 Maple Mathematics Lingo对如下min f ( x)s.t.gi ( x) &

28、#179; 0.i = 1, 2,", m由定义可知有如下两个定理定理1：最优化的任意全局极小点必为局部极小值点.定理2：若 f (x), gi (x)(i = 1, 2,", m) 为定义在 Rn 上的连续函数,则（1） 以上的可行解的集合D为（2） 以上的最优解的集合为.定义3： 设f : D Ì Rn ® R1 ,若 $ x* Î D 使（1） "x Î D 均有 f ( x* ) £ f ( x) 则称 x* 为f 在 D上的非严格全局极小点。（2） "x Î D, x ¹ x

29、* , 有 f ( x* ) < f ( x)则称 x* 为 f 在 D 上的严格全局极小点。定义1: 对 "d >0, 满足不等式 x - x0 < d 的点x的集合称为 x0 的邻域。记为：N| - x0 < d ,d > 0定义2：设f : D Ì Rn ® R1 , 若 $ x* Î D,d > 0 使（1）" x Î N ( x*,d ) Ç D 均有：f ( x* ) £ f ( x) 则称 x* 为 f 的非严格局部极小点。（2）" x Î N

30、( x* , d ) Ç D , 且x ¹ x* , 有 f (x* ) < f ( x)则称 x* 为 f 的严格局部极小点。§4 最优解与极值点一，极小点概念：ìì 严格局部极小点ï局部极小点í非严格局部极小点 极小点ïîíì 严格全局极小点ï全局极小点íîî非严格全局极小点例如：图中一元函数 f 定义在区间a , b上, x* 为严格局部极o ax* b1x小点，x* 为非严格局部极小点.1 22a 为全局严格极小点 。f对于最优化一

31、般可作如下分类：ììì线性ïïïïï无约束íì一维ï静态ïï非线性ín维íîî最优化ïïíïì线性ïï约束íïîî非线性ïì无约束ï动态íïîî约束工程优化课件穆学文 2010，910应用范围很广，工具箱不断在扩展。 Mathematic，Maple

32、具有强大的符号计算功能，主要用于数学方面。 Lingo主要对优化，特别是整数，十分有效.西安电子科技大学 穆学文 20101若令f ( x + p) - f ( x ) - lT p00= ap则 f 在 x0 处可微时，有 lim a = 0 ，即 a 是无穷p ® 0小量。f ( x + p) - f ( x ) = lT p + o ( p )(2)00其中 o ( p ) = a p 表示 p 的高阶无穷小，与一元函数可微性定义类似（ o (t ) 即 lim o (t ) = 0 ）tt® 0 t定义1：设 f : D Ì Rn ® R1 ,

33、x Î D , 若$ l Î Rn ，使对0"p Î Rn 有：f ( x + p ) - f ( x ) - lT pliim00= 0(1)p ®0p则称 f(x) 在x0 处可微。§1 多元函数及其导数§1 .1 多元函数的可微性和梯度以后我们研究的最优化涉及的均是多元函数，并要求它们的可微性，下面先给出定义。f : D Ì Rn ® R1 表示 f 是定义在Rn 中区域 D上的 n元实值函数第二章 基础知识l 多元函数及其导数l 等高线l 二元函数l 多元函数的极值l 凸集、凸函数和凸l 重要的不

34、等式l 下降迭代算法及其收敛性l 课件邮箱：mxw_1334.coml ：654321工程优化课程理学院数学系：穆学文:mxw1334西安电子科技大学 穆学文 20102两边同时在q0 处关于求导数，根据复合函数微分法有 f (t (q0 ) = éëxn¢ (q0 )ùû 恰为曲线L在x0 处的切，有Ñf ( x )T × t (q ) = 000即函数 f (x) 在 x0 处的梯度Ñf ( x0 ) 与过该点在等值面上的任一条曲线L在此点的切线垂直。从而与过该点的切平面垂直，从而性质一。性质1的证明:

35、9;f ( x0 ) t (q0 )过点 x0 的等值面方程为：f (x ) = r , r = f (x0 )(6)f ( x) = f (x ) n0 00设x2= xn (q ) 是过点 x 0 同时又完全在等值面上的任一条光滑曲线 L 的方程,为参数. 点x0 对应的参数是 q0 ，把此曲线方程代入f (xn (q ) = r0两边同时在q0 处关于求导数，根据复合函数微分法有§1 .2 梯度的性质设 f(x) 在定义域内有连续偏导数，即有连续梯度 Ñf ( x) ，则梯度有以下两个重要性质：性质1: 函数在某点的梯度不为零，则必与过该点的等值面的切平面垂直.性质2

36、: 梯度方向是函数具有最大变化率的方向。定义2: 以 f (x) 的 n 个偏导数为分量的称为f(x) 在 x 处的梯度。记为鶶 ( x) ¶f (x)ùTf," ¶x ú(4)n û梯度也可称为函数 f(x) 关于x 的一阶导数。若 f 在x0 处可微,将 代入得 f ( x + p ) = f ( x ) + Ñf ( x )T p + o ( p )(5)000这与一元函数展开到两项的 Taylor 公式是相对应的。证明：令 l = l1 , l2 ," , ln ，T依次取

37、 p = pi ei , i = 1, 2,", n , p ii 为任意无穷小变量，ei 是，由 f 在 x0 处可微，则 对p = piei ，即f ( x0 + piei ) - f ( x0 ) = lii pii + o ( pii ) i = 1, 2,", n两边除以 p ii 并取 pii ® 0 的极限有：¶f ( x0 ) = lim f ( x0 + piei ) - f ( x0 ) = li = 1, 2,", ni¶xPii®0piiii定理1: 若f (x) 在 x0 处可微，则f (x) 在该

38、点处关变量的一阶偏导数，且é ¶f ( x ) ¶f ( x )¶f ( x ) ùTTl =0000,00 ú(3)¶x û西安电子科技大学 穆学文 20103由于¶f ( x0 ) =Ñf ( x )T e 内积 Ñf ( x ) cos b¶p0=0为方向 p 与 Ñf ( x0 ) 的夹角。为使 ¶f (x0 ) 取最小值，应取 1800 ，即¶pp = -Ñf ( x0 )则 e = p = - Ñf (x) t可见

39、：负梯度方向即为函数的最速下降法方向； 梯度方向即为函数的最速上升方向。性质二得证。Ñf (x) 以上我们看到方向导数正负决定了函数升降， 而升降速度的快慢由方向导数绝对值大小来决定， 绝对值越大，升降速度越大。因此又将方向导数 ¶f (x0 )¶p称为f(x)在 x0 处沿方向 p 的变化率。推论： 若 Ñf ( x0 ) p < 0 ，则 p 是函数 f (x) 在 x0 处的下降T方向。 若 Ñf ( x )T p > 0 ，则 p 是函数 f(x) 在 x 处的上00升方向。证明：因为 p= te ，t 0，则 Ñ

40、f ( x0 ) p < 0 ，T¶f ( x0 )T有¶p = Ñf ( x0 ) e < 0 ，由前面证明即知 p 为下降方向。（同样可证明后者）定理2：若 f : Rn ® R1 在点 x 处可微，则 ¶ f ( x0 ) = Ñ f ( x )T e ，0¶ p0其中 e 为 p的。证明：利用方向导数定义并将f ( x + p ) = f ( x ) + Ñf ( x )T p + o ( p )000中的 p 换成 te 有：¶f ( x )tÑf ( x )T e + o

41、 (t )0 = lim0= Ñf ( x )T e¶pt ®0+t0由定义及极限性质可知： 若 ¶f ( x0 ) < 0 ，则 f(x) 从x 出发在 x 附近沿¶p00p方向是下降的。 ¶f (x0 ) < 0 ，则 t0 充分小时, f (x0 +te) - f (x0 ) <0¶pt即 f ( x) < f ( x0 ) , x = x0 + te 若¶f ( x0 ) > 0 ，则 f(x) 从x0 出发在 x0 附近沿¶p方向 p 是上升的。为说明第二条性质，先

42、引进下面方向导数定义：定义3: 设 f : Rn ® R1 在点x处可微，p为固定，e 为p方向的，则称极限：¶f ( x0 ) = lim f ( x0 + te ) - f ( x0 )¶pt ® 0+t¶f ( x0 )为函数 f (x) 在点 x0 处沿方向 p 的方向导数，其中 ¶p为其记号。西安电子科技大学 穆学文 20104§1 .3 Hesse矩阵多元函数的一阶导数即梯度Ñf (x) ，导数即Hesse阵éùê ¶2 f ( x ) ¶2 f ( x

43、 ) ¶2 f ( x )úêúê ¶x2xn¶x1 úê 1úê 222úÑ2 f ( x)=Ñ( f¶ ( x ) ¶ f ( x )" ¶ f ( x )ú¶ 2¶x2¶xn¶x2 úê #2# úê#úúê ¶2 f ( x ) ¶2 f ( x )¶2 f (

44、 x )úê"2 úê¶ 2 xn¶xn úëû几个常用的梯度公式：(1)f ( x ) = C () 则，Ñf ( x ) = 0(2)f ( x ) = bT x则，Ñf ( x ) = b(3)fx则，Ñf ( x) = 2x(4)Q对称矩阵。f ( x ) = xT Qx则，Ñf ( x) = 2Qx这个的是：é 4 ùé 2 ù -Ñ f ( x ) ê- 2 úê

45、5 5 úe =0 =ë û= êú-Ñ f ( x0 )( 4 )2 (- 2 )2 ê - 1 5 úêë 5 úû新点是é+ 2 5 ù é + 2 5 ùx1 = x0 + e = é0ù ê 5 ú = ê 5 úê1ú + ê 1 ú ê 1 úë û ê - 5 ú

46、 ê1 - 5 úë 5 û ë 5 ûfx x + x2 | = 26 - 2 51 2 2 x15解： 由于f则函数在 x 0 = 0,1T 处的最速下降方向是é- ¶f ( x) ùê ¶x ùé+4ùp = -Ñ2 ú = ê úx2 û x1 =0 ë-2ûx2 =1êë ¶x2 úû x1 =0x2 =1例1： 试求目标函数f

47、 (3212在点 x0 =0,1T 处的最速下降方向，并求沿这个方向移动一个长度后新点的目标函数值。函数在与其梯度正交的变化率为 0。 函数在与其梯度成锐角的是上升的。 函数在与其梯度成钝角的是下降的。Ñf ( x0 )x0-Ñf ( x0 )西安电子科技大学 穆学文 20105x2ffx2Lx1 xx21P0x1l 在Ox x 平面上任给一点 P (x(0), x(0 )，就对应有一个1 2o 12目标函数值 f = (x(0) - 2)2 + (x(0) -1)20 12l 这个值就是过 P0 点作 ox1 x2 平面的垂线与S曲面交点的纵坐标。l 反之，任给一个值 f

48、 ,使目标函数 f ( x) 取值为f 00的点 x 的个数就不相同了。可能没有，可能只有一个，可能有多个。例1.求解 min( x - 2)2 +( x -1)212这是定义在ox1x2平面上的无约束极小化，其目标函数fx -1)22在 ox1 x 2 f 三中代表一个曲面 S 。§2等高线二维最优化 具有鲜明的几何解释，并且可以象征性地把这种解释推广到 n中去。因此我们简要 一下图解法对于以后理解和掌握最优化的理论和 是很有益处的。l 一阶中值公式：对x,$ l Î (0,1), 使f (x) = f (x*)+ Ñf (x*+l(x-x*)T(x-x*)l

49、Lagrange：对x,$ m Î (0,1), 记xm=x*+ m (x-x*)f (x) = f (x*)+ Ñf T(x*)(x-x*) + (1/2)(x-x*)T Ñ2f (xm )(x-x*)§1 .4 多元函数的Taylor展开公式设 f (x): Rn ® R ，导。在x* 的邻域内z一阶Taylor展开式：f (x) = f (x*)+ Ñf T(x*)(x-x*) + ox-x*l Taylor展开式：f (x) = f (x*)+ Ñf T(x*)(x-x*) + (1/2)(x-x*)T Ñ

50、2f (x*)(x-x*)+ ox-x*2下面几个Jacobi公式是今后常用到的：f ( x) =bT xÑf ( x) = b Ñ2 f (x) = 0n´n fxÑf ( x) = x Ñ2 f ( x) = If ( x) = 1 xTQxÑf (x) = Qx, Ñ2 f ( x) = Q2西安电子科技大学 穆学文 201061 n nnn二次函数的一般形式为 fxnn ) = 2 ååq jjxiix jj + åbiixii + ci =11 jj=1i=11其中 qijj , bi

51、i, c 均为。 qijj = qjjii其矩阵表示形式是：f (x ) = 1 x T Qx + b T x + c2其中Q 为对称矩阵æ qq" q öæ b1 öç 11121n ÷ç b ÷Q = ç q21 q22 " q2 n ÷ b = ç 2 ÷ç # ÷ç # ÷ç qq" q ÷ç b ÷è n1n 2nn øè n

52、ø§3二次函数在n元函数中，除了线性函数：nfn ) = å aiixii + cii=1æ a1 öç a ÷或 f (x) = aT x + c, aT = ç 2 ÷ç # ÷ç a ÷è n ø外，最简单最重要的一类就是二次函数。等值面具有以下性质：l 不同值的等值面之间不相交，因为目标函数是单值函数。l 除了极值点所在的等值面外，在区域内部中断，因为目标函数是连续的。l 等值面稠的地方，目标函数值变化得较快，而稀疏的地方变化得比较慢。l

53、 一般地，在极值点附近，等值面（线）近似地呈现为同心椭球面族（椭圆族）。定义：在三维和三维以上的空间中，使目标函数取同一值的面x| f(x)=r, r是称为目标函数的等值面。l 我们感 的是至少有一个交点（f ³ 0 ）的情形。0l 此时用平面L截曲面S得到一个圆，将它投影到 ox1 x2 平面上，仍为同样大小的圆。在这个圆上每一点的目标 函数值均为 f 0 , 若一条曲线上任何一点的目标函数值等于同一 ，则称此曲线为目标函数的等值线。l 易见，变动 f 的值，得到不同等值线，这是一组同心圆 ，对应 f = 0的等值线缩为一点G，对应 f<0的等值线为空集。l 易见，随着 f

54、值变小，等值线圆半径变小，最后缩为一点，即为的最小值点G，x * = (2,1)Tl 这一事实的几何意义是：过 f 轴上坐标为的点作 ox1x2 坐标平面的平行平面 L，可能与曲面S 无交点（ f < 0 时），可能与S有一0个交点（ f = 0 时），可能与S交成一条曲0线（f > 0 ）。0西安电子科技大学 穆学文 20107根据几何知识，Q为正定矩阵的二次型1 yT Qy 的等值面是以坐标原点y* = 0 为中心的同心21椭球面族。由于上式中的bT Q-1b是，回到原2坐标系中去，原二次函数就是以x* = -Q-1 b 为中心的同心椭球面族。这族椭球面的中心恰是二次目标函数

55、的唯一极小点。定理： 若二次函数 fTT x + c 中Q正定，则它的等值面是同心椭球面族，且中心为 x* =-Q-1 b 证明：作变换 x = y - Q-1b , 代入二次函数式中：Y ( y) = f ( y - Q-1b)= 1 ( y - Q -11b )TT Q ( y - Q -11b ) + bTT ( y - Q -11b ) + c2= 1 yT Qy - 1 bT Q-1b + c22æ 6 -3 1 ö例：判定矩阵是否正定 Q = ç -3 2 0 ÷ç÷ç 1 0 4 ÷è

56、48;解：对称矩阵Q的三个顺序主子式依次为：6 > 06 -3 > 0-3 26 -3 1-3 2 0 > 01 0 4Q 是正定矩阵等价于如下条件非奇异矩阵G，满足Q = GT G Q 的所有特征根大于零 Q 的所有主子式0 下三角矩阵L ，满足Q = LT L判定一个对称矩阵Q是不是正定的，可用Sylvester定理判定。Sylvester定理：一个n×n对称矩阵Q是正定矩阵 的充要条件是矩阵Q的各阶顺序主子式的。思考：半正定矩阵的判定是否有同样的结论？代数学中将特殊的二次函数 ff ( x ) = 1 x T Q x2称为二次型。对于二次函数，更关心的是 Q 为正定矩阵的情形。定义：设Q为n×n对称矩阵, 若 "x Î Rn , x ¹ 0，均有 xT Qx ³ 0 ,则称矩阵 Q 是半正定的。若 "x Î Rn ， 均有 xT Qx > 0 ，则称矩阵Q是正定的。若 "x Î Rn , x ¹ 0 ，均有 x T Q x < 0，则称Q是负定的