拉格朗日对偶问题与神经网络

对于一个无约束优化问题，如果目标函数是一个凸函数(或凹函数)，那么我们只需要求得梯度为0的点即可，极大似然估计其实就是一个凸优化的问题。

对于一个约束优化问题，如果目标函数和不等式约束函数都是凸函数，且等式约束为线性函数，那么KKT点就是原问题的极值点。

我们先来看一个约束优化问题(这里设定目标函数和不等式约束都是凸函数)

min f(x,y)

s.t.  y≤g(x)

该问题的拉格朗日函数为

L(x,y,λ)=f(x,y)+λ(y-g(x))

令t(x,y)=y-g(x)

KKT点就是：∇f(x,y)+λ∇t(x,y)=0，即为

上图中一圈一圈的圆是目标函数f(x,y)的等值线，中心点为函数值的最小点；红色的曲线为不等式约束y-g(x)≤0的部分，向左上是大于0的部分，右下是小于0的部分，红线本身是等于0的部分，那么我们知道右下和曲线本身的部分才是满足不等式约束的。带箭头的直线是梯度方向，蓝色的是目标函数各个点的梯度方向，红色的是不等式约束函数的梯度方向。

虽然圆的中心点最小，但它不在不等式满足的范围内，我们要的是在满足不等式的范围内找最小。这里只有当目标函数的梯度与不等式约束函数的梯度方向相反的时候才是原问题的极值点。也就是KKT条件中的∇f(x,y)+λ∇t(x,y)=0，只有它们方向相反的时候才可能相加为0，而其他的情况都不可能。虽然两个梯度的方向相反，但是大小却未必相同，所以λ是一个调节因子，调节到它们的大小刚好相等，这样才能相加刚好为0。而且λ也必须大于等于0，否则就会把不等式约束函数的梯度方向调节到与目标函数的梯度相同的方向，这样也无法等于0了。

第二个约束优化问题(目标函数和不等式约束都是凸函数)

min f(x)，x∈(R^n)

s.t.  (a_i^T)x+(b_i)≤0,i=1,...,m

该问题的拉格朗日函数为

L(x,λ)=f(x)+(\sum_{i=1}^m)(λ_i)( (a_i^T)x+(b_i) )

之前的问题是一个单条件约束，这里是一个多条件约束，那么我们就不能只找一个条件约束的梯度来匹配目标函数的梯度

令(g_i)(x)= (a_i^T)x+(b_i) ,i=1,...,m

KKT点为：∇f(x)+(\sum_{i=1}^m)(λ_i)∇(g_i)(x)=0

这意味着我们需要将所有的条件约束的梯度结合起来与目标函数的梯度做一个方向相反的整合。

上图中的圆与之前一样，约束条件都是线性的，这里以m=5为例来说明，它们的约束范围为橙色的部分。我们可以看到圆的中心依然不在约束范围内，在约束范围内找最小，就是(x^*)这个点。(x^*)只属于(g_α(x))和(g_β(x))这两条直线上，其他的三条直线是不起作用的。那么α,β属于有效指标集I，则(g_α(x^*))=(g_β(x^*))=0(见凸优化整理(三) 中的与切锥关系密切的两个集合)，且∇f((x^*))+(λ_α)∇(g_α(x^*))+(λ_β)∇(g_β(x^*))=0。虽然 (g_α(x^*))=(g_β(x^*))=0，但它们的梯度并不为0，见上图中两个橙色箭头的直线，蓝色箭头的直线为目标函数的梯度方向。那么两个约束条件函数的梯度方向经过(λ_α)和(λ_β)的调节后通过平行四边形法则刚好与目标函数的梯度大小相等，方向相反，这里的(λ_α)和(λ_β)都必须大于0。其他三个约束条件由于不起作用，(g_i)((x^*))<0,i≠α,β，则它们对应的(λ_i)=0,i≠α,β，因为它们要满足KKT的互补松弛条件(λ_i) (g_i)((x^*))=0。

这三个不起作用的约束条件函数的梯度从上图中可以看到，它们两两的交点梯度和都跟目标函数的梯度同向，不可能构成相反的方向达到相加为0的效果，所以它们的调节因子(λ_i)只能调节到0，以满足KKT条件∇f(x)+(\sum_{i=1}^m)(λ_i)∇(g_i)(x)=0。结合以上两点，所以必须满足λ≥0。