🧑‍🏫我们以一个简单的等式约束优化问题为例

\begin{aligned} minf(x,y)\\ s.t.\quad h(x,y)=0 \end{aligned}

Pasted image 20240212183354.png ✔等值线与 $h(x,y)$ 相交的所有点都是满足约束的点（若 $f(x,y)$ 的值域为实数值域，则实际上等值线有无数条，在这种情况下 $h(x,y)$ 上的点都是满足约束的点）但极值点只有可能在等值线与函数图像相切的地方取到，若在相交的地方取到，那么沿着 $h(x,y)$ 的图像往前走或者往后走，一定还有其它的等值线与它相交，也就是 $f(x,y)$ 的值还可以变小或变大

此时，在相切点处，目标函数和约束的梯度线性相关（方向相反，大小成倍数关系）（若干个约束在空间中可构成或者相交处出一个新的约束，不用管这个约束的实际表达式是怎样的，也不用管这个约束在空间中的几何形式，我们可以知道的是，这“一组”约束既然与目标函数存在相切点，那么这“一组”约束中的各个约束必然在这一点处与目标函数都相切，因此各个约束的梯度必然都与目标函数在这一点的梯度共线，只是大小不同），若等式约束有若干个，目标函数梯度在若干等式约束张成的空间中，有：

\begin{aligned} \nabla{f}=\sum_{i}\lambda_{i}\nabla{h_i} \end{aligned}

移项合并，同时结合必须满足的约束条件，有：

\begin{aligned} \nabla{f}-\sum_{i}\lambda_{i}\nabla{h_i}=0 \\ h_i(x,y)=0 \end{aligned}

此时我们已经得到拉格朗日乘子法的标准条件形式，但记住拉格朗日乘子法的相关条件为极值点的必要而非充分条件

❗拉格朗日乘子法无法生效的情况：由本目录下微分与梯度一节中的证明可知，切点处的梯度表达式为：

(\displaystyle\frac{\partial{f}}{\partial{x}},\displaystyle\frac{\partial{f}}{\partial{y}})

而该梯度向量的“斜率”表达式为：

\displaystyle\frac{\displaystyle\frac{\partial{f}}{\partial{y}}}{\displaystyle\frac{\partial{f}}{\partial{x}}}=\displaystyle\frac{f'_y}{f'_x}

若多元函数的其中某个维度的偏导数为0，则可以将其自变量和因变量互换，不影响上式成立，但如果全部维度的偏导数都为0，那么此时拉格朗日乘数法失效

📋上述情况都是约束为等式约束，若存在不等式约束：

\begin{aligned} minf(x,y)\\ s.t.\quad h(x,y)=0\\ g(x,y)\leq0 \end{aligned}

KKT条件

为了便于推导理解，我们将同时含有等式约束和不等式约束的问题拆分成两部分：

目标函数保持不变，约束条件仅包含不等式约束
在上述的基础上，添加等式约束（按拉格朗日乘子法添加）目标函数取最优值的情况分为两种：
1. 最优值在可行域内部取到，如上左图所示，此时不等式约束相当于不存在，问题退化为无约束问题
2. 最优值在可行域边界取到，如上右图所示，此时不等式约束为等式约束

对于第1种情况，由于不等式约束不存在，直接对等式约束采用拉格朗日乘子法

\begin{aligned} \nabla{f}+\sum_{i}\lambda_{i}\nabla{h_i}+\sum_{i}\mu_{i}\nabla g_{i}=0 \\ h_i(x,y)=0\\ g_i(x,y)\leq0\\ \mu_{i}=0 \end{aligned}

对于第2种情况，所有约束都转变为等式约束，故直接采用拉格朗日乘子法即可：

\begin{aligned} \nabla{f}+\sum_{i}\lambda_{i}\nabla{h_i}+\sum_{i}\mu_{i}\nabla g_{i}=0 \\ h_i(x,y)=0 \\ g_i(x,y)=0\\ \mu_{i}\geq0 \end{aligned}

此时不等式约束的乘子 $\mu$ 取0 ❓为什么 $\mu_{i}\geq0$ ？——>以上图为例， $g_{i}(x)$ 的梯度必然指向不可行域，而 $f(x,y)$ 的梯度指向可行域，故两个梯度的方向必然相反，乘子（即梯度系数）若取负数，则两个梯度会变为同向

综合以上两种情况，可归纳出KKT条件如下：

\begin{aligned} \nabla{f}+\sum_{i}\lambda_{i}\nabla{h_i}+\sum_{i}\mu_{i}\nabla g_{i}=0 \\ h_i(x,y)=0\\ \mu_{i}g_i(x,y)=0\\ g_i(x,y)\leq0\\ \mu_{i}\geq0 \end{aligned}

线性/非线性优化问题的极值点一定满足该方程组（KKT条件为优化问题极值点的必要条件）

Slater条件

以上介绍的内容为拉格朗日函数/对偶，其为解决非线性优化的重要方法，解决思路可根据拉格朗日松弛进行理解，但KKT方法只是必要条件，且不能保证强对偶性的成立如果原问题为凸优化问题，且存在至少一个定义域相对内部点使不等式约束严格满足（即严格小于/大于），则该问题满足Slater条件，此时强对偶性成立 ❗此时KKT条件即是最优性的充要条件 🌎KKT、Slater、凸优化之间的关系如下： Pasted image 20240215152315.png