如何证明一个函数是凸的?

计算科学 凸优化
2021-12-02 21:17:57

我正在使用名为 theano 的符号数学库计算函数的梯度。然后我使用梯度下降来找到函数的最小值。

我想证明最小值是全局最小值。如何证明我的函数是凸函数?

3个回答

有很多方法可以证明函数是凸的:

  • 根据定义
  • 使用保留凸性的组合规则从已知凸函数构造它
  • 证明 Hessian 是半正定的(你关心的任何地方)
  • 证明函数的值总是位于函数的切平面之上

除非您对函数的属性有所了解(例如,它是否是二次多项式、单调等),否则您无法通过实验确定函数是否为凸函数。您需要将您的问题限制在较小的功能子集上。

你问如何证明一个函数是凸的——但看起来你真正的问题是如何证明你的局部最小值是全局的。有很多非凸函数,它们的局部最小值也是全局的,有时,你甚至可以证明它:-)

您可能会考虑的一种选择是采用分支定界全局优化方法。这是探索整个感兴趣区域的系统方法。从理论上讲,这可能非常昂贵,但在实践中,您通常可以修剪掉大部分感兴趣的区域,从而节省大量计算。

以下是 Stephen Boyd 和 Jacob Mattingley 关于该主题的一些幻灯片讲义要使用它,您不仅需要能够计算函数的局部最小值(您当前拥有的东西),还需要能够计算任意区域上函数的良好下界

如果您认为这种方法可能对您的应用程序有好处,请向我们提供有关您的问题的更多详细信息(通过编辑您的问题),也许我可以填写更多详细信息。