非凸函数的子梯度

计算科学 优化 凸优化 非凸的
2021-12-06 23:06:38

这些说明(第 2.3 节)中,指出:

当且仅当处可微分时,点是函数不一定是凸的)的最小化器。xffx0f(x).

有人可以为我提供上述陈述的证明参考吗?

有没有参考资料可以让我们更多地了解非凸函数的次梯度?在上述注释的第3 节次梯度的微积分中,针对凸函数提出了许多次梯度的性质。我想知道这些属性中哪些仍然适用于非凸函数。

先感谢您!

2个回答

的(全局!)最小化当且仅当已经在您链接到的注释中得到充分解释的事实 - 这真的很简单,但这里是为了完整起见再次争论。假设的全局最小化器。然后,根据定义, 这正是凸次微分(和次微分)的定义。对于另一个方向,您只需交换最后一个等式即可看到一个定义暗示另一个。(请注意,这个论点仅适用于全局最小化器——这就是凸性xf0f(x)xf

f(x)f(x)0=0T(xx)for any xRn,
f真的很重要,因为对于凸函数,每个最小化器都是全局最小化器)。

至于非凸函数的其他属性:简短的回答是none请注意,反向假设是可微分的,即集合是非空的。这听起来并不多(事实上,对于任何(局部有限)凸函数都是如此),但它几乎只适用于凸函数。事实上,您可以证明如果次微分处处非空,则是凸的(参见https://math.stackexchange.com/q/1499059)。所以所有其他属性——它们是关于次微分的某些元素的陈述——通常只在空洞的意义上是正确的(作为关于空集的陈述)。ff(x)f

然而,非凸函数的子微分有进一步的推广,它们对于更大(但仍然受限)的函数类是非空的,并且承认相似的性质(特别是必要的最优性条件)。不用说,班级越大,他们的工作就越棘手。一个突出的例子是 Clarke 的局部 Lipschitz 连续函数的广义梯度(参见第 10 章 Clarke,泛函分析,变分法和最优控制,Springer 2013)。您可以在Schirotzek, Nonsmooth analysis , Springer 2007中找到更广义的导数

就注释中使用的次微分定义而言,该陈述根据定义是直接的。

对于更一般的次微分概念,Clarke, FH (1990) 的第 38 页上的命题 2.3.2,“优化和非平滑分析”说:

如果f达到局部最小值或最大值x, 然后0f(x).