#引言
在机器学习的算法理论推导中，在很多地方会用到拉格朗日乘数法，在支持向量机$SVM(Support Vector Machines) $ 的学习中，我们会接触到对偶问题和KTT条件问题。于是有必要将拉格朗日乘数法与它们内在的联系弄清楚。
约束最优化问题
假设$f(x)$，$c_i(x)$，$h_j(x)$是定义在$R^n$上的连续可微函数，考虑约束最优化问题：
$$\begin{align} \min \limits_{x \in R^n} &f(x) \newline s.t. &c_i(x) \ge0,i=1,2,…,k \newline &h_j(x)=0,j=1,2,…,l \end{align}$$
现在如果不考虑约束条件，原始问题就是：
$$\min \limits_{x \in R^n}f(x)$$
如果其连续可微，利用高等数学的知识，对求导数，然后令导数为0，就可解出最优解，如果加上约束条件，那么就要考虑到使用条件极值来求解，拉格朗日乘数法就是来求解这种约束的极值的。
引进广义拉格朗日函数（generalized Lagrange function）:
$$L(x,\alpha,\beta) = f(x)+\sum_{i=1}^k \alpha_i c_i(x) + \sum_{j=1}^l \beta_j h_j(x)$$
其中 $x=(x^{(1)},x^{(2)},…,x^{(n)})^T \in R^n , \alpha_i,\beta_j$是拉格朗日乘子，并且 $\alpha_i \ge 0$
现在，我们知道$L(x,\alpha,\beta)$是关于$\alpha_i,\beta_j$的函数，那么通过确定$\alpha_i,\beta_j$的值使得$L(x,\alpha,\beta)$取得最大值(当然在求解的过程中$x$是常量)，确定了$\alpha_i,\beta_i$的值，就可以得到$L(x,\alpha,\beta)$的最大值。当$\alpha_i,\beta_i$确定时，$\max \limits_{\alpha,\beta:\alpha_i \ge 0} L(x,\alpha,\beta)$ 就只和$x$有关的函数了，定义这个函数为：
$$\theta_p(x) = \max \limits_{\alpha,\beta:\alpha_i \ge 0}L(x,\alpha,\beta)$$
其中：
$$L(x,\alpha,\beta) = f(x)+\sum_{i=1}^k \alpha_i c_i(x) + \sum_{j=1}^l \beta_j h_j(x)$$
下面通过$x$是否满足约束条件，通过两个层面来进行分析这个函数：
- 考虑到某个$x$违反了原始的约束，即$c_i(x)>0$或者$h_j(x) \not= 0$，那么：
$$\theta_p(x) = \max \limits_{\alpha,\beta:\alpha_i \ge 0}[f(x)+\sum_{i =1}^k \alpha_i c_j(x)+\sum_{j=1}^l \beta_jh_j(x)] = +\infty$$
注意中间最大化的式子就是确定$\alpha_i,\beta_j$的之后的结果，若$c_i(x) > 0$，则令$\alpha_i \to +\infty$，如果$h_j(x) \not= 0$，很容易取值$\beta_j$使得$\beta_jh_j(x) \to +\infty$ - 考虑$x$，满足原来的约束，则$\theta_p(x) = \max \limits_{\alpha,\beta:\alpha_i \ge 0}[f(x)] = f(x)$，注意中间的最大化是确定$\alpha_i,\beta_j$的过程，$f(x)$就是个常量，常量的最大值就是本身
通过上面可以得出：
$$\begin{eqnarray}f(x)=\begin{cases}f(x), &x满足原始问题的约束 \cr +\infty,&其他\end{cases}\end{eqnarray}$$
那么在满足约束条件下：
$$\min \limits_{x} \theta_p(x) = \min \limits_{x} \max \limits_{\alpha,\beta:\alpha_i \ge 0} L(x,\alpha,\beta) = \min \limits_{x}f(x)$$
即$\min \limits_{x} \theta_p(x)$与原始的优化问题等价，所以常用$\min \limits_{x} \theta_p(x)$代表原始问题，下表p表示原始问题，定义原始问题的最优值：
$$\hat{p} = \min \limits_{x} \theta_p(x)$$
对偶问题
定义关于$\alpha,\beta$的函数：
$$\theta_D(\alpha,\beta) = \min \limits_{x}L(x,\alpha,\beta)$$
等式的右边是关于$x$的函数的最小化，$x$确定后，最小值就只与$\alpha,\beta$有关了，所以是一个关于$\alpha,\beta$的函数。
考虑到极大化$\theta_D(\alpha,\beta) = \min \limits_{x}L(x,\alpha,\beta)$，即：
$$\max \limits_{\alpha,\beta:\alpha_i \ge 0} \theta_D(\alpha,\beta) = \max \limits_{\alpha,\beta:\alpha_i \ge 0} \min \limits_{x}L(x,\alpha,\beta)$$
这个就是原始问题的对偶问题，那么原始问题的表达式：
$$\min \limits_{x} \theta_p(x) = \min \limits_{x} \max \limits_{\alpha,\beta:\alpha_i \ge 0} L(x,\alpha,\beta)$$
从形式上来看很对称，只不过原始问题是先固定的$L(x,\alpha,\beta)$中的$x$，优化出的参数$\alpha,\beta$，在优化最优$x$，而对偶问题是先固定$\alpha,\beta$，优化出最优的$x$，然后确定参数$\alpha,\beta$
定义对偶问题的最优值：
$$\hat{d}= \max \limits_{\alpha,\beta:\alpha_i \ge 0}\theta_D(\alpha,\beta)$$
原始问题和对偶问题的关系
定理：若原始问题与对偶问题都有最优值，则
$$\begin{aligned} \hat{d} & = \max \limits_{\alpha,\beta:\alpha_i \ge 0} \min \limits_{x}L(x,\alpha,\beta) \newline &\le \min \limits_{x} \max \limits_{\alpha,\beta:\alpha_i \ge 0} L(x,\alpha,\beta) = \hat{p}\end{aligned}$$
证明：对任意的$\alpha,\beta$和$x$，有：
$$\theta_D(\alpha,\beta) = \min \limits_{x}L(x,\alpha,\beta) \le L(x,\alpha,\beta) \ \le \max \limits_{\alpha,\beta:\alpha_i \ge 0} L(x,\alpha,\beta) = \min \limits_{x} \theta_p(x)$$
即：$\theta_D(\alpha,\beta) \le \theta_p(x)$
由于原始问题与对偶问题都有最优值，所以：$\max \limits_{\alpha,\beta:\alpha_i \ge 0}\theta_D(\alpha,\beta) \le \min \limits_{x}\theta_p(x)$
即：$\hat{d} = \max \limits_{\alpha,\beta:\alpha_i \ge 0} \min \limits_{x}L(x,\alpha,\beta) \le \min \limits_{x} \max \limits_{\alpha,\beta:\alpha_i \ge 0} L(x,\alpha,\beta) = \hat{p} $
也就是说原始问题的最优值不小于对偶问题的最优值，但是我们要通过对偶问题来求解原始问题，就必须使得原始问题的最优值与对偶问题的最优值相等，于是可以得出下面的推论：
推论：设$\hat{x}$和$\hat{\alpha}，\hat{\beta}$分别是原始问题和对偶问题的可行解，如果$\hat{d}$ ，那么$\hat{x}$和$\hat{\alpha},\hat{\beta}$分别是原始问题和对偶问题的最优解。
所以，当原始问题和对偶问题的最优值相等：$\hat{d}=\hat{p}$ ，可以用求解对偶问题来求解原始问题（当然是对偶问题求解比直接求解原始问题简单的情况下），但是到底满足什么样的条件才能使得$\hat{d}=\hat{p}$，这就是KTT条件的来源
KTT条件
定理：对于原始问题和对偶问题，假设函数$f(x)$和$c_i(x)$是凸函数，$h_i(x)$是仿射函数(即由一阶多项式构成的函数，$f(x) =Ax+b$，A是矩阵，$x，b$是向量)；并且假设不等式约束$c_i(x)$是严格可行的，即存在$x$，对所有的$i$有$c_i(x) < 0$，则存在$\hat{x}$和$\hat{\alpha}，\hat{\beta}$，使得$\hat{x}$ 是原始问题的最优解，$\hat{\alpha}，\hat{\beta}$是对问题的最优解，并且$\hat{d}=\hat{p}=L(\hat{x},\hat{\alpha},\hat{\beta})$
定理：对于原始问题和对偶问题，假设函数$f(x)$和$c_i(x)$是凸函数，$h_i(x)$是仿射函数(即由一阶多项式构成的函数，$f(x) =Ax+b$，$A$是矩阵，$x，b$是向量)；并且假设不等式约束$c_i(x)$是严格可行的，即存在$x$，对所有的$i$有$c_i(x) < 0$，则$\hat{x}$和$\hat{\alpha},\hat{\beta}$分别是原始问题和对偶问题的最优解的充分必要条件是$\hat{x}$和$\hat{\alpha}，\hat{\beta}$，满足下面的$Karush-Kuhn-Tucker(KKT)$ 条件:
$$\begin{aligned} &\nabla _x L(\hat{x},\hat{\alpha},\hat{\beta}) =0\newline &\nabla _{\alpha}L(\hat{x},\hat{\alpha},\hat{\beta}) =0 \newline &\nabla _{\beta} L(\hat{x},\hat{\alpha},\hat{\beta}) =0\newline &\hat{\alpha_i}c_i(\hat{x})=0, i=1,2,…,k(KTT对偶互补条件)\newline &c_i(\hat{x}) \le 0,i=1,2…,k \newline &\hat{\alpha_i} \ge 0,i=1,2,…k \newline &h_j(\hat{x}) =0,j=1,2,…,l) \end{aligned}$$
关于KKT 条件的理解：前面三个条件是由解析函数的知识，对于各个变量的偏导数为0（这就解释了一开始为什么假设三个函数连续可微，如果不连续可微的话，这里的偏导数存不存在就不能保证），后面四个条件就是原始问题的约束条件以及拉格朗日乘子需要满足的约束。
特别注意当$\hat{\alpha_i}\ge 0$时，由KKT对偶互补条件可知：$c_i(\hat{x}) =0$，这个知识点会在$ SVM$ 的推导中用到.