库恩-塔克条件学习笔记

1. 非负约束

单变量：
$$
Max\ \pi=f(x_1)\\
s.t.\ x_1\ge 0
$$
要满足最大值，必须满足以下三个条件中的一个：
$$
f'(x_1)=0\ 且\ x_1>0\\
f'(x_1)=0\ 且\ x_1=0\\
f'(x_1)<0\ 且\ x_1=0
$$
以上三个条件可以合并为：
$$
f'(x_1)\le0,\ x_1\ge 0\ 且\ x_1f'(x_1)=0
$$
当多变量时，对于：
$$
Max\ \pi=f(x_1,x_2,\cdots,x_n)\\
s.t.\ x_j\ge 0,\ (j=1,2,\cdots,n)
$$
有：
$$
f_j\le0,\ x_j\ge 0\ 且\ x_jf_j=0,\ (j=1,2,\cdots,n)
\tag{1.1}
$$

2. 不等式约束效应

对于三变量两约束的情形：
$$
Max\ \pi=f(x_1,x_2,x_3)\\
s.t.\ g^1(x_1,x_2,x_3)\le r_1\\
g^2(x_1,x_2,x_3)\le r_2\\
且\ x_1,x_2,x_3\ge 0
\tag{2.1}
$$
引入两个虚拟变量\(s_1,s_2\)，使得上述不等式转化为等价情形：
$$
Max\ \pi=f(x_1,x_2,x_3)\\
s.t.\ g^1(x_1,x_2,x_3)+s_1 = r_1\\
g^2(x_1,x_2,x_3)+s_2 = r_2\\
且\ x_1,x_2,x_3\ge 0
\tag{2.1′}
$$
如果写成拉格朗日函数有（暂不考虑非负条件）：
$$
Z’=f(x_1,x_2,x_3)+\lambda_1[r_1-g^1(x_1,x_2,x_3)-s_1]+\lambda_2[r_2-g^2(x_1,x_2,x_3)-s_2]
\tag{2.2}
$$

可以得到常规的一阶条件：
$$
\frac{\partial Z’}{\partial x_1}=\frac{\partial Z’}{\partial x_2}=\frac{\partial Z’}{\partial x_3}=\frac{\partial Z’}{\partial s_1}=\frac{\partial Z’}{\partial s_2}=\frac{\partial Z’}{\partial \lambda_1}=\frac{\partial Z’}{\partial \lambda_2}=0
$$

但因为\(x_1,x_2,x_3,s_1,s_2\)都必须是非负的，由公式\((1.1)\)可得：
$$
\frac{\partial Z’}{\partial x_j}\le 0,\ x_j\ge 0\ 且\ x_j\frac{\partial Z’}{\partial x_j}=0\\
\frac{\partial Z’}{\partial s_i}\le 0,\ s_i\ge 0\ 且\ s_i\frac{\partial Z’}{\partial s_i}=0\\
\frac{\partial Z’}{\partial \lambda_i}=0\\
(i=1,2\ \ j=1,2,3)
\tag{2.3}
$$

由于\(\frac{\partial Z’}{\partial s_i}=-\lambda_i\)，公式\((2.3)\)第二行可以转化为：
$$
s_i\ge 0,\ \lambda_i\ge 0\ 且\ s_i\lambda_i=0
\tag{2.4}
$$
又因为\(\frac{\partial Z’}{\partial \lambda_i}=0\)可知\(s_i=r_i-g^i(x_1,x_2,x_3)\)，代入\((2.4)\)得：
$$
r_i-g^i(x_1,x_2,x_3)\ge 0,\ \lambda_i \ge 0\ 且\ [r_i-g^i(x_1,x_2,x_3)]\lambda_i=0
$$
因此公式\((2.3)\)可在消去\(s_i\)的情况下重写为：
$$
\frac{\partial Z’}{\partial x_j}=f_j-(\lambda_1g_j^1+\lambda_2g_j^2)\le 0,\ x_j\ge 0\ 且\ x_j\frac{\partial Z’}{\partial x_j}=0\\
r_i-g^i(x_1,x_2,x_3)\ge 0,\ \lambda_i \ge 0\ 且\ [r_i-g^i(x_1,x_2,x_3)]\lambda_i=0
\tag{2.5}
$$

公式\((2.5)\)就是公式\((2.1)\)的库恩-塔克条件（的一种形式）。在知道此结果的情况下，我们发现\((2.1)\)可以在不引入\(s_i\)的情况下推出公式\((2.5)\)。

构造拉格朗日函数的经典形式：
$$
Z=f(x_1,x_2,x_3)+\lambda_1[r_1-g^1(x_1,x_2,x_3)]+\lambda_2[r_2-g^2(x_1,x_2,x_3)]
\tag{2.6}
$$
然后，

1. 令偏导数\(\partial Z/\partial x_i\le 0\)，但\(\partial Z/\partial\lambda_i\ge 0\)；
2. 给\(x_j\)和\(\lambda_i\)施加非负约束；
3. 要求每个变量和\(Z\)对这些变量的偏导数之间要存在松弛互补，即，要求它们的乘积为零。

得到结果：
$$
\frac{\partial Z}{\partial x_j}=f_j-(\lambda_1g_j^1+\lambda_2g_j^2)\le 0,\ x_j\ge 0\ 且\ x_j\frac{\partial Z}{\partial x_j}=0\\
\frac{\partial Z}{\partial \lambda_j}=r_i-g^i(x_1,x_2,x_3)\ge 0,\ \lambda_i \ge 0\ 且\ \lambda_i\frac{\partial Z}{\partial \lambda_j}=0
\tag{2.7}
$$

例题1

有消费者效用最大化问题
$$
Max\ U=U(x,y)\\
s.t.\ P_xx+P_yy\le B\\
x\le X_0\\
且x,y\ge 0
$$
构造拉格朗日函数：
$$
Z=U(x,y)+\lambda_1(B-P_xx-P_yy)+\lambda_2(X_0-x)
$$
库恩-塔卡条件为：

\(
Z_x=U_x-P_x\lambda_1-\lambda_2\le0,\ x\ge0,\ 且\ xZ_x=0\\\\
Z_x=U_x-P_y\lambda_1\le0,\ y\ge0,\ 且\ yZ_y=0\\\\
Z_{\lambda_1}=B-P_xx-P_yy\ge0,\ \lambda_1\ge0\ 且\ \lambda_1Z_{\lambda_1}=0\\\\
Z_{\lambda_2}=X-x_0\ge0,\ \lambda_2\ge0\ 且\ \lambda_2Z_{\lambda_2}=0\)

对于第三行\(\lambda_1Z_{\lambda_1}=0\)，有：

$$
B-P_xx-P_yy=0,\ 或\ \lambda_1=0
$$
如果把\(\lambda_1\)解释为预算的边际效用，且预算有盈余，那么\(\lambda_1=0\)。

对于第四行\(\lambda_2Z_{\lambda_2}=0\)，有
$$
X-x_0=0,\ 或\ \lambda_2=0
$$
如果把\(\lambda_2\)解释为放送约束的边际效用，且配额约束没有被完全满足，那么\(\lambda_2=0\)。

数字实例：
$$
Max\ U=xy\\
s.t.\ x+y\le 100\\
x\le 40\\
且\ x,y\ge 0
$$
拉格朗日函数为：
$$
Z=xy+\lambda_1(100-x-y)+\lambda_2(40-x)
$$
库恩-塔克条件为：
\(
Z_x=y-\lambda_1-\lambda_2\le 0,\ x\ge 0\ 且\ xZ_x = 0\\\\
Z_y=x-\lambda_2\le 0, \ y\ge0,\ 且\ yZ_y=0\\\\
Z_{\lambda_1}=100-x-y\ge 0, \lambda_1\ge 0\ 且\lambda_1Z_{\lambda_1}=0\\\\
Z_{\lambda_2}=40-x\ge0,\ \lambda_2\ge 0\ 且\ \lambda_2Z_{\lambda_2}=0
\)

试错法求解：通过假设变量为零，消除某些项来简化。

因为假设\(x,y\)等于0没有意义，所以假设\(x,y\)都是非零的。

此时：
$$
y-\lambda_1-\lambda_2=x-\lambda_2(=0)
$$
所以：
$$
y-\lambda_2=x
$$
假设配额没有被用尽，此时\(\lambda_2=0\)，那么有\(x=y\)。代入预算约束得：\(x=y=50\)，与\(x\le40\)矛盾。

那么必须采用另一个假设，即\(x^*=40\)，配额约束完全满足，那么\(y^*=60\)。此时\(\lambda_1^*=40\)和\(\lambda_2^*=20\)。

3. 库恩-塔克条件的更一般情形

n个变量、m个约束的情形，库恩-塔克条件简化为：
$$
\frac{\partial Z}{\partial x_j}\le0,\ x_j\ge0\ 且\ x_j\frac{\partial Z}{\partial x_j}=0,\space(极大化)\\
\frac{\partial Z}{\partial \lambda_i}\le0,\ \lambda_i\ge0\ 且\ \lambda_i\frac{\partial Z}{\partial \lambda_i}=0\\
(i=1,2,\cdots,m\\\space j=1,2,\cdots,n)
\tag{3.1}
$$
对于极小化问题，有类似的：
$$
\frac{\partial Z}{\partial x_j}\ge0,\ x_j\ge0\ 且\ x_j\frac{\partial Z}{\partial x_j}=0,\space(极小化)\\
\frac{\partial Z}{\partial \lambda_i}\le0,\ \lambda_i\ge0\ 且\ \lambda_i\frac{\partial Z}{\partial \lambda_i}=0\\
(i=1,2,\cdots,m\\\space j=1,2,\cdots,n)
\tag{3.2}
$$

例题2

求解极小化问题：
$$
Min C=(x_1-4)^2+(x_2-4)^2\\
s.t.\ 2x_1+3x_2\ge6\\
-3x_1-2x_2\ge -12\\
且\ x_1,x_2\ge0
$$
拉格朗日函数：
$$
Z=(x_1-4)^2+(x_2-4)^2+\lambda_1(6-2x_1-3x_2)+\lambda_2(-12+3x_1+2x_2)
$$
由\((3.2)\)得边际条件为：
$$
\frac{\partial Z}{\partial x_1}=2(x_1-4)-2\lambda_1+3\lambda_2\ge0\\
\frac{\partial Z}{\partial x_2}=2(x_2-4)-3\lambda_1+2\lambda_2\ge0\\
\frac{\partial Z}{\partial \lambda_1}= 6-2x_1-3x_2\le0\\
\frac{\partial Z}{\partial \lambda_2}=-12+3x_1+2x_2\le0
$$
再加上负约束和互补松弛条件。

试错法：

首先尝试\(\lambda_1>0,\lambda_2>0\),并检查两个约束条件对应的\(x_1,x_2\)的值。

由互补松弛条件得\(\partial Z/\partial \lambda_1=\partial Z/\partial \lambda_2=0\)，因此，
$$
2x_1+3x_2=6\\
3x_1+2x_2=12
$$
解得\(x_1=4\frac{4}{5},x_2=-1\frac{1}{5}\)，违反了非负约束。

接下来假设\(x_1>0,x_2>0\)，由互补松弛条件得\(\partial Z/\partial x_1=\partial Z/\partial x_2=0\)，得到：
$$
2(x_1-4)-2\lambda_1+3\lambda_2=0\\
2(x_2-4)-3\lambda_1+2\lambda_2=0
$$
消去\(\lambda_2\)得到
$$
4x_1-6x_2+5\lambda_1+8=0
$$
进一步假设\(\lambda_1=0\)，得到\(x_1-\frac{3}{2}x_2=-2\)。

再假设\(\lambda_2>0\)，有\(\partial Z/\partial \lambda_2=0\)，即\(3x_1+2x_2=12\)。

解方程组：
$$
x_1-\frac{3}{2}x_2=-2\\
3x_1+2x_2=12
$$
得：\(x_1=2\frac{2}{13}>0,x_2=2\frac{10}{13}>0\)

回代得\(\lambda_1=0,\lambda_2=1\frac{16}{13}\)。

以上解均满足条件，故求得最终解。

另：

若上面消去的是\(\lambda_1\)，得到\(6x_1-4x_2+5\lambda_2-8=0\)；

进一步假设\(\lambda_2=0\)，得到\(\frac{3}{2}x_1-x_2=2\)；

再假设\(\lambda_1>0\)，有\(\partial Z/\partial \lambda_1=0\)，即\(2x_1+3x_2=6\)；

解方程组：
$$
\frac{3}{2}x_1-x_2=2\\
2x_1+3x_2=6
$$
得\(x_1=\frac{24}{13},x_2=\frac{10}{13}\)

回代得\(\lambda_1=-\frac{28}{13},\lambda_2=0\)，不满足非负约束。

参考资料：《数理经济学的基本方法》——（美）蒋中一