【凸优化】最优性条件

以前学机器学习的时候，在 SVM 中遇到过拉格朗日对偶问题，后来学习强化学习看自然梯度以及 TRPO 也遇到了拉格朗日对偶问题。这里，就把凸优化中的一些内容，尤其是最优性条件以及拉格朗日对偶问题总结一下。

无约束优化问题的最优性条件

先考虑无约束非线性规划问题

其中决策变量 ，目标函数 。我们先引进下降方向的概念。

下降方向

定义：设函数 。若存在 使

则称 是 在 处的下降方向。

定理**：设 在 处可微，。若 ，则称 是 在 处的下降方向。

这个定理是很显然的，梯度方向是函数值上升变化最大的方向，与它为钝角的方向就是函数值下降的方向。

记，，则 中元素均为 在 处的下降方向。

一阶最优性条件

一阶必要条件：设 在 处可微。若 是 (UNP) 的局部最优解，则 。

这一点我们在高等数学里已经知道了，梯度为 0 的点是极值点的必要条件。一般的满足 的点我们称之为平稳点。

一阶充分条件：设 是 上的下凸函数，并在在 处可微。若 ，则 是 (UNP) 问题的全局最优解。这一点学过高数的都知道是显然的。

二阶最优性条件

二阶必要条件：设 在 处二阶连续可微。若 是 (UNP) 的局部最优解，则 ， 半正定。

这就是梯度为零向量，然后海森矩阵半正定。

二阶充分条件：设 在 处二阶连续可微。 ， 正定。则 是 (UNP) 的严格局部最优解。

注意到，严格局部最优也可能是半正定的，正定是充分条件，半正定是必要条件。
**
这些最优性条件都可以用多元函数的泰勒展开证明，泰勒展开如下：

无约束二次规划问题的最优性条件

无约束二次规划问题的通用形式为：

其中 是对称矩阵，。

最优点的充要条件：设 。则 是 (UQP) 的最优解的充要条件是 ， 半正定。
必要性：根据二阶必要条件，，显然必要性没问题
充分性：由 为半正定矩阵可知， 是一个下凸的函数，对于下凸函数，平稳点一定是最优解。

约束优化问题的最优性条件

考虑约束非线性规划问题：

其中决策变量 ，可行域 。目标函数 。

可行方向

可行方向定义：设集合 ，。若存在 ，使

则称 是 在 处的可行方向。

对于 ，记 为 在 处的可行方向集。

可行下降方向定义：对于问题 (CNP)，设 。若 ，并且 是 在 处的下降方向，则称 是 (CNP) 在 处的可行下降方向。

定理：设 ， 在 处可微。若 是 (CNP) 的局部最优解，则

这个定理是很显然的，极小值点是没有可行下降方向的。

下面分别分析线性约束集合和一般不等式约束集合的可行方向集。

带线性约束集合的可行方向集

设 ，其中 。若 ，则将 进行分块：

称是 在 处对应于起作用约束的系数矩阵，是 在 处对应于不起作用约束的系数矩阵。约束起作用时，这个点刚好在某个约束边界上，那个边界起作用。

定理：设 ，若 ，并且公式 (1) 成立，则：

这个定理粗看起来很奇怪，其实一点都不奇怪，看了后面的部分就很容易理解了。下面，我们来粗略的证明：
证明：设 ，由于 是可行方向有：存在 ，使 ，故

由于 ，显然有 。

一般不等式约束集合的可行方向集

现在考虑约束 记 。
对 ，记 ，当 时，称约束 为 在 处起作用的约束，或者称之为紧约束。再记：

为什么定义这两个符号，为什么这两个符号里有梯度，对约束函数进行泰勒展开就很显然了。

定理：设 ，。若 时 在 处可微， 时 在 处连续，则 。当 为线性函数时，。

这个定理我们不证明，我们只需要知道：对于非线性约束，可行方向集在 之间就行了。这是很显然的事情，对于非线性约束，沿着切线(与梯度正交)的方向不是可行方向，而对于线性约束，沿着梯度垂直的方向是可行方向。

推论：设 ，。 在 处可微， 若 时 在 处可微， 时 在 处连续。若 是 (CNP) 的局部最优解，则

当 为线性函数时，有

这里就是说，下降方向集与可行方向集的交集为空。一般老师，非线性等式约束和不等式约束结合在一起的话，一般没有可行方向了，但存在序列可行方向。就是只能沿着约束条件的弯曲的边界走。

序列可行方向

定义：设集合 ，，。若存在序列 ，有：，使

则称 是 在 处的序列可行方向。
记 为 在 处的序列可行方向集，又称切锥。

下面给出几个要点：

• 是闭集和锥
• 
• 设 。若 是 (CNP) 的局部最优解，则 (CNP) 在 处不存在序列可行的下降方向。(显然，不证)

定义**：设 ， 在 处可微。若 是 (CNP) 的局部最优解，则 。

现在考虑 时的序列可行方向集。
记 。对 ，记

定理**：设。若 ， 时 在 处可微， 时 在 处可微，则 。当 和 为线性函数时，。

我们需要知道对于非线性等式约束，一般是没有可行方向的，只有序列可行方向。上面的定理也是很显然的东西。下面我们给出一个定理，但是不证明(不是很好证)：

定理：设。若 ， 时 在 处可微，， 时 在 处连续， 时 在 处可微， 线性无关，则

通过以上两个定理我们知道：

定理：设。 是 (CNP) 的局部最优解， 在 处可微， 时 在 处可微，， 时 在 处连续， 时 在 处可微，有

1. 若 由线性约束组成，则
2. 若 线性无关，则

这个定理非常重要，直接引出了一阶必要条件。
**

一阶必要条件

我们现在讨论 时 (CNP) 的最优性条件，即考虑问题：

分别建立其 Fritz John 条件和 K-T 条件。

定理：Fritz John 条件，设 ， 在 处可微， 时 在 处可微，， 时 在 处连续， 时 在 处可微，若 是 (CNP) 的局部最优解，则存在不全为 0 的 和 ，使

简单说一下证明过程，我们已经知道了 ，这意味着

无解，根据择一性定理，就可以得到 Fritz John 条件了。

由于在 Fritz John 条件中，目标函数的梯度的系数可能刚好为 0 使 FJ 条件成立，这会导致梯度信息丢失，为了保证该系数不为 0 ，需要对可行域加一些约束规格，由此得到 K-T (Kuhn-Tucker) 条件。下面我们介绍两种约束规格。

1. 线性约束规格： 是线性函数。
2. 正则点约束规格： 是 的正则点，即 线性无关。

定理：KKT 条件，设 ， 在 处可微， 时 在 处可微，， 时 在 处连续， 时 在 处可微，若 是 (CNP) 的局部最优解，并且约束规格成立 (二选一) 则存在 和 ，使

这个定理比较好证明，就是在 FJ 条件中把 给消掉了。

事实上，在约束规格下，有 。

当 在 处可微时，KKT 条件可以写成。

加上优化问题中已有的约束条件，KKT 条件可以写为：

一般的我们称上面第一个式子为拉格朗日函数， 为拉格朗日乘子。

一阶充分条件

在凸性条件下，KKT 条件也是 (CNP) 的最优解的充分条件。

定理：**设，， 在 处可微。若 是 (CNP) 的 KKT 点，且 为凸函数， 是凹函数, 是线性函数, 则 是 (CNP) 问题的最优解.

所以对于凸优化问题, 我们利用 KKT 条件, 解方程找到 KKT 点就行了. 但是对于非凸优化问题, KKT点不一定是局部最优解, 这时需要用二阶最优性条件判断.

约束二次规划问题的最优性条件

现在考虑特殊的非线性规划问题: 约束二次规划问题:

其中 是对称矩阵, . 记 . 设 是 (CQP) 的 KKT 点, 是对应的拉格朗日乘子, 满足条件:

是 中与 对应的部分, 则 KKT 条件为:

定理: 设 . 则 是 (CQP) 的局部最优解, 当且仅当存在 和 , 使

这个定理这里不证明, 注意: 这里的优化问题是一个非凸的问题.

二阶最优性条件

直接看结论吧:

对偶及鞍点问题

拉格朗日对偶问题

考虑非线性规划问题:

我们把上述问题的对偶问题定义为:

其中

称为拉格朗日对偶函数.

弱对偶定理:** 设 分别是原问题和对偶问题的可行解, 则

这是很显然的事情, 根据定义可以直接看出来. 下面我们根据弱对偶定理给出四个推论:

推论1: 对于原问题和对偶问题, 必有

这个推论就是把弱对偶定理抄了一遍.
推论2: 如果 , 其中 , 则 分别是原问题和对偶问题的最优解.
推论3: 如果 , 则对每个 , 有 .
推论4: 如果 , 则原问题没有可行解.

根据弱对偶定理, 这四个推论都很显然. 我们根据弱对偶定理就知道, 一定有

如果等号不成立, 则称存在对偶间隙. 为了保证不存在对偶间隙, 我们需要加一些限定, 得到强对偶定理. 这里, 我们不加证明的给出强对偶定理.

强对偶定理: 设 是 中的一个非空凸集, 分别是 上的凸函数和凹函数, 是 上的线性函数, 即 , 又设存在点 , 使得

则

且若上式中, inf 为有限值,则 在 达到, 其中 . 如果 inf 在点 达到, 必有

强对偶定理表明, 对于凸优化问题, 在适当的约束下(线性等式约束), 原问题的极小值与对偶问题的极大值是相等的.

鞍点与最优性条件

考虑非线性规划问题:

我们把上述问题的对偶问题定义为:

其中

称为拉格朗日对偶函数. 并且我们定义拉格朗日函数为 :

我们先定义拉格朗日函数的鞍点, 设 为拉格朗日函数, 如果对每个 都有

则称 为 的鞍点.

鞍点定理: 设 是原问题拉格朗日函数的鞍点, 则 分别是原问题和对偶问题的最优解. 反之, 若 分别凸函数和凹函数, 是线性函数, 即 , 且 满秩. 又设存在 , 使 . 如果 是原问题的最优解, 则存在 其中 , 使 是拉格朗日函数的鞍点.

所以我们知道, 对于一般优化问题, 鞍点一定是最优解. 但注意到, 对于一般问题(非凸优化), 最优解不一定是拉格朗日函数的鞍点, 不能认为鞍点是最优解的必要条件, 鞍点是充分条件.

关于原问题拉格朗日函数的鞍点以及KKT条件, 有下面的定理**: 设在原问题中, 可行集为 , 满足 KKT 条件, 即找到了 满足 KKT 条件. 又设 为 凸函数, 为凹函数, 为线性函数, 则 是原问题拉格朗日函数的鞍点. 反之, 设 可微, 若 是拉格朗日函数的鞍点, 则 满足 KKT 条件.

所以我们知道: 对于一般优化问题, 鞍点一定满足 KKT 条件. 对于凸优化, 线性等式约束的优化问题, 满足 KKT 条件的点一定是鞍点.
**

参考文献

最优化理论与方法（第二版），陈宝林。