管理科学理论2课件.ppt

1、一，等式约束问题一，等式约束问题1，切向量与正规性，切向量与正规性定义定义1 设设x0 是由方程组是由方程组gi(x)=0，i=1,2,m，确定的曲面确定的曲面S上的一点，若在上的一点，若在S上存在曲线上存在曲线x(t)，x(0)=x0，x(0)=h，则称向量是曲面则称向量是曲面S上点上点x0处的切向量。处的切向量。定义定义2：如果关于：如果关于h 的线性方程组：的线性方程组：系数矩阵系数矩阵 )(),()()()()(,2,1,0)(),(0010011010100 xgxgxxgxxgxxgxxgmihxxghxgmnmnmjjjii 满秩，则称满秩，则称x0为曲面为曲面S上的一个正规点。

2、上的一个正规点。l注注1 是是x0处法空间的一组基。处法空间的一组基。l注注2 方程组方程组 的一组线的一组线性无关的解构成曲面性无关的解构成曲面S上上x0处切空间的一组基。处切空间的一组基。l2，具等式约束问题的极值必要条件，具等式约束问题的极值必要条件l考虑二维问题：考虑二维问题：min f(x,y)S.t.g(x,y)=0l结论结论1:若在极小点若在极小点(x0,y0)处处,g(x0,y0)0，则则 f(x0,y0)与与 g(x0,y0)线性相关，即线性相关，即 f(x0,y0)+g(x0,y0)=0。l结论结论2：(Lagrange乘子规则乘子规则)设设(x0,y0)是局部极小点，且是

3、局部极小点，且 g(x0,y0)0，则存在常数则存在常数 ，对函数，对函数F(x0,y0)=f(x0,y0)+g(x0,y0)，满足满足 F(x0,y0)=f(x0,y0)+g(x0,y0)=0.)(,),(001xgxgm mihxgi,2,1,0),(0 结论结论3（充分条件）：设点（充分条件）：设点x0满足必要条件：满足必要条件：F(x0)=f(x0)+g(x0)=0.若若则则x0是局部极小点。是局部极小点。二，具不等式约束的问题二，具不等式约束的问题1，下降方向和可行方向，下降方向和可行方向考虑一般非线性约束优化问题：考虑一般非线性约束优化问题：例：求解例：求解 mihxghhxFhh

4、xFiT,2,1,0);(0,0)(),(0020 pjmixhxgxSxfji,1;,1,0)(,0)()(min 01,01,01)(min21212221xxxxxSxxxf1)下降方向的选择下降方向的选择 如果方向如果方向P在点在点x0处是下降方向，则处是下降方向，则P应与应与 f(x0)同侧，同侧，即：即：记记 为点为点x0处的下降方向集。处的下降方向集。2)可行方向的选择可行方向的选择 在在x0处的可行方向应满足处的可行方向应满足:结论结论1：若：若 所有方向所有方向P都是可行的。都是可行的。结论结论2：若：若 当当 时时0)(0 PxfT0)(00 PxfPFTpjPxhmiPx

5、gji,2,1,0)(,2,1,0)(00 00Sx Sx 0 0)()(,0)(000 xgixIixgPiiT则则P为可行方向。为可行方向。记记 为可行方为可行方向集。向集。注：对等式约束而言，所有约束都是起作用约束。注：对等式约束而言，所有约束都是起作用约束。2，最优性条件，最优性条件定义定义1：若对：若对 x C和和0，有有 x C，则称，则称C为锥，如果为锥，如果C是是凸的，则称其为凸锥。凸的，则称其为凸锥。定义定义2：设是约束集，称：设是约束集，称为为x0处的可行方向锥。处的可行方向锥。下面进一步讨论最优性条件。设下面进一步讨论最优性条件。设x*是问题是问题 的最优解，则的最优解，

6、则x*处处)(,0)(000 xIiPxgPGiT ,0,00 SPxPPD niRxmixgxf,1,0)()(min 00FG 换言之，在换言之，在x*处满足处满足 的方向的方向P必有必有 称称 为为FritzJohn 条件。其中条件。其中 线性无关。线性无关。在最优点在最优点x*处应满足处应满足 lFarkas引理：给定向量引理：给定向量a i（i=1,2,k）与）与b，不存在向量，不存在向量P同同时满足条件时满足条件 和和 的充要的充要条件是条件是 向量向量b 在在ai 所张成的凸锥内，即满足所张成的凸锥内，即满足 0)(PxfT)(,0)(xIiPxgiT xIiiixgxf)()(

7、)(,),(1 xgxgm mixgxgxfiiiiii,1,0)(0),()(kiPaTi,2,1,0 0 PbT0,1 ikiiiab 定理定理1:设设x*为问题为问题的一个可行点的一个可行点,并且前并且前t个约束为起作用约束个约束为起作用约束,则则x*为最为最优解的一个必要条件是下式成立优解的一个必要条件是下式成立:例例:考虑问题考虑问题 mibxaRxxfiniiijn,1,),(min10,*)(1 itiiiaxf 0)(,0)(,01)(,)(min231223111xxgxxgxxxgxxf）（成成立立。使使显显然然找找不不到到，是是最最优优点点，起起作作用用约约束束），（*)

8、(*)(*)(,0,)1,0(*)(,)1,0(*)()0,1(*)(3,1*)(01*35113131xgxgxfxgxgxfxIxTTTT l从上例看出，满足定理从上例看出，满足定理1还需增加一些约束规范，如梯度向还需增加一些约束规范，如梯度向量线性无关等，上例有量线性无关等，上例有 更一般的有：更一般的有：l定理定理2（KuhnTucker）最优性必要条件：）最优性必要条件：在最优点在最优点x*处，设处，设线性无关，则存在线性无关，则存在满足：满足：称上式为称上式为KT条件条件，满足上式的点称，满足上式的点称KT点点。相应的广义相应的广义Lagrange函数为：函数为：pjxhxIixg

9、ji,1),();(),(TpTm ,;,11*)(*)(31xgxg mixgxhxgxfiiimipjjjii,1,0,0)(0)()()(11 pjjjimiixhxgxfxL11)()()(),(例例1：验证以下问题在最优解处：验证以下问题在最优解处K-T条件成立。条件成立。解解:例例2:013)2()3()(0)4(16)()(min222122211xxxhxxxgxxf .)(,0)(,2613,0,)2,133(),3;1)(,0)(,51,403,)2.3,4.6(),2;1)(,0)(,0,81,)0,0(),1*xIxgxxIxgxxIxgxTTT .06)(,026)(

10、,01)(,)(min212221211221xxxhxxxgxxgxxxf解解:定理定理3 设设x*是一个可行点，若存在使是一个可行点，若存在使K-T条件成立，并且对应条件成立，并且对应的的Lagrange函数的函数的Hessen阵在子空间阵在子空间M上正定，则上正定，则x*是一个严是一个严格的局部极小点。格的局部极小点。其中：其中：注注 若若 线性无关，线性无关，则则M是约束集在是约束集在x*处的切空间。处的切空间。4*)()5,1(*41183001.02.2.0,0,0)26(,0)1(,021,022);1,1()(,)2,2()(,)0,1()(,)1,2()(1211212122

11、2121112212111121211xfxxxxxxxTKxhxxxgxgxxfTTTT 或或条条件件为为 pjxhyxIixgyyMjTiT,1,0)(;,0)(*pjxhxIixgji,1),();(),(定理定理4：凸规划问题的可行凸规划问题的可行K-T点必为最优解。点必为最优解。3，Lagrange函数的鞍点函数的鞍点定义定义1：如果对：如果对有有则称点则称点 是是Lagrange函数：函数：的鞍点。的鞍点。定理定理5：若：若 是鞍点，则是鞍点，则 是原问题的整体最优解，是原问题的整体最优解，但逆一般不成立。但逆一般不成立。例例 考虑非线性规划问题：考虑非线性规划问题：注注 可验证可

12、验证x*=(0,0)T是问题的极小点是问题的极小点(在在x*是处，取是处，取*=3，则，则K-T条件成立条件成立)。pmnRRRx ,)0(,),(),(),(xLxLxL ),(x)()()(),(xhxgxfxLTT ),(xx .0)(,3)(min222221xxhxxxxf下证其下证其Lagrange函数函数没有鞍点。没有鞍点。反证法反证法，假设鞍点，假设鞍点 存在，由定理存在，由定理5知，知，必为问题的必为问题的最优解，故最优解，故 ,由鞍点定义，对所有的由鞍点定义，对所有的x与与，有有即即:由于当由于当x1=0，x2取充分大时，总能使右端为负值，推出矛盾。取充分大时，总能使右端为

13、负值，推出矛盾。l鞍点迭代方法鞍点迭代方法:设设Lagrange函数函数其中其中 为某个取定的步长，迭代过程中为某个取定的步长，迭代过程中 逐步缩小，每次迭代需逐步缩小，每次迭代需计算两迭代点之间的距离，如距离减小计算两迭代点之间的距离，如距离减小 被接受，否则缩小，被接受，否则缩小，最后当两点距离充分小时，迭代终止。最后当两点距离充分小时，迭代终止。),(xxTxx)0,0(*2222213),(xxxxxL ),(),(),(xLxLxL 22221)3(00 xxx ),(,0max),()()()()1()()()()1(kkkkkkxkkxLxLxx miiixgxfxL1)()()

14、,(4，对偶问题，对偶问题 原原 对对 问问 偶偶 题：题：问问(1)题题(2)例例 考虑问题考虑问题极小点为极小点为x*=(2,2)T，极小值为，极小值为8，令，令 因此因此最优点最优点*=4，最大值，最大值 (*)=8。0)(,0)()(minxgxhxSxxf 0),(min),(),(max xLx .0,04)(,)(min21212221xxxxxhxxxf 4minmin0,),4(min)()4(),(22201210212122212122212121 xxxxxxxxxxxxxxxxLxx42max.0,4,0,42)(202 对对偶偶问问题题：当当当当l1）对偶定理）对偶

15、定理定理定理1（弱对偶定理）若（弱对偶定理）若x 是原问题（是原问题（1）的可行解，）的可行解，而（而（，）是对偶问题（是对偶问题（2）的可行解，则）的可行解，则进一步有：进一步有：l定理定理2（对偶定理）：（对偶定理）：是是Lagrange函数鞍点的充要条件是：函数鞍点的充要条件是：（i）x*是原问题的解；（是原问题的解；（ii）*0，*是对偶问题是对偶问题的解；的解；（iii）),()(xf),(max)(min,0 xfSxSxx *,0),(),()(*xf2）对偶问题的几何解释）对偶问题的几何解释设原问题为：设原问题为：对偶问题为：对偶问题为：l当约束集当约束集S在映射（在映射（g，

16、f）下的像）下的像G是非凸时，可能出现对是非凸时，可能出现对偶间隙：偶间隙：三，常用非线性约束优化的方法三，常用非线性约束优化的方法1，序列线性规划法（，序列线性规划法（Sequence Linear Programming）0)()(minxgxf )()(minmax)(max0 xgxfSx )()(*xf2,序列无约束极小化方法序列无约束极小化方法例例构造新函数如下：构造新函数如下：为避免间断，令新函数为：为避免间断，令新函数为：F（x）=f（x）+M p（x），其中），其中M为某正数，为某正数，为某一连续可微函数。为某一连续可微函数。上例取上例取 0122)(min2xxSxxxf

17、SxMSxxfxF,),()(SxSxxp,0,0)(22)12(,0min012,0012,)12()(xxxxxp以下就不同的函数构造方法分别介绍以下就不同的函数构造方法分别介绍1）外罚函数法（外点法）外罚函数法（外点法）上例中：上例中：注注（1）对等式约束问题可取对等式约束问题可取（2）对不等式约束问题可取）对不等式约束问题可取)()(),(xpMxfMxFkk 2212,0min2),(xMxMxFkk1,)()(1 lrrxhxp1,0)(,)(0)(,02)()()(,0min)(111 mjjjjmjmjjjjxgxgxgxgxgxgxp(3)对一般问题取：对一般问题取：l定理定

18、理 设设 的最优解存的最优解存在，在，Mk为满足为满足Mk+1 Mk(k=1,2,)的正数序列，的正数序列，且且Mk，如果如果F(x,Mk)的极小点序列的极小点序列x(k)存在且存在且收敛到收敛到x#，则，则x#为原问题的最优解。为原问题的最优解。l注注 由于由于 ，故常以此作为收敛，故常以此作为收敛判别准则。判别准则。mjlrrjxhxgxp11)()(,0min)()()(),(xpMxfMxFkk 0)(lim)(kkkxpM2）内罚函数法（内点法）内罚函数法（内点法）罚函数（响应函数）：罚函数（响应函数）：对不等式约束问题，取对不等式约束问题，取惩罚因子为惩罚因子为3）混合罚函数法）混

19、合罚函数法 对一般约束问题记：对一般约束问题记：)()(),(xxfxFkk mjjmjjxgxorxgx11)(ln()(,)(1)(1,1 kk mjxgjImjxgjIjj,1,0)(;,1,0)(21 取罚函数为取罚函数为4）精确罚函数法）精确罚函数法 罚函数取为：罚函数取为：例例精确罚函数为：精确罚函数为：mjjxgxfxF1)(,0min1)(),(22)()(,0min)(ln)(),(122IjlrrjkIjjkkkxhxgMxgxfmxF 012.)0(,)(minxtsaaxxf 012,1)2(012,12,0min1),(xifxaxifaxxaxxF 5）乘子法）乘子

20、法（1）等式约束问题）等式约束问题Lagrange函数为函数为罚函数为：罚函数为：其中的迭代公式为其中的迭代公式为（2）不等式约束问题）不等式约束问题引入松弛变量得增广引入松弛变量得增广Lagrange函数：函数：lkkkkxhxfxL1)()(),(lkkkkxhcxLcxF12)(2),(),(,1,0;,1),()()()1(klrxchkrkrkr mjjjmjjjjzxgczxgxfczxF12212)(2)()(),(经过推导得关于经过推导得关于z的极小：的极小：3）具等式和不等式的问题）具等式和不等式的问题增广增广Lagrange函数为：函数为：jjjxcgcz )(,0max1

21、2 mjjjjxcgczzxcgcxfFcxFjjj122)(,0max1)(,0max21)(min),(2 liiliiimjjjjxhcxhxcgcxfcxF121122)(2)()(,0max21)(),(其中的迭代公式为其中的迭代公式为例例解解 增广增广Lagrange函数为：函数为：lixchmjxcgkikjkikjkjkj,1),(,1),(,0max11 ,1.)(min12221xtsxxxf 1,211),1()1(2),(12222111212221cxcxxcxxxcxxxF 34)1(,0max,0.4,0,642)1()(1)1()()(2)0()()()(1kk

22、kkkkkkxcxcccx 3，可行方向法，可行方向法定理定理 如果方向如果方向p 满足满足 则称则称p是是 x（k）处的可行下降方向。处的可行下降方向。1）Zoutendijk可行方向法可行方向法(1)线性约束线性约束需求解如下需求解如下线性规划问题线性规划问题例例 0)()(,0)()()()(kTkkjTxfpxIjxgp ljmidxcbxaxfjTjiTi,1;,1;,)(min nipljxIipcpaxfpikkkTjkTikTk,1,1,1),(,0,0)(min)()()(2,0,3)3)(4()(min2121212xxxxxxxf 3)(,)1,2(,)1,1(1,10,

23、048min3,1)(,)2,1(,)0,1(1,1;95.918.6,018.695.9)(min3)(,)2,512.0(,1965)84.7,32.12()(;)8.1,2.0(*)3(*)3()2()2()2()1()2()2()2()2()2()1()2()2()2()1()2()2()2()1()2()1()1()1()2()1()1()1()2()1()2()1()1()1()1()1()1()1(0)0()0()0(xfxxxppppppppxIxppppppppxfpxIxxfpxTTTTTTTT 2)非线性约束非线性约束(具不等式约束问题具不等式约束问题)l点点 处的可行方

24、向处的可行方向P应满足应满足l但在此严格不等式约束下，可能得不到最优解，为此将严但在此严格不等式约束下，可能得不到最优解，为此将严格不等式改为格不等式改为l为了避免为了避免 的选取过大或过小，引进新变量的选取过大或过小，引进新变量 ，于是找方向，于是找方向的线性规划问题为的线性规划问题为:l为避免拉锯现象，引入为避免拉锯现象，引入 起起约束可行方向法约束可行方向法，起作用约，起作用约束集改为：束集改为：0)(PxgiTSx iiTPxg )(nipxIjxgpxfpikkjTkT,1,1)(,)(,)(min)()()(0,2,1,)(0),()()(kkkjkkmjxgixI l全约束可行方

25、向法：全约束可行方向法：l求解如下线性规划问题：求解如下线性规划问题：设最优解为（设最优解为（P（k），k），若），若 k=0，则，则x（k）为最优解，为最优解，迭代终止。若迭代终止。若 k 0,则得到可行下降方向则得到可行下降方向P（k）。例例 nipmixgxgpxfpikikiTkT,1,1,2,1),()(,)(min)()()(0)(,0)(024)(05)(,024)()3)(4()(min251422221322212222211212xxgxxgxxxxgxxxgxxxxgxxxfl取初始点取初始点 x(0)=(1/2，1)T。得到。得到l找方向的线性规划问题为：找方向的线性规

26、划问题为：l其最优解为其最优解为 ,可行下降方向为可行下降方向为 .)1,0()(,)0,1()(,)0,1()(,)2.1()(,)2,1()(,)25.6,15()()0(5)0(4)0(3)0(2)0(1)0(TTTTTTxgxgxgxgxgxf .2,1,1;1;21;415;4152;4152;25.615min211212121ippppppppppi 023,85,1021 ppTP)85,1()0(1）相关投影概念）相关投影概念（1）正交互补空间）正交互补空间（2）正交投影算子）正交投影算子定理：设子空间定理：设子空间 U 的基矩阵为的基矩阵为 N，则，则(i)从从R到子空间到

27、子空间U 的投影算子的投影算子 f 可表为矩阵可表为矩阵(ii)从从R 到子空间到子空间 V=UT 的正交投影算子的正交投影算子 q 可表为矩阵可表为矩阵（3）正交投影算子的性质）正交投影算子的性质2）线性约束问题）线性约束问题 eCxbAxxf,)(minnTRxUuxFxfNNNNF ,)()(1nTTRxUVvxQxqNNNNEQ ,)()(1 设设 x 处起作用约束超平面的法矩阵为处起作用约束超平面的法矩阵为 N（其秩为（其秩为 r）；）；Q 为为从从R n 到起作用约束超平面交集上的投影算子，则到起作用约束超平面交集上的投影算子，则(i)如果如果 则则 是可行下降方向。是可行下降方向

28、。(ii)如果如果当当 0，则，则 x 为为K-T点。点。(3)步长的选择步长的选择 先确定出不违反约束的最大步长，再求最优步长。先确定出不违反约束的最大步长，再求最优步长。4)非线性约束的处理非线性约束的处理 首先将约束线性化，即用迭代点处起作用约束曲面的切平面首先将约束线性化，即用迭代点处起作用约束曲面的切平面近似曲面，再用该点处负梯度方向作为近似搜索方向近似曲面，再用该点处负梯度方向作为近似搜索方向;最后将最后将nTRxNNNNEQ ,)(1)(0)(xfQpxfQ )()(0)(1xfNNNqxfQTT所求得的点投影到约束曲面上所求得的点投影到约束曲面上.(i)约束线性化后约束线性化后

29、,原问题的近似问题为原问题的近似问题为(ii)拉回措施拉回措施 设起作用约束的法矩阵为设起作用约束的法矩阵为N，取方向，取方向 q=N，其，其中中 应满足应满足:线性化得线性化得:拉回方向拉回方向:lrxxhxxhxIjxxgxxgRxxfkTkrTkrkkTkjTkjn,1,)()()(,)()(),(min)()()()()()()(11)()()()()()()()()()(0,1,0)()()(,0)()(,1,0)()(,0)(NNNqNNNNlrNyhyhxIjNygyglrNyhxIjNygTTTTkrkrkTkjkjkrkkj5,直接法直接法网格法网格法 事实上是一种穷举法，在

30、约束区域上打网格，事实上是一种穷举法，在约束区域上打网格，在全部网格点上计算目标函数值，（在满足约束的在全部网格点上计算目标函数值，（在满足约束的点上）通过比较目标函数值，选出最优点。点上）通过比较目标函数值，选出最优点。随机实验法随机实验法(Monte Carlo)在约束区域上随机选在约束区域上随机选出一些（实验）点，希望这些点在区域内的分布是出一些（实验）点，希望这些点在区域内的分布是均匀的，被选到的机会相同，由此认识目标函数的均匀的，被选到的机会相同，由此认识目标函数的大致状况。大致状况。v迭代方法：迭代方法：产生产生0，1上均匀分布的上均匀分布的n个随机数个随机数 x1，x2，xn，令，令 yi=ai+（bi-ai）xi，i=1，2，n检验该点处约束条件是否成立，如成立，再检验该点处约束条件是否成立，如成立，再观察函数值是否下降，否则重新产生随机数。观察函数值是否下降，否则重新产生随机数。以迭代次数或限定相邻两个目标函数值的变以迭代次数或限定相邻两个目标函数值的变化幅度作为迭代的终止准则。化幅度作为迭代的终止准则。该法适用于维数较低，约束区域较为简单的该法适用于维数较低，约束区域较为简单的问题，否则得到的解近似程度较高。问题，否则得到的解近似程度较高。