优化 | KKT条件学习笔记：理论介绍、详细计算案例 ...

Karush–Kuhn–Tucker (KKT) 条件，或者叫Kuhn–Tucker (KT) 条件，是在满足约束正则条件下，一个非线性规划(Nonlinear programming, NLP)问题取得最优解的一阶必要条件(first derivative tests 或 first-order necessary conditions)。KKT条件最初以Harold W. Kuhn和Albert W. Tucker的名字命名，他们在1951年首次发表了这些条件。后来学者发现1939年William Karush已经在硕士论文中声明了必要条件。

综上，将 x_j 增加 \Delta ，NLP的目标函数 z 值约增加 \Delta\left[\frac{\partial f(\overline{x})}{\partial x_j}-\sum_{i=1}^{m}\overline{\lambda}_i\frac{\partial g_i(\overline{x})}{\partial x_j}\right] 如果括号中的值大于0，我们可以取 \Delta >0 以增加目标值；如果括号中的值小于0，我们可以取 \Delta <0 以增加目标值。因此，若要 \overline{\mathbf{x}} 最优，KKT条件中的 (2) 式必须成立。即 \\ \begin{eqnarray} \frac{\partial f(\overline{x})}{\partial x_j}{-}\sum\limits_{i=1}^{m}\overline{\lambda}_i\frac{\partial g_i(\overline{x})}{\partial x_j}=&0, \quad \forall j=1,\dots,n \end{eqnarray}  \\

\begin{eqnarray} &&\text{If}~\overline{\lambda}_i >0,~&\text{then}~g_i(\overline{x})=b_i\label{binding} \\ &&\text{If}~g_i(\overline{x})< b_i,~&\text{then}~\overline{\lambda}_i=0\label{nonbinding} \end{eqnarray}  

• (7) 表明第 i 条约束有约束力（binding），即如果额外一单位资源是有价值的，则当前最优解一定用完了可用的 b_i 单位资源。
  
• (8) 表明第 i 条约束无约束力（non-binding），即如果该约束对应的资源当前没有用完，则额外数量的该资源没有价值。
  

Theorem 2
对最大化NLP问题 (1) ，若 f(x) 为凹（concave）函数，且 g_1(x),\dots,g_m(x) 为凸（convex）函数，则任意满足Theorem 1条件的 \overline{x}=(\overline{x}_1,\overline{x}_2,\dots,\overline{x}_n) 都是 (1 ) 的最优解。
对最小化NLP问题 (2) ，若 f(x) 为凸函数，且 g_1(x),\dots,g_m(x) 为凸函数，则任意满足Theorem 1条件的 \overline{x}=(\overline{x}_1,\overline{x}_2,\dots,\overline{x}_n) 都是 (2) 的最优解。

求解如下NLP问题 \\ \begin{eqnarray*} \min z=&&e^{-x_1}+e^{-2x_2}\\ \mathbb{s.t.}\quad &&x_1+x_2\leqslant 1\\ &&x_1,x_2\geqslant 0 \end{eqnarray*} \\

可以看到，我们使用KKT条件，将一个带有目标函数的非线性规划，转化成了一个无目标函数的KKT方程组。一般情况下，该KKT方程组的解，就是原非线性规划的最优解。

• 若 \mu_1\neq 0,\mu_2\neq 0 ，从 (12),(13) 可得 x_1=0，x_2=0 ，带入 (11) 得 \lambda=0 ，然后由 (9),(10) 得 \mu_1=-1，\mu_2=-2 ，违反条件 (14) ;
  
• 若 \mu_1\neq 0,\mu_2= 0 ，从 (12) 可得 x_1=0 ，从 (10) 可知 \lambda=2e^{-2x_2}>0 ，又由于 11 ，可得 x_2=1 ，带入 (9) 得 \mu_1=2e^{-2}-1<0 ，违反条件 (14) ;
  
• 若 \mu_1= 0,\mu_2\neq 0 ，从 (13) 可得 x_2=0 ，从 (9) 可知 \lambda=2e^{-x_1}>0 ，又由于 (11) ，可得 x_1=1 ，带入 (10) 得 \mu_2=e^{-1}-2<0 ，违反条件 (14) ;
  
• 若 \mu_1= 0,\mu_2= 0 ，带入 (9),(10) 可得\\ \begin{aligned} &\lambda=e^{-x_1}   && (15)  \\ &\lambda=2e^{-2x_2}  && (16)  \\  \end{aligned}  \\ 都表明 \lambda>0 ，带入 (11) 得到 \\ \begin{aligned} &x_1+x_2=1  && (17)  \\  \end{aligned}  \\则由 (15)-(17) 解得 x_1=\frac{2-\ln{2}}{3} ， x_2=\frac{1+\ln{2}}{3} ， \lambda=2^{\frac{1}{1}}e^{-\frac{2}{3}} ，所有KKT条件都满足。
  

如果最优点 \overline{\mathbf{x}} 不满足约束规范（constraint qualification）或正则条件（regularity condition），KKT条件在 \overline{\mathbf{x}} 处可能不成立。

记 \overline{\mathbf{x}} 为 NLP (1) 或 (5) 的最优解，如果所有$g_i$连续，点$\overline{x}$处所有binding约束（包括有约束力的变量非负性约束）的梯度构成一组线性独立向量，则KKT条件在$\overline{\mathbf{x}}$处一定成立。

\\  \begin{aligned} \underset{x} \max  \underset{y} \min \quad & cx+dy \\ s.t.\quad  &Ax+By=b, \\ &x,y\geqslant 0. \end{aligned}  \\

\\  \begin{aligned} \min  \quad &\frac{1}{2}x^2+y^2-xy-2x-6y \\ s.t. \quad&x\geqslant 2y, \\ &x^2+\frac{1}{2}y\leqslant 2, \\ &2x+y\leqslant 3, \\ &x,y\geqslant 0. \end{aligned}  \\

1. Winston, Wayne & Goldberg, Jeffrey. Operations research: applications and algorithms. (2004).

2. Brezhneva, O.A., Tret’yakov, A.A. & Wright, S.E. A simple and elementary proof of the Karush–Kuhn–Tucker theorem for inequality-constrained optimization. Optim Lett 3, 7–10 (2009).

3. The Kuhn-Tucker and Envelope Theorems

4. Bazaraa, M., H. Sherali, and C. Shetty. Nonlinear Programming: Theory and Algorithms. New York: John Wiley, 1993.