[机器学习笔记#1]从 Logistic Regression 讲讲分类器和机器学习
[机器学习笔记#2] 一步步用 softmax Regression 实现手写字符识别
[资源分享]机器学习资料和常用工具汇总

（这次的笔记是为了以后的内容做准备，提前介绍一些基础数学知识，以便日后引用）

在机器学习中经常会遇到一类受限优化问题，要求某目标函数在限制条件下的最优值点。

最基本的一类问题可简述为：

问题1：给定目标函数 $f(x)$（假设convex），求当x取值满足$g(x)=0$的条件下，x的最优值使得$f(x)$的值最小/最大。

例如：
$$x=\underset{x}{argmax}f(x)$$ $$s.t.g(x)=0$$ 由于这里我们预先假设$f(x)$是一个凸函数（convex function），当不存在限制条件时，其最大值当取在使得$\mathrm{\nabla }f(x)=0$处。而存在限制条件时，表示x在定义域中的位置必须落在曲面$g(x)=0$上，可想象为x在该曲面表面滑动，直到找到使得$f(x)$最大的位置时停止。

我们可以非常自然的得到一个结论：满足此条件的位置$x_A$上，必然有$\mathrm{\nabla }f(x)=\lambda \mathrm{\nabla }g(x)$，其中$\lambda$是非零实变量，被称为拉格朗日乘数（Lagrange multiplier）。如下图所示（图片出自PRML P. 708）。
因为如果在此处$\mathrm{\nabla }f(x)$和$\mathrm{\nabla }g(x)$不共线，$\mathrm{\nabla }f(x)$将在该点有一个切向分量，x可沿该分量方向运动，到达一个使 $f(x)$ 更大的点（参考gradient ascend），最终会稳定在一个使得 $\mathrm{\nabla }f(x)$ 和$\mathrm{\nabla }g(x)$ 共线的位置。

所以可知求解问题1中的受限优化问题，等同于求解：
$$x,\lambda =\underset{x,\lambda }{argmax}L(x,\lambda )$$ $$L(x,\lambda )=f(x)+\lambda g(x),\lambda \ne 0$$ $$s.t.{\mathrm{\nabla }}_{x}L(x,\lambda )=0,{\mathrm{\nabla }}_{\lambda }L(x,\lambda )=0$$
其中$L(x,\lambda )$被称为拉格朗日方程。

以下借用PRML中的一个例子，令： $$\mathbf{\text{x}}=(x_1,x_2),f(\mathbf{\text{x}})=1-x_1^2-x_2^2,g(\mathbf{\text{x}})=x_1+x_2-1=0$$
即如下图示：
所以： $$L(\mathbf{\text{x}},\lambda )=1-x_1^2-x_2^2+\lambda (x_1+x_2-1)$$ 求导得：
$$-2x_1+\lambda =0$$ $$-2x_2+\lambda =0$$ $$x_1+x_2-1=0$$ 解得 $x_1=x_2=0.5$

问题2：给定目标函数 $f(x)$（假设convex），求当x取值满足$g(x)\ge 0$的条件下，x的最优值使得$f(x)$的值最小/最大。

例如：
$$x=\underset{x}{argmax}f(x)$$ $$s.t.g(x)\ge 0$$ 问题1中的等式变成了不等式，x的可能取值空间从曲面 $g(x)=0$ ，变成了 $g(x)\ge 0$所表示的内部空间j及表面，如下图：

所以分两种情况考虑：

1. x 取在 $g(x)>0$的腔体内，此时问题跟无限制条件时无区别，所以是求解$\mathrm{\nabla }f(x)=0$，等同于将拉格朗日方程中的$\lambda$设为0的情况；
2. x 取在 $g(x)=0$的曲面上，此时优化$f(x)$跟问题1无区别，使用拉格朗日方程求解。
   
   

整合起来就是求：
$$x,\lambda =\underset{x,\lambda }{argmax}L(x,\lambda )$$ $$L(x,\lambda )=f(x)+\lambda g(x)$$ 其中： $$g(x)\ge 0$$ $$\lambda \ge 0$$ $$\lambda g(x)=0$$ 上述条件被称为 Karush-Kuhn-Tucker 条件，简称 KKT 条件。注意这里是针对 maximization的情况，如果是 minimization， 则拉格朗日方程变为 $L(x,\lambda )=f(x)-\lambda g(x)$ （原因自己想，提示：当最优解在曲线表面时，即情况2，$\mathrm{\nabla }f(x)$ 应该朝着哪个方向？）。

KKT条件在SVM 的数学模型中有重要体现。