拉格朗日乘子法和（对偶性与KKT条件）

https://blog.csdn.net/weixin_37688445/article/details/79275526
https://www.matongxue.com/madocs/939.html
https://www.matongxue.com/madocs/987/

拉格朗日乘子法（约束条件为等式）

$\begin{cases} min f(x) \\ \\ h_i(x)=0，i=0，1，...，n \end{cases}$

在两个图线外相切的时候达到最小值，法向量方向相反

$\begin{cases} \nabla f(x)=-\nabla \lambda*h_i(x) => \nabla f(x)+\nabla \lambda*h_i(x)=0\\ \\ h_i(x)=0，i=0，1，...，n \end{cases}$

最终表达式：

$\begin{cases} L(x,a)=min[f(x)+\sum_{i=1}^{n}a_ih_i(x)] \\ h_i(x)=0，i=0，1，...，n \end{cases}$

求解： $\nabla_xL(x,a)=0$ 还有 $\nabla_aL(x,a)=0$ 可得最优解的x和a

image.png

拉格朗日的KKT条件

初试条件：

$\begin{cases} min f(x) \\ \\ g(x) <= 0 \end{cases}$

推导出来的最终公式：

$\begin{cases} 式1： L(x,a)=min[f(x)+\lambda*g(x)]\\ 式2： g(x) = 0 \\ 式3：\lambda>0 \end{cases}$

情况1：如果可行解直接落在约束条件范围内，即落在g(x)<0的范围内，则直接删掉约束条件即可。（但是最优点依旧满足前提：公式1即使两条线在 $r_f$ ≈0的时候不相交）
情况2：如果可行解落在约束条件外，则最优解在边界上去的，即在g(x)=0的曲线上取得。（此时转换为前面讲的等式条件下求最优解的问题，直接套上面的公式）

image.png

以上两种状况要么落在约束区域内，则 $\lambda_解$ =0，因为直接去掉约束条件即可，要么落在约束条件边界上，则 $g(x)_解=0$ , 综合起来就是 $\lambda*g(x)=0$

还有一个问题就是 $\lambda$ 的取值问题，当 $\lambda$ 不等于0的时候，即最优解在 $g(x)=0$ 上取得时， $f(x,y)$ 梯度方向必须要和 $g(x)=0$ 的梯度方向相反，即 $-\nabla_xf(x)=\lambda\nabla_xg(x)$ ，所以 $\lambda$ 一定大于0，要不然就恒非零了。

image.png

注：什么是 $\max_{a,\beta:a>=0}\min_{x}L(x,a,\beta)$ ？

在 $a$ 和 $\beta$ 不变的情况下，求得一个 $x$ 使得 $L$ 的值最小，然后球的一个 $a>=0$ 和 $\beta$ 使得L最大。

拉格朗日对偶性：（ $\lambda$ 改为a表示）

原始最优化问题：

$\begin{cases} 式1： \min_{x \in R^n} f(x)\\ \\ 式2： c_i(x)<=0 ， i=1，2，...，k \\ \\ 式3：h_j(x)=0 ，j=1，2，...，l \end{cases}$

$L(x,a,\beta)=f(x)+\sum_{i=1}^{k}a_ic_i(x)+\sum_{j=1}^{l}\beta_jh_j(x)$

极小极大问题：

$令\theta_P(x)=\max_{a,\beta:a_i>=0}L(x,a,\beta)$

如果 $i$ 和 $j$ 当中有一个不满足式2/式3条件，那么必然存在某个 $i$ 满足 $c_i(x)>0$ ，可令 $a_i->+\infty$ ，或者存在某个 $j$ 满足 $h_j(x) \ne 0$ ，则可令 $\beta_jh_j(x)\rightarrow +\infty$ ，而将其余各个 $a_i$ ， $\beta_j$ 均取为 $0$ ，使得 $\theta_P(x)=+\infty$

所以max化的拉格朗日函数 $\theta_P(x)=\begin{cases} f(x) ， x满足原始问题约束\\ +\infty ，其他 \end{cases}$

接着考虑max条件下的min最优值：
$p^*=min \theta_P(x)=\min_{x} \max_{a,\beta:a_i>=0} L(x,a,\beta)$

极大极小问题：

$\max_{a,\beta}\theta_D(a,\beta)=\max_{a,\beta}\min_{x}L(x,a,\beta)，a_i>=0$

最优解： $d^*=\max_{a,\beta:a_i>=0}\theta_D(a,\beta)$

极大极小问题与极小极大问题的解什么时候相等？

maxmin和minmax的最优解有以下大小关系：
$d^*=\max_{a,\beta:a_i>=0}\min_{x}L(x,a,\beta)<=\min_{x} \max_{a,\beta:a_i>=0} L(x,a,\beta)=p^*$

如果满足 $f(x)$ 和 $c_i(x)$ 是凸函数， $h_j(x)$ 是仿射函数，和KKT条件，则：
$d^*=L(x^*,a^*,\beta^*)=p^*$

KKT条件是 $d^*=p^*$ 的充要条件
$\nabla_xL(x^*,a^*,\beta^*)=0$

$a_i^*c_i(x^*)=0，i=1,2,...,k$

$c_i(x^*)<=0 ，i=1,2,...,k$

$a_i^*>=0 ， i=1,2,...,k$

$h_j(x^*)=0，j=1，...，l$

KKT条件是啥？

对于 $\begin{cases} \min_{x}f(x)\\\\ g_i=0 \\\\ h_i\le 0 \end{cases}$

有 $\begin{cases} \nabla f(x)+\sum_{i=1}^{N}\lambda_i\nabla g_i+\sum_{i=1}^{M}u_j\nabla h_j=0 \\ g_i=0 \\ h_i \le 0 \\ u_j \ge 0 \\ u_jh_j=0 \end{cases}$