拉格朗日函数
职责权限-启迪中学
2023年2月22日发(作者：粉条生产线)深入理解拉格朗日乘子法（LagrangeMultiplier)和KKT条件
在求取有约束条件的优化问题时，拉格朗日乘子法（LagrangeMultiplier)和KKT
条件是非常重要的两个求取方法，对于等式约束的优化问题，可以应用拉格朗日
乘子法去求取最优值；如果含有不等式约束，可以应用KKT条件去求取。当然，
这两个方法求得的结果只是必要条件，只有当是凸函数的情况下，才能保证是充
分必要条件。KKT条件是拉格朗日乘子法的泛化。之前学习的时候，只知道直
接应用两个方法，但是却不知道为什么拉格朗日乘子法（LagrangeMultiplier)和
KKT条件能够起作用，为什么要这样去求取最优值呢？
本文将首先把什么是拉格朗日乘子法（LagrangeMultiplier)和KKT条件叙述一
下；然后开始分别谈谈为什么要这样求最优值。
一.拉格朗日乘子法（LagrangeMultiplier)和KKT条件
通常我们需要求解的最优化问题有如下几类：
(i)无约束优化问题，可以写为:
minf(x);
(ii)有等式约束的优化问题，可以写为:
minf(x),
s.t.h_i(x)=0;i=1,...,n
(iii)有不等式约束的优化问题，可以写为：
minf(x),
s.t.g_i(x)<=0;i=1,...,n
h_j(x)=0;j=1,...,m
对于第(i)类的优化问题，常常使用的方法就是Fermat定理，即使用求取f(x)的导
数，然后令其为零，可以求得候选最优值，再在这些候选值中验证；如果是凸函
数，可以保证是最优解。
对于第(ii)类的优化问题，常常使用的方法就是拉格朗日乘子法（Lagrange
Multiplier)，即把等式约束h_i(x)用一个系数与f(x)写为一个式子，称为拉格朗
日函数，而系数称为拉格朗日乘子。通过拉格朗日函数对各个变量求导，令其为
零，可以求得候选值集合，然后验证求得最优值。
对于第(iii)类的优化问题，常常使用的方法就是KKT条件。同样地，我们把所有
的等式、不等式约束与f(x)写为一个式子，也叫拉格朗日函数，系数也称拉格朗
日乘子，通过一些条件，可以求出最优值的必要条件，这个条件称为KKT条件。
(a)拉格朗日乘子法（LagrangeMultiplier)
对于等式约束，我们可以通过一个拉格朗日系数a把等式约束和目标函数组合
成为一个式子L(a,x)=f(x)+a*h(x),这里把a和h(x)视为向量形式，a是横向量，
h(x)为列向量，之所以这么写，完全是因为csdn很难写数学公式，只能将就了.....。
然后求取最优值，可以通过对L(a,x)对各个参数求导取零，联立等式进行求取，
这个在高等数学里面有讲，但是没有讲为什么这么做就可以，在后面，将简要介
绍其思想。
(b)KKT条件
对于含有不等式约束的优化问题，如何求取最优值呢？常用的方法是KKT条件，
同样地，把所有的不等式约束、等式约束和目标函数全部写为一个式子L(a,b,x)=
f(x)+a*g(x)+b*h(x)，KKT条件是说最优值必须满足以下条件：
1.L(a,b,x)对x求导为零；
2.h(x)=0;
3.a*g(x)=0;
求取这三个等式之后就能得到候选最优值。其中第三个式子非常有趣，因为
g(x)<=0，如果要满足这个等式，必须a=0或者g(x)=0.这是SVM的很多重要性
质的来源，如支持向量的概念。
二.为什么拉格朗日乘子法（LagrangeMultiplier)和KKT条件能够得到最优值？
为什么要这么求能得到最优值？先说拉格朗日乘子法，设想我们的目标函数z=
f(x),x是向量,z取不同的值，相当于可以投影在x构成的平面（曲面）上，即成
为等高线，如下图，目标函数是f(x,y)，这里x是标量，虚线是等高线，现在假
设我们的约束g(x)=0，x是向量，在x构成的平面或者曲面上是一条曲线，假设
g(x)与等高线相交，交点就是同时满足等式约束条件和目标函数的可行域的值，
但肯定不是最优值，因为相交意味着肯定还存在其它的等高线在该条等高线的内
部或者外部，使得新的等高线与目标函数的交点的值更大或者更小，只有到等高
线与目标函数的曲线相切的时候，可能取得最优值，如下图所示，即等高线和目
标函数的曲线在该点的法向量必须有相同方向，所以最优值必须满足：f(x)的梯
度=a*g(x)的梯度，a是常数，表示左右两边同向。这个等式就是L(a,x)对参数
求导的结果。（上述描述，我不知道描述清楚没，如果与我物理位置很近的话，
直接找我，我当面讲好理解一些，注：下图来自wiki）。
而KKT条件是满足强对偶条件的优化问题的必要条件，可以这样理解：我们要
求minf(x),L(a,b,x)=f(x)+a*g(x)+b*h(x)，a>=0，我们可以把f(x)写为：
max_{a,b}L(a,b,x)，为什么呢？因为h(x)=0,g(x)<=0，现在是取L(a,b,x)的最大值，
a*g(x)是<=0，所以L(a,b,x)只有在a*g(x)=0的情况下才能取得最大值，否则，
就不满足约束条件，因此max_{a,b}L(a,b,x)在满足约束条件的情况下就是f(x)，
因此我们的目标函数可以写为min_xmax_{a,b}L(a,b,x)。如果用对偶表达
式：max_{a,b}min_xL(a,b,x)，由于我们的优化是满足强对偶的（强对偶就是
说对偶式子的最优值是等于原问题的最优值的），所以在取得最优值x0的条件
下，它满足f(x0)=max_{a,b}min_xL(a,b,x)=min_xmax_{a,b}L(a,b,x)=f(x0)，
我们来看看中间两个式子发生了什么事情：
f(x0)=max_{a,b}min_xL(a,b,x)=max_{a,b}min_xf(x)+a*g(x)+b*h(x)
=max_{a,b}f(x0)+a*g(x0)+b*h(x0)=f(x0)
可以看到上述加黑的地方本质上是说min_xf(x)+a*g(x)+b*h(x)在x0取得了
最小值，用fermat定理，即是说对于函数f(x)+a*g(x)+b*h(x)，求取导数要等
于零，即
f(x)的梯度+a*g(x)的梯度+b*h(x)的梯度=0
这就是kkt条件中第一个条件：L(a,b,x)对x求导为零。
而之前说明过，a*g(x)=0，这时kkt条件的第3个条件，当然已知的条件h(x)=0
必须被满足，所有上述说明，满足强对偶条件的优化问题的最优值都必须满足
KKT条件，即上述说明的三个条件。可以把KKT条件视为是拉格朗日乘子法的
泛化。
梯度、Hessian矩阵、平面方程的法线
以及函数导数的含义
想必单独论及“梯度、Hessian矩阵、平面方程的法线以及函数导数”等四个基本
概念的时候，绝大部分人都能够很容易地谈个一二三，基本没有问题。
其实在应用的时候，这几个概念经常被混淆，本文试图把这几个概念之间的关系
整理一下，以便应用之时得心应手。
这四个概念中，Hessian矩阵是最不容易混淆，但却是很多人难以记住的概念，
其它三个概念很容易记住，但却在某些时候很容易混淆。
Hessian矩阵：设有凸函数f(X)，X是向量（x1,x2,...,xn)，Hessian矩阵M定义为：
M的第i行,第j列元素为df(X)/dxidxj,即为f(X)对于变量xi和xj的二次偏导数。
梯度：设有凸函数f(X)，X是向量（x1,x2,...,xn)，函数f(X)在点X0处的梯度是一
个向量，等于（df(X0)/dx1,df(X0)/dx2,....,df(X0)/dxn),即是对于各个变量的偏导数
的向量。例子：如果方程是z=f(x,y)，梯度是在XOY平面内的一个向量，与z无关。
因此要特别注意梯度不是点(X，f(X))处的切线方向。
平面方程的法线：设平面方程Ax+By+Cz+D=0，向量（A,B,C)为这个平面的法线
方向。
函数导数：二维直线的方程y=kx+b，我们说k是直线的斜率；二维曲线y=f(x)的导
数f'(x)表示在点x处的切线的斜率，注意是切线的斜率，不是切线的方向，它是标
量，不是向量。任意曲线y=f(x1,x2,...xn)，对每一个变量求取偏导数，得到一个向量
（df(X)/dx1,df(X)/dx2,....,df(X)/dxn)，这个向量就是函数在点X处的梯度，即梯度
是表示曲线f(X)在X处变化最剧烈的方向，特别注意梯度并不是在点(X,f(X))处的
切线方向,梯度只是在点(X,f(X))处的切线方向在X构成的“平面”上的投影。注意，
对于二维直线y=kx+b，它也是可以求取梯度的，它的梯度是向量（k），只有一个
值，表示的是x方向上的向量，大小是x方向上的单位变化导致y变化量的大小，
即就是切线的斜率。
一个问题，我们把二维直线方程y=-kx-b写为平面方程的形式，kx+y+b=0，
这个时候怎么理解？我们可以理解为把y=-kx-b这条直线往z轴的两个方向拉伸
得到的平面，就是kx+y+b=0。那么这个平面方程的法线就是（k,1,0)，这个
法线向量与平面kx+y+b=0垂直，这个时候如果我们用XOY平面去与这个平面相
交，即令z=0，就表示直线y=-kx-b，因此法线（k,1)是与直线垂直的。注意y=-kx
-b的导数的含义：（-k）表示的是x轴方向的梯度，值为直线的斜率。
一定要注意平面方程的形式与其它三个概念的方程形式是不同的，平面方程的右
边是0，而其它三个概念的方程中必须有一个变量在等式的左边，可以表示为
f(X)，或者y等形式，本质上f(X)和y都表示的是一个变量，只有方程的形式
对的时候才能适用相关的计算，例如，我们不能对方程Ax+By+Cz+D=0，使用梯
度或者导数的计算，这个地方非常容易混淆，特此提醒！
pku，sewm，shinning