约束最优化的理论与方法

第七章约束最优化的理论与方法一般形式的约束最优化问题min()fx..()0,istcxiE()0,icxiI{|()0,;()0,}iiXxcxiEcxiI可行域min()nxRfx一般形式的无约束最优化问题*xX*()(),fxfxxX全局极小点设则称x*为问题的全局极小点；如果成立，**()(),,fxfxxXxx则称x*为严格全局极小点.进一步，如果成立，(总体极小点)*,xX设**2(,){|||||}.Nxxxx**()(),(,)fxfxxNxX局部极小点：如果对于某一成立，则称x*是问题的局部极小点，0有其中则称x*为严格局部极小点.进一步，如果成立，***()(),(,),fxfxxNxXxx全局极小点是局部极小点√有效约束、无效约束与内点、边界点有效(起作用)约束：对于可行点，，x在点xxxx0)(xci0)(xci()0icx若0)(xci()0ixcx称是约束如果0)(xci就称不等式约束在点是有效约束。并称可行点位于约束的边界。无效约束：对于可行点就称不等式约束是无效约束的内点.E:等式约束指标集I:不等式约束指标集(){|()0,}iIxicxiI()()AxEIxnxRx点处的有效约束集(有效集)(),()icxiAx是在x点处的有效约束(),()icxiAx是在x点处的非有效约束假设已知有效约束A(x)min()fx..()0,istcxiE()0,icxiImin()fx..()0,(*)istcxiAx定理（一阶必要条件）1:DnfDRR设在开集上连续可微，若min()()0.nxRxDfxgx是的局部极小点，则定理（凸最优性定理）11:.nfDRRfC设是凸函数，且则()0.xgx是总体极小点min()nxRfx定理（二阶必要条件）1:DnfDRR设在开集上二阶连续可微，若min()()0,()0((*)).nxRxDfxgxGxGx是的局部极小点，则正半定定理（二阶充分条件）1:DnfDRR设在开集上二阶连续可微，()0().xDfgxGx则是的一个严格局部极小点的充分条件是和是正定矩阵2()fxC*()0fx2*()fx*xmin()fx设函数，若，并且半正定，则是的局部最优解。*xmin()fx*x设是的局部最优解，则在处的下降方向一定不是可行方向。×√定义设f(x)为定义在空间nR上的连续函数，点_nxR，若对于方向nsR存在数0使成立__()(),(0,),fxsfx则称s为f(x)在_x处的一个下降方向.在点_x处的所有下降方向的全体记为_().Dx定理设函数f(x)在点_x处连续可微，如存在非零向量nsR使成立_()0Tfxs则s是f(x)在点_x处的一个下降方向.给出了在f(x)连续可微是下降方向同函数f(x)的梯度之间的关系.()fx(){|()0}TDxddfx下降方向集序列可行方向*,0,{}{}(1,2,)..nkkxXdRdkst设如果序列和*.dXx则称是在处的序列可行方向*(*):SFDxXXx，在处的所有序列可行方向组成的集合*,kkxdXkk,00kkdd具有和，可行方向*,0,0,..nxXdRst设如果*,[0,]xtdXt*.dXx则称是在处的可行方向*(*,):FDxXXx在处的所有可行方向组成的集合线性化可行方向*,0,nxXdR设如果*()0,;TidcxiE*.dXx则称是在处的线性化可行方向(*,):LFDxX*()0,Tidcx*Xx在处的所有线性化可行方向组成的集合12(,)Tddd11223()iiiicxaxaxa1122()(,)iTiiadcxdda*();iIx1112223(*)()()iiiicxdaxdaxda(*)()Tiicxdcx如果所有的约束函数都在*xX处可微，则有(*,)(*,)(*,)FDxXSFDxXLFDxX*,[0,]xtdXt*,kkxdXkk,00kkdd和*()0,;TidcxiE*()0,Tidcx*();iIx序列可行方向可行方向线性化可行方向(*,)(*,)FDxXSFDxX(*,)(*,)dFDxXdSFDxX,2kkkdd(*,)(*,)SFDxXLFDxX(*,)(*,)dSFDxXdLFDxX*,kkxdXkk,00kkdd和*()0,;TidcxiE*()0,Tidcx*();iIx序列可行方向线性化可行方向0d√0d*kkxdX(*)(*)(*)Tikkikkicxdcxdcx引理min()fx..()0,istcxiE()0,icxiI*xX设是下列问题的局部极小点()()*ifxcxx如果和都在处可微，{}kx则所有可行序列d的序列可行方向满足**()0,(,)TdfxdSFDxX**(,)()SFDxXDx在局部极小点处没有可行下降方向证明:反证法.假设存在可行序列{}kx的序列可行方向d**..()0,(,),TstdfxdSFDxX并且序列*lim.kkxx****()()()()(||||)Tkkkfxfxxxfxoxx*||*||kkkxxddxx****()||||()(||||)Tkkfxxxdfxoxxk0*()()kfxfxk矛盾引理min()fx..()0,istcxiE()0,icxiI*xX设是下列问题的局部极小点()()*ifxcxx如果和都在处可微，则必有**()0,(,)TdfxdFDxX**(,)()FDxXDx在局部极小点处没有可行下降方向Farkas引理设nmRA为nm矩阵，,nRb则下述两组方程中有且仅有一组有解：0,0,(1)TAxbx,0,(2)TAyby其中.,mnRyRxFarkas引理在最优化理论研究中起重要作用Farkas引理的另一种形式设l.l’是两个非负整数，a0,ai(i=1,…,l)和bi(i=1,…,l’)是Rn中的向量，则线性方程组和不等式组0,1,,,Tidail0,1,,',Tidbil00Tda无解当且仅当存在实数(1,,)(1,,')iiilil和非负实数使得'011.lliiiiiiaabKKT定理*xX设是下列问题的局部极小点()()*ifxcxx如果和都在的邻域内一阶连续可微.()CQ如果约束规范条件min()fx..()0,istcxiE()0,icxiI(*,)(*,)SFDxXLFDxX*..ist则存在成立**1(*)()miiifxcx*()0,icxiE*()0,icxiI*0,iiI**()0,iicxiI驻点条件可行性条件乘子非负条件互补松弛条件KKT条件{1,,}l{1,,}lm13122min..00xstxxx2x1x*(0,0)Tx*10()1cx*20()1cx**1(*)()miiifxcx*()0,icxiE*()0,icxiI*0,iiI**()0,iicxiI*1()0fx(*,){|}0LFDxXdd(*,){|,0}0SFDxXdd最优点不一定是KKT点2221232221123212314253min()32..()30()0()0()0()0fxxxxstcxxxxcxxxcxxcxxcxx*(1,1,1,)KKTTx验证最优点是否为点.*{1,2}I(*)(6,2,4)Tfx1(*)(2,2,2)Tcx2(*)(1,1,0)Tcx126210221042001222证明**1(*)()miiifxcx*0,iiI**()0,iicxiI*(,)dSFDxX设*x是局部极小点**()0,(,)TdfxdSFDxX(*,)(*,)SFDxXLFDxX*(,)dLFDxX*()0,;TidcxiE**()0,();TidcxiIx*()0Tdfx*()dDx*(,)LFDxX方程组无解***(),0(())..iiRiEiIxst*****()(*)()()iiiiiEiIxfxcxcx*****()(*)()()iiiiiEiIxfxcxcx*****()(*)()()iiiiiEiIxfxcxcx**0,\()iiIIx令***\()()iiiIIxcx**1()miiicx{1,,}El{1,,}Ilm***1()()miiifxcx*0,iiI*()(*)0iiIxcx**\()0iiIIx**()0,.iicxiI线性函数约束规范条件(LFCQ):**()(())icxiEIx所有的约束函数都是线性函数.线性无关约束规范条件(LICQ):**()(())icxiEIx约束函数的梯度线性无关.可以证明(1)如果LFCQ成立，则CQ成立(2)如果LICQ成立，则CQ成立定理:*xX设是约束优化问题的局部极小点，LGCQLICQ如果成立或者成立，KKT.则条件成立一阶最优性充分条件定理*,xX设*()()ifxcxx如果和都在处可微，并且有**()0,0(,)TdfxdSFDxX成立，*.x则是问题的一个严格局部极小点证明:*.x假设不是严格局部极小点..kxXst则*()()kfxfx**,,1,2,kkxxxxk且有不失一般性，我们可假定**2||||kkkxxddxx*2||||kkxx*(,)dSFDxX**2()()()()Tkkkkfxfxdfxo*()fx0*()0Tkdfx*()0Tdfxk矛盾***2(){|()0,(*),0}TiiFdLFDcxdiIx线性化零约束方向集2**2**2*1(,)()()mxxiiiLxfxcx定理(二阶必要性条件)*x设是约束优化问题的局部极小点，*Lagrange是相应的乘子.LICQ如果成立，则2***2(,)0,().TxxdLxddF定理(二阶充分性条件)*KKTx设是一个点，*是相应的如果2***2(,)0,(),0,TxxdLxddFdLagrange乘子.*.x则是问题的严格局部极小点§7.2二次罚函数方法设法将约束问题求解转化为无约束问题求解．具体说：根据约束的特点，构造某种惩罚函数，然后把它加到目标函数中去，将约束问题的求解化为一系列无约束问题的求解．二次罚函数法引例：求解等式约束问题:222121,minxxxxf02.21xxts解:图解法求出最优解.1,1*Tx构造：22,2121222121xxxxxxxxF但是21,xxF性态极坏，无法用有效的无约束优化算法求解．设想构造：2221212;2Qxxxxx其中求解此无约束问题得：12221xx当时，有：