拉格朗日乘子法Lagrange Multiplier详解以及乘子lambda的意义

主要介绍经典拉格朗日乘子法的原理,之后讨论该方法中出现的参数λ\lambda的意义

拉格朗日乘子法的数学原理

经典拉格朗日乘子法是下面的优化问题(注:x\bold x是一个向量):

(1)minxf(x)s.t.g(x)=0\begin{matrix} \min_{\bold x} f(\bold x)\\[2ex] s.t. g(\bold x)=0 \end{matrix}\tag{1}

直观上理解,最优解xoptimal\bold x_{optimal}一定有这样的性质,以x\bold x是二维变量为例:(网上下的图。为了符合行文风格,这里的g(x,y)=cg(x,y)=c应为g(x,y)=0g(x,y)=0
f与g的等高线图
这里采用等高线方式描述f(x,y)f(x,y)(对方程f(x,y)=df(x,y)=d对不同dd绘图),并绘制约束条件g(x,y)=0g(x,y)=0的曲线。可见,当g(x,y)=0g(x,y)=0f(x,y)f(x,y)的某条等高线相切时,可取得最优解。

“当g(x,y)=0g(x,y)=0f(x,y)f(x,y)的某条等高线相切”,是取得最优解的充要条件(前提是f(x,y)f(x,y)是凸函数),该条件可拆分成两部分:

  1. g(x,y)g(x,y)f(x,y)f(x,y)的某条等高线相切
  2. g(x,y)=0g(x,y)=0

因为g(x,y)g(x,y)f(x,y)f(x,y)的某条等高线相切,可等价于寻找使这两个函数梯度方向共线的点,所以上述条件可用方程组描述如下所示:

(2){f(x)=λg(x)g(x)=0\begin{cases} \nabla f(\bold x) = \lambda\nabla g(\bold x)\\[2ex] g(\bold x)=0 \end{cases} \tag{2}

这时引入拉格朗日函数:

(3)L(x,λ)=f(x)+λg(x)L(\bold x,\lambda) = f(\bold x)+\lambda g(\bold x) \tag{3}

该函数有这样的特性:

(4){xL(x,λ)=xf(x)+λg(x)λL(x,λ)=g(x)\begin{cases} \nabla_\bold xL(\bold x,\lambda)=\nabla_\bold x f(\bold x)+\lambda g(\bold x)\\[2ex] \nabla_\lambda L(\bold x,\lambda) = g(\bold x) \end{cases} \tag{4}

即若令拉格朗日函数的梯度为零,即(4)(4)式为零,即可得到方程(2)(2),虽然λ\lambda有所出入但不影响。

系数λ\lambda的作用

另外讨论一下(3)(3)式中λ\lambda的意义:

(2)(2)式可以看出,λ\lambda在共线的基础上描述了目标函数和约束函数的梯度的长度比值。当然若以(4)(4)为基准,(2)(2)式第一项应写为f(x)=λg(x)\nabla f(\bold x) = -\lambda\nabla g(\bold x),我们对该等式两边取绝对值如下,以消除正负号可能对读者带来的困扰。

(5)λ=f(x)g(x)|\lambda|=|\frac{\nabla f(\bold x)}{\nabla g(\bold x)}| \tag{5}

可以发现,当λ|\lambda|越小,g(x)\nabla g(\bold x)的模就越大于f(x)\nabla f(\bold x)。极端情况下,λ0|\lambda\to0|,此时g(x)|\nabla g(\bold x) |\to \infty。这意味着在x\bold x点,g(x)g(\bold x)几乎是垂直的,对增量非常敏感:当最优值不小心变一点点,条件g(x)=0g(\bold x)=0将严重偏离;若λ|\lambda|很大,g(x)g(\bold x)几乎是水平的,则其对增量不敏感(若g(x)g(\bold x)的轻微偏离不会造成太大的损失,可以适当牺牲约束条件的精确性,来换取更优的解)。

换句话说,λ|\lambda|越小,其求得的结果灵敏度越高,反之越低;可以说λ|\lambda|是衡量最优解灵敏度的一种方法。(当然也可以直接求g(x)\nabla g(\bold x)来衡量灵敏度,这样更绝对一点)

0%