第四章 约束最优化方法

第六章约束最优化方法第六章约束最优化方法问题minf(x)s.t.g(x)≤0分量形式略h(x)=0约束集S={x|g(x)≤0,h(x)=0}6.1Kuhn-Tucker条件一、等式约束性问题的最优性条件：考虑minf(x)s.t.h(x)=0回顾高等数学中所学的条件极值：问题求z=f(x,y)极值minf(x,y)在ф(x,y)=0的条件下。S.t.ф(x,y)=0引入Lagrange乘子：λLagrange函数L(x,y;λ)=f(x,y)+λф(x,y)(fgh)(fh)即第六章6.1Kuhn-Tucker条件一、等式约束性问题的最优性条件：(续)若(x*,y*)是条件极值，则存在λ*，使fx(x*,y*)+λ*фx(x*,y*)=0fy(x*,y*)+λ*фy(x*,y*)=0Ф(x*,y*)=0推广到多元情况，可得到对于(fh)的情况：minf(x)s.t.hj(x)=0j=1,2,…,l若x*是(fh)的l.opt.,则存在υ*∈Rl使矩阵形式：分量形式：ljjjxhxf1***0)()(0)()(***xxhxf一、等式约束性问题的最优性条件：(续)几何意义是明显的：考虑一个约束的情况：最优性条件即：第六章6.1Kuhn-Tucker条件-▽f(ㄡ)ㄡ▽h(ㄡ)h(x)-▽f(x*)▽h(x*)这里x*---l.opt.▽f(x*)与▽h(x*)共线，而ㄡ非l.opt.▽f(ㄡ)与▽h(ㄡ)不共线。hjjjxhxf1**)(*)(第六章6.1Kuhn-Tucker条件二、不等式约束问题的Khun-Tucker条件：考虑问题minf(x)s.t.gi(x)≤0i=1,2,…,m设x*∈S={x|gi(x)≤0i=1,2,…,m}令I={i|gi(x*)=0i=1,2,…,m}称I为x*点处的起作用集（紧约束集）。如果x*是l.opt.,对每一个约束函数来说，只有当它是起作用约束时，才产生影响，如：(fg)g2(x)=0x*g1(x)=0g1(x*)=0,g1为起作用约束第六章6.1Kuhn-Tucker条件二、不等式约束问题的Khun-Tucker条件：（续）特别有如下特征：如图在x*：▽f(x*)+u*▽g(x*)=0u*0要使函数值下降，必须使g(x)值变大，则在ㄡ点使f(x)下降的方向（-▽f(ㄡ)方向）指向约束集合内部，因此ㄡ不是l.opt.。▽g(ㄡ)-▽f(ㄡ)X*-▽f(x*)▽g(x*)第六章6.1Kuhn-Tucker条件二、不等式约束问题的Khun-Tucker条件：（续）定理（最优性必要条件）：（K-T条件）问题(fg),设S={x|gi(x)≤0},x*∈S,I为x*点处的起作用集，设f,gi(x),i∈I在x*点可微，gi(x),iI在x*点连续。向量组{▽gi(x*),i∈I}线性无关。如果x*----l.opt.那么，u*i≥0,i∈I使点。称条件的点满足互补松弛条件。那么，可微，如果在TKxTKmixgumiuxguxfixgxxguxfiiimiiiiIiii**1*)(,,2,10)(,,2,100)()()(,0)()(第六章6.1Kuhn-Tucker条件二、不等式约束问题的Khun-Tucker条件：（续）0),(0),(042),(05),(..)2()3(),(min22141213212122221211222121xxxgxxxgxxxxgxxxxgtsxxxxf例123412g1=0g2=0g4=0x1g3=0x2x*▽g2(x*)▽g1(x*)-▽f(x*)(3,2)T第六章6.1Kuhn-Tucker条件二、不等式约束问题的Khun-Tucker条件：（续）用K-T条件求解：0)()()()2,2())2(2),3(2()()2,1()()2,4()2,2()(}2,1{120),(0),(232131*32*231*1*2*1*2211212211*xgxgxfuuxxxfxgxxxgIxxgxxgxTTTTTT使计算可得起作用集），交点（点在10,01)(21)2(,22)(,)2(2)3(2)(43221121gxggxxxgxxxf第六章6.1Kuhn-Tucker条件二、不等式约束问题的Khun-Tucker条件：（续）0)(,,2,1,00)()(xgumiuxguxfiiimiii个未知量个方程66)6(0)5(0)4(0)42()3(0)5(0,,,)2(022)2(2)1(02)3(224132122221143214221232111xuxuxxuxxuuuuuuuxuxuuxux第六章6.1Kuhn-Tucker条件二、不等式约束问题的Khun-Tucker条件：（续）可能的K-T点出现在下列情况：①两约束曲线的交点：g1与g2,g1与g3,g1与g4,g2与g3,g2与g4,g3与g4。②目标函数与一条曲线相交的情况：g1，g2,g3,g4对每一个情况求得满足(1)~(6)的点(x1,x2)T及乘子u1,u2,u3,u4,验证当满足可得，且ui≥0时，即为一个K-T点。下面举几个情况：●g1与g2交点：x=(2,1)T∈S,I={1,2}则u3=u4=0解点。是故得TKxuuuxuxuxuxT)1,2(032,31022)2(202)3(22122122111第六章6.1Kuhn-Tucker条件二、不等式约束问题的Khun-Tucker条件：（续）●●点。故不是不满足点；故不是得交点：与TKgSTKSxxxxggTTT,0,)5,0(,)5,0()5,0(00521222131.04,060)20(20)30(20}4,3{)0,0(:,43432143点故非得解故交点TKuuuuuuISxggT第六章6.1Kuhn-Tucker条件二、不等式约束问题的Khun-Tucker条件：（续）●034.04742),(),(0502)2(202)3(20},1{0)()(135132013452121320134522211221114321xxgTKSxxuxxuxxuuuIxgxf点故均不是得解则相切的情况：与目标函数第六章6.1Kuhn-Tucker条件三、一般约束问题的Kuhn-Tucker条件线性无关。，向量组约束规格）。（的某邻域内连续可微。在）（，连续，在可微在设为起作用集。，问题定理：)}(,),(,),)(({,,,2,1))((,))((},0)(,0)(|{)(,,2,10)(,,2,10)(..)(min)(1xhxhIixgCQxljhxIixgxIixgIxhxgxSxfghljxhmixgtsxffghlijiiji第六章6.1Kuhn-Tucker条件三、一般约束问题的Kuhn-Tucker条件(续)点。是则及为凸规划，满足可微性若亦可微，那么在如果还有那么如果TKxoptlxCQfghmixguuxhvxguxfxIixgxhvxguxfljRvIiuoptlxiiiljjjmiiiiljjjIiiiji..)(,,2,10)(00)()()())((0)()()(,,2,1,,,0..111第六章6.2既约梯度法一、解线性约束问题的既约梯度法为既约梯度称相应非基变量基变量，使非奇异，存在分解：、既约梯度及搜索方向）个正分量。（的每个极点都有列线性无关；的任意、非退化假设：的多面体同可行集：秩）、问题：（NBxfxfrxfxfxfxxxxxxxBNBASxbBmSmASLPxbAxxSRbmAAxbAxtsxfPTBTNTNNBNBNBNBmmmnm11)()(,)()()(0,0],,[,30212.)(}0,|{,,0..)(min1第六章6.2既约梯度法一、解线性约束问题的既约梯度法（续）为可行方向。故即有）时，（则取由故又）时，，（当为可行方向，即时当为可行方向寻找下降可行方向：dSdxdxddxbAxdxAAdddxAdbAxbAdAxdxAdproofxdAdddjjjjjjjj.00}0|min{.)(,0,0.0,00,0,,)(0,0:..0,00)1(第六章6.2既约梯度法一、解线性约束问题的既约梯度法（续）0))()(()())(()()()(0)(:)2(0,00][.1111NTNNTBTNNTNNTBNTNBTBTTNBjjNNBNBNBNBdrdNBxfxfdxfNdBxfdxfdxfdxfdxfdNdBddxddNdBdNdBdddNBAdddd分解：要求下降方向及中，对应可行，可取在故要使得到根据考虑分解第六章6.2既约梯度法一、解线性约束问题的既约梯度法（续）点。若的下降可行方向；为若那么方向定理：按上述方案产生的分量。为其中：时当时当的方案向的一种产生下降可行方、结合TKxdPdddNdBdrrrrxrrdddNBNjjjjjjjN~02)(,01,00::)2()1()3(1第六章6.2既约梯度法一、解线性约束问题的既约梯度法（续）证毕。非零，于是或至少一个由于又保证故总有对.0,000,0,0.0000001.221NTNjjjjjjjjjjNjjjNTNNBjjjjjjjjjdrrxrdrrxrrdrdrdrAdNdBddrxdrrdrxproof第六章6.2解线性约束问题的既约梯度法（续）得证。即条件：可得取故时，，当原因：则取矛盾；与那么，反证。若存在可得000)()(0)()(0)(,)();0000,0,0)00)(0:0)02111xuuuNBxfxfuBBxfxfuAvxfTKRBxfviiixrxdrruxuxuruuiidrdNjrridTTNTBTNTBTBTBTTTnTBTjjjjjNNNTNTNNBjjjjN第六章6.2既约梯度法一、解线性约束问题的既约梯度法（续）证毕。也就是即故恒有时当时当，即由第三式得：由第一式得：点即.00,0,000000000,0)()(0)()(0)(000)(~111dNdBdddrxdrdrrxuxxuuxxurNBxfxfuuNvxfBxfvuBvxfxuuuAvxfTKxNBNjjjjjjjjjjjNTNBBBTBTNTBTNTNTNTTNTBTTBTTBTTTT第六章6.2既约梯度法算法：x(1)∈S,k=1k=k+1