【觀點】運籌學發展概況（上）

本文已發於微信公眾號【運籌OR帷幄】：【觀點】運籌學發展概況（上）

作者： 藍色的信封

『運籌OR帷幄』責任編輯： @文雨之（東北大學系統工程博士生）

本篇文章是由以上作者在博客上的優秀文章（原文鏈接: 運籌學的發展概況），通過『運籌OR帷幄』責任編輯整理修改而成的。

歡迎原鏈接轉發，付費轉載請前往 @留德華叫獸 的主頁獲取信息，盜版必究。

敬請關注和擴散本專欄及同名公眾號，會邀請全球知名學者陸續發布運籌學、人工智慧中優化理論等相關乾貨、知乎Live及行業動態：

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

0.前言

『運籌OR帷幄』特別推出了運籌學歷史回顧的專題運籌學的發展概論，本篇文章為運籌學概論（上），後續會推出中篇和下篇，盡請各位持續關注。60 多年以來，運籌學在研究與解決複雜的實際問題中不斷地發展和創新，各種各樣的新模型、新理論和新演算法不斷湧現，有線性的和非線性的，連續的和離散的、確定性的和不確定性的。至今它已成為一個龐大的、包含多個分支的學科，其中一些已經發展得比較成熟，另外一些還有待完善，還有一些才剛剛形成。

1.數學規劃

數學規劃是在決策變數滿足一定約束下求一個或多個函數的極小值或者極大值。它以大量實踐中抽象出來的典型最優化模型為研究對象，利用數學工具研究這些模型的數學性質，構造與實現求解方法，以及將演算法應用於實際問題。

2.線性規劃

自1939 年蘇聯數學家康托羅維奇提出線性規劃問題和1947 年美國數學家丹齊格求解線性規劃問題的通用方法──單純形法以來，線性規劃可以說是研究得最為透徹的一個研究方向。單純形法統治線性規劃領域達40 年之久，而且至今仍是最好的應用最廣泛的演算法之一。雖然它在最壞情況具有指數複雜性，但在平均意義下已經證明是一個多項式演算法。目前，關於單純形演算法的研究主要在於如何選取主元。

另一大類演算法是內點法，它起源於1979 年蘇聯數學家卡奇揚提出的多項式橢球演算法，而因1984 年美籍印度裔數學家卡瑪卡提出的多項式時間演算法而迅速成為國際熱點，各式各樣的演算法大量湧現：諸如仿射變換法、勢函數方法、對數罰函數法、路徑跟蹤法、原始對偶法、不可行內點法等等。

目前線性規劃的內點法也趨於成熟，這方面的研究者們目前大都致力於以線性規劃作為特例的錐規劃，以及如何利用線性規劃鬆弛求解整數規劃等方面的研究。然而，就線性規劃而言，是否存在強多項式演算法仍然是一個重要且困難的理論問題。

3.非線性規劃

等式約束規劃問題的最優性條件可追溯到拉格朗日，一般非線性規劃問題的最優性條件則歸功於卡羅胥和庫恩與塔克，是他們奠定了非線性規劃的理論基礎。然而，目前還有不少人試圖在沒有強互補的條件下進行理論分析和演算法研究。對偶理論是非線性規劃理論研究的另一個重點。在計算方法方面，早期的方法以最速下降法和牛頓法為主。1959 年擬牛頓法的引入和1964 年非線性共軛梯度法的出現，吸引了許多研究者研究非線性規劃。目前，序列二次規劃演算法是一類被用於廣泛求解一般非線性規劃的有效演算法，同時也還有許多研究者在為改善這類演算法努力，其中包括序列線性規劃演算法以及內點演算法等。非線性規劃演算法通常使用線搜索策略選取步長，或通過求解信賴域子問題而得到新的迭代點。這兩個方面的研究非常基本，但仍有改善的空間。2001年弗萊徹和勒斐通過將非線性規劃問題視為雙目標問題而提出的濾子方法和2002 年鮑威爾提出的基於二次插值的直接法是近些年來兩個重要的演算法進展。對於約束規劃問題，如何推廣鮑威爾的直接法；對於大規模問題，如何設計子空間演算法；以及如何有效求解一般非線性規劃的全局最優，和一些來自於圖像處理等領域的特殊的非光滑問題是目前非線性規劃比較重要的研究問題。

總之，儘管在表面上看非線性規劃已經有許許多多的研究，但由於非線性的存在，好的研究結果還將會不斷出現，並且隨著問題的不同而產生更加具有針對性的特殊演算法。

4.錐規劃

錐規劃是線性空間中凸錐上的數學規劃，它是線性規劃與非線性規劃的推廣。自上世紀90 年代中期開始，它一直是國際優化領域的研究熱點。相關的研究帶動了數學規劃學科的深入發展，促進了代數、群論、拓撲學、幾何學、非線性分析等分支在數學規劃中的融合，以及優化理論與技術在工程、交通、經濟與金融、管理等領域的廣泛應用。

目前的錐規劃方面的研究成果主要包括以下4 個方面：

• 二階錐優化和半定優化

線性二階錐優化和半定優化已經得到了很好的發展，並且廣泛地應用於各種實際問題。近些年，人們開始致力於非線性二階錐優化和非線性半定優化的理論與演算法研究；

• 對稱錐優化

上世紀末國際優化專家開始致力於這一領域的研究，主要集中在求解對稱錐上線性優化問題的內點演算法方面。近幾年，人們開始探討對稱錐上的非線性優化問題和非凸優化問題的理論與各種演算法；

• 齊次錐優化

齊次錐的理論早在1963 年就有相關研究，但齊次錐優化問題的研究最近才開始；

• 雙曲錐優化

這方面目前只有很少的理論研究，需要尋求合適的工具開展其理論與演算法的研究。

5.矩陣規劃

在眾多的科學領域與社會經濟中，很多優化問題的決策變數是一個具有特殊結構的矩陣，這樣的優化問題被稱為矩陣優化或者矩陣規劃。矩陣規劃的早期研究可以追溯到1981 年，然而真正的研究是在20 世紀90 年代，它以被譽為21 世紀的線性規劃-半定規劃為研究起點。至今，線性半定規劃的理論趨於完善，人們正在發掘它在實際中的應用。然而，目前的數值軟體只能有效地求解矩陣維數小於500 的小規模線性半定規劃問題，因此，開展大規模半定規劃的數值方法研究是當前一項十分迫切而又重要的課題。

此外，由著名華裔數學家陶哲軒等人在2006 年提出的壓縮感測理論而引發的低秩矩陣問題，其理論與演算法研究是當今優化領域與信息科學領域（例如，信號處理、圖像恢復與重建）共同關心的熱點研究課題。

6.小結

在未來一段時期里，矩陣（錐）優化理論與演算法、張量（錐）優化理論與演算法、多項式優化理論與演算法研究等方向必將引起人們的關注。

變分不等式與互補問題是一類具有普遍意義的均衡優化模型。它不僅為非線性優化、極大極小、對策論、非線性方程、微分方程等提供了一個統一的理論框架，而且在力學工程、交通、經濟、管理等實際部門有廣泛的應用。

互補問題首先由丹齊格和科特爾於1963 年提出。次年，科特爾在他的博士論文中第一次提出求解它的非線性規劃演算法。變分不等式問題首先由哈特曼和斯塔姆巴切在1966 年提出。後來發現，變分不等式是互補問題的一個推廣，且其數學性質和應用有驚人的相似之處。所以，它們經常在文獻中成對出現。變分不等式與互補問題被提出後，很快引起了當時運籌學界和應用數學界的廣泛關注和濃厚興趣，許多人參與了這類問題的研究。經過40 余年的探索，特別是20 世紀最後10 年的研究，人們在理論與演算法方面取得了豐富、系統的成果, 並在科技與經濟中得到了廣泛的應用。

當前主要是對於廣義變分不等式和錐互補問題的研究，而對於不確定信息下變分不等式和互補問題的研究無疑是發展的必然。歸納起來，對它們的研究可分為理論與演算法兩方面：

前者主要研究解的存在性、唯一性、穩定性與靈敏度分析以及它們與其他數學問題的聯繫等；

後者則主要建立有效的求解方法及相應的理論和數值分析。

以上『運籌OR帷幄』專欄所有文章都會同步發送至 留德華叫獸的頭條主頁， 以及同名微信公眾號，目前預計受眾10w +

如果你是運籌學/人工智慧碩博或在讀，請在下圖的公眾號後台留言：「加微信群」。系統會自動辨認你的關鍵字，並提示您進一步的加群要求和步驟，邀請您進全球運籌或AI學者群（群內學界、業界大佬雲集）。

同時我們有：【運籌學|優化愛好者】【供應鏈|物流】【人工智慧】【數據科學|分析】千人QQ群，想入群的小夥伴可以關注下方公眾號點擊「加入社區」按鈕，獲得入群傳送門。

學術界|工業界招聘、徵稿等信息免費發布，請見下圖：