数值优化——KKT条件与PHR增广拉格朗日乘子法

数值优化——KKT条件与PHR增广拉格朗日乘子法

数值优化是机器学习和运筹学等领域的重要基础，其中KKT条件和拉格朗日乘子法是解决约束优化问题的关键工具。本文详细介绍了KKT条件的四个必要条件，以及PHR增广拉格朗日乘子法在处理非凸等式约束和不等式约束问题中的应用。虽然文章发布于2025年1月，但其内容具有较强的理论性和参考价值，对于从事相关领域研究的读者具有重要启发。

Karush–Kuhn–Tucker (KKT) Conditions

无约束优化函数具有一些共同特点，如最优解梯度为零等。在约束优化当中有无相似的性质呢？这里给出一个普通的带约束优化问题：

当然，上述问题不能是退化问题，退化的优化问题我们一般不给予考虑。则其最优解满足以下条件：

（1）primal feasibility 这个条件是指所得到的最优解一定满足等式约束以及不等式约束。

（2）complementary slackness 最优解的不等式约束的值与其对偶变量的乘积为零

（3）dual feasibility 不等式约束的对偶变量的值大于等于零

（4）stationarity

以上条件便被称为KKT条件，其可视化后的情况如下：

举个例子，如下图所示的QP优化问题（严格凸）：

因为其最优解满足KKT条件，所以将其KKT条件求解出来之后进行求解就可找到最优解了：

PHR增广拉格朗日乘子法

非凸问题，等式约束

Uzawa’s Method难以解决f(x)不是严格非凸的问题，因此我们想在寻找另一种方法来求解。如下优化问题：

如果采用Uzawa’s Method的话，由于我们对λ的取值，图中紫色框住的部分一定是非连续的：

那为了解决这个问题，并使该方法能够应用于非凸的函数优化问题当中，我们对上述方法进行改进：

其中ρ与λ-均为常数，ρ越大所获得的优化函数越接近原来的优化函数，并且我们无需交换minmax问题的顺序。我们先看最大化问题：

由上图可以看出，这样一个最大化问题其实就是关于λ的二次函数，所以对其求λ的导数我们可以得到最优的λ*与λ-的关系为：

将取得的最优λ带入后可得：

这样一来我们就把约束问题转化为简单易解得一个无约束的优化问题了。那因为我们为了能够好的求解这个问题，在原问题之上增加了一项，那怎样使上图这样一个优化问题的解与原问题相同呢？除了在前面提到的增大ρ的取值之外，不断迭代更新λ*的值也是很好的方法

对比Uzawa’s Method我们可以看到增广拉格朗日方法其实就是在后面增加了增广项。

我们在Uzawa’s Method来看待增广拉格朗日方法，我们知道，在运用Uzawa’s Method时所获得的d(λ)可能梯度是不连续的，如图中所示，这样的函数依靠sub-gradent难以收敛到最小值。而采用拉格朗日增广方法，如果我们先验的λ存在（如图），那么我们得到的最优λ(k+1)将会是下一次的先验值。因此通过不断迭代，我们能够求得优化函数的最优解。

除此之外，我们将增广拉格朗日方法所得到的d(λ)绘制出来就是图中的d(λ-)，我们可以看到，这个函数不仅是一阶导数连续，而且其最优解与采用Uzawa’s Method所获得的最优解是一模一样的。

总结一下，针对非凸的等式约束的优化问题，我们采用如下的拉格朗日函数进行求解，灰色部分一般省略：

满足KKT条件的解可以通过如下方式解出：

内部优化问题（第一个等式）是一种比较容易解决的无约束优化问题，同时其求解精度也不需要太高，因为有外层优化的存在。

非凸问题，不等式约束

对于不等式约束的优化问题，我们对每个不等式约束增加一项，使其成为等式约束，形式如下：

但这样会使优化问题的维数提升至m+n维，所以我们想寻求更加智能的方法。我们知道，更新x的取值是通过最小化拉格朗日函数实现的，针对上图这种思路，我们有：

在这里不加证明的给出，上图这一式等于：

我们可以看到，此时就与s无关了。因此不等式约束的拉格朗日函数为：

更新μ的方式为：

综上，一般的包括等式约束与不等式约束的增广拉格朗日方法，其实就是将等式约束与不等式约束的增广拉格朗日方法加起来：

这样一个拉格朗日函数更新方法为：

内部优化与外部优化的停止条件如下：