『運籌OR帷幄』原創
作者：覃含章
編者按
本文介紹了判斷一個優化問題是否是凸/非凸問題的常用方法：基于定義/一般形式判斷；求導&一階/二階充要條件判斷;基于疊加/變化/複合而成;基于定義的蒙特卡洛采樣暴力數值驗證。
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."）
參考文獻：