约束最优化的理论与方法

1、第七章第七章约束最优化的理论约束最优化的理论与方法与方法一般形式的约束最优化问题一般形式的约束最优化问题min( )f x. .( )0,ist c xiE( )0,ic xiI |( )0,;( )0,iiXx c xiE c xiI可行域可行域min( )nx Rf x一般形式的无约束最优化问一般形式的无约束最优化问题题*xX*()( ),f xf xxX 全局极小点全局极小点设设则称则称x*为问题的为问题的全局极小点全局极小点；如果如果成立，成立，*()( ),f xf xxX xx 则称则称x*为为严格全局极小点严格全局极小点.进一步，如果进一步，如果成立，成立，(总体极小点总体极小点

2、)*,xX设*2( , ) |.N xxx x*()( ),(,)f xf xxN xX 局部极小点：局部极小点：如果对于某一如果对于某一成立，成立， 则称则称 x*是问题的是问题的局部极小点局部极小点，0 有其中其中则称则称x*为为严格局部极小点严格局部极小点.进一步，如果进一步，如果成立，成立，*()( ),(,),f xf xxN xX xx 全局极小点是局部极小点全局极小点是局部极小点有效约束、无效约束与内点、边界点有效约束、无效约束与内点、边界点有效有效(起作用起作用)约束：约束：对于可行点对于可行点 ， ，x在点xxxx0)(xci0)(xci( )0ic x 若0)(xci( )

3、0ixc x 称 是约束如果如果0)(xci就称不等式约束就称不等式约束在点在点是有效约束。是有效约束。并称可行点并称可行点位于约束位于约束的边界。的边界。无效约束：无效约束：对于可行点对于可行点就称不等式约束就称不等式约束是无效约束是无效约束的内点的内点. .E E: :等式约束指标集等式约束指标集I I: :不等式约束指标集不等式约束指标集( ) |( )0,iI xi c xiI( )( )A xEI xnxR x点处的有效约束集点处的有效约束集( (有效集有效集) )( ),( )ic x iA x是在是在x点处的有效约束点处的有效约束( ),( )ic x iA x是在是在x点处的非

4、有效约束点处的非有效约束假设已知有效约束假设已知有效约束A(x)min( )f x. .( )0,ist c xiE( )0,ic xiImin( )f x. .( )0,( *)ist c xiA x定理定理（一阶必要条件）（一阶必要条件）1:DnfDRR设在开集 上连续可微，若min( )()0.nx RxDf xg x是的局部极小点，则定理定理（凸最优性定理）（凸最优性定理）11:.nfDRRfC设是凸函数，且则()0.xg x是总体极小点min ( )nx Rf x定理定理（二阶必要条件）（二阶必要条件）1:DnfDRR设在开集 上二阶连续可微，若min( )()0,()0( ( *)

5、.nx RxDf xg xG xG x是的局部极小点，则正半定定理定理（二阶充分条件）（二阶充分条件）1:DnfDRR设在开集 上二阶连续可微，()0().xDfg xG x则是 的一个严格局部极小点的充分条件是和是正定矩阵2( )f xC*()0f x2*()f x*xmin( )f x设函数设函数，若若，并且并且半正定，则半正定，则是是的局部最优解的局部最优解。 *xmin( )f x*x设设是是的局部最优解，则在的局部最优解，则在处的下降方向一定不是可行方向。处的下降方向一定不是可行方向。 定义定义设f(x)为定义在空间nR上的连续函数，点_nxR，若对于方向nsR存在数0使成立_()(

6、 ),(0, ),f xsf x则称s为f(x)在_x处的一个下降方向下降方向.在点_x处的所有下降方向的全体记为_( ).D x定理定理设函数f(x)在点_x处连续可微，如存在非零向量nsR使成立_( )0Tf xs则s是f(x)在点_x处的一个下降方向.给出了在给出了在f(x)连续可微是下降方向同函数连续可微是下降方向同函数f(x)的梯度的梯度 之间的关系之间的关系. .( )f x( ) |( )0TD xd df x下降方向集下降方向集序列可行方向序列可行方向*,0,(1,2,). .nkkxXdRdkst设如果 序列和*.dXx则称 是 在 处的序列可行方向*( *):SFD xXX

7、x，在 处的所有序列可行方向组成的集合*,kkxdXkk,00kkdd具有和，可行方向可行方向*,0,0, . .nxXdRst设如果*,0, xtdXt *.dXx则称 是 在 处的可行方向*( *, ):FD x XXx在 处的所有可行方向组成的集合线性化可行方向线性化可行方向*,0,nxXdR设如果*()0,;Tidc xiE*.dXx则称 是 在 处的线性化可行方向( *, ):LFD x X*()0,Tidc x*Xx在 处的所有线性化可行方向组成的集合12(,)Tdd d1 1223( )iiiic xa xa xa1122( )(,)iTiiadc xd da*();iI x11

8、12223( *)()()iiiic xdaxdaxda( *)( )Tiic xdc x如果所有的约束函数都在如果所有的约束函数都在*xX处可微，处可微，则有则有( *, )( *, )( *, )FDx XSFDx XLFDx X*,0, xtdXt *,kkxdXkk,00kkdd和*()0,;Tidc xiE*()0,Tidc x*();iI x序列可行方向序列可行方向可行方向可行方向线性化可行方向线性化可行方向( *,)( *,)FD xXSFD xX( *,)( *,)dFD xXdSFD xX ,2kkkdd( *,)( *,)SFD xXLFD xX( *,)( *,)dSFD

9、 xXdLFD xX *,kkxdXkk,00kkdd和*()0,;Tidc xiE*()0,Tidc x*();iI x序列可行方向序列可行方向线性化可行方向线性化可行方向0d 0d *kkxdX( *)( *)( *)Tikkikkic xdc xdc x引理引理min( )f x. .( )0,ist c xiE( )0,ic xiI*xX设是下列问题的局部极小点( )( )*if xc xx如果和都在处可微，kx则所有可行序列d的序列可行方向 满足*()0,(,)Tdf xdSFD xX *(,)()SFD xXD x在局部极小点处没有可行下降方向在局部极小点处没有可行下降方向证明证明

10、: :反证法反证法. .假设存在可行序列假设存在可行序列kx的序列可行方向的序列可行方向d*.( )0,( ,),Tst df xdSFD x X 并且序列并且序列*lim.kkxx*()()()()(|)Tkkkf xf xxxf xoxx*|*|kkkxxddxx*() |()(|)Tkkf xxxdf xoxxk 0*()()kf xf xk 矛盾矛盾引理引理min( )f x. .( )0,ist c xiE( )0,ic xiI*xX设是下列问题的局部极小点( )( )*if xc xx如果和都在处可微，则必有*()0,(,)Tdf xdFD xX *(,)()FD xXD x在局部

11、极小点处没有可行下降方向在局部极小点处没有可行下降方向FarkasFarkas引理引理设nmRA为nm 矩阵，,nRb 则下述两组方程中有且仅有一组有解：0 ,0 ,(1)TAxb x,0 ,(2)TA yby其中.,mnRyRxFarkasFarkas引理在最优化理论研究中起重要作用引理在最优化理论研究中起重要作用Farkas引理的另一种形式引理的另一种形式设设l. l是两个非负整数，是两个非负整数，a0,ai (i=1,l)和和bi (i=1,l)是是Rn中的向量，则线性方程组和不等式组中的向量，则线性方程组和不等式组0,1, ,Tid ail 0,1, ,Tid bil00Td a 无解

12、当且仅当存在实数无解当且仅当存在实数(1, )(1, )iiilil和 非 负 实 数使得使得011.lliiiiiiaabKKTKKT定理定理*xX设是下列问题的局部极小点( )( )*if xc xx如果和都在的邻域内一阶连续可微.()CQ如果约束规范条件min( )f x. .( )0,ist c xiE( )0,ic xiI( *,)( *,)SFD xXLFD xX*. .ist则存在成 立*1( *)()miiif xc x*()0,ic xiE*()0,ic xiI*0,iiI*()0,iic xiI驻点条件驻点条件可行性条件可行性条件乘子非负条件乘子非负条件互补松弛条件互补松弛

13、条件KKTKKT条件条件1, l1,lm 13122min. .00 xstxxx2x1x*(0,0)Tx *10()1c x*20()1c x *1( *)()miiif xc x*()0,ic xiE*()0,ic xiI*0,iiI*()0,iic xiI*1()0f x ( *,) |0LFD xXd d( *,) |,00SFD xXd d最优点不一定是最优点不一定是KKTKKT点点2221232221123212314253min( )32. .( )30( )0( )0( )0( )0f xxxxstc xxxxcxxxc xxcxxc xx *(1,1,1,)KKTTx 验证最

14、优点是否为点.*1,2I ( *)( 6, 2, 4)Tf x 1( *)(2,2,2)Tc x2( *)( 1,1,0)Tc x 12621022104200 1222 证明证明*1( *)()miiif xc x*0,iiI*()0,iic xiI*(,)dSFD xX设*x 是局部极小点*()0,(,)Tdf xdSFD xX ( *,)( *,)SFD xXLFD xX*(,)dLFD xX*()0,;Tidc xiE*()0,();Tidc xiI x*()0Tdf x*()dD x*(,)LFD xX方程组无解方程组无解*(),0() . .iiR iEiI xst*()( *)(

15、)()iiiii Ei I xf xc xc x*()( *)()()iiiii Ei I xf xc xc x*()( *)()()iiiii Ei I xf xc xc x*0, ()iiI I x令* ()()iii I I xc x*1()miiic x1, El1,Ilm *1()()miiif xc x*0,iiI *()( *)0iiI xc x* ()0iiI I x*()0,.iic xiI 线性函数约束规范条件线性函数约束规范条件(LFCQ):*()()ic xiEI x所有的约束函数都是线性函数.线性无关约束规范条件线性无关约束规范条件(LICQ):*()()ic xiE

16、I x约束函数的梯度线性无关.可以证明可以证明(1) 如果如果LFCQ成立，则成立，则CQ成立成立(2) 如果如果LICQ成立，则成立，则CQ成立成立定理定理: :*xX设是约束优化问题的局部极小点，LGCQLICQ如果成立或者成立，KKT.则条件成立一阶最一阶最优性充优性充分条件分条件定理定理*,xX设*( )( )if xc xx如果和都在 处可微，并且有*()0,0(,)Tdf xdSFD xX 成立，*.x则 是问题的一个严格局部极小点证明证明: :*.x假设 不是严格局部极小点. .kxX st则*()()kf xf x*,1,2,kkxx xx k且有不失一般性，我们可假定不失一般

17、性，我们可假定*2|kkkxxddxx*2|kkxx*( , )d SFD x X*2()()()()Tkkkkf xf xdf xo*()f x0*()0Tkdf x*()0Tdf xk 矛盾矛盾*2()|()0,( *),0TiiFdLFDc xdiI x 线性化零约束方向集线性化零约束方向集2*2*2*1(,)()()mxxiiiL xf xc x 定理定理( (二阶必要性条件二阶必要性条件) )*x设 是约束优化问题的局部极小点，*Lagrange是相应的乘子.LICQ如果成立，则2*2(,)0,().TxxdL xddF 定理定理( (二阶充分性条件二阶充分性条件) )*KKTx设

18、是一个点，*是相应的如果2*2(,)0,(),0,TxxdL xddFd Lagrange乘子.*.x则 是问题的严格局部极小点 7.2 7.2 二次罚函数方法二次罚函数方法设法将约束问题求解转化为无约束问题求解设法将约束问题求解转化为无约束问题求解具体说：具体说：根据约束的特点，构造某种惩罚函数，根据约束的特点，构造某种惩罚函数，然后把它加到目标函数中去，将约束问题的然后把它加到目标函数中去，将约束问题的求解化为一系列无约束问题的求解求解化为一系列无约束问题的求解二次罚函数法引例：引例： 求解等式约束问题求解等式约束问题: :222121,minxxxxf02.21xxt s解解: :图解法求出最优解图解法求出最优解 .1 , 1*Tx 构造：构造：22,2121222121xxxxxxxxF但是但是21,xxF性态极坏，性态极坏， 无法用有效的无约束无法用有效的无约束优化算法求解优化算法求解设想构造：设想构造：2221212;2Q xxxxx其中其中求解此无约束问题得：求解此无约束问题得： 12221xx当当时时， 有：有： TTTxxxx1 , 1,*2*121是一个非常大的正数是一个非常大的正数等式约束问题等式约束问题 1minnRxxf .0istcxiE二次罚函数二次罚函数 21;( )2ii EQ xfxcx 0ic x 如果0