最优化理论与算法(第八章)

第八章约束优化最优性条件§8.1约束优化问题一、问题基本形式min()fx1()01,,..()0,,ieiecximstcximm（8.1）特别地，当()fx为二次函数，而约束是线性约束时，称为二次规划。记1()0(1,,);()0,,ieieXxcximcximm，称之为可行域（约束域）。1,,eEm，1,,eImm，()()0iIxicxiI称()EIx是在xX处的积极约束的指标集。积极约束也称有效约束，起作用约束或紧约束（activeconstraintsorbindingconstraints）。应该指出的是，如果x是（1）的局部最优解，且有某个0iI，使得0()0icx则将此约束去掉，x仍是余下问题的局部最优解。事实上，若x不是去掉此约束后所得问题的局部极小点，则意味着0，存在x，使得xx，且()()fxfx，这里x满足新问题的全部约束。注意到当充分小时，由0()icx的连续性，必有0()0icx，由此知x是原问题的可行解，但()()fxfx，这与x是局部极小点矛盾。因此如果有某种方式，可以知道在最优解x处的积极约束指标集()()AxEIx，则问题可转化为等式的约束问题：min()fx..()0istcx()iAx（8.2）一般地，这个问题较原问题（8.1）要简单，但遗憾的是，我们无法预先知道()Ax。§8.2一阶最优性条件一、几种可行方向定义8.1设xX，ndR是一非零向量。如果存在0，使得xtdX，[0,]t则称d是x处的一个可行方向。X在x处的的所有可行方向的集合记为(,)FDxX定义8.2设xX，若ndR满足：()0TidcxiE（8.3）()0Tidcx()iIx（8.4）则称d是x处的线性化可行方向。X在x处的的所有线性化可行方向的集合记为(,)LFDxX。定义8.3设xX，ndR，若存在序列kd和0k，使得对一切k，有kkxdX，且kdd，0k，则称d是x处的序列可行方向。X在x处的的所有序列可行方向的集合记为(,)SFDxX。引理8.4设xX，且所有约束函数都在x处均可微，则有：(,)(,)(,)FDxXSFDxXLFDxX（8.5）证明：对任何*(,)dFDxX，由定义8.1可知，存在0使得xtdX，[0,]t令kdd，和(1,2,,)2kkk则显然有kkxdX，且kdd，0k因而*(,)dSFDxX，由d的任意性，即知**(,)(,)FDxXSFDxX。又对任何*(,)dSFDxX，如果0d，则显然*(,)dLFDxX。假定0d，由定义8.3，存在序列(1,2,,)kdk和0(1,2,,)kk，使得kkxdX，且0kdd和0k。由kkxdX有，0()()(),TikkkkikkcxddcxodiE0()()(),()TikkkkikkcxddcxodiIx在上两式的左右两端除以k，然后令k趋于无穷，即得d满足()0TidcxiE()0Tidcx()iIx因而*(,)dLFDxX，由d的任意性，即知**(,)(,)SFDxXLFDxX，证毕。二、一阶最优性条件引理8.5设xX是问题（8.1）的局部极小点，若()fx和()icx(1,,)im都在x处可微，则必有*()0Tdfx，(,)dSFDxX。证明：对任何*(,)dSFDxX，存在序列(1,2,,)kdk和0(1,2,,)kk，使得kkxdX，且kdd和0k。由kkxdx，而且x是局部极小点，故对充分大的k有：()()()()()Tkkkkkkfxfxdfxdfxod由上式可知，*()0Tdfx，引理于是证毕。引理8.5表明：在极小点处，所有的序列可行方向都不是下降方向。引理8.6（Farkas引理）线性方程组和不等式组001,,(8.6)01,,'(8.7)0(8.8)TiTiTdaildbilda无解的充要条件是存在实数(1,,)iil和非负实数(1,,')iil使得：'011lliiiiiiaab（8.9）证明：假定（8.9）式成立，且0i，那么对任意满足（8.6），（8.7）的d，都有'0110llTTTiiiiiidadadb因而不等式组无解。另一方面，若不存在实数i，非负实数i，使（8.9）式成立。考虑集合：'11,,0lliiiiiiiiSaaabR易证S是nR中的一个闭凸锥，且0aS。由凸集分离定理：必存在ndR，使得0TTdadaaS（a是一常数）由于0S，所以00Tda。又由于S是锥，故0，有ibS，从而Tidb因而必有0Tidb(1,,')il再由,iiaaS(1,,)il有,,0iiaaS类似可得0Tida，()0Tida(1,,)il亦即0Tida(1,,)il由以上讨论可见，d是不等式组（8.6）——（8.8）的一个解。注：这里介绍的Farkas引理，以及其他教科书上给出的择一定理、Motzkin定理与Gordan定理，均是由凸集分离定理得出的同一类定理，它们在导出约束最优性条件方面起着至关重要的作用。定理8.7（Karush-Kuhn-Tucker定理）设x是（8.1）的局部极小点，若(,)(,)SFDxXLFDxX，则必存在i(1,,)im，使得：1()()0()0miiiiiifxcxcxiI（8.10）证明：由引理8.5，(,)dSFDxX，有()0Tdfx，因而(,)dLFDxX，有()0Tdfx。由LFD的定义，知()0()0()()0TiTiTidcxiEdcxiIxdcx无解。由Farkas引理，知存在iR()iE和0i(())iIx，使得()()()()iiiiiEiIxfxcxcx再令0i(())iIIx，即得1()()miiifxcx，且满足0,()0()iiicxiI。注：1)称1(,)()()()()mTiiiLxfxcxfxcx为Lagrange函数，i称为Lagrange乘子；2）（8.10）通常称为问题（8.1）的K-T-T条件（或K-T条件），而满足（8.10）的点xX称为K-T-T点（或K-T点），（8.10）中的第二式称为互补松弛条件；3）当约束规范性条件(,)(,)SFDxXLFDxX不成立时，局部极小点不一定是K-T点。三、(,)(,)SFDxXLFDxX的一些充分条件定理8.8若所有的()icx(())iEIx都是线性函数，则(,)(,)SFDxXLFDxX。证明：(,)dLFDxX，有()0()0()TiTidcxiEdcxiIx取kdd，12kk，那么当iE时，有()()()0Tikkikicxdcxdcx当()iIx时，有()()()0Tikkikicxdcxdcx而当()iIIx时，由()0icx知：当k充分大时（0k），有()0ikkcxd。即有kkxdX这表明(,)dSFDxX即(,)(,)LFDxXSFDxX再由(,)(,)SFDxXLFDxX，即得(,)(,)SFDxXLFDxX，证毕。定理8.8若1)()()icxiE线性无关；2）集合()0,;()0,()TTiiSddcxiEdcxiIx非空。则(,)(,)SFDxXLFDxX。证明：先证(,)SSFDxX设d是S中任一向量，令(1,,1)iedinm是子空间1span{(),,(),}emcxcxd的正交补中的标准正交基。（由dS，故d与正交1()()cxiE，因而上述生成子空间的维数为1em）。考虑下面以为参数的非线性方程组()01,,()01,,1()0ieTieTcximdxxinmdxx（8.11）它将确定以为参数的一个隐函数()xx。由于在xx处，上述方程组的Jacobi矩阵非奇异，且0,xx是方程组的解。根据隐函数定理，对充分小的，必存在解()xx且满足02()dxd。事实上，将方程组确定的隐函数对求导，有()()01,,()01,,1()1TieTieTcxximdxinmdx令0，得()(0)01,,(0)01,,1(0)1TieTieTcxximdxinmdx上述方程组得系数矩阵非奇异，故有唯一解，又显然2dd方程组的解，因而有2(0)dxd。下证当(0)充分小时，()xX。事实上，由()x是由方程组（8.11）确定的隐函数，由方程组（8.11）的第一式知，(())0(1,,)iecxim当()iIx时，由S的定义，有()0Tidcx故当(0)充分小时，有(())(())()(())((0))()()0Tiiiiiicxcxcxcxcxcx最后一个不等式是由于0时，2()()()(0)()0TTTiiidcxcxxcxd当()iIIx时，由()0icx。故当充分小（0）时，有(())0icx。因此有()xX。现取()kkkxxd则有2()(0)(0)kkkxxddxd（0k，0k）由上面分析，()kkkxdxX这表明2(,)dSFDxXd，或(,)dSFDxX由d是S中任意向量，故(,)SSFDxX。再由(,)SFDxX是闭集（可直接验证），故有()(,)ClSSFDxX注意到()()0,;()0,()(,)TTiiClSddcxiEdcxiIxLFDxX从而得：(,)(,)SFDxXLFDxX，定理证毕。定理8.9若在x处()icx(())iEIx线性无关，则(,)(,)SFDxXLFDxX。证明：1）若()Ix是空集，则易知上一定理的条件满足，从而结论成立。2）若()Ix非空，那么对任何()jIx，由于()icx(())iEIx线性无关，必存在jd，使得：()0Tjidcx（()iEIx，ij），()1Tjjdcx。事实上，若记()1,2,,EIxk，则1(),,()kcxcx线性无关。记11,,kdd是11span(),,()kcxcx的一组标准正交基。取11111()((),)((),)kkkkkdcxcxddcxdd则d与11,,kdd正交，即与11span(),,()kcxcx正交。因此有：(,())0idcx(1,,1)ik而2(,())(,)kdcxddd因而取2kddd即满足要求，对每个()jIx，均可仿此构造出jd。令()jjIxdd，易证：dS，即S非空，由上一定理有：(,)(,)SFDxXLFDxX