在这篇文章中，我将首先介绍局部最优性的一阶和二阶必要条件，然后给出两个最常用的约束优化算法——拉格朗日乘子法与 KKT 条件的使用方法。
局部最优性
局部最优解的必要条件：
一阶定理：$\forall x \in \mathbb{R}^n$，$y = f(x) \in \mathbb{R}$，若 $x^*$ 为局部最优解且 $f$ 在 $x^*$ 的邻域内一阶可导，则 $\nabla f(x^*) = 0$。
证明思路：将 $f$ 在 $x^*$ 处一阶泰勒展开 $f(x) = f(x^*) + \Delta x^\textrm{T} \nabla f (x^*)$，要在邻域内 $f(x^*)$ 最小，则恒有 $\Delta x^\textrm{T} \nabla f (x^*) \geq 0$。因为 $\Delta x$ 可正可负（左邻域和右邻域），所以恒有 $\nabla f(x^*) = 0$。
二阶定理：$\forall x \in \mathbb{R}^n$，$y = f(x) \in \mathbb{R}$，若 $x^*$ 为局部最优解且 $f$ 在 $x^*$ 的邻域内二阶可导，则 $\nabla f(x^*) = 0$ 且 $\nabla^2 f(x^*)$ 为半正定矩阵。
证明思路：将 $f$ 在 $x^*$ 处二阶泰勒展开 $f(x) = f(x^*) + \frac{1}{2} \Delta x^\textrm{T} \nabla^2 f (x^*) \Delta x$，要在邻域内 $f(x^*)$ 最小，则恒有 $\Delta x^\textrm{T} \nabla^2 f (x^*) \Delta x \geq 0$，所以 $\nabla^2 f (x^*)$ 半正定。这里涉及到线性代数的部分我会在后面给出相应的介绍与分析，敬请期待。
优化算法
最常用的无约束非线性优化算法是一维搜索，其核心是找到合适的迭代方向和每次迭代的最优步长。如果没有曲线信息可供利用（一阶、二阶甚至更高阶的导数），那么可以用 黄金分割法、斐波那契法 等方法缩小搜索区间，也可以借助多项式的强大表示能力执行 插值法（牛顿法就是二点二次插值）；如果有信息可用，那么通常借助泰勒展开式获得迭代方向。具体地，如果有一阶信息可供利用，那么可以采用 梯度法（最速下降法）及其一系列的改进方法（泰勒一阶展开）；如果有二阶信息可供利用，那么可以采用 牛顿法 及其一系列的改进方法（泰勒二阶展开）。牛顿法的两大问题分别是 Hessian 矩阵不总正定和 Hessian 矩阵的逆太难算。对于前者，改进策略是提出各种修正方案保证迭代方向一定是函数下降的方向；对于后者，改进策略是各种 拟牛顿法（用别的矩阵来代替 Hessian 矩阵的逆）。此外，收敛速度介于梯度法和牛顿法之间的重要方法是 共轭方向法，其本质上是保证每一次迭代都是有效的，即同一个迭代方向不会多次出现。
关于共轭梯度法的部分，请移步 理解共轭梯度法（上）· 梯度法及其分析 、 理解共轭梯度法（下）· 共轭梯度法 。对于上文提及的别的优化算法，我会未来找时间撰写相关文章。
接下来将介绍两个最常用的约束优化算法，熟练掌握这两者是开启 CS 某些领域的科 (灌) 研 (水) 之路的必要条件。
拉格朗日乘子法
适用范围：设 $x \in \mathbb{R}^n$，目标函数为 $f(x)$，需满足 $n$ 个等式约束 $g_i(x) = 0 |_{i=1, ..., n}$。求 $\min_x f (x)$。
-
若只有一个等式约束，即
$n=1$，则在极值点处必然有目标函数曲线和约束函数曲线相切。根据梯度与等高线垂直这一结论，目标函数和约束函数的梯度必然相互平行：$$ \nabla f + \lambda \nabla g = 0, \quad \lambda \in \mathbb{R} $$ -
若有多个等式约束，则在极值点处，目标函数曲线的梯度是多条约束函数曲线的梯度的线性组合：
$$ \nabla f + \Big(\lambda_1 \nabla g_1 + \lambda_2 \nabla g_2 + ... \lambda_n g_n \Big) = 0, \quad \lambda_1, \lambda_2, ... \lambda_n \in \mathbb{R} $$
综上，引入拉格朗日函数 $L (x, \lambda) = f(x) + \sum_{i} \lambda_i g_i (x)$，其中 $\lambda_i$ 被称为拉格朗日乘子。通过联立
$$ \begin{aligned} \left\{ \begin{array}{l} \nabla_x L(x^*, \lambda^*) = 0 \\ \nabla_\lambda L(x^*, \lambda^*) = 0 \qquad (\leftrightarrow g_i(x^*) = 0, \forall i) \end{array} \right. \end{aligned} $$
即可求解极值点 $x^*$ 和乘子的最优值。这里 $\lambda := [\lambda_1, ..., \lambda_n]^\textrm{T}$。 如有必要，我们还需要带入局部最优解的必要条件来对多个潜在的解进行验证。
KKT 条件
适用范围：设 $x \in \mathbb{R}^n$，目标函数为 $f(x)$，需满足 $n$ 个等式约束 $g_i(x) = 0 |_{i=1, ..., n}$ 和 $m$ 个不等式约束 $h_j(x) \leq 0 |_{j=1, ..., m}$。求 $\min_x f (x)$。
-
不等式约束没起作用：拉格朗日乘子法即可解决。
-
不等式约束起作用了：只可能在约束边界取得，因此不等式约束实际上通过等式约束来体现。那么同样有：在极值点处，目标函数曲线的梯度是多条约束函数曲线的梯度的线性组合。但是需要注意的是：在极值点目标函数曲线的梯度必然和不等式约束函数曲线的梯度方向的线性组合相反，所以
$\mu_j > 0 |_{j=1, ..., m}$。 可总结为$$ \begin{aligned} \left\{ \begin{array}{l} \nabla_x f(x^*) + \sum_i \lambda_i \nabla_x g_i (x^*) + \sum_j \mu_j \nabla_x h_j (x^*) = 0 \qquad (\leftrightarrow L (x^*, \lambda^*, \mu^*) = 0) \\ h_j(x^*) = 0, \quad \forall j = 1, ..., m \\ \mu^*_j > 0, \quad \forall j = 1, ..., m \end{array} \right. \end{aligned} $$这里同样引入拉格朗日函数
$L (x, \lambda, \mu) = f(x) + \sum_{i} \lambda_i g_i (x) + \sum_{j} \mu_j h_j (x)$，其中$\mu := [\mu_1, ..., \mu_m]^\textrm{T}$。
将上述两种情况总结到一起就得到了 KKT 条件：
$$ \begin{aligned} \left\{ \begin{array}{l} \nabla_x f(x^*) + \sum_i \lambda_i^* \nabla_x g_i (x^*) + \sum_j \mu_j^* \nabla_x h_j (x^*) = 0 \\ g_i(x^*) = 0, \quad \forall i = 1, ..., n \\ h_j(x^*) \leq 0, \quad \forall j = 1, ..., m \\ \mu_j^* \geq 0, \quad \forall j = 1, ..., m \\ h_j (x^*) \mu_j^* = 0, \quad \forall j = 1, ..., m \end{array} \right. \end{aligned} $$
最后一个是 KKT 互补条件。当 $\mu^*_j=0$ 时，$h_j$ 没有出现在拉格朗日函数中，说明这个不等式约束没起作用，即 $h_j<0$ 恒成立；当 $\mu^*_j> 0$ 时，$h_j=0$，说明 $h_j$ 起作用了，在边界上起的作用。这个条件将两种情形整合到了一起。
如有必要，我们还需要带入局部最优解的必要条件来对多个潜在的解进行验证。
最后
笔者对拉格朗日乘子法和 KKT 条件的分析较为简略，读者可阅读讲义 Lagrange Multipliers and the Karush-Kuhn-Tucker conditions 加深理解。
转载申请
本作品采用 知识共享署名 4.0 国际许可协议 进行许可，转载时请注明原文链接。您必须给出适当的署名，并标明是否对本文作了修改。