资源描述：
《关于拉格朗日乘子法及KKT条件的探究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、关于拉格朗日乘子法及KKT条件的探究姓名：XXX学号：XXXO(北京理工大学机械与车辆学院车辆工程，北京100081)摘要：拉格朗日乘子法(LagrangeMultiplier)和KKT(Karush-Kuhn-Tucker)条件是求解约束优化问题的重要方法，在有等式约束时使用拉格朗日乘子法，在有不等约束时使用KKT条件。当然，这两个方法求得的结果只是必要条件，只有当目标函数是凸函数的情况下，才能保证是充分必要条件。本文将首先描述拉格朗日乘子法和KKT条件，然后对其进行推导，最后谈谈为什么要这样求最优值。1.拉格朗日乘子法及KKT条件概述通常我们需要求解的最优
2、化问题有如卜•几类：(i)无约束优化问题，可以写为：min/(X);⑴)有等式约束的优化问题，可以写为：min/(X);s.t./z.(X)=O;丿・=1,2…，”；(iii)有不等式约束的优化问题，可以写为：s.t./?.(%)=0;j=l,2・・・,p;g&(X)SO;k=,2…,q;对于第(i)类的优化问题，常常使用的方法就是Fermat定理，即求取/(X)的导数，然后令其为零，可以求得候选最优值，再在这些候选值中验证；如果是凸函数，可以保证是最优解。对于第(ii)类的优化问题，常常使用的方法就是拉格朗日乘子法，即把等式约束巧・(X)用一个系数与/(X
3、)写为一个式子，称为拉格朗日函数，而系数称为拉格朗日乘子。通过拉格朗日函数对各个变量求导，令其为零，可以求得候选值集合，然后验证求得最优值。对于第(iii)类的优化问题，常常使用的方法就是KKT条件。同样地，我们把所有的等式、不等式约束与/(X)写为一个式了，也叫拉格朗口函数，系数也称拉格朗口乘子，通过一些条件，可以求出最优值的必要条件，这个条件称为KKT条件。1.1拉格朗日乘子法通过引入拉格朗日乘子兔把等式约束和目标函数组合成为一个新的目标函数：F(X,Q)=/(X)+£/l/j(X)冃把F(XM)作为一个新的无约束条件的目标函数来求解它的极值点，所得结果就
4、是满足约束条件/?.(X)=0(J=l,2,...,p)的原口标函数/(X)的极值点。其屮F(X,2)称为拉格朗Fl函数。函数F(X,2)具有极值的必要条件为：些^=0i=ox.3F返=0"1,2…,p可得p+n个方程，从而解得X=[x}x2••-]r和舜=共p+〃个未知变量的值。由上述方程组求得的<•••<]'是函数/(X)极值点的坐标值。1.2KKT条件工程上大多数优化问题都可表示为具有不等式约朿条件的优化问题，求解此类问题的目标函数极值点一般用KKT条件。首先，设计变量％=［西兀2…兀丁为n维变量，它受有q个不等式约束，p个等式约束。然后把所有的不等式约
5、束、等式约束和目标函数全部写为一个函数:pqF(X,入〃)=/(X)+j>/j(X)+j>&(X)J=1Jt=l对F(XM,“)求导，得以下极值条件:dXf；=1k=l汽X)=0(心1,2,・・・加〃風(Xj=O伙=1,2,…,g)以0(k=l,2,・・・,q)2严0°=1,2,…，刃其屮，〃是对应于不等式约束的拉格朗H乘子向量“二［““2…血丁，并有非负的要求。对于仅有等式约束的优化问题，上式F(X,入“)中省去乞以和X),即变为等式约束的拉格朗H乘子法。所以说KKT条件是拉格朗日乘子法的泛化。KKT最优化条件是Karush［1939］以及Kuhn和Tuck
6、er［1951］先后独立发表出来的。这组最优化条件在Kuhn和Tucker发表Z后才逐渐受到重视，因此许多书只记载成［Kuhn-Tucker最优化条件(Kuhn-Tuckerconditions)］o1.拉格朗日乘子法及KKT条件的推导2.1拉格朗日乘子法的推导为推导简便起见，考虑两变量目标函数/(xPx2)在单个等式约束条件g(xpx2)=0H的最优化问题。一方面，于(力在极值点X*处必满足:故有:df(2.1.1)(2.1.2)另一方而，由J*g(xl,x2)=0,故冇：dg=半琳+^~dx21.=0ax,dx2(2.1.3)由以上两式可得:吋心
7、/dx
8、2!dg/3X('dg/dx2x(2.1.4)不妨令dg/dxil,=A(z=1,2)(2.1.5)则冇字一聲l.=03%!OXjA^--A.=o(2.1.6)令H(x“2,2)=/(xpx2)-A^(xpx2),那么下而两个问题是互相等价的:min/(xpx2)s.t.g(x^x2)=0>ominH(xpx2,/l)(2.1.7)这是因为函数H存在极值的必要条件为(2.1.8)dH_dH_dH3x)dx7dA而上式的结果恰与式(2.1.6)及g(xpx2)=0是等价的。这样就将原约束问题转为一个无约束的最优化问题，通过求解H(x„x2,A)函数的极小值完成对
9、/(xpx2)极小值的求取。以上推导对
