【学习笔记】拉格朗日乘数法&KKT

osfly / 2023-08-25 / 原文

拉格朗日乘数法&KKT 学习笔记

前置芝士：导数，解方程组，~~加减乘除~~。

偏导

对一个多元函数中的某一个变量求偏导，实际上就是将其他变量视为系数，对此变量求导。

例：\(f(x,y)=2x^2+3\ln y-6xy\)，分别求 \(\dfrac{\partial f(x,y)}{\partial x}\) 和 \(\dfrac{\partial f(x,y)}{\partial y}\)（即对 \(x\) 与 \(y\) 求偏导）。

解：

对 \(x\) 求偏导：

\[\dfrac{\partial f(x,y)}{\partial x}=4x-6y \]

对 \(y\) 求偏导：

\[\dfrac{\partial f(x,y)}{\partial y}=\frac{3}{y}-6x \]

拉格朗日乘数法

介绍

拉格朗日乘数法是求一个多元函数在受到一些奇奇怪怪的约束（等式约束）的情况下的最值（max/min）。

内容

设一多元函数 \(f(x_1,x_2,...,x_m)\)，求在一系列的等式约束 \(h_i(x_1,x_2,...,x_m)=0\) 下的极值。其中 \(i\in [1,n]\)，\(n\) 为等式约束的数量，\(m\) 为未知数数量。

构造拉格朗日函数 \(L(x_1,x_2,...,x_m,\lambda_1,\lambda_2,...,\lambda_n)=f(x_1,x_2,...,x_m)+\large\sum\limits_{i=1}^{n}\lambda_ih_i(x_1,x_2,...,x_m)\)。

接着，分别求 \(\dfrac{\partial L}{\partial x_1}\)，\(\dfrac{\partial L}{\partial x_2}\)，...，，\(\dfrac{\partial L}{\partial x_m}\)，\(\dfrac{\partial L}{\partial \lambda_1}\)，\(\dfrac{\partial L}{\partial \lambda_2}\)，...，，\(\dfrac{\partial L}{\partial \lambda_n}\)。

令 \(\dfrac{\partial L}{\partial x_1}\)，\(\dfrac{\partial L}{\partial x_2}\)，...，，\(\dfrac{\partial L}{\partial x_m}\)，\(\dfrac{\partial L}{\partial \lambda_1}\)，\(\dfrac{\partial L}{\partial \lambda_2}\)，...，，\(\dfrac{\partial L}{\partial \lambda_n}\) 均等于 \(0\)，得到一个关于 \(x_1,x_2,...,x_m,\lambda_1,\lambda_2,...,\lambda_n\) 的方程组。

最后，解方程组，得到 \(x_1,x_2,...,x_m\) 的值。将得到的值代回到 \(f(x_1,x_2,...,x_m)\)，得到的结果即为在 \(h_i(x_1,x_2,...,x_m)\) 等式约束下的极值。

注意：\(\lambda\ge 0\)

例：已知 \(4x^2+y^2+xy=1\)，求 \(2x+y\) 的最大值。

解：

设二元函数 \(f(x,y)=2x+y\)，约束条件 \(h(x,y)=4x^2+y^2+xy-1=0\)。

构造拉格朗日函数 \(L(x,y,\lambda)=2x+y+\lambda(4x^2+y^2+xy-1)\)

对 \(x,y,\lambda\) 求偏导得：

\[\begin{aligned} &\frac{\partial L}{\partial x}=2+8\lambda x+\lambda y\\ &\frac{\partial L}{\partial y}=1+2\lambda y+\lambda x\\ &\frac{\partial L}{\partial \lambda}=4x^2+y^2+xy-1 \end{aligned} \]

令以上三者均为 \(0\)，得方程组：

\[\left\{ \begin{aligned} 2-8\lambda x-\lambda y=0\\ 1-2\lambda y-\lambda x=0\\ 4x^2+y^2+xy-1=0 \end{aligned} \right. \]

解得

\[\left\{ \begin{aligned} x=\frac{\sqrt{10}}{10}\\ y=\frac{\sqrt{10}}{5}\\ \lambda=\frac{\sqrt{10}}{5} \end{aligned} \right. \]

将
\( \left\{ \begin{aligned} x=\frac{\sqrt{10}}{10}\\ y=\frac{\sqrt{10}}{5} \end{aligned} \right. \) 带入到 \(f(x,y)\) 得 \(f(x,y)=2x+y=\dfrac{2\sqrt{10}}{5}\)

所以 \(2x+y\) 的最大值为 \(\dfrac{2\sqrt{10}}{5}\)

KKT

介绍

事实上这玩意有点复杂，涉及到向量啊超平面啊等乱七八糟的东西。在这里我们只讨论求解最大最小值的基本方法。

我们回过头看拉乘，发现他只能解决等式约束的极值。那么对于不等式约束，我们要如何求解极值？

KKT闪亮登场！

内容

设一函数 \(f(x)\)，求在一系列的等式约束 \(h_i(x)=0\) 与不等式约束 \(g_j(x)\leqslant 0\) 下的极值。其中 \(i\in [1,n],j\in [1,m]\)，\(n\) 为等式约束的数量，\(m\) 为不等式约束数量。

构造拉格朗日函数 \(L(x,\alpha_1,\alpha_2,...,\alpha_m,\lambda_1,\lambda_2,...,\lambda_n)=f(x,y)+\alpha_1g_1(x)+...+\lambda_1h_1(x)+...\)

对 \(x\) 求偏导并令其等于 \(0\)，再令 \(\alpha g(x)=0\)。全部联立起来可得方程组，解方程组再代回去即可。

注意，\(\alpha,\lambda\geqslant 0\)，且在解方程组的同时要记得讨论 \(\alpha\) 与 \(0\) 的关系。

当然，KKT也可以解决多元函数的问题，只是在后面多添几个未知数而已。为了简便我们这里只写一元函数。

不难看出，KKT本质是拉乘的推广。

例：求 \(f(x_1,x_2)=x_1^2-6x_1+9+x_2^2+2x_2+1\) 在 \(\left\{\begin{aligned}&x_1-x_2\geqslant 1\\&x_1+x_2\leqslant 2\end{aligned}\right.\) 约束下的最小值。

解：将约束转化为 KKT 的标准形式

\[\left\{ \begin{aligned} &g_1(x_1,x_2)=1-x_1+x_2\leqslant 0\\ &g_2(x_1,x_2)=x_1+x_2-2\leqslant 0 \end{aligned} \right. \]

并构造拉格朗日函数 \(L(x_1,x_2,\alpha _1,\alpha _2)=f(x_1,x_2)+\alpha _1g_1(x_1,x_2)+\alpha _2g_2(x_1,x_2)\)，分别对 \(x_1\) 和 \(x_2\) 求偏导可得

\[\left\{ \begin{aligned} &2x_1-6-\alpha _1+\alpha _2=0\\ &2x_2+2+\alpha _1+\alpha _2=0 \end{aligned} \right. \]

令 \(\alpha g(x)=0\) 有

\[\left\{ \begin{aligned} &\alpha _1(1-x_1+x_2)=0\\ &\alpha _2(x_1+x_2-2)=0 \end{aligned} \right. \]

下面就是根据上面的两个联立方程组对 \(\alpha _1\) 与 \(\alpha _2\) 的符号进行分类讨论，需要注意的是 KKT 是拉格朗日问题的推广，仍然满足 \(\alpha _1,\alpha _2\geqslant 0\)：

若 \(\alpha_1>0\) 且 \(\alpha_2>0\)，则有

\[\left\{ \begin{aligned} &1-x_1+x_2=0\\ &x_1+x_2-2=0 \end{aligned} \right. \]

解得 \(\left\{\begin{aligned}&x_1=\dfrac{3}{2}\\&x_2=\dfrac{1}{2}\end{aligned}\right.\)，回代进另一个方程组有

\[\left\{ \begin{aligned} &-\alpha _1+\alpha _2=3\\ &\alpha _1+\alpha _2=-3 \end{aligned} \right. \]

可得 \(\alpha _2=0\)，与假设矛盾，舍去；

若 \(\alpha_1>0\) 且 \(\alpha _2=0\)，则有

\[\left\{ \begin{aligned} &1-x_1+x_2=0\\ &2x_1-6-\alpha _1=0\\ &2x_2+2+\alpha _1=0 \end{aligned} \right. \]

解得 \(\alpha _1=-3\)，与假设矛盾，舍去；

若 \(\alpha_1=0\) 且 \(\alpha_2>0\)，则有

\[\left\{ \begin{aligned} &x_1+x_2-2=0\\ &2x_1-6+\alpha _2=0\\ &2x_2+2+\alpha _2=0 \end{aligned} \right. \]

解得 \(\alpha _2=0\)，与假设矛盾，舍去；

若 \(\alpha _1=0\) 且 \(\alpha _2=0\)，显然假设可以成立，则有

\[\left\{ \begin{aligned} &2x_1-6=0\\ &2x_2+2=0 \end{aligned} \right. \]

解得 \(\left\{\begin{aligned}&x_1=3\\&x_2=-1\end{aligned}\right.\)，此即为 \(f(x_1,x_2)\) 取得最小值时的解。
综上所述，\(f(x_1,x_2)=x_1^2-6x_1+9+x_2^2+2x_2+1\) 在 \(\left\{\begin{aligned}&x_1-x_2\geqslant 1\\&x_1+x_2\leqslant 2\end{aligned}\right.\) 约束下的最小值为 \(f(3,-1)=0\)。