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

BOBO · 发表于 1736316578

本帖最后由 BOBO 于 2025-1-21 14:48 编辑

一、Karush–Kuhn–Tucker (KKT) Conditions

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

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

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

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

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

（4）stationarity

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

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

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

二、PHR增广拉格朗日乘子法

（1）非凸问题，等式约束

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条件的解可以通过如下方式解出：

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