管理科学理论-2VIP免费

第四章约束非线性优化的理论与方法第四章约束非线性优化的理论与方法一，等式约束问题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)(),(0010011010100xgxgxxgxxgxxgxxgmihxxghxgmnmnmjjjii满秩，则称x0为曲面S上的一个正规点。注1是x0处法空间的一组基。注2方程组的一组线性无关的解构成曲面S上x0处切空间的一组基。2，具等式约束问题的极值必要条件考虑二维问题：minf(x,y)S.t.g(x,y)=0结论1:若在极小点(x0,y0)处,g(x0,y0)0，则f(x0,y0)与g(x0,y0)线性相关，即f(x0,y0)+g(x0,y0)=0。结论2：(Lagrange乘子规则)设(x0,y0)是局部极小点，且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，下降方向和可行方向考虑一般非线性约束优化问题：例：求解mihxghhxFhhxFiT,,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PxfT}0)({00PxfPFTpjPxhmiPxgji,,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*是问题的最优解，则x*处)}(,0)({000xIiPxgPGiT,0,,0{0SPxPPDniRxmixgxf,,1,0)()(min00FG换言之，在x*处满足的方向P必有称为Fritz－John条件。其中线性无关。在最优点x*处应满足Farkas引理：给定向量ai（i=1,2,…,k）与b，不存在向量P同时满足条件和的充要条件是向量b在ai所张成的凸锥内，即满足0)(PxfT)(,0)(xIiPxgiTxIiiixgxf)()()(,),(1xgxgmmixgxgxfiiiiii,,1,0)(0),()(kiPaTi,,2,1,00PbT0,1ikiiiab定理1:设x*为问题的一个可行点,并且前t个约束为起作用约束,则x*为最优解的一个必要条件是下式成立:例:考虑问题定理1:设x*为问题的一个可行点,并且前t个约束为起作用约束,则x*为最优解的一个必要条件是下式成立:例:考虑问题mibxaRxxfiniiijn,,1,),(min10,*)(1itiiiaxf0)(,0)(,01)(,)(min231223111xxgxxgxxxgxxf）（成立。使显然找不到，是最优点，起作用约束），（*)(*)(*)(,0,,)1,0(*)(,)1,0(*)()0,1(*)(}3,1{*)(01*35113131xgxgxfxgxgxfxIxTTTT从上例看出，满足定理1还需增加一些约束规范，如梯度向量线性无关等，上例有更一般的有：定理2（Kuhn－Tucker）最优性必要条件：在最优点x*处，设线性无关，则存在满足：称上式为K－T条件，满足上式的点称K－T点。相应的广义Lagrange函数为：pjxhxIixgji,,1),();(),(TpTm,,;,11*)(*)(31xgxgmixgxhxgxfiiimipjjjii,,1,0,0)(0)()()(11...