优化 | 怎样判断一个优化问题是否为凸优化问题？

首先这个问题一般来说是很难的。比如：判断一个多元四次（及以上）偶多项式是否是凸的是strongly NP-hard的（http://web.mit.edu/~a_a_a/Public/Publications/convexity_nphard.pdf）。也就是说，除非NP=P，不存在（伪）多项式算法可以判断一个优化问题是凸或非凸的。

所以实际上难点就在于如何判断一个函数是否是凸的。

当然，如果这些方法都没用，我们还是只能回归初心（凸函数的定义），可以数值地来进行蒙特卡洛验证：每次取俩点，然后看凸组合的值是否小于等于值的凸组合...做很多很多次采样

以下sao操作来自于Stephen Boyd（我不背锅，来源是Boyd本人的凸优化公开课课程）：如果当你蒙特卡洛采样了很多很多次都没有发现反例，那么可以认为大概率这函数估计是凸的，这个时候你可以把它放在paper里作为“猜想”（conjecture），说不定过段时间某个年轻有为发奋向上的青年AP就写了个几十页proof把你的“猜想”给证明了 -- 这也是判断是否是凸函数的好方法233 （别人问你怎么想到这个conjecture的："Intuition."）

参考文献：

Boyd, Stephen, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.

✄------------------------------------------------

看到这里了，说明您也喜欢这篇文章，您可以点击「分享」「在看」与朋友们交流，或顺手「点赞」给我们一个支持，让我们做的更好哦。

欢迎微信搜索并关注「目标检测与深度学习」，不被垃圾信息干扰，只分享有价值知识！