优化基础系列 - 3. 等式约束优化问题 -- Lagrange 乘子初探
1. 问题描述
这一讲关注以下等式约束优化问题 \[ \begin{align} \label{eq:pblm-2} &\min_{x \in \mathbb{R}^n} f(x) \\ &\text{ s.t. } g_i(x) = 0, i = 1, 2, \ldots, m \nonumber \end{align} \]
接下来讨论这三个问题最优解需要满足的必要条件。
2. 等式约束优化问题
这里需要关注：
引入了等式约束，问题就变了（从无约束优化问题变成了等式约束优化问题）
相应的，最优解需要满足的必要条件，也要发生改变（最优解不仅要满足驻点条件，还应该需要满足等式约束）
如何以一种更加本质并且更加统一的视角，将驻点条件和等式约束有机结合起来？这是这一部分讨论的出发点
2.1 错误思路：直接做问题转化
教科书讲的是：
引入 Lagrange 乘子，将等式约束引入到优化问题的目标函数中，将等式约束问题转化为以下无约束问题： \[ \begin{align} \label{eq:pblm-2-lagrange} \min_{x \in \mathbb{R}^n} f(x) + \sum_{i=1}^m \lambda_i g_i(x) \end{align} \] 其中，\(\lambda_i\) 是 Lagrange 乘子。
接下来，针对上述无约束优化问题 \(\eqref{eq:pblm-2-lagrange}\)，应用驻点条件，可以得到： \[ \begin{align} \label{eq:sln-2-lagrange} \nabla f(x) + \sum_{i=1}^m \lambda_i \nabla g_i(x) = 0 \end{align} \]
最优解除了要满足 ，还应该满足等式约束 \[ \begin{align} \label{eq:sln-2-constraint} g_i(x) = 0, i = 1, 2, \ldots, m \end{align} \] 最终，\(\eqref{eq:sln-2-lagrange}\) + \(\eqref{eq:sln-2-constraint}\) 就是等式约束优化问题的必要条件
但这是反直觉的：
为什么等式约束问题 \(\eqref{eq:pblm-2}\) 可以转化为无约束优化问题 \(\eqref{eq:pblm-2-lagrange}\)？
Lagrange 乘子在这个问题转化过程中，扮演了什么角色？
等式约束优化问题的必要条件 + 其实是关于 \(x_1,\cdots,x_n\) 和 \(\lambda_1,\cdots,\lambda_m\) 的方程组
也就是说等式约束优化问题 \(\eqref{eq:pblm-2}\) 原本只需要求解 \(x\)，转化为无约束优化问题 \(\eqref{eq:pblm-2-lagrange}\) 后需要求解 \(x\) 和 Lagrange 乘子 \(\lambda\)，这就会导致 \(x\) 依赖 Lagrange 乘子 \(\lambda\)，会产生以下问题：
Lagrange 乘子在这个问题转化过程中，扮演了什么角色？
Lagrange 乘子是否可以任意？如果不可以，Lagrange 乘子应该如何确定？
Lagrange 乘子与最优解有什么关系？
2.2 正确思路：等式约束必要条件 → 无约束问题优化目标函数
这一部分的思路：
先推导等式约束优化问题的必要条件（
拉格朗日乘子条件）再用必要条件反推无约束优化问题的目标函数
讨论一下
拉格朗日乘子条件的几何解释
等式约束一阶必要条件就是拉格朗日乘子条件， 后面会指出，拉格朗日乘子条件 其实就是 KKT条件 （只有等式约束情况下）的特例。
定理 1（拉格朗日乘子条件）：
假设：
- \(f,\, h_i\) 在 \(x^*\) 附近一阶可微；
- \(x^*\) 是上面问题的局部极小点；
- \(\{\nabla h_i(x^*)\}_{i=1}^m\) 线性无关（即 \(\nabla h(x^*)\) 满秩，这个条件称为
约束资格条件 / LICQ）。
则存在 \(\lambda^* \in \mathbb{R}^m\)，使得 \[ \begin{align} \label{eq:lag-1} \nabla f(x^*) + \sum_{i=1}^m \lambda_i^* \nabla h_i(x^*) &= 0, \\ \label{eq:lag-2} h_i(x^*) &= 0, \qquad \qquad i = 1,\ldots,m. \end{align} \]
如果定义 \(L(x) = f(x) + \sum_{i=1}^m \lambda_i g_i(x)\)
\(\eqref{eq:lag-1}\)： \(0 = \nabla_x L(x,\lambda) = \nabla f(x) + \sum_{i=1}^m \lambda_i \nabla h_i(x)\)
\(\eqref{eq:lag-2}\)： \(0 = \nabla_\lambda L(x, \lambda) = h(x)\)
\(\eqref{eq:lag-1}\) + \(\eqref{eq:lag-2}\)：\(0 = \nabla_x L(x,\lambda)\)
所以，拉格朗日乘子条件（等式\(\eqref{eq:lag-1}\) 和 \(\eqref{eq:lag-2}\)），是以下无约束优化问题目标函数的梯度： \[
\min_{x \in \mathbb{R}^n} L(x,\lambda) = f(x) + \sum_{i=1}^m \lambda_i h_i(x)
\] 也就是说，无约束优化问题是通过 拉格朗日乘子条件 反推出来的。
2.3 拉格朗日乘子条件 的证明
证明思路概览
先只用“局部极小点”的定义 + “可行曲线”，推出：
在所有可行方向 \(d\) 上，有 \(\nabla f(x^*)^\top d = 0\)。
再用线性代数：
可行方向的集合 \[ \mathcal{T} = \{ d : \nabla h_i(x^*)^\top d = 0,\ i = 1,\ldots,m \} \] “对所有 \(d \in \mathcal{T},\, \nabla f(x^*)^\top d = 0\)” 等价于\(\nabla f(x^*)\) 垂直于 \(\mathcal{T}\)，即 \(\nabla f(x^*) \in \mathcal{T}^\perp\)。
因为 \(\mathcal{T} = \operatorname{null}(\nabla h(x^*)^\top)\)，所以 \(\mathcal{T}^\perp = \operatorname{range}(\nabla h(x^*))\)，
这就意味着\[ \nabla f(x^*) = - \nabla h(x^*) \lambda^* \]
对某个 \(\lambda^*\) 成立，即得证。
下面把每一步写严一点。
2.4 拉格朗日乘子条件 的几何解释
几何解释：
无约束时：极小点要求 $ f(x^*)=0 $。
有等式约束时：你只能沿“可行方向”（即切空间）动，所以要求 \[ \nabla f(x^\ast)\ \perp\ \text{切空间}. \]
切空间是所有与 $ h_i(x^) $ 正交的方向集合。 因此“$ f(x^) $ 垂直于切空间”等价于： \[ \nabla f(x^\ast) \in \left\{ \nabla h_i(x^\ast) \right\} \] 也就是 \[ \nabla f(x^\ast) = -\sum_{i=1}^m \lambda_i^\ast \nabla h_i(x^\ast). \] $ f(x^) $ 落在 $ { h_i(x^) } $ 张成的线性空间里。
3. 不等式约束优化问题
这里需要关注：
引入了不等式约束，问题就变了（从
无约束/等式约束优化问题变成了不等式约束优化问题）相应的，最优解需要满足的必要条件，也要发生改变（最优解不仅要满足驻点条件，还应该需要满足
不等式约束）如何以一种更加本质并且更加统一的视角，将
驻点条件和不等式约束有机结合起来？这是这一部分讨论的出发点
接下来的思路：
先推导
不等式约束优化问题的必要条件 –KKT条件再用
KKT条件反推无约束优化问题的目标函数讨论一下
KKT条件的几何解释KKT条件在只有等式约束时会退化成什么形式
3.1 不等式约束 最优解的可能情况（\(m=1\) 的情况）
优化问题 \(\eqref{eq:pblm-3}\) 的最优解必须要满足 不等式约束 条件，即 \[
\begin{align}
h(x^*) \leq 0
\end{align}
\]
所以，相对于 不等式约束 条件 \(h(x)\le0\)，最优解有以下可能情况：
约束活跃：最优解满足 \(h(x^*) = 0\)，即最优解在不等式约束边界上约束不活跃：最优解满足 \(h(x^*) < 0\)，即最优解在不等式约束内部，此时可以视为无约束优化问题
相对于目标函数 \(f(x)\) 及其梯度 \(\nabla f(x)\)，最优解又会有哪些情况呢？
为了将上面两种情况统一起来 - 首先定义 Lagrange 函数 \[
\begin{align}
L\left( x,\lambda \right) = f(x) + \lambda h(x)
\end{align}
\] - 约束活跃 和 约束不活跃 两种情况下，可以统一表示为以下条件 \[
\begin{align}
\nabla L(x,\lambda) = 0, \qquad \lambda \geq 0
\end{align}
\]