[机器学习笔记#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. \quad g(x)=0 $$ 由于这里我们预先假设\(f(x)\)是一个凸函数（convex function），当不存在限制条件时，其最大值当取在使得\(\nabla f(x)=0\)处。而存在限制条件时，表示x在定义域中的位置必须落在曲面\(g(x)=0\)上，可想象为x在该曲面表面滑动，直到找到使得\(f(x)\)最大的位置时停止。

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

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

以下借用PRML中的一个例子，令： $$ \textbf{x}=(x_1,x_2), \ \ f( \textbf{x})=1-x_1^2-x_2^2, \ \ g(\textbf{x})=x_1+x_2-1=0 $$
即如下图示：
所以： $$L(\textbf{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)\geq0\)的条件下，x的最优值使得\(f(x)\)的值最小/最大。

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

所以分两种情况考虑：

1. x 取在 \(g(x)>0\)的腔体内，此时问题跟无限制条件时无区别，所以是求解\( \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) \geq0
$$ $$ \lambda \geq0 $$ $$ \lambda g(x)=0 $$ 上述条件被称为 Karush-Kuhn-Tucker 条件，简称 KKT 条件。注意这里是针对 maximization的情况，如果是 minimization， 则拉格朗日方程变为 \(L(x,\lambda)=f(x)-\lambda g(x)\) （原因自己想，提示：当最优解在曲线表面时，即情况2，\( \nabla f(x)\) 应该朝着哪个方向？）。

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