在數學中乙個非凸的最優化問題是什麼意思？

1樓：重直

凸優化問題(convex optimization)的定義是目標函式是凸(convex)的，且可行域是凸(convex)的。不符合這個定義的優化問題就是非凸的優化問題(non-convex optimization)，就這麼簡單~

2樓：留德華叫獸

樓主我碩士運籌學出身，現在師從德國海德堡大學組合優化教授，TSP鼻祖之一。

1，首先大家需要知道Convex VS Non-Convex的概念吧？

數學定義就不寫了，介紹個直觀判斷乙個集合是否為Convex的方法，如下圖：

簡單的測試乙個集合是不是凸的，只要任意取集合中的倆個點並連線，如果說連線段完全被包含在此集合中，那麼這個集合就是凸集，例如左圖所示。

先補充一點：舉幾個常見的nonconvex例子，通常2次以上的polynomial不論出現在目標函式或約束條件裡，都是noconvex，更不用說什麼sin、cos函式了；2次函式在目標函式，如果不是SDP（半正定）的話，也是nonconvex。

2，凸優化-相對簡單

凸優化有個非常重要的定理，即任何區域性最優解即為全域性最優解。由於這個性質，只要設計乙個較為簡單的區域性演算法，例如貪婪演算法（Greedy Algorithm）或梯度下降法（Gradient Decent），收斂求得的區域性最優解即為全域性最優。因此求解凸優化問題相對來說是比較高效的。

這也是為什麼機器學習中凸優化的模型非常多，畢竟機器學習處理大資料，需要高效的演算法。

3，非凸優化-非常困難

而非凸優化問題被認為是非常難求解的，因為可行域集合可能存在無數個區域性最優點，通常求解全域性最優的演算法複雜度是指數級的（NP難）。如下圖：

最經典的演算法要算蒙特卡羅投點法了，大概思想便是隨便投個點，然後在附近區域（可以假設convex）用2中方法的進行搜尋，得到區域性最優值。然後隨機再投個點，再找到區域性最優點。如此反覆，直到滿足終止條件。

假設有1w個區域性最優點，你至少要投點1w次吧？並且你還要假設每次投點都投到了不同的區域，不然你只會搜尋到以前搜尋過的區域性最優點。

再補充一點：數學規劃模型裡面如果有整數變數，這個問題通常被稱為 highly nonconvex(極度非凸)，如下圖：

實心黑點組成的集合，是乙個離散集，按照1中判斷乙個集合是否為凸集的技巧，我們很容易驗證這個離散集是非凸的。因此整數規劃問題也是乙個非凸優化問題，並且它也是NP難的。

因此數學規劃裡最難的一類問題，叫做混合整數非線性規劃(mixed integer nonlinear programming)。

那麼整數規劃的求解思路呢，也遵循了科學研究的本質，即被分解為求解乙個個的線性規劃問題。感興趣的朋友可以搜尋分支定界法。

舉個最簡單的例子：

min x_1+x_2^3

s.t. x_1^2-x_2>=2

x_1>=0, x_2 is binary.

預計不久將來會辦個關於運籌學、數學規劃、數學建模，及其在機器學習、人工智慧、資料科學方面的應用的知乎LIVE。

再沉澱段時間。

更新，「運籌學」綜述Live入口如下：

大資料人工智慧時代的運籌學 -- Robin Shen 2017.06.11的知乎Live

以及運籌學、AI專欄 @運籌OR帷幄：

『運籌OR帷幄』大資料人工智慧時代的運籌學

最後按照慣例廣告一波：

歐洲、北美、全球留學及資料科學深度私人定製諮詢，從此DIY - 知乎專欄

3樓：王業磊

數學中最優化問題的一般表述是求取，使，其中是n維向量，是的可行域，是上的實值函式。

凸優化問題是指是閉合的凸集且是上的凸函式的最優化問題，這兩個條件任一不滿足則該問題即為非凸的最優化問題。

其中，是凸集是指對集合中的任意兩點，有，即任意兩點的連線段都在集合內，直觀上就是集合不會像下圖那樣有「凹下去」的部分。至於閉合的凸集，則涉及到閉集的定義，而閉集的定義又基於開集，比較抽象，不贅述，這裡可以簡單地認為閉合的凸集是指包含有所有邊界點的凸集。

是凸函式是指對於定義域中任意兩點，有，直觀上就是向下凸出，如下圖示意。

實際建模中判斷乙個最優化問題是不是凸優化問題一般看以下幾點：

目標函式如果不是凸函式，則不是凸優化問題

決策變數中包含離散變數（0-1變數或整數變數），則不是凸優化問題

約束條件寫成時，如果不是凸函式，則不是凸優化問題

Convex set

Convex function