翻译:次梯度以及一阶最优性条件(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.


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

若下述不等式成立:

f(z) \geqslant{f(x)} + <z-x, y>, \forall z \in X.

则我们说y\in X是函数f \in \Gamma _0(X)x \in X点上的一个次梯度,并且属于f在该点(用\partial f(x)表示)的一个次微分。

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

一个典型的例子是绝对值函数f(x)=|x|,它在0点是不可导的。但在这个点上,它可以由l(x)=\alpha x, \alpha \in [-1,1]组成的所有直线支持。这个集合即该函数在0点的次微分,用\partial f(0)表示。

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

现在,通过定义非限制问题中的一个最优点x^{\#},必有f(z) \geqslant{f(x^{\#}) + <z-x, 0>}, \forall z \in x ,并且因此0必须是函数fx^{\#}点处的一个子梯度。

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

x^{\#} \in arg min_{x}{f(x)} \Longleftrightarrow 0 \in \partial f(x^{\#})

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

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

\sum_{i}{\partial f_i} \subseteq \partial \sum_{i}{f_i}

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


 

发表评论

电子邮件地址不会被公开。 必填项已用*标注