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

---

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

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

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

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

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

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

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

之所以要區分凸優化問題和非凸的問題原因在於凸優化問題中局部最優解同時也是全局最優解，這個特性使凸優化問題在一定意義上更易於解決，而一般的非凸最優化問題相比之下更難解決。

資料來自維基，稍有刪減改動。

附上wiki鏈接：

Convex optimization

Convex set

Convex function

---

樓主我碩士運籌學出身，現在師從德國海德堡大學組合優化教授，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專欄：

[運籌帷幄]大數據和人工智慧時代下的運籌學 - 知乎專欄

最後按照慣例廣告一波：

歐洲、北美、全球留學及數據科學深度私人定製諮詢，從此DIY - Ruobing Shen的文章 - 知乎專欄

---

這個公式是不是應該是&<=?

---

推薦閱讀：