《混合整數規劃的DC等價和DC算法》是依託上海交通大學，由牛一帥擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：混合整數規劃的DC等價和DC算法
- 項目類別：青年科學基金項目
- 項目負責人：牛一帥
- 依託單位：上海交通大學
項目摘要,結題摘要,
項目摘要
DC規劃(凸函式之差)是非線性最最佳化問題中一類特殊又非常重要的問題，是近年來國際上最最佳化領域熱門的研究方向。因DC函式和DC集(由DC函式構成的非凸集)的普遍存在性，很多困難的非線性最最佳化問題都可等價的轉化為DC規劃問題研究和求解，而且往往能得到比傳統方法更好的求解效果。該項目將深入地研究混合整數規劃的DC規劃等價形式，以期通過求解等價DC規劃問題來最終求解混合整數規劃。我們將從0-1二元變數的情況開始討論，進而深入地研究一般整數變數的情況；從線性目標函式和約束，到非線性目標函式和約束，最終設計出求解一般線性與非線性混合整數規劃的基於DC規劃的若干高效的新算法。我們還將開發一套開原始碼軟體包，以便學術界同行和套用科學界有關專家們測試和使用。
結題摘要
隨著人工智慧、量子計算和大數據時代的到來，很多核心技術問題實際上需要解決一些困難的最最佳化問題。而含有連續或離散變數的非線性最最佳化問題就是普遍存在的核心問題之一（如深度神經網路的訓練、火星岩石的識別和分類、量子糾纏態的判定等）。本項目的研究對象主要包含三個方面：混合整數規劃問題、多項式規劃問題和相關套用問題的研究。主要切入點是：從DC規劃的角度研究這些問題的DC等價表示，及相應的DC規劃求解算法的設計。本項目的主要研究成果包含“理論”和“套用“兩方面。理論方面主要包括：（1）對混合整數規劃問題的研究和求解。我們開發了基於DC規劃的若干求解算法，深入研究了DC割平面技術並提出了並行DC割平面算法，開發了並行分支定界框架，並研究了基於離散動力系統的若干混合整數規劃求解算法。（2）對於非線性規劃問題（特別是多項式規劃問題）的研究和求解。提出了多項式的平方差（DSOS）和凸平方差（DCSOS）分解理論，並基於DCSOS分解開發了多項式規劃的DC求解算法。套用方面主要包括：（1）跨學科相關套用問題的研究，例如，機器學習中自然語言處理問題、高階資產組合最佳化、矩陣特徵值互補問題、空間-時間深度神經網路模型、雷射誘導電漿光譜分析和量子糾纏態判定等若干實際套用問題的研究。（2）相關最最佳化軟體和科學計算程式包的開發，例如，基於DC規劃和並行分支定界算法的混合整數規劃求解器、基於DC割平面的混合0-1線性規劃求解器、DC規劃圖形界面集成開發環境DCIDE、自然語言處理工具包NLPTOOL、基於DSOS和DCSOS的多項式分解軟體包、求解0-1多項式規劃的離散動力系統算法包（Lie和Houbolt等差分格式）、DC規劃基礎類庫（DC函式類、DC模型類和DCA算法類）、POLYLAB多項式矩陣類庫以及空間-時間深度學習的模型和代碼等。在本項目的資助下，目前見刊論文4篇，在審論文3篇，在研論文9篇，應邀國際大會報告9次和國內外學術報告6次，邀請海內外專家來校學術交流7次，同9位專家開展學術合作，赴美國和加拿大訪學三個月，作為組委成員參與組織國際學術大會1次，獲得國際大會最佳海報獎1次，開發最最佳化和科學計算軟體16款，其中部分代碼以MIT開源軟體的形式共享在Github平台上，另有兩款軟體（“混合整數規劃的並行分支定界DC規劃求解器”和“DCIDE”）正在申請智慧財產權。
