【數(shù)學(xué)基礎(chǔ)】 怎么判斷一個(gè)優(yōu)化問題是凸優(yōu)化還是非凸優(yōu)化？
作者：覃含章
編者按
本文介紹了判斷一個(gè)優(yōu)化問題是否是凸/非凸問題的常用方法：基于定義/一般形式判斷；求導(dǎo)&一階/二階充要條件判斷;基于疊加/變化/復(fù)合而成;基于定義的蒙特卡洛采樣暴力數(shù)值驗(yàn)證。
1、一般來說，判斷一個(gè)問題是否是凸的是強(qiáng)NP-難的
首先這個(gè)問題一般來說是很難的。比如：判斷一個(gè)多元四次（及以上）偶多項(xiàng)式是否是凸的是strongly NP-hard的：
（http://web.mit.edu/~a_a_a/Public/Publications/convexity_nphard.pdf）。也就是說，除非NP=P，不存在（偽）多項(xiàng)式算法可以判斷一個(gè)優(yōu)化問題是凸或非凸的。
2、凸問題的一般形式
所以實(shí)際上難點(diǎn)就在于如何判斷一個(gè)函數(shù)是否是凸的。
3、判斷一個(gè)函數(shù)是否是凸的一些“奇技淫巧”
當(dāng)然，如果這些方法都沒用，我們還是只能回歸初心（凸函數(shù)的定義），可以數(shù)值地來進(jìn)行蒙特卡洛驗(yàn)證：每次取倆點(diǎn)，然后看凸組合的值是否小于等于值的凸組合...做很多很多次采樣
以下sao操作來自于Stephen Boyd（我不背鍋，來源是Boyd本人的凸優(yōu)化公開課課程）：如果當(dāng)你蒙特卡洛采樣了很多很多次都沒有發(fā)現(xiàn)反例，那么可以認(rèn)為大概率這函數(shù)估計(jì)是凸的，這個(gè)時(shí)候你可以把它放在paper里作為“猜想”（conjecture），說不定過段時(shí)間某個(gè)年輕有為發(fā)奮向上的青年AP就寫了個(gè)幾十頁(yè)proof把你的“猜想”給證明了 -- 這也是判斷是否是凸函數(shù)的好方法233 （別人問你怎么想到這個(gè)conjecture的："Intuition."）
參考文獻(xiàn)：
Boyd, Stephen, and Lieven Vandenberghe.?Convex optimization. Cambridge university press, 2004.
往期精彩回顧
本站知識(shí)星球“黃博的機(jī)器學(xué)習(xí)圈子”（92416895）
本站qq群704220115。
加入微信群請(qǐng)掃碼：