【数学基础】 怎么判断一个优化问题是凸优化还是非凸优化？
共 1028字，需浏览 3分钟
·
2021-02-12 04:11
作者：覃含章
编者按
本文介绍了判断一个优化问题是否是凸/非凸问题的常用方法：基于定义/一般形式判断；求导&一阶/二阶充要条件判断;基于叠加/变化/复合而成;基于定义的蒙特卡洛采样暴力数值验证。
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.
往期精彩回顾
本站知识星球“黄博的机器学习圈子”（92416895）
本站qq群704220115。
加入微信群请扫码：