拉格朗日乘子法：从函数的求导到不等式约束的求解

本篇文章简单梳理了关于拉格朗日乘子法的相关问题及一些相关概念的介绍。

基本概念

拉格朗日乘子法（Lagrange Multiplier）在某些地方又叫做拉格朗日乘数法。在求解最优化问题中，这个方法是最常用的方法之一。最优化问题往往抽象为某个函数，即求函数的最大值或最小值。求解最大值和最小值的求解可以相互转换（对偶）。对于求解最优化问题分为以下三种情况（难度依此递增）：

无约束条件

一般情况下，只需要对给出的函数进行求导，令其导函数为0的点可能就是极值点，将可能的结果分别代回原函数进行验证即可。

假设有这样一个函数$f(x)$，令$g(x)=f^{'}(x)$，$g(x)=0$的解有$x_1,x_2,x_3,\cdots$。求函数$f(x)$的最优解就只需要分别将$x_1,x_2,x_3,\cdots$代入$f(x)$，比较大小，得到最优解$x_i$。

从这里开始引出拉格朗日乘子法

等式约束条件

设目标函数为$f(x)$, 约束条件为$h_k(x) $, $k=1,2,\cdots,l$，即要求$f(x)$的最优解，但是有$l$个$h(x)$等式约束（限制）求解。这里我们定义拉格朗日函数为

$$F(x, \lambda)=f(x)+\sum\limits_{k=1}^{l}\lambda_kh_k(x)$$

$\lambda_k$表示约束条件的待定系数。之后解变量的偏导方程，如下:

$$\frac{\partial F}{\partial x_k}=0, \frac{\partial F}{\partial \lambda_k}=0, k=1,2,\cdots, l$$

求解得到了$l+1$个方程，将结果代回原方程验证即可得到解。

举例：

给定一个椭圆$\frac{x^2}{a^2}+\frac{y^2}{b^2}+\frac{z^2}{c^2}=1$，求解$f(x,y,z)=8xyz$的最大值。

求解过程如下：

• 通过拉格朗日乘子法的定义，得到如下方程

  $$\begin{array}{l}F(x,y,z,\lambda)&=f(x,y,z)+\lambda\cdot h(x,y,z) \\ &=8xyz+\lambda\cdot(\frac{x^2}{a^2}+\frac{y^2}{b^2}+\frac{z^2}{c^2}-1) \end{array}$$

• 接下来对$F(x,y,z,\lambda)$求偏导，分别得到

  $$\frac{\partial F(x,y,z,\lambda)}{\partial x}=8yz+\frac{2\lambda x}{a^2}=0$$

  $$\frac{\partial F(x,y,z,\lambda)}{\partial y}=8xz+\frac{2\lambda y}{b^2}=0$$

  $$\frac{\partial F(x,y,z,\lambda)}{\partial z}=8xy+\frac{2\lambda z}{c^2}=0$$

  $$\frac{\partial F(x,y,z,\lambda)}{\partial \lambda}=\frac{x^2}{a^2}+\frac{y^2}{b^2}+\frac{z^2}{c^2}-1=0$$

• 联立前三个方程可以得到$bx=ay$和$az=cx$，代入最后一个方程，解得：

  $$x=\frac{\sqrt{3}}{3}a$$

  $$y=\frac{\sqrt{3}}{3}b$$

  $$z=\frac{\sqrt{3}}{3}c$$

• 最后代入原方程，解得最大体积

  $$V_{max}=f(\frac{\sqrt{3}}{3}a,\frac{\sqrt{3}}{3}b,\frac{\sqrt{3}}{3}c)=\frac{8\sqrt{3}}{9}abc$$

不等式约束条件

设目标函数为$f(x)$, 不等式约束条件为$c_i(x)$,$i=1,2,\cdots,k$，等式约束条件为$h_j(x) $, $j=1,2,\cdots,l$，即要求$f(x)$的最优解，但是有$k$个$g(x)$不等式和$l$个$h(x)$等式约束（限制）求解。这里我们定义拉格朗日函数为

$$L(x,a,b)=f(x)+\sum\limits^{k}_{i=1}a_ic_i(x)+\sum\limits^{l}_{j=1}b_jh_j(x)$$

这里用一个叫做KKT条件的方法，把所有的不等式约束、等式约束和目标函数全部写为一个式子$L(a,b,x)=f(x)+a*c(x)+b*h(x)$。

KKT条件是指最优解必须满足以下条件：

• $L(a,b,x)$求$x$求导为0
• $h(x)=0$
• $a*c(x)=0$

这样就可以将不等式约束转换为了等式约束，求$L(a,b,x)$的偏导等于零即可求得最优参数。

$$\min f(x)\Leftrightarrow \min\limits_x \max\limits_{a,b} L(x,a,b)$$

经过对偶变换得：

$$\max\limits_{a,b} \min L(x,a,b)$$

因为$c(x)<0$，所以只有当$a*c(x)=0$时，$L(x,a,b)$才能取得最大值。以上就可以使用同等式约束的求解方法进行求解。

补充部分

定义不等式约束问题的标准写法

$f(x), c_i(x),h_j(x)$是定义在$R^n$上的连续可微函数，考虑约束最优化问题：

$\min f(x) \quad x\in R^n$

$s.t. c_i(x) \leq 0 \quad i = 1...k$

$h_j(x)=0 \quad j = 1...l$

即有$k$个不等式约束$c_i(x)$和$l$个等式约束$h_j(x)$

拉格朗日函数

$L(x,\alpha, \beta)=f(x)+\sum^{k}_{i=1}\alpha_ic_i(x)+\sum^{l}_{j=1}\beta_jh_j(x)$

其中的$\alpha_i$和$\beta_j$，称为拉格朗日乘子，$\alpha_i \geq 0$

几何意义

对于一个二维空间来说，求解最短路径的问题。将维度升高，变为对于多维空间来说，求解最短路径问题。

比较直观的解释，爬山的目标是到山顶，根据梯度上升（下降）的方法来寻求优解，即爬到山顶。

对偶概念的简单介绍

一对一的一种方式，把一种概念、公理或数学结构转换为另一种概念、公理或数学结构。如果A的对偶是B，那么B的对偶是A。A的对偶有时候是A的本身。

有界线性泛函数：复杂对象映射到简单对象上

群表示：简单对象具有类似线性结构的简单结构

范畴论：映射箭头所构成的集合

（像集，映射）——>原像集

对联可以称为一种对偶，上联与下联有对应的关系（相似和取逆）。对偶是有一定要有自然合理的对应关系（或者说能够吹出来的自然合理关系）。

常见的自然、合理法则首推：相似（包括同构）和取逆（包括互反）

常见对偶的例子：

1. 奇数和偶数
2. 洛必达法则和Stolz 定理（相当于离散洛必达法则）
3. Fourier 系数与 Fourier 变换（傅里叶）

对偶可以理解为，一个问题不好理解转换为另一个简单方式的问题来理解，二者在本质上是相同的。

比如：某个函数的最大化不方便求解，那么就求这个函数的最小化。

未完待续……

1. 罚函数
2. 广义乘子法
3. KKT的求导证明