To Be Continue~
共轭函数
假设 \(f: \mathbb{R}^n \rightarrow \mathbb{R}\)，函数 \(f^*: \mathbb{R} \rightarrow \mathbb{R}\)。若两函数满足：
\[f^*(y) = \underset{x \in dom f}{\sup} (y^Tx-f(x)) \]则 \(f^*\) 是 \(f\) 的共轭函数，共轭函数是使上式的上确界小于 \(\infty\) 的部分。可以理解为对于每一个确定的 \(y\)，\(y^Tx\) 都是一个线性函数，此时 \(y^Tx - f(x)\) 变为线性函数与原函数在 \(x\) 的定义域上的差值，这个差值即为 \(y^Tx - f(x)\) 的值域，若此时确定的 \(y\) 不能使值域的上确界小于无穷大，则不保留，反之则保留。所有保留的 \(y\) 构成共轭函数的定义域，而所有 \(y^Tx - f(x)\) 不是 \(\infty\) 的上确界构成共轭函数的值域。
易知共轭函数是凸函数
示例
- 放射函数：\(f(x) = ax +b\) 的共轭函数为：
观察易得，如果 \(y \ne a\) ，那么无论 \(y\) 取值多少，\(yx - ax -b\) 的上确界都是 \(\infty\)。但是当 \(y = a\) 时，\(yx - ax -b\) 为常数 \(-b\)，上确界为 \(-b\)，即此共轭函数定义域为 \(a\)，值域为 \(-b\)。
- 负对数函数：\(f(x) = -\log x\)的共轭函数为：
首先\(f^*(y)^{\prime\prime} \lt 0，\) 对于某一 \(y\) 有 \(f^*(y)^{\prime} = y + \frac{1}{x} = 0\) 时，共轭函数取得最大值，此时 \(x = -\frac{1}{y}\) 使得共轭函数取得上确界，即共轭函数简化为 \(f^*(y) = -\log(-y) - 1\)
拉格朗日乘子法
首先解释拉格朗日函数的形式的原因
由简单的二维形式，并且受到等式约束的例子出发
其中 \(g(x,y) = c\) 可以理解为等高线，即 \(z = g(x,y)\) 为三维曲面，当 \(z = c\) 时，可以想象为用平面 \(z = c\) 去截 \(z = g(x,y)\) 这个三维曲面所获得的曲线，而这条曲线上满足
\(g(x,y) = c\)。同理，如图蓝色线所示为三维曲面 \(f(x,y)\) 的各个等高线。如果没有约束，很显然最值会落到最小的圈里面。正是有了约束，\(x,y\) 需要同时在蓝色和绿色线上，那么最值点就应该是两条等高线相切的时候取得，因为如果仅仅是相交，就还在内部或者外部存在其他等高线使得取得的值更大或者更小，只有相切的时候，可能取得最优值。
很显然想要两者相切必然有 \(f(x,y)\) 与 \(g(x,y)=C\) 的梯度一定是平行，则有 \(\nabla f(x,y) = \lambda (g(x,y)-C)\)。所以就容易理解当拉格朗日函数 \(F(x,y) = f(x,y) + \lambda (g(x,y) -C)\) 取得极值时就等价于两者的梯度平行。特别地，当拉格朗日函数所有点满足等式约束 \(g(x,y)=C\) 时两个函数完全等价的。因此 \(F(x,y)\) 最优若等价于 \(f(x,y)\) 最优需要满足：
\[\begin{cases} F_x^{\prime} = 0 \\ F_y^{\prime} = 0 \\ g(x,y) = C \ \& \ \lambda \ne 0 \end{cases} \]事实上，这种做法等价于利用等式约束来进行换元后，变为无约束的情况，从而按照一般的求最值来求得最优解。
那么给出带约束的原问题的一般形式：
\[\begin{cases} &\min f(x,y) \\ &s.t. \quad m_i(x) = 0 \ (i=1,2,...,m), n_j(x) \le 0 \ (j=1,2,...,n) \end{cases} \]即既有等式约束又有不等式约束（不等式约束，可以将其想象为一个范围，而这个范围依然是有边界的，边界就是等式约束，取得最优点一般会在边界处），这样可以得到拉格朗日函数
\[L(x,\lambda,\nu)=f(x)+\sum_{i=1}^m \lambda_i m_i(x) + \sum_{j=1}^n \nu_j n_j(x) \]其中 \(\nu_j \ge 0 \quad n_j(x) \le 0\)
同理，若我们想要 \(L(x,\lambda,\nu)\) 与 \(f(x)\) 同时取得最优，需要满足等式约束，而不等式约束到达边界（即取到等号）或者 \(\nu=0\) 已到达消除不等式约束以及使得拉格朗日函数和原函数同时取得最优的目的。总结如下
\[\begin{cases} L_x^{\prime} = 0 \\ m_i(x) = 0 \ \& \ \lambda_i \ne 0 \\ \nu_j g_j(x) = 0 \end{cases} \]此时拉格朗日函数和原函数完全等价。所以进行如下推导：
\[\begin{aligned} \because &\sum_{j=1}^n \nu_j n_j(x) \le 0 \quad \sum_{i=1}^m \lambda_i m_i(x)=0 \\ & \max \sum_{j=1}^n \nu_j n_j(x) = 0 \\ \therefore &\underset{\nu}{\max} L(x, \nu) = f(x) \\ \therefore& \underset{x}{\min} \underset{\nu}{\max} L(x, \nu)=\underset{x}{\min} f(x) \end{aligned} \]整理一下便为 KKT 条件：
\[\begin{cases} \nu_j^* n_j(x^*)=0 \\ \nu_j^* \ge 0 \\ \frac{\partial L(x^*,\nu ^*)}{\partial x} = 0 \end{cases} \]弱对偶性的证明
若对偶性是指：
\[\underset{x}{\min}\underset{\lambda, \nu}{\max}L(x,\lambda,\nu) \ge \underset{\lambda, \nu}{\max}\underset{x}{\min}L(x,\lambda,\nu) \]这等价于证明“凤尾”是大于“鸡头”的。证明挺简单的如下：
\[\because \ \underset{x}{\min}L(x,\lambda,\nu) \le L(x,\lambda,\nu) \\ \therefore \ \underset{\lambda, \nu}{\max}\underset{x}{\min}L(x,\lambda,\nu) \le L(x,\lambda,\nu) \]上式先变化 \(x\) 使 \(L\) 变到 \(x\) 能使其变到的最小的一个域。在这个域里面 \(\lambda, \nu\) 是可以任意变化的，但即便 \(\lambda, \nu\) 变化使其达到最大值也只是 \(\underset{x}{\min}L(x,\lambda,\nu)\) 的顶端了。可 \(\underset{x}{\min}L(x,\lambda,\nu)\) 整个域的所有取值可能都比 \(L(x,\lambda,\nu)\) 小，所以有 \(\underset{\lambda, \nu}{\max}\underset{x}{\min}L(x,\lambda,\nu) \le L(x,\lambda,\nu)\)
同理：
证毕