最优化理论与方法概述课件.ppt

1、1.1 最优化问题的例子例1 对边长为a的正方形铁板，在四个角处剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？2max (2 )axx配料每磅配料中的营养含量钙蛋白质纤维每磅成本（元）石灰石谷物大豆粉0.380 0.00 0.000.001 0.09 0.020.002 0.50 0.08 0.0164 0.0463 0.1250例例2.2.（混合饲料配合）设每天需要混合饲料的批量（混合饲料配合）设每天需要混合饲料的批量为为100100磅，这份饲料必须含：至少磅，这份饲料必须含：至少0.8%0.8%而不超过而不超过1.2%1.2%的钙的钙; ;至少至少22%22%的蛋白质的蛋

2、白质; ;至多至多5%5%的粗纤维。假定主要的粗纤维。假定主要配料包括石灰石、谷物、大豆粉。这些配料的主要配料包括石灰石、谷物、大豆粉。这些配料的主要营养成分如下表所示。试以最低成本确定满足动物营养成分如下表所示。试以最低成本确定满足动物所需营养的最优混合饲料。所需营养的最优混合饲料。00010005. 008. 002. 010022. 050. 009. 0100008. 0002. 0001. 0380. 0100012. 0002. 0001. 0380. 0100. .1250. 00463. 00164. 0min3213232321321321321xxxxxxxxxxxxxxx

3、xt sxxxZ解解: :根据前面介绍的建模要素得出此问题的数学模型如下根据前面介绍的建模要素得出此问题的数学模型如下: :设设 是生产是生产100100磅混合饲料磅混合饲料所须的石灰石、谷物、大豆粉的量（磅）。所须的石灰石、谷物、大豆粉的量（磅）。321xxx121212min ()() 012. .() 012()ninjnf x xxg x xxils th x xxjm m n， ， ， ， ，11()()()() ()()TTlmG Xg Xg XH Xh XhX， ， ，min()()0. .()0fG Xs tH X，X12( ,)nXx xx min. .00jifxs tgx

4、hx 目标函数目标函数不等式约束不等式约束等式约束等式约束 称满足所有约束条件的向量称满足所有约束条件的向量 为为可行解，或可行点可行解，或可行点，全体，全体可行点的集合称为可行点的集合称为可行集，记为可行集，记为 。x |0,1,2,0,1,2,ijnDx hximgxjp xR 若若 是连续函数，则是连续函数，则 是闭集。是闭集。( ),( )ijhxgxDD 在可行集中找一点在可行集中找一点 ，使目标函数，使目标函数 在该点在该点取最小值，即满足：取最小值，即满足： 的过程即为最优化的求解过程。的过程即为最优化的求解过程。 称为问题的称为问题的最优点或最优解最优点或最优解， 称为称为最优

5、值最优值。 *x fx *min. .0.0jifxfxs tgxhx*x *fx定义定义1：整体（全局）最优解：整体（全局）最优解：若若 ，对于一切，对于一切 ，恒有恒有 则称则称 是最优化问题的整体最优解。是最优化问题的整体最优解。定义定义2：局部最优解：局部最优解：若若 ，存在某邻域，存在某邻域 ，使得对于，使得对于一切一切 ，恒有，恒有 则称则称 是最优化问题是最优化问题的局部最优解。其中的局部最优解。其中 严格最优解：严格最优解：当当 ，有，有 则称则称 为问题的为问题的严格最优解。严格最优解。*xD xD *fxfx *x*xD *()Nx *()xNxD *fxfx *x*()

6、|,0Nxxxx *xx *fxfx *x1,2()tf x x 12(,)tf x xtC 12xx，221212()f x xxx，n梯度：多元函数梯度：多元函数 关于关于 的的一阶导数一阶导数12( )(,)Tnffff xxxx( )f xxnHesse Hesse 矩阵：多元函数矩阵：多元函数 关于关于 的二阶的二阶偏导数矩阵偏导数矩阵 22222111222221 222222212f Xf Xf Xxxxxnxf Xf Xf Xf Xf Xx xxxnxf Xf Xf Xx xx xnnxn ( )f xx例：求目标函数的梯度和Hesse矩阵。解：因为 则 又因为： 故Hesse

7、阵为： 2221231 22 33( )223f xxxxxxx xx 2202220222Xf2, 2, 20, 2, 2232322222312212212xfxxfxfxxfxxfxf TxxxxxxxXf233122122, 3222,22 23322xxxXf 21122xxxXf 32223122xxxxXf下面几个公式是今后常用到的：（1） ，则 （2） ，则 (单位阵） （3） ，Q对称， 则（4）若 ，其中f： 则： TfXb X nnXfbXf0.212TfXX X IXfXXf2. 12TfXX QX .,2QXfQXXf 0tfXtp.1RRn.:11RR 020.TT

8、tfXtpptpfXtp p 多元函数Taylor展开式在最优化理论中十分重要。许多方法及其收敛性的证明都是从它出发的。 定理：设定理：设 具有二阶连续偏导数。具有二阶连续偏导数。则：则： 其中 而011:nfRR 212TTf Xpf Xf Xppf X p.XXp )|(|21|)(|202000000popxfppxfxfpxfpopxfxfpxfTTT 多元函数Taylor展开其他形式： 000220000()1()()(| )2TTf xf xf xxxxxf xxxoxx THANK YOUSUCCESS 凸集和凸函数在非线性规划的理论中具有重要作用，凸集和凸函数在非线性规划的理论

9、中具有重要作用，下面给出凸集和凸函数的一些基本知识。下面给出凸集和凸函数的一些基本知识。定义定义1 设设 ，若对，若对D中任意两点中任意两点 与与 ，连接，连接 与与 的线段仍属于的线段仍属于D；换言之，对；换言之，对 ， D，0,1恒有恒有 +(1- ) D则称则称D为为凸集凸集。 + (1- ) 称为称为 和和 的的凸组合凸组合。nRD ) 1 (x) 2 (x) 1 (x) 2 (x ) 1 (x) 2 (xa a ) 1 (xa a) 2 (xa a) 1 (xa aa a) 2 (x) 1 (x) 2 (x例例 规定：欧式空间规定：欧式空间 是凸集，空集是凸集，空集 是凸集，是凸集，

10、单点集单点集 x x 为凸集为凸集nR 12,XXS12,AXb AXb1212(1)(1)(1)AXXAXAXbbbaaaaaa|SX AXb12(1)XXSaamin . . 0TC XstAXbX,nmm nnCR bRARXR*|,0RX AXb X*R凸集的性质凸集的性质有限个凸集的交集仍然是凸集。有限个凸集的交集仍然是凸集。 设设 是凸集，则是凸集，则 是凸集。是凸集。12,kD DD12kDDD设设 是凸集，则是凸集，则 是凸集。是凸集。D |,Dy yx xD凸集的和集仍然是凸集。凸集的和集仍然是凸集。 设设 是凸集，则是凸集，则 是凸集。是凸集。12,D D1212|,DDy

11、 yxz xD zD推论：设推论：设 是凸集，是凸集， ，则，则 也是凸集，也是凸集， 其中其中 。iD1kiiiD iR 1,2,ik 定义定义3 3 极点（顶点）极点（顶点）：设设D D为凸集，为凸集，XD,XD,若若X X不能用不能用X X(1)(1)D,XD,X(2)(2)DD两点的两点的 一个凸组合表示为一个凸组合表示为X=XX=X(1)(1)+ (1-)X+ (1-)X(2)(2), ,其中其中01 01 ， 则称则称X X为为D D的一个极点。的一个极点。 kii=1=1定义定义2.2.凸组合凸组合：设：设X X(1)(1)，X X(2)(2)，X X(k)(k)是是n n维欧式

12、空间中的维欧式空间中的k k个个点，若存在点，若存在1,1, 2 2, , , k k满足满足00i i1,( 1,( i=1,2,k), 使使X=X=1 1X X(1)(1)+2 2 X X(2)(2)+ +k k X X(k)(k)， 则称则称X X为为X X(1)(1)，X X(2)(2)，X X(k)(k)的凸组合。的凸组合。定义定义4 设设D为为R 中非空凸集，若对中非空凸集，若对 ， D ，(0,1)恒有恒有n ) 1 (x) 2 (xa a f +(1- ) + (1- )f (*) 1 (xa) 2 (xa)() 1 (xfaa)()2(x则称则称 为为D上的凸函数；进一步，若

13、上的凸函数；进一步，若 时，时，(*)式式仅仅成立。成立。)(xf xf(x)( )( )( ) ()Tf yf xf xyx 证明：必要性证明：必要性(1) )( )(1) ( )fxyf xf yaaaaaaaa即即()( )( ( )( )f xyxf xf yf xaaaa由由TaylorTaylor公式公式()( )( ) ()(|()|)Tf xyxf xf xyxoyxaaaaaa (|()|)( )( )( ) ()Toyxf yf xf xyxa aa a 令令 得得0a a( )( )( ) ()Tf yf xf xyx(1) )( )(1) ( )fxyf xf yaaa

14、aaaaa设设 则则( )( )( ) ()Tf yf xf xyx充分性充分性,0,1x yDa a令令(1)xyzaaaa即即所以所以(1) )( )(1) ( )fxyf xf yaaaaaaaa(1)xyDaaaa( )( )( ) ()Tf xf zf zxz( )( )( ) ()Tf xf zf zxz 同理同理( )( )( ) ()Tf yf zf zyz ( )(1) ( )( )(z) ( ()(1)()Tf xf yf zfxzyzaaaaaaaa ( )(1) ( )( )0f xf yf zaaaa(1) )( )(1) ( )fxyf xf yaaaaaaaa定理

15、定理3 3（二阶条件）：（二阶条件）： 设设D D是是R R 中非空开凸集中非空开凸集, , 是定义在是定义在D D上的二次可微函数上的二次可微函数, ,则则 是是凸函数凸函数的充要条件为对的充要条件为对 x x D D, 0, 0,即即HesseHesse矩阵矩阵 半正半正定定。n n)(xf)(xf )(2xf )(2xf 若若 x D , 0，即，即Hesse矩阵矩阵正定正定，则，则 为为严格严格凸函数凸函数。 )(2xf )(xf证明：必要性证明：必要性,0,nxD pRpD 所以所以0,(, ), xpDa aa a 由由TaylorTaylor公式公式221()( )( )( )(

16、)2TTf xpf xf xpp G x poaaaaaaaa 令令 得得0a a因为因为 为开集。为开集。由一阶条件由一阶条件()( )( )Tf xpf xf xpaaaa 所以所以221( )()02Tp G x poaaaa221()( )02Top G x pa aa a( )0Tp G x p 由由p p的任意性，的任意性， 半半正定。正定。( )G x充分性充分性,x yD其中其中(),0,1xyxaaaa因为因为 半正定半正定故故 为凸函数。为凸函数。( )G 所以所以( )( )( ) ()Tf yf xf xyx( )f x1( )( )( ) ()()( )()2TTf

17、yf xf xyxyxGyx 严格凸函数？严格凸函数？充分性充分性,x yD其中其中(),0,1xyxaaaa因为因为 正定，正定，故故 为严格凸函数。为严格凸函数。( )G 所以所以( )( )( ) ()Tf yf xf xyx( )f x1( )( )( ) ()()( )()2TTf yf xf xyxyxGyx xy 221122( )32210f xxxxx2212( )f xxx 1212( )( )162,41,f xf xxxxx（）222222121221( )( )( )( )6,4,0,f xf xf xf xxxx xx x260( )04f x是正定的，( )f x

18、故是凸的。22122( )f xxx（ ）因，220( )02f x故，( )f x所以是凹的。若规划若规划 ljhmigtsfji, 2 , 1, 0)(, 2 , 1, 0)(. .)(minxxx中中, 和和- 为凸函数为凸函数, 是线性函数是线性函数,则上述问题为则上述问题为凸规划。凸规划。)(xf)(xig)(xih定义定义6:6:凸规划凸规划 设设D D 为凸集为凸集, , 是定义在是定义在D D上的上的凸函数，则称规划问题凸函数，则称规划问题 为凸规划。为凸规划。min( )x Df x ( )f xnR min . . 0TC XstAXbX2212121212min 22.

19、. 1 0,0 xxx xstxxxx221212()22f Xxxx x12()1g Xxx定理定理5 5：（1)1)凸规划的任意局部极小点就是整体极小点，凸规划的任意局部极小点就是整体极小点，且极小点集合是凸集。且极小点集合是凸集。 (2)(2)如果凸规划的目标函数是严格凸函数，如果凸规划的目标函数是严格凸函数，又存在极小点，则它的极小点还是唯一的。又存在极小点，则它的极小点还是唯一的。2221231 3( ) 3234f xxxxxx2211 22( )23f xxxxx222123221213123min ( )2. . 4 510 ,0f xxxxstxxxxx x xTHANK YOUSUCCESS