優(yōu)化 | 怎樣判斷一個優(yōu)化問題是否為凸優(yōu)化問題？
編者按
本文介紹了判斷一個優(yōu)化問題是否是凸/非凸問題的常用方法：基于定義/一般形式判斷；求導&一階/二階充要條件判斷;基于疊加/變化/復合而成;基于定義的蒙特卡洛采樣暴力數(shù)值驗證。
1、一般來說，判斷一個問題是否是凸的，是強NP-難的
首先這個問題一般來說是很難的。比如：判斷一個多元四次（及以上）偶多項式是否是凸的是strongly NP-hard的（http://web.mit.edu/~a_a_a/Public/Publications/convexity_nphard.pdf）。也就是說，除非NP=P，不存在（偽）多項式算法可以判斷一個優(yōu)化問題是凸或非凸的。
2、凸問題的一般形式
所以實際上難點就在于如何判斷一個函數(shù)是否是凸的。
3、判斷一個函數(shù)是否是凸的一些“奇技淫巧”
當然，如果這些方法都沒用，我們還是只能回歸初心（凸函數(shù)的定義），可以數(shù)值地來進行蒙特卡洛驗證：每次取倆點，然后看凸組合的值是否小于等于值的凸組合...做很多很多次采樣
以下sao操作來自于Stephen Boyd（我不背鍋，來源是Boyd本人的凸優(yōu)化公開課課程）：如果當你蒙特卡洛采樣了很多很多次都沒有發(fā)現(xiàn)反例，那么可以認為大概率這函數(shù)估計是凸的，這個時候你可以把它放在paper里作為“猜想”（conjecture），說不定過段時間某個年輕有為發(fā)奮向上的青年AP就寫了個幾十頁proof把你的“猜想”給證明了 -- 這也是判斷是否是凸函數(shù)的好方法233 （別人問你怎么想到這個conjecture的："Intuition."）
參考文獻：
Boyd, Stephen, and Lieven Vandenberghe.?Convex optimization. Cambridge university press, 2004.
?------------------------------------------------
看到這里了，說明您也喜歡這篇文章，您可以點擊「分享」「在看」與朋友們交流，或順手「點贊」給我們一個支持，讓我們做的更好哦。
歡迎微信搜索并關(guān)注「目標檢測與深度學習」，不被垃圾信息干擾，只分享有價值知識！