最优化理论算法及工程应用ppt课件.ppt

《最优化理论算法及工程应用ppt课件.ppt》由会员分享，可在线阅读，更多相关《最优化理论算法及工程应用ppt课件.ppt（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Page 2第一章第一章 预备知识预备知识最优化问题最优化问题方向导数与极值问题方向导数与极值问题泰勒级数问题泰勒级数问题凸集、凸函数与凸优化问题凸集、凸函数与凸优化问题算法概述算法概述Page 31.最优化问题最优化问题最优化定义最优化定义: 最优化是从所有可能方案中选择最合理方案以达到最优目最优化是从所有可能方案中选择最合理方案以达到最优目标的一门学科。标的一门学科。最优化问题最优化问题： 寻求某些变量的取值使其符合某些限制条件，并使某个目寻求某些变量的取值使其符合某些限制条件，并使某个目标函数达到最大值或最小值的问题。标函数达到最大值或最小值的问题。最优化方法包括: 线性规划、非线性规划

2、、整数规划、动态规划、多目标规划、组合优化等等。Page 41.最优化问题的发展最优化问题的发展n 最优化问题可以追溯至最优化问题可以追溯至17世纪法国数学家拉格朗日关世纪法国数学家拉格朗日关于一个函数在一组等式约束条件下的极值问题于一个函数在一组等式约束条件下的极值问题 (求解多元求解多元函数极值的函数极值的 Lagrange 乘数法乘数法 )。n 19 世纪柯西引入了最速下降法求解非线性规划问题。世纪柯西引入了最速下降法求解非线性规划问题。n 20 20世纪三、四十年代线性规划世纪三、四十年代线性规划(LP)理论的引入使得优理论的引入使得优化理论的研究出现了重大进展。化理论的研究出现了重大

3、进展。 n 1951年库恩和塔克给出了非线性规划年库恩和塔克给出了非线性规划(NLP)的最优性的最优性条件。条件。n 随着计算机技术的发展，各种最优化算法应运而生。随着计算机技术的发展，各种最优化算法应运而生。 Page 5最优化问题的数学模型一般形式1 . 1 . 1 Ds.t.x f(x),min 2 . 1 . 1, 2 , 1, 0. .mixct si 3 . 1 . 1, 1, 0pmixci 其中其中nTnRxxxx,21（目标函数）（目标函数） （等式约束）（等式约束）（不等式约束）（不等式约束）Page 62.n元函数的Taylor公式n 一元函数的泰勒展开式：一元函数的泰勒

4、展开式： 设函数在定义域内连续可微，则有设函数在定义域内连续可微，则有凸集、凸函数与凸优化问凸集、凸函数与凸优化问题题20000( )0()()()()2!()!nnnfxf xxf xfxxxfxxRn 10,)!1()(10)1(nnnxnxxfR 其中其中Page 7n 二元函数的二元函数的Taylor展式：展式：),(),(),(000000yxfyyxxyxfyyxxf2000011(,)(,)2!nnxyf xyxyf xyRxynxy10),()!1(1001yyxxfyyxxnRnn其中其中Page 83.函数的方向导数与极值问题函数的方向导数与极值问题n 目标函数的等值面（线

5、）目标函数的等值面（线）对于简单的问题，可用等值线或等值面来描述函数的对于简单的问题，可用等值线或等值面来描述函数的变化趋势，还可以直观地给出极值点的位置。变化趋势，还可以直观地给出极值点的位置。 1）目标函数的等值面，其数学表达式为）目标函数的等值面，其数学表达式为f(x)=c。 在这种线或面上所有点的函数值均相等，因此，这种线或在这种线或面上所有点的函数值均相等，因此，这种线或面就称为函数的等值线或等值面。面就称为函数的等值线或等值面。当当c取一系列不同的常数值时，可以得到一组形态相取一系列不同的常数值时，可以得到一组形态相似的等值线或等值面，称为函数的等值线簇或等值面簇。似的等值线或等值

6、面，称为函数的等值线簇或等值面簇。Page 9函数的方向导数与极值问题函数的方向导数与极值问题2）当）当n=2时，该点集是设计平面中的一条直线或曲线。时，该点集是设计平面中的一条直线或曲线。 例例1： 目标函数目标函数f(x)一一60 x1一一120 x2的等值线族。的等值线族。 这是一组相互平行的直线，函数值沿箭头所指方间逐渐下这是一组相互平行的直线，函数值沿箭头所指方间逐渐下降。如图所示。降。如图所示。凸集、凸函数与凸优化问凸集、凸函数与凸优化问题题Page 10函数的方向导数与极值问题函数的方向导数与极值问题3）当）当n=3时，该点集是设计空间中的一个平面或曲面。时，该点集是设计空间中的

7、一个平面或曲面。例例2 函数函数 的图形的图形(旋转抛物面旋转抛物面)，以及用平，以及用平面面f(X)c切割该抛物面所得交线在设计空间中的投影。切割该抛物面所得交线在设计空间中的投影。如图所示。如图所示。4）当）当n大于大于3时，该点集是设计空间时，该点集是设计空间 中的一个超曲面。中的一个超曲面。4十4x一x十xf(x)12221Page 11函数的方向导数与极值问题函数的方向导数与极值问题n 方向导数方向导数 讨论函数讨论函数 在一点在一点P沿某一方向的变化率问题。沿某一方向的变化率问题。 如果函数在点如果函数在点 是可微分的，那末函数在该点沿任意是可微分的，那末函数在该点沿任意方向方向L

8、的方向导数都存在，且有的方向导数都存在，且有 其中其中 为为x轴到方向轴到方向L的转角的转角), ( yxfz),(yxPsincosyfxflfPage 12函数的方向导数与极值问题函数的方向导数与极值问题n 梯度梯度 函数在一点的梯度是这样一个向量函数在一点的梯度是这样一个向量, 它的方向与取得最它的方向与取得最大方向导数的方向一致大方向导数的方向一致, 而它的模为方向导数的最大值。而它的模为方向导数的最大值。 以以 的的n个偏导数为分量的向量称为在处的梯度，个偏导数为分量的向量称为在处的梯度， 记为记为 梯度也可以称为函数关于向量的一阶导数。梯度也可以称为函数关于向量的一阶导数。)(xf

9、Tnxxfxxfxxfxf)(,)(,)()(21Page 13n Hesse矩阵22221211222222122222212()()()()()()()()()()()nnnnnfxfxfxxxxxxfxfxfxxxxxfHxfxfxfxxxxxxxx20c2()0Tb x2()2Tx AxA（其中TAA）Page 14函数的方向导数与极值问题函数的方向导数与极值问题n 梯度与方向导数之间的关系梯度与方向导数之间的关系(1) 若若 ，则，则P的方向是函数在点的方向是函数在点 处的下降方向；处的下降方向；(2) 若若 ，则，则P的方向是函数在点的方向是函数在点 处的上升方向。处的上升方向。

10、方向导数的正负决定了函数值方向导数的正负决定了函数值的升降，而升降的快慢就由它的的升降，而升降的快慢就由它的绝对值大小决定绝对值越大，绝对值大小决定绝对值越大，升降的速度就越快升降的速度就越快0)(0PxfT0)(0PxfT0 x0 xPage 15结论：结论：(1)梯度方向是函数值的最速上升方向；梯度方向是函数值的最速上升方向；(2)函数在与其梯度正交的方向上变化率为零；函数在与其梯度正交的方向上变化率为零；(3)函数在与其梯度成锐角的方向上是上升的，而在与其梯度函数在与其梯度成锐角的方向上是上升的，而在与其梯度成钝角的方向上是下降的；成钝角的方向上是下降的；(4)梯度反方向是函数值的最速下

11、降方向梯度反方向是函数值的最速下降方向Page 16函数的方向导数与极值问题函数的方向导数与极值问题n 可行方向可行方向定义定义 设设 x是规划（是规划（NPNP）一个可行点）一个可行点, ,若非零向量若非零向量 d满足满足： 当当 时时， , 0(0, )Rxd则称则称 为集为集dRx处的一个可行方向（处的一个可行方向（feasible directionfeasible direction）。）。合合 在点在点 若下降方向关于区域若下降方向关于区域 D D 可行，可行，则称为则称为可行下降方向可行下降方向。Page 17函数的方向导数与极值问题函数的方向导数与极值问题n 无约束优化极值问题

12、无约束优化极值问题 定理定理3.1 (3.1 (一阶必要条件一阶必要条件) )( )f x在在一一次可微次可微；x(2)(2) 为为 的局部极值点，则的局部极值点，则( )0fx（1 1）函数函数x( )f x定理定理3.2. (3.2. (充分条件充分条件) )( )0fx（3 3）HesseHesse矩阵矩阵2( )0fx（）。）。则则为的严格局部极小值点（极大值）为的严格局部极小值点（极大值） ( )f x在在二次可微二次可微；x（1 1）函数函数2( )0fx（2 2）xPage 18凸集、凸函数与凸优化问题凸组合：已知 ，任取k个点，如果存在常 数 ， 使得 则称 为 的凸组合。 凸

13、集凸集：设集合：设集合 ，如果，如果 中任意两点中任意两点的凸组合仍然属于的凸组合仍然属于 , ,则称则称 为凸集。为凸集。nRDnRD0ia),2, 1(ki11kiiaxxakiii1xix),2, 1(kiDDDPage 19凸集、凸函数与凸优化问题设设 ，任取，任取 如果有如果有 ，有，有则称则称 为为 上的（严格）凸函数。上的（严格）凸函数。ab凸函数凸函数1x2x1P2Ppab凹函数凹函数1x2xnRDf:Dxx21,1, 0,2121iiaaafD)()()(22112211xfaxfaxaxafPage 20n 凸函数的判断条件凸函数的判断条件（1） 一阶导数向量法一阶导数向量

14、法 是凸集是凸集 上的凸函数的充要条件是，上的凸函数的充要条件是， 有有 (2) 二阶导数矩阵法二阶导数矩阵法 设设 在凸集在凸集X上有二阶连续偏导数，则上有二阶连续偏导数，则 是凸函数的是凸函数的充要条件是，充要条件是， 有有 半正定。半正定。)(xfDDxx21,)()()()() 1 ()2() 1 () 1 ()2(xxxfxfxfT)(xf)(xfDx)(2xfPage 21n 凸规划凸规划 设有规划 设P为凸规划，则：min ( ). .( )0,1,2,ifst gimxx当当 ( )f x( )(1,2,)igimx为凸函数时，称规划为凸函数时，称规划 P为凸规划。为凸规划。（1）规划规划P的可行解集为的可行解集为 ( )0,1iRgimxx为凸集为凸集 （2）规划规划P的最优解集为的最优解集为 *( )min( )x RRffxxx（3）规划规划P的任何局部极小点都是全局极小值点（全局最优解）的任何局部极小点都是全局极小值点（全局最优解） 为凸集为凸集 Page 22Page 23Page 24Page 25Page 26Page 27Page 28