信息论
香农熵：
\[\begin{split} H(P)&=\mathbb{E}_{x\sim P}[I(x)]=-\mathbb{E}_{x\sim P}[\log P(x)]\\ &=-\int P(x)\log P(x) dx \end{split}\]KL散度：
\[\begin{split} D_{KL}(P\|Q)&=\mathbb{E}_{x\sim P}\left[\log\frac{P(x)}{Q(x)}\right]=\mathbb{E}_{x\sim P}\left[\log P(x)-\log Q(x)\right]\\ &=\int P(x)[\log P(x)-\log Q(x)]dx \end{split}\]交叉熵：
\[\begin{split} H(P,Q)&=H(P)+D_{KL}(P\|Q)=-\mathbb{E}_{x\sim P}[\log Q(x)]\\ &=-\int P(x)\log Q(x)dx \end{split}\]凸优化
KKT方法
一般来说，优化问题总会带有约束。为了在可行域$\mathbb{S}$优化函数$f(\bm{x})$，KKT(Karush-Kuhn-Tucker)方法是十分常用的。如果$\mathbb{S}$被若干等式以及不等式限制，用该方法就可以得到$f$取最优解的必要条件。以下假设我们要求$f(\bm{x})$的最小值。
可行域$\mathbb{S}$由若干等式约束与不等式约束组成：
\[\mathbb{S}=\lbrace\bm{x}\mid\forall i,g^{(i)}(\bm{x})=0 \text{ and }\forall j,h^{(j)}(\bm{x})\leq 0\rbrace\]对于每一个约束引入变量$\lambda_i,\alpha_j$，这些变量被称为KKT乘子
我们的优化目标函数被称为广义Lagrangian
\[L(\bm{x},\bm{\lambda},\bm{\alpha})=f(\bm{x})+\sum_i\lambda_ig^{(i)}(\bm{x})+\sum_j\alpha_jh^{(j)}(\bm{x})\]对于$\bm{x}$的约束减弱为：只要存在一个可行点并且$f(\bm{x})$不允许取到$\infty$，那么
\[\min_{\bm{x}}\max_{\bm{\lambda}}\max_{\bm{\alpha},\bm{\alpha}\geq 0}L(\bm{x},\bm{\lambda},\bm{\alpha})\tag{1}\label{lag}\]与原优化目标函数
\[\min_{\bm{x}\in\mathbb{S}}f(\bm{x})\]有相同的最优目标函数值和最优点集$\bm{x}$
原理分析
如果某个$\bm{x}$不满足约束$g^{(i)}(\bm{x})=0,h^{(j)}(\bm{x})\leq 0$之一，那就可以选择与$g^{(i)}(\bm{x})$同号并且绝对值充分大的$\lambda_i$，或者选择充分大的$\alpha_j$。这样会导致
\[\max_{\bm{\lambda}}\max_{\bm{\alpha},\bm{\alpha}\geq 0}L(\bm{x},\bm{\lambda},\bm{\alpha})=+\infty\]从而$\eqref{lag}$绝不可能在$f(\bm{x})$不为$\infty$时取到最小值。因此，$\eqref{lag}$的结果是满足约束的。
求解过程
假设$f(\bm{x}),\bm{x}\in\mathbb{S}$的一个极小值点为$\bm{x}^\ast$，那么很容易推出$\nabla_{\bm{x}}f(\bm{x}^\ast)=0$，那么我们能不能直接也让$\nabla_{\bm{x}} L(\bm{x},\bm{\lambda},\bm{\alpha})=0$，然后求解就完事了呢，显然没那么简单，因为这根本没考虑$\mathbb{S}$的限制。
为了分析KKT乘子带来的影响，我们首先看一下等式约束的情况。
由于$\eqref{lag}$中的$\bm{\lambda}$可以任意取值，实际上每个$g^{(i)}(\bm{x})$只能为0。因此这里对$\bm{\lambda}$的最优化导致的结果实际上与原来的等式约束是完全等价的。我们可以放心的加上条件$\nabla_{\lambda_i}L(\bm{x},\bm{\lambda},\bm{\alpha})=g^{(i)}(\bm{x})=0$
然而不等式约束就不再是如此简单。
-
假设对某个$\bm{x}^\ast$有$h^{(j)}(\bm{x}^\ast)<0$，即该极小值点在不等式约束的内部（不含边界）。那么即使去掉这个约束，直接令$\nabla_{\bm{x}} f(\bm{x})=0$也是可以找到这个解的。不过我们现在要优化的是$L$，那么就要消除本来不在目标函数中的$h^{(j)}(\bm{x})$的影响，即令$\alpha_j=0$。
-
如果$h^{(j)}(\bm{x}^\ast)=0$，即该极小值点在不等式约束的边界上，那么就麻烦了。在$\bm{x}^\ast$的邻域内，可能有在边界之外的点使得$f$更小（也可能没有）。换言之这个极小值点可能是由不等式约束给卡出来的，如果去掉这个约束，极小值点会向着约束边界之外移动。
但无论如何都有$\alpha_jh^{(j)}(\bm{x})=0$，即$\bm{\alpha}\odot \bm{h}(\bm{x})=0$
综上，我们的条件为
- 广义Lagrangian的梯度为0
- 所有关于$\bm{x}$和KKT乘子的约束都满足
- 不等式约束所显示的“互补松弛性”：$\bm{\alpha}\odot \bm{h}(\bm{x})=0$
注意
:由于这里的条件都只让梯度为0，因而求出来的只是驻点而非极值点，即只能保证求出的所有解都是原始目标函数的驻点。如果真的要求极小值点还需要有一个局部凸的条件：$\nabla_{\bm{xx}} L(\bm{x},\bm{\lambda},\bm{\alpha})$正定。
KKT方法实质上统一求解了两类驻点（全局的、由不等式约束产生的）。
This work is licensed under a
Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International license.
