优化 | 怎样判断一个优化问题是否为凸优化问题？
编者按
本文介绍了判断一个优化问题是否是凸/非凸问题的常用方法：基于定义/一般形式判断；求导&一阶/二阶充要条件判断;基于叠加/变化/复合而成;基于定义的蒙特卡洛采样暴力数值验证。
1、一般来说，判断一个问题是否是凸的，是强NP-难的
首先这个问题一般来说是很难的。比如：判断一个多元四次（及以上）偶多项式是否是凸的是strongly NP-hard的（http://web.mit.edu/~a_a_a/Public/Publications/convexity_nphard.pdf）。也就是说，除非NP=P，不存在（伪）多项式算法可以判断一个优化问题是凸或非凸的。
2、凸问题的一般形式
所以实际上难点就在于如何判断一个函数是否是凸的。
3、判断一个函数是否是凸的一些“奇技淫巧”
当然，如果这些方法都没用，我们还是只能回归初心（凸函数的定义），可以数值地来进行蒙特卡洛验证：每次取俩点，然后看凸组合的值是否小于等于值的凸组合...做很多很多次采样
以下sao操作来自于Stephen Boyd（我不背锅，来源是Boyd本人的凸优化公开课课程）：如果当你蒙特卡洛采样了很多很多次都没有发现反例，那么可以认为大概率这函数估计是凸的，这个时候你可以把它放在paper里作为“猜想”（conjecture），说不定过段时间某个年轻有为发奋向上的青年AP就写了个几十页proof把你的“猜想”给证明了 -- 这也是判断是否是凸函数的好方法233 （别人问你怎么想到这个conjecture的："Intuition."）
参考文献：
Boyd, Stephen, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
✄------------------------------------------------
看到这里了，说明您也喜欢这篇文章，您可以点击「分享」「在看」与朋友们交流，或顺手「点赞」给我们一个支持，让我们做的更好哦。
欢迎微信搜索并关注「目标检测与深度学习」，不被垃圾信息干扰，只分享有价值知识！