翻译:次梯度以及一阶最优性条件(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的值的过程,即。我们稍后再进一步介绍,但这个逆转次微分运算符的思路是非常重要的。 在继续之前,有必要提一下(并且这并不难理解)下述包含关系对于次微分的和是成立的: 对关注的大部分问题而言,上述关系可以强化为相等的关系, 但注意如果,则上述包含关系意味着,这对于证明是个极小值而言(这正是我们最感兴趣之处)足矣。