参考：foundations of machine learning , appendix B

书里没考虑等式约束。

原始的优化问题：

\[\min \limits_{x} f(x)\] \[\text{subject to: } g_i(x)\leq0\]

拉格朗日函数：

\[F(x) = f(x)+\sum_{i}\alpha_i g_i(x)\] \[\text{subject to: }\alpha_i \leq 0\]

所以

\[f(x) \geq F(x)\]

设 \(p^*\leq f(x)\), \(q^*\leq F(x)\)

强对偶：

\[p^*=q^*\]

弱对偶：

\[p^*\leq q^*\]

接着引入

\[\begin{equation} \max\limits_{\alpha}\min\limits_{x}F(x) \label{maxmin} \end{equation}\]

符合公式$\ref{maxmin}$的$x$和$\alpha$，在两种情况下是鞍点（证明书上无）。

而鞍点有以下性质：是鞍点，即是原问题的解。

推导：

​ pass（书上有）

KKT条件：f,g都需要是可微凸函数，

\[\nabla_x \mathcal{L} = \nabla_x f(x)+\sum_i\alpha_i\nabla_x g(x) = 0\] \[\nabla_{\alpha_i} \mathcal{L} = g_i(x) \leq 0\] \[\sum_i \alpha_i g_i(x)=0\]

推导:

\[\begin{equation} \begin{split} f(x)-f(\bar{x})&\geq \nabla_x f(\bar{x})(x-\bar{x}) \text{ (f得是凸函数，还能可微)}\\ &=(-\sum_i\alpha_i\nabla_x g(x) )*(x-\bar{x})\\ &\geq -\sum_i\alpha_i (g(x)-g(\bar{x}) \text{ (p得是凸函数并且可微)}\\ &\geq -\sum_i\alpha_i g(x) \geq 0 \end{split} \end{equation}\]