工优第六章

第六章约束最优化方法本章主要内容：§1约束优化问题的最优性条件§2惩罚函数法§3可行方向法{|()0,()0},Dxgxhx12()((),(),...,()),Tmgxgxgxgx约束优化问题的一般形式约束优化问题则约束优化问题可表示为min()..()0,1,2,...,(1)()0,1,2,...,ijfxstgximhxjl12()((),(),...,()),Tlhxhxhxhx记min()..()0(1)()0fxstgxhx令是约束优化问题的可行域。约束优化问题的一般形式约束优化问题()0()0()0jjjhxhxhx因为一般形式的等价形式min()..()0(*)fxstgxmin()..()0,1,2,...,(1)()0,1,2,...,ijfxstgximhxjl约束优化问题的一般形式min()..()0(1)()0fxstgxhx在约束优化问题中，自变量的取值受到限制，目标函数在无约束情况下的驻点很可能不在可行域内，一般不能用无约束优化的方法处理约束优化问题。设，若为的局部极小点，且在内连续可微，则:nfRR(*)0.fx()fxx(*)Nx回顾：无约束优化的一阶必要条件一般约束优化的一阶最优性条件,xD()0igx()0igx()，Ix(){|()0,1,2,,}.iIxigxim设可行解，则称是在处的积极约束指标集，记为若x定义(积极约束)积极约束指标的全体组成的集合，称为处的积极约束xmin()..()0,1,2,...,(1)()0,1,2,...,ijfxstgximhxjl一般约束优化的一阶最优性条件或称紧约束、起作用约束。处的,xD()0igx()0igx(){|()0,1,2,,}.iIxigxim例1：设，则称是在处的积极约束或称紧约束、在积极约束指标集若xxmin()..()0,1,2,...,(1)()0,1,2,...,ijfxstgximhxjl积极约束的判断222112212()20,()10,gxxxgxxx2122()2()0,22gx22222()()()10,22gx22(,),22Tx31()0.gxx求在的起作用约束集。x32()0,2gx(){1,2}.Ix令解：因为起用作约束。为(1)的可行点，处可微，在处连续,在处连续向量集线性无关。若是(1)的局部最优解，使得x证明：参见陈宝林书P220.x()()0,iIxigx(())igiIxx(())iwiIx(1,,)jvjl()1()()()00,()liijjiIxjifxwgxvhxwiIx(),()(),1,,ijgxhxiIxjl(2)min()..()0,1,2,...,(1)()0,1,2,...,ijfxstgximhxjlxx一般约束优化的一阶最优性条件定理(一阶必要条件),(())ifgiIx(1,..,)jhjl在可微，则存在和x(())igiIx()1()()()00,()liijjiIxjifxwgxvhxwiIx(2)定理中的条件在处连续变为连续可微，则11()()()00,1,...,()0,1,...,mliijjijiiifxwgxvhxwimwgxim(3)当时，，由(3)可知，从(3)中自然消失,得到(2).()iIx()0igx0,iw()0(())iwgxiIx一般约束优化的一阶最优性条件()1()()()00,()liijjiIxjifxwgxvhxwiIx(2)11()()()00,1,...,()0,1,...,mliijjijiiifxwgxvhxwimwgxim(3)(1)的一阶必要条件是由Kuhn和Tuchker与1951年提出，故一阶必要条件称为K-T条件，互补松弛条件1939年，Karush也类似考虑了约束优化的最优性条件，故一阶必要条件称作K-K-T条件，将K-T点称作K-K-T点。一般约束优化的一阶最优性条件满足(2)或(3)的点是K-T点。11(,,)()()()(4)mliijjijLxwvfxwgxvhx11()()()0mliijjijfxwgxvhx与(3)中的第一个式子密切相关的是下面一个函数：011()()()mliijjijfxwgxvhx(3)(,,)xLxwv函数(4)的思想可追溯到Lagrange，故常被称为Lagrange函数，其中称为Lagrange乘子向量。11(,...,),(,...,)TTml0,1,...,()0,1,...,iiiwimwgxim一般约束优化的一阶最优性条件11(,,)()()()(4)mliijjijLxwvfxwgxvhx若是(1)的局部最优解，则存在，使得*x**0,lwvR*****(,,)0,()0.TxLxwvwgx0,1,...,()0,1,...,iiiwimwgxim为(1)的可行点，处可微，在处连续向量集线性无关。若是(1)的局部最优解，使得xx()()0,iIxigx(())iwiIx(1,,)jvjl(),()(),1,,ijgxhxiIxjlxx定理(一阶必要条件),(=1,...,)ifgim(1,..,)jhjl在可微，则存在和11()()()0mliijjijfxwgxvhx(3)一阶必要条件重述为min()..()0,1,2,...,(1)()0,1,2,...,ijfxstgximhxjlx定理(一阶必要条件)为(1)的可行点,fgi在处可微,gi在处连续,hj(j=1,…,l)在处连续可微,向量集线性无关。若是(1)的局部最优解，则存在数和,使得x(())iIx()()0,iIxigx(())iIxx(())iwiIx(1,,)jvjl()1()()()00,()liijjiIxjifxwgxvhxwiIx(),()(),1,,ijgxhxiIxjl(2)xx在上述定理中，当m=0时，考虑的是仅含等式的约束优化，min()..()0,1,2,...,(5)jfxsthxjl定理(一阶必要条件)为等式约束(5)的可行点，f在处可微,hj(j=1,…,l)在处连续可微，向量集线性无关。若是(5)的局部最优解，则存在数，使得xxx(1,,)jvjl1()()0ljjjfxvhx()1,,jhxjl(6)xmin()..()0,1,2,...,(5)jfxsthxjl等式约束优化的一阶最优性条件这是经典的条件极值问题，它的最优性条件和求解方法已在多元函数微分学中得到解决。问题求在条件下的极值。(,)zfxy(,)0xy定理(一阶必要条件)为等式约束(5)的可行点，f在处可微,hj(j=1,…,l)在处连续可微，向量集线性无关。若是(5)的局部最优解，则存在数，使得xxx(1,,)jvjl1()()0ljjjfxvhx()1,,jhxjl(6)x问题求在条件下的极值。引入Lagrange乘子Lagrange函数(,)zfxy(,)0xy(,,)(,)(,)LxyfxyxyR************(,)(,)0(,)(,)0(,)0xxyyfxyxyfxyxyxy若是条件极值，则存在，使得***(,)xy等式约束优化的一阶最优性条件min()..()0,1,2,...,(1)()0,1,2,...,ijfxstgximhxjl在上述定理中，当l=0时，考虑的是仅含不等式的约束优化，min()..()0,1,2,...,(7)ifxstgxim定理(一阶必要条件)为不等式约束优化(7)可行点,,f和gi在处可微，线性无关。若是(7)的局部最优解，则存在，使得xx()()0iIxigx(1,...,)iwim()()igxiIx(8)x1()()0miiifxwgx0,()0,1,...,iiiwwgxim定理(一阶必要条件)为(1)的可行点,fgi在处可微,gi在处连续,hj(j=1,…,l)在处连续可微,向量集线性无关。若是(1)的局部最优解，则存在数和,使得x(())iIx()()0,iIxigx(())iIxx(())iwiIx(1,,)jvjl()1()()()00,()liijjiIxjifxwgxvhxwiIx(),()(),1,,ijgxhxiIxjl(2)xxxmin()..()0,1,2,...,(7)ifxstgxim(8)1()()0miiifxwgx0,()0,1,...,iiiwwgxim不等式约束优化的一阶最优性条件定理(一阶必要条件)为不等式约束优化(7)可行点,,f和gi在处可微，线性无关。若是(7)的局部最优解，则存在，使得xx()()0iIxigx(1,...,)iwim()()igxiIxx(),()jfxhx**,x**(,)0LxnsR*()0(1,,)Tjshxjl2**(,)0TxsLxs*x定理（二阶充分条件）在问题（5）中，若（1）（2）存在使得Lagrange函数的梯度为零，即（3）对任意的非零向量，且均有则是问题（5）的严格局部极小点.等式约束优化的二阶最优性条件min()..()=0,1,2,...,(5)jfxsthxjl是二阶连续可微函数；()1()()()00,()liijjiIxjifxwgxvhxwiIx(2)11()()()00,1,...,()0,1,...,mliijjijiiifxwgxvhxwimwgxim(3)满足(2)或(3)的点是K-T点一般约束优化的一阶最优性条件若题目要求K-T点求解(3.1)(3.3)，的就是K-T点;若验证某点是否为K-T点，求解(2.1)，它们的解中使得(2.2)成立的就是K-T点.(2.1)(2.2)(3.1)(3.2)(3.3),xxxxnml个未知量nm个方程它们的解中使得(3.2)成立123()2,3xfxx21(),gxx32(),gxx例2:求约束极值问题K-T点的计算解：记的K-T点。112()4,gxxx2212121212min()6684..00fxxxxxxxstxx则11(),1gx21(),0gx30(),1gx112323110203101xx31()()0,iiifxgx由K-T条件得到11()()()0(3.1)0,1,...,(3.2)()0,1,...,(3.3)mliijjijiiifxwgxvhxwimwgxim112323110203101xx0,()0,1,2,3iiigxi由K-T约束条件21()0gxx32()0gxx112()40gxxx再加上问题本身的约束条件联立(1-1),(1-2)和(1-3),求x