翻译:次梯度以及一阶最优性条件(Subgradient and First-order Optimality Condition)

本文是对文章Basics of Convex Analysis的部分翻译,若本文对您的任何权益造成侵犯,请联系我。

This article is a partial translation of Basics of Convex Analysis, if this infringes any of your rights, please contact me.


次梯度以及一阶最优性条件

若下述不等式成立:

则我们说是函数点上的一个次梯度,并且属于在该点(用表示)的一个次微分。

上述不等式表明函数的图像(graph)是由不等式右侧定义的超平面所(hyperplane)支撑的。一个次梯度因此也是这众多支持超平面其中一个的“斜率(slope)”。如果该函数在点处可微,则这样的次梯度有且仅有一个(即标准梯度),与此对应地,也只有一个支持超平面。相对地,如果一个函数在点处不可谓(比如,在处有个扭曲)那么就能有无穷多个支持超平面,并且相对应地,在该点的次微分是一个连续的次梯度的集合。

一个典型的例子是绝对值函数,它在0点是不可导的。但在这个点上,它可以由组成的所有直线支持。这个集合即该函数在0点的次微分,用表示。

函数的演示(粗线表示)以及其中两个支持直线(虚线表示)。这两条支持直线都有次微分中的斜率。注意,那条水平线也是支持超平面之一,表明。并且因此由一阶条件(下文定义),这个函数在原点有一个极小值。

现在,通过定义非限制问题中的一个最优点,必有,并且因此0必须是函数点处的一个子梯度。

这就是一阶最优性条件(FOC):

如果我们将次微分看做一个运算符那么,直观地,寻找极小可以看做“逆转”次微分并计算它在点0的值的过程,即。我们稍后再进一步介绍,但这个逆转次微分运算符的思路是非常重要的。

在继续之前,有必要提一下(并且这并不难理解)下述包含关系对于次微分的和是成立的:

对关注的大部分问题而言,上述关系可以强化为相等的关系, 但注意如果,则上述包含关系意味着,这对于证明是个极小值而言(这正是我们最感兴趣之处)足矣。