拉格朗日对偶

更新于 2024-04-10 分类： Research 阅读次数：本文字数： 1.2k 阅读时长 ≈ 4 分钟

无论原问题是不是凸优化问题，都可以将原问题转化为凸优化问题来求解。当Lagrange对偶问题的强对偶性成立时，可以利用求解对偶问题来求解原问题；而原问题是凸优化问题时，强对偶性往往成立。否则，可以利用求解对偶问题求出原问题最优值的下界。总的来说，拉格朗日乘子法是一个工具（手段或方法），来解决在有约束情况的求函数极值的问题。

拉格朗日乘法（Lagrange multiplier）是一种在最优化的问题中寻找多元函数在其变量受到一个或多个条件的相等约束时的求局部极值的方法。这种方法可以将一个有 n 个变量和 k 个约束条件的最优化问题转换为一个解有 n+k 个变量的方程组的解的问题。

虽然在应用拉格朗日乘子法时，我们把条件极值问题转化称为一个方程求解的问题，整个过程都是代数的。但拉格朗日乘子法的原创思想是非常几何直观的，用向量语言表述起来很漂亮，也很容易理解和记忆。

凸优化（八）——Lagrange对偶问题

考虑一个最优化问题

\[ \operatorname*{max}_{x,y} f(x,y) \qquad s.t.\;\; g(x,y)=c \]

为了求 \(x\) 和 \(y\) ，引入一个新的变量 \(\lambda\) 称为拉格朗日乘数，再引入朗格朗日函数的极值

\[\mathcal{L}(x,y,\lambda)=f(x,y)-\lambda \cdot \bigl( g(x,y) - c\bigl) \tag 1\]

红线表示 \(g(x,y) = c\) ，蓝线是 \(f(x,y)\) 的等高线，所有箭头表示梯度下降最快的方向。图中红线与等高线相切的位置就是待求的极大值

I. 单约束

对(1)式直接求微分，并令其为零，计算出鞍点

\[ \nabla_{x,y,\lambda} \mathcal{L}(x,y,\lambda) = 0 \]

有三个未知数，所以需要3个方程。求 \(\lambda\) 的偏微分有 \(\nabla_{\lambda} \mathcal{L}(x,y,\lambda) = 0 \implies g(x,y)=0\)，则总结得

\[ \nabla_{x,y,\lambda} \mathcal{L}(x,y,\lambda) = 0 \iff \begin{cases} \nabla_{x,y} f(x,y) = \lambda \nabla_{x,y} g(x,y) \\ g(x,y)=0 \end{cases} \]

I.I. 例子1

设一个具体的例子，我们需要求下列问题

\[ \operatorname*{max}_{x,y} f(x,y) = x^2y \qquad s.t.\;\; g(x,y): x^2+y^2-3=0 \]

只有一个约束，使用一个乘子，设为 \(\lambda\)，列出拉格朗日函数

\[ \mathcal{L}(x,y,\lambda)=f(x,y)-\lambda \cdot \bigl( g(x,y) - c\bigl) = x^2y + \lambda(x^2+y^2-3) \]

接下来求解上式，分别对三个待求量偏微分

\[ \begin{align} \nabla_{x,y,\lambda} \mathcal{L}(x,y,\lambda) & = \left( \frac{\partial \mathcal{L}}{\partial x},\frac{\partial \mathcal{L}}{\partial y},\frac{\partial \mathcal{L}}{\partial \lambda}\right)\\ & = (2xy + 2\lambda x, x^2 + 2\lambda y, x^2 + y^2 - 3) \end{align} \]

令偏微分分别等于0，得到

\[ \nabla_{x,y,\lambda} \mathcal{L}(x,y,\lambda) = 0 \iff \begin{cases} 2xy+2\lambda x = 0 \\ x^2 + 2\lambda y = 0 \\ x^2 + y^2 - 3 = 0 \end{cases} \iff \begin{cases} x(y + \lambda) = 0 & (i)\\ x^2 = -2\lambda y & (ii)\\ x^2 +y^2 = 3 & (iii) \end{cases} \]

根据上式，我们可以解得 \(\mathcal{L}\):

\[ (\pm \sqrt{2},1,-1 ); (\pm \sqrt{2},-1,1 );(0,\pm \sqrt{3},0) \]

根据几个不同的解带入 \(f(x,y)\) 得到，2，-2，0，也就是我们需要的最大值，最小值，对应的直观图像解释如下图所示（非常直观的展现约束和等高线的含义）.

I.II. 例子2

关于拉格朗日乘子法的应用，有一个十分著名的：求**离散概率分布 \(p_1,p_2,\cdots,p_n\) 的最大信息熵。

\[ f(p1,p2,\cdots,p_n) = - \sum_{j=1}^n p_j log_2{p_j} \\ s.t. \quad g(p1,p2,\cdots,p_n) = \sum_{k=1}^n p_k = 1 \text{（概率和为1）} \]

单约束问题，引入一个乘子 \(\lambda\) ，对于 \(k \in [1,n]\) ，要求

\[ \frac{\partial}{\partial p_k} (f + \lambda(g - 1)) = 0 \] 将 \(f\) 和 \(g\) 带入有 \[ \frac{\partial}{\partial p_k} \left( -\sum_{k=1}^np_klog_2{p_k} + \lambda (\sum_{k=1}^n p_k - 1)\right) = 0 \]

计算这 n 个等式的偏微分，我们可以得到： \[ -\left( \frac{1}{\ln(2)} + log_2p_k \right) + \lambda = 0 \]

这说明所有的 \(p_i\) 都相等，所以得到 \(p_k = \frac{1}{n}\) 。

我们可以得到一个结论是：均匀分布的信息熵是最大的 。