最优化方法 第三章(约束最优性条件)

一约束优化罚函数法可行方向法最优性条件二三五二次逼近法四乘子法一、最优性条件约束优化问题的分类..0,1,,,0,1,,.minnRieiefstgiImhiEmmxxxx等式约束问题不等式约束问题约束优化问题的求解困难极小点可能位于约束域中间，也可能位于边界；迭代点处可行方向有限制，不再是任意方向；无约束问题的最优性条件不再适用；一、最优性条件等式约束优化问题的最优性条件min,..,0fxystgxy求解方法代入法（消元法）(,)0()gxyyx(,())zfxx拉格朗日乘子法(,)(,)Ffxygxy一、最优性条件推广到多元函数，多等式约束问题min()..()0,1,2,...,jfxsthxjl定理(等式约束一阶必要条件)考虑等式约束优化问题,为可行点，f(x)在处可微,hj(j=1,…,l)在处连续可微，向量集线性无关。若是等式约束问题的局部最优解，则存在数，使得xxx(1,,)jvjl1()()0ljjjfxvhx()1,,jhxjlx拉格朗日函数1(,)()()ljjjLxvfxvhx一、最优性条件等式约束一阶必要条件的含义目标函数的梯度属于约束函数在处的梯度张成的子空间，共面，在正交补空间投影为0；x单个约束一、最优性条件目标函数的梯度正交于一阶可行变分子空间，即()()0,1,,jVxxhxxjl1()()0ljjjfxvhx一阶可行变分子空间是指由变分构成的子空间，这些变分使得约束函数展开到一阶时，在向量处仍然成立；xxx此时，目标函数的一阶变分，与无约束优化的“零梯度条件”类似。一、最优性条件定理(等式约束二阶必要条件)221(()())0lTjjjyfxvhxy()()0,1,,jyVxxhxxjl或者1(,)()()ljjjLxvfxvhx的海塞矩阵关于y在处半正定。定理当然还需要目标函数和约束函数二阶连续可微。x一、最优性条件定理(等式约束二阶充分条件)221(()())0lTjjjyfxvhxy()()0,1,,jyVxxhxxjl或者1(,)()()ljjjLxvfxvhx的关于y的矩阵在处关于正定，则是满足约束的局部最小点。若目标函数和约束函数二阶连续可微，且满足xx2(,)xxLxv一、最优性条件拉格朗日乘子的意义----灵敏度min()..Tfxstaxb仅考虑一个线性约束的等式优化问题xxxxTaxb()fxacos()()()()()()TTtfxxfxfxxoxaxoxboxcos()()tfxxfxbb拉格朗日乘子为最优目标费用随约束的增长而递减的变化率。多个线性约束情形：1cos()liiitbox可推广至非线性约束一、最优性条件不等式约束优化问题的最优性条件..0,1,,,0,1,,.minnRieiefstgiImhiEmmxxxx{|()0,()0},Dxgxhx可行域：其中的元素可行点；,xD()0igx()0igx()，Ix(){|()0,1,2,,}iIxigxim设可行解，则称不等式约束是在处的积极约束（activeconstraint）或称紧约束、处的积极约束指标集，记为若x起用作约束。积极约束指标的全体组成的集合，称为x一、最优性条件例：设222112212()20,()10,gxxxgxxx2122()2()0,22gx22222()()()10,22gx22(,),22Tx31()0.gxx求在的起作用约束集。x32()0,2gx(){1,2}.Ix令解：因为Ox一、最优性条件如果是不等式约束问题的局部最小点，那么仍是该问题不考虑在处的非积极约束后新问题的局部极小值点；xx非积极约束不重要，可以在最优性条件中忽略这些非积极约束；在局部最小点处，积极约束可以转化为等式约束进行处理；..0,,0,.minnRiifstgiIhiExxxx..0,(),0,minnRiifstgiIhiExxxxx一、最优性条件定理(一阶必要条件)考虑一般约束优化问题,为可行点，f(x)和gi(x)在处可微gi(x)在处连续,hj(j=1,…,l)在处连续可微向量集线性无关。若是局部最优解，则存在数和使得x(())iIxx()()0iIxigx(())iIxx(())iwiIx(1,,)jvjl()1()()()00,()liijjiIxjifxwgxvhxwiIx(),()(),1,,ijgxhxiIxjlxx一般约束优化的一阶最优性必要条件一、最优性条件x(())iIx定理中的条件gi(x)在处连续加强为连续可微，则上述结论等价于11()()()00,1,...,()0,1,...,mliijjijiiifxwgxvhxwimwgxim当时，，可知，自然消失。()iIx()0igx0,iw()0(())iwgxiIx一、最优性条件()0,1,...,iiwgxim约束优化的一阶必要条件是由Kuhn和Tuchker与1951年提出，所以一阶必要条件又称为K-T条件，满足K-T条件的点称为K-T点。互补松弛条件1939年，Karush也类似考虑了约束优化的最优性条件，所以也有人一阶必要条件称作K-K-T条件，将K-T点称作K-K-T点。拉格朗日函数11(,,)()()()mliijjijLxwvfxwgxvhx***(,,)0.xLxwv**0,()0liiwvRwgx一、最优性条件一阶最优性必要条件几何解释假设约束优化问题不含有等式约束，令(),0,iiiiIcyywgxww0显然，上述集合是由紧约束梯度张成的锥。因此，KKT条件可解释为：若是约束优化问题的最优解，则−𝛻𝑓𝑥必位于点的上述锥中。xx一、最优性条件事实上，对于不等式约束优化问题，在点处，下降方向需满足xmin..0,ifstgiIxx0Tfxd可行方向需满足0Tigxd若为局部极小值点，则在该点处一定不存在可行下降方向，即x0Tfxd0Tigxd无解00,iiifxwgxww0Gordan引理一、最优性条件一般约束优化的二阶最优性条件(二阶必要条件)()()0,()0,TTjiyVxxhxxgxxiI若目标函数和约束函数二阶连续可微，11(,,)()()()mliijjijLxwvfxwgxvhx2(,,)0TxxyLxwvy有(二阶充分条件)若目标函数和约束函数二阶连续可微，()yVx2(,,)0TxxyLxwvy则x为满足约束的严格局部最小值点。一、最优性条件123()2,3xfxx21(),gxx32(),gxx例:求约束极值问题解：记的K-T点。112()4,gxxx2212121212min()6684..00fxxxxxxxstxx则11(),1gx21(),0gx30(),1gx11232311003101xx31()()0,iiifxgx由K-T条件得到K-T点计算：不知道的位置x一、最优性条件11232311003101xx0,()0,1,2,3iiigxi由K-T约束条件，得到21()0gxx32()0gxx112()40gxxx再加上问题本身的约束条件联立(1-1),(1-2)和(1-3),求x和相应的乘子1122133(11)3xx123,,0121240,0,0(13)xxxx1122132(4)000xxxx(12)一、最优性条件12(1)0:xx若1121(4)00xx由可得1232320与矛盾。:0,0)2(21xx若302112x3322x022x020与矛盾。213200xx11221333xx112(4)0xx121212340,0,,0xxxx一、最优性条件1113x3313x031x030与矛盾。213200xx11221333xx112(4)0xx121212340,0,,0xxxx:0,0)3(21xx若20一、最优性条件:0,0)4(21xx若230421xx若10321xx4621xx矛盾。421xx221xx11221121x3x311221333xx112(4)0xx213200xx121212340,0,,0xxxx12xx是K-T点。一、最优性条件1(1,1)Tx2(0,0)Tx221221212min(2)6..00xxstxxxx22212112212()(2)6,(),()fxxxgxxxgxxx112222(2)11(),(),()221xfxgxgxxx11112211(),(),()221fxgxgx12()0,()0gxgx例：验证点是否为K-T点？解：记在点处，都是起作用约束，则1(1,1)Tx目标函数和约束函数的梯度分别是()()()0(2)0,()iiiIxifxwgxwiIx1()ljjjvhxK-T点计算：知道的位置x一、最优性条件11112211(),(),()221fxgxgx故点是K-T点。1(1,1)Tx设1221102210121220220解之得，即12=0,=2一、最优性条件12()0,()0gxgx22212411(),(),()001fxgxgx在点处，都是起作用约束，目标函数和约束函数的梯度分别是2(0,0)Tx故点不是K-T点。设1241100010122400解之得，即12=-4,=02(0,0)Tx一、最优性条件约束优化问题求解方法简介利用最优性条件直接求解困难，需要借助数值算法求解。求解方法可以分为两类直接解法在满足不等式约束的可行设计区域内直接求出问题的约束最优解。代表性算法：可行方向法、随机方向法等。x(k+1)＝x(k)+α(k)S(k)(k=0,1,2,…)由于整个过程在可行域内进行，因此，迭代计算不论何时终止，都可以获得比初始点好的设计点。若目标函数为凸函数，可行域为凸集，则可获得全