作者知乎ID：留德華叫獸
作者簡介：作者 @留德華叫獸系美國克萊姆森大學運籌學碩士，Ph.D. Candidate，後跳槽至歐盟瑪麗居里博士專案，期間前往義大利IBM Cplex實習半年，現任德國海德堡大學交叉學科計算中心、組合最佳化實驗室助理研究員，主攻影像處理。
敬請關注和擴散本公眾號及同名專欄，會邀請全球知名學者陸續釋出運籌學、人工智慧中最佳化理論等相關乾貨、知乎Live及行業動態：
『運籌OR帷幄』大資料人工智慧時代的運籌學–知乎專欄：http://t.cn/RlNoO3P
『運籌OR帷幄』專欄有獎徵稿專帖：http://t.cn/RHH0eEG
前言
運籌學在國內，遠沒有新興的人工智慧以及傳統學科統計來的普及。人工智慧、統計最後幾乎都能化簡成求解一個能量/損失函式的最佳化問題。但相信很多人不知道，運籌學正是研究最佳化理論的學科。而因此，我把運籌學稱為人工智慧、大資料的“引擎”，正本清源其在人工智慧中重要性。
1，運籌學、線性規劃回顧
2，整數規劃問題
3，什麼是組合最佳化
4，非凸最佳化
5，整數規劃與非凸最佳化的關係
6，整數規劃、非凸最佳化為何重要
7，整數規劃在工業界的應用
8，整數規劃在AI的應用和展望
注：以下文中黑體字代表其在學術界的術語
首先，對運籌學（O.R.）還比較陌生的童鞋，請戳本專欄的開篇之作：
運籌學–一門建模、最佳化、決策的科學 – 知乎專欄
:http://t.cn/ROBybx3
運籌學、線性規劃（Linear Programming）回顧
1
運籌學的初學者，歡迎檢視我在下面的回答：
運籌學如何入門？
: http://t.cn/RlNoHiM
運籌學、數學規劃（Math Programming）問題的數學表示式，由自變數（Variables）、目標函式（Objective Function）和約束條件（Constraints）組成，所有最佳化問題本質上都可以化簡為由它們組成的數學表示式，然後求解滿足約束條件下使得目標函式最大/小的變數的值。
如上圖，當自變數是連續的，目標函式和不等式是線性的時候，該問題被稱為線性規劃問題。線性規劃因其具有的良好性質（例如，最優解必定出現在極點），可以用單純型法（Simplex Method）或內點演算法（Interior Method）高效地求解，熟悉演算法複雜度的童鞋，知道它是多項式時間可解的（Polynomial Time Solvable–O（n^k））。這裡n表示自變數個數。
可行域（Feasible Set）：可行解的集合。如下圖，陰影區域（多面體、Polyhedron）即為三個線性不等式（半平面）組成的可行域。是不是很眼熟？其實高中代數課大家就已接觸過線性規劃了。
整數規劃（Integer Programming）問題
2
整數規劃，或者離散最佳化（Discrete Optimization），是指數學規劃問題中自變數存在整數。與線性規劃連續的可行域不同，整數規劃的可行域是離散的。
如上圖，藍線依舊代表線性不等式，但是這裡x,y被約束成整數變數，因此可行域變成了紅線區域內的9個離散的點。
凸包（Convex Hull）:整數規劃所有可行點的凸包圍，即圖中紅線組成的多面體（想象多維的情況）。凸包是未知的，已知的是藍線的不等式，並且凸包是非常難求解的，或者形成凸包需要指數數量級的線性不等式（圖中紅線）。如果知道了凸包的所有線性表示，那麼整數規劃問題就可以等價為求解一個凸包表示的線性規劃問題。
另外，除了整數規劃，還有混合整數規劃（Mixed Integer Programming, MIP），即自變數既包含整數也有連續變數。如下圖：
x是連續的，y被約束成整數變數，這時候可行域變成了4條離散的橘黃色線段+4處的紅色整數點（0,4）。課後作業，求圖中的凸包。
整數規劃的精確演算法通常需要用到分支定界法（Branch and Bound Method）,以及增加分支定界效率的各種技巧，例如割平面方法（Cutting Planes Method）。總的來說，求解整數規劃的精確解是NP難的，也就是指數級演算法複雜度（Exponential Time Solvable）。
怎麼來理解指數級複雜度呢？假設這裡的整數是0,1變數，那麼我們可以簡單地理解為演算法複雜度是2^n（需要解2^n個線性規劃問題）。也就是說，每增加一個0，1變數，求解的速度就有可能要增加一倍！例如求解n=100的整數規劃問題需要1小時，那麼求解n=101的規模可能會需要2小時，n=102需要4小時，n=105需要32小時。。這就是指數爆炸！
因此，整數規劃問題被看作數學規劃裡、甚至是世界上最難的問題之一，被很多其他領域（例如機器學習）認為是不可追蹤（Intractable）的問題，也就是他們直接放棄治療了。
作為研究世界上最難問題的學者，想出瞭解決整數規劃問題的各種其他途徑，例如近似演算法（Approximation Algorithms），啟發式演算法（Heuristic Algorithms），遺傳演算法（Evolution Algorithms, Meta-Heuristic）等等。它們雖然不能求得整數規劃的最優解，但是卻能在短時間（通常多項式時間）內給出一個較好的可行解。
篇幅限制，我將在下一篇專欄著重探討整數規劃精確解的演算法、整數規劃求解器、近似演算法以及啟發式演算法，敬請期待。
什麼是組合最佳化
(Combinatorial Optimization)
3
通俗的講，我把組合最佳化理解為，在組合最佳化種可能性裡找出最優的方案。假設自變數為n，用強力搜尋法（Brute–force Algorithm）來解組合最佳化的演算法複雜度最壞需要n的階乘！什麼概念？這比指數爆炸還要可怕！
從這個意義上講，組合最佳化是整數規劃的子集。的確，絕大多數組合最佳化問題都可以被建模成（混合）整數規劃模型來求解。但是似乎學術圈更多地把組合最佳化與圖（Graph）最佳化以及網路流（Network Flow）最佳化聯絡在一起，並且最終目標不在精確解，而是近似解。（這點可以從整數規劃的國際會議上看出）
Anyway，這裡開始，我將混淆整數規劃、離散最佳化、組合最佳化。
下面給出一個經典的組合最佳化例子-最大流問題（Max Flow Problem）：
給定一張圖G（V，E），V是點（Node）的集合，E是邊（Edge）的集合。該問題試圖從點0到5導流最大的流量，邊上的數字代表該條邊的最大流量，因此形成了約束條件–每條邊的流量不得超過該條邊的限額。自然而然地，該問題可以被建模成一個整數規劃問題。
我們跳過模型和演算法，直觀的判斷該問題的演算法複雜度大概為多少。設想從0出發，有倆種可能線路，0到1以及0到2；從1和2出發，有分別有倆種可能的線路。因此，可以初步判斷，改問題如果用強力演算法（窮舉法），演算法複雜度將為指數級！
但是聰明的組合最佳化學家，把這個看似指數級演算法複雜度的問題，用巧妙的演算法多項式時間便可求解出最優解。This is the beauty of Mathematics!
時間關係，該問題的具體模型和近似演算法，會放在下一篇專欄展開，有興趣的可以搜尋“Max Flow/Min Cut”。
非凸最佳化 （Non-Convex Optimization）
4
凸（Convex） VS 非凸的概念，數學定義就不寫了，介紹個直觀判斷一個集合是否為Convex的方法，如下圖：
簡單的測試一個集合是不是凸的，只要任意取集合中的倆個點並連線，如果說連線段完全被包含在此集合中，那麼這個集合就是凸集，例如左圖所示。
凸最佳化有個非常重要的定理，即任何區域性最優解即為全域性最優解。由於這個性質，只要設計一個較為簡單的區域性演算法，例如貪婪演算法（Greedy Algorithm）或梯度下降法（Gradient Decent），收斂求得的區域性最優解即為全域性最優。因此求解凸最佳化問題相對來說是比較高效的。這也是為什麼機器學習中凸最佳化的模型非常多，畢竟機器學習處理大資料，需要高效的演算法。
而非凸最佳化問題被認為是非常難求解的，因為可行域集合可能存在無數個區域性最優點，通常求解全域性最優的演算法複雜度是指數級的（NP難）。如下圖：
最經典的演算法要算蒙特卡羅投點法(Monte Carlo Algorithm)了，大概思想便是隨便投個點，然後在附近區域（可以假設convex）用2中方法的進行搜尋，得到區域性最優值。然後隨機再投個點，再找到區域性最優點。如此反覆，直到滿足終止條件。
假設有1w個區域性最優點，你至少要投點1w次吧？並且你還要假設每次投點都投到了不同的區域，不然你只會搜尋到以前搜尋過的區域性最優點。
整數規劃與非凸最佳化的關係
5
大家或許不知道，（混合）整數規劃被稱為極度非凸問題（highly nonconvex problem），如下圖：
實心黑點組成的集合，是一個離散集，按照4中判斷一個集合是否為凸集的技巧，我們很容易驗證這個離散集是非凸的，並且相比4中的非凸集更甚。因此整數規劃問題也是一個非凸最佳化問題。
整數規劃、非凸最佳化為何重要
6
雖然時間是連續的，但是社會時間卻是離散的。例如時刻表，通常都是幾時幾分，即使精確到幾秒，它還是離散的（整數）。沒見過小數計數的時刻表吧？
同樣，對現實社會各行各業問題數學建模的時候，整數變數有時是不可避免的。例如：x輛車，y個人。x，y這裡便是整數變數，小數是沒有意義的。
決策變數(
Decision Varible
): x={0,1}.
0/1變數被廣泛地應用在商業和決策領域。我們假設變數x={0,1}，當x=1的時候，我們便可以建模執行x這個決策；x=0，則表示不執行。這樣引入決策變數x的建模技巧，在工業界案例中屢見不鮮。
從這些案例，社會是由一個個離散變數組成的。
關於非凸最佳化，現實生活中，萬物的本質是非凸的，就像萬物是趨於混亂（Chaos）的，規則化需要代價。如果把4中的圖看作山川盆地，你在現實中有見過左圖那麼“光滑”的地形麼？右圖才是Reality！
說到這裡，當然不能否定了凸最佳化和連續最佳化的作用，科學的本質便是由簡到難，先把簡單問題研究透徹，然後把複雜問題簡化為求解一個個的簡單問題。求解整數規劃便是利用分支定界法求解一個個線性規劃問題，非凸最佳化同樣如此。
整數規劃在工業界的應用
7
路徑最佳化問題（Routing Problem）–交通領域（GPS導航）；
倉儲、運輸等物流（Logistics）以及供應鏈(Supply chain)領域；
製造業裡的生產流程最佳化（Process Optimization）；
電力領域的電網的佈局以及分配(Power Grid)；
電子工程裡的設施部件分配問題(Facility Layout Problem)；
能源領域的最佳化，如：如何鋪設輸油管道；
火車、課程、飛機時刻表安排問題等排程問題 (Scheduling Problem);
資產配置 （Asset Allocation）、風險控制 (risk management)等經濟金融領域的應用；
以上工業界的應用，頻繁使用著決策變數，以及整數變數，建模成（混合）整數規劃模型，而機器學習（ML），特別是深度學習（DL），至今沒有怎麼滲透進來。也希望有志青年探索ML、DL在這些領域的應用。
國內(全球)TOP網際網路公司、學術界超高薪的攬才計劃有哪些？
:http://t.cn/RYc9fzj
整數規劃在AI的應用和展望
8
如果你是AI初學者，請戳：
大話“人工智慧、資料科學、機器學習”–綜述
: http://t.cn/RXkSyMn
這裡我舉一個統計和機器學習的例子，這個模型也可以和統計裡經典的Lasso問題聯絡起來，以及可以給出L0範數問題的精確解。
如下圖，是一個分段常數迴歸問題。統計中大家都知道線性迴歸和常數迴歸，其中常數迴歸即求一組數的平均值。但是這裡，我們想對資料分段，並且不知道分段的節點在哪裡。如下例所示，假設n個點，要分成三段作常數迴歸，節點有2個。那麼節點的選擇有n選2種可能性，從這個意義上理解，這個問題是一個組合最佳化的問題。
自變數有實數變數w和整數變數x，y_i是常數，即點i的值，w_i是迴歸值，上半部分的表示式可以看作是偽表示式（pseudo formulation），L0函式即向量中非零的個數（可能需要一些高等的數學知識）。我們直接看下半部分的混合整數非線性規劃模型。
我們引進了一個0/1決策變數，X_{ei},這個變數是作用在邊上的。我們希望當它是處於節點位置，即倆段常數迴歸的臨界處，就等於1；但它處於某一段常數迴歸中間時，就等於0.
因此目標函式前半部分是迴歸方程，希望迴歸的誤差越小越好，後半部分即為規則化項（regularization term），用來約束分段的個數，來懲罰過多的分段以防止過擬合（over-fitting）。大家經常可以在訊號處理、影像處理中看到這樣的目標函式。
約束條件第一個不等式保證了同一個分段迴歸中，w_i和w_{i+1}的值相等，因為x_{ei}=0；而在節點處，他們可以不相等，M是一個很大的常數，以保證節點處x_{ei}=1時，不等式總是成立。
寫出了這個整數規劃模型，我們就可以程式設計並呼叫整數規劃的最佳化求解器來求解這個問題的最優解。例如IBM Cplex。雖然整數規劃通常的演算法複雜度是指數級的，但是比起強力搜尋，還是會高效很多很多。這樣我們就可以得到每個點的迴歸值w以及分段的節點，即哪些點x_e=1。
深度學習的最佳化問題在運籌學看來是“小兒科”，這句話可能會打臉大部分觀眾。雖然目標函式非常複雜，但是它沒有約束條件阿！
深度學習裡的損失函式，是一個高度複合的函式。例如h(x)=f(g(x))就是一個f和g複合函式。深度學習裡用到的函式，Logistic, ReLU等等，都是非線性 ，並且非常多。把他們複合起來形成的函式h,便是非凸的。但是深度學習訓練引數的最佳化問題，本質是一個無約束的非凸最佳化問題。求解這個非凸函式的最優解，類似於求凸最佳化中某點的gradient，然後按照梯度最陡的方向搜尋。不同的是，複合函式無法求gradient，於是這裡用方向傳播法（Back Propagation）求解一個類似梯度的東西，反饋能量，然後更新。
機器學習、資料科學因為處理資料量龐大，因此研究問題主要的方法還是凸最佳化模型（包括線性規劃、錐最佳化），原因正是求解高效，問題可以scale。
想學資料分析（人工智慧）需要學哪些課程？
:http://t.cn/RQo3JRK
雖然目前還很小眾，但是隨著計算機硬體能力的提高，以及GPU平行計算的流行，以及非凸最佳化演算法、模型的進化，想必非凸最佳化，（混合）整數規劃會是未來的研究熱點。
敬請關注我老闆，Gerhard Reinelt 教授，以及我們的合作教授之一，法國Rouen的Stephane Canu教授，最近便投身於整數規劃在機器學習的應用。（當然還有我：）以及蒙特利爾的Andrea Lodi教授，目前與Yoshua探索著MIP與DL的交叉。當然還有運籌學界泰斗之一，MIT ORC的Dimitris Bertsimas，近十年都在統計、資料學界推崇整數規劃。
如果你是運籌學/人工智慧碩博或在讀，請新增微訊號：zf13772441490（備註請務必按照：姓名/暱稱-加群型別-單位/學校-最高/在讀學位-研究方向，否則不會透過），她會拉你進全球運籌或AI學者群（群內學界、業界大佬雲集）。
運籌學/控制論/隨機最佳化愛好者
➦qq群：686387574
人工智慧愛好者
➦qq群：685839321
『運籌OR帷幄』專欄原文請戳閱讀原文