拉格朗日乘子法与拉格朗日对偶函数
拉格朗日乘子法与拉格朗日对偶函数
拉格朗日乘子法和拉格朗日对偶函数是数学优化领域中的重要工具，广泛应用于各种约束优化问题的求解。本文将详细介绍这两种方法的基本原理、应用示例以及它们之间的关系，帮助读者深入理解这些优化理论的核心概念。
一、拉格朗日乘子法
在数学优化问题中，拉格朗日乘数法（Lagrange multipliers）是一种用于求解等式约束条件下局部最小（最大）值的策略。它的基本思想是通过将含约束条件的优化问题转化为无约束条件下的优化问题，以便于得到各个未知变量的梯度，进而求得极值点。
拉格朗日乘法的基本形态：求函数z = f(x, y) 在约束 ϕ(x, y) = 0 下的条件极值问题，可以转化为函数
L(x, y, λ) = f(x, y) + λϕ(x, y)
的无条件极值。
由于计算一个函数的无条件极值是很容易的（通过对函数的各个变量求偏导数，然后令所有的偏导数都为0，解这个方程组即可），所以拉格朗日乘法通过将条件极值问题转化为无条件极值问题，从而很好的解决了条件极值问题。
二、拉格朗日函数应用示例
此处以麻省理工学院数学课程的一个实例来作为介绍拉格朗日乘数法。
求双曲线xy=3上离远点最近的点。
取双曲线上任意一点(x, y)到原点的距离d = sqrt(x^2+y^2)，所以这个问题实际上是在xy=3的约束下，求得d = sqrt(x^2+y^2) 的最小值，它等价于求z = x^2 + y^2
我们将x^2 + y^2 = c的曲线族画出来，如下图所示，当曲线族中的圆与xy=3曲线进行相切时，切点到原点的距离最短。也就是说，当f(x, y) = c的等高线和双曲线g(x, y)相切时，我们可以得到上述优化问题的一个极值。
先将问题描述为下面的约束优化问题：
{ min f(x, y) = x^2 + y^2
s.t. xy-3=0
令
ϕ(x, y) = xy-3
那么拉格朗日函数为：
L(x, y, λ) = f(x, y) + ϕ(x, y) = x^2 + y^2 + λ(xy-3)
对上式中的x, y, λ分别求偏导，然后令所有的偏导为0，可以得到：
{ ∂L/∂x = 2x+ λy = 0
∂L/∂y = 2y + λx = 0
∂L/∂λ = xy - 3 = 0
求解这个方程组，可以得到两个解：
{ x=sqrt(3)
y=sqrt(3)
λ = -2
{ x=-sqrt(3)
y=-sqrt(3)
λ = -2
此时就得到了x, y的解。
拉格朗日乘法特别适用于带有一个或多个等式约束条件的优化问题，我们在学习时更多的应该是了解其优化思想精髓并加以利用，特别是在机器学习中，各种优化理论应用特别广泛。
三、拉格朗日对偶函数 (Lagrange Dual Function)
拉格朗日对偶函数是与原优化问题相对应的一个函数，它是在拉格朗日乘数法中引入的概念。对偶函数提供了一种从不同角度观察和分析原优化问题的方法。
为什么要使用拉格朗日对偶性：
- 对偶问题的对偶是原问题；
- 无论原始问题与约束条件是否是凸的，对偶问题都是凹问题，加个负号就变成凸问题了，凸问题容易优化。
- 对偶问题可以给出原始问题最优解（p*）的一个下界；
- 当满足一定条件时，原始问题与对偶问题的解是完全等价的；
对偶函数与原函数的关系：
f(x) ≥ L(x, λ, ν) ≥ g(λ, ν)
其中：
f(x)表示原问题约束条件下的函数，L(x, λ, ν)为拉格朗日函数，g(λ, ν)为拉格朗日对偶函数
一般优化问题的Lagrange乘子法
minimize f0(x), x ∈ R^n
subject to fi(x) ≤ 0, i=1,...,m
hj(x)=0, j=1,...,p
Lagrange函数
L(x, λ, μ) = f0(x) + ∑(i=1 to m) λi fi(x) + ∑(j=1 to p) νi hj(x)
此处可以理解为对固定的X, Lagrange函数L(x, λ, ν)为关于λ和ν的仿射函数。
Lagrange对偶函数
g(λ, ν) = inf L(x, λ, ν) = inf (f0(x) + ∑(i=1 to m) λi fi(x) + ∑(j=1 to p) νi hj(x))
对关于λ和ν的仿射函数逐点求取下确界，可以得出该函数是关于λ和ν的凹函数。
此处的Lagrange对偶函数是对Lagrange函数，求取下确界。
此时，如果没有下确界，定义：
g(λ, ν) = -∞
根据定义有：对∀λ≥0，∀ν,若原优化问题有最优解p*，则
g(λ, ν) ≤ p*
图中虚线部分为不等式的约束条件fi(x)，可行域为图中红色部分；
黑色曲线是我们要求的函数在≤0这个约束条件下的最小值。
此处我们可以给定λ一个值，如0.1，那么黑色实线部分加上0.1 倍虚线部分的点状线，因此在可行域内，我们总能根据 不同的λ,求出与之对应的g(λ)的值，如下图
此处g(λ)曲线其实就是关于原函数的对偶函数，可以看出是一个凹函数。
原问题是：inf_x f0(x)
从而转化为
inf_x sup_(λ≥0) L(x, λ)
此处含义为：对对偶函数L(x, λ) 对λ求上界，再对x求其下界
强对偶条件：
若要对偶函数的最大值即为原问题的最小值，考察需要满足的条件:
f0(x⋆) = g(λ⋆, ν⋆)
= inf_x(f0(x) + ∑(i=1 to m) λi⋆ fi(x) + ∑(j=1 to p) νi⋆ hj(x))
≤ f0(x) + ∑(i=1 to m) λi⋆ fi(x⋆) + ∑(j=1 to p) νi⋆ hj(x⋆)
≤ f0(x⋆)
四、拉格朗日对偶函数示例
原问题为：
minimize x^Tx, x ∈ R^n
subject to Ax=b
对应的Lagrange函数为
L(x, ν) = x^Tx + ν^T(Ax+b)
对L求x的偏导，带入L，得到对应的Lagrange对偶函数
∂L/∂x = ∂(x^Tx + ν^T(Ax+b))/∂x = 2X + A^T ν 令0 ⇒ x* = -1/2 A^T ν
得出x的最优解是-1/2 A^T，代入原式L(x, ν) = x^Tx + ν^T(Ax+b)可得，
L(x, ν) = x^Tx + ν^T(Ax+b)
= (-1/2 A^T)^T (-1/2 A^T) + ν^T (A(-1/2 A^T) - b)
= 1/4 ν^T AA^Tν - 1/2 ν^T AA^Tν -ν^Tb
= -1/4 ν^T AA^Tν - ν^T b
= g(v)
g(ν) = -1/4 ν^T AA^Tν - ν^T b
对g求ν的偏导，求g的极大值，作为原问题的最小值
∂g/∂ν = ∂(-1/4 ν^T AA^Tν - ν^T b)/∂ν = -1/2 AA^T ν -b 令0 ⇒ AA^Tν = -2b
⇒ A^TAA^Tν = -2A^T b
⇒ A^T ν = -2 (A^TA)^-1A^Tb
⇒ -1/2 A^T ν = (A^TA)^-1A^Tb
⇒ x* = (A^TA)^-1A^Tb
得出极小值点x* = (A^TA)^-1A^Tb,代入原函数
min(x^Tx) = ((A^TA)^-1A^Tb)^T ((A^TA)^-1A^Tb)
= b^T A(A^TA)^-1 (A^TA)^-1 A^Tb
= b^T A(A^TA)^-2 A^Tb
极小值点的结论，和通过线性回归计算得到的结论是完全一致。