《社會計算問題與逆變分不等式求解》是依託南京大學,由何炳生擔任項目負責人的面上項目。
基本介紹
- 中文名:社會計算問題與逆變分不等式求解
- 項目類別:面上項目
- 項目負責人:何炳生
- 依託單位:南京大學
項目摘要,結題摘要,
項目摘要
社會計算中許多問題都歸結為一個最優平衡問題,與經典的變分不等式通常要求自變數落在一定範圍內不同,刻畫巨觀調控平衡問題的變分不等式一般要求其函式(調控目標)落在規定的範圍內而自變數(政策)變動儘可能小。這類問題的數學模型是將經典的變分不等式中自變數與函式互換位置得到的逆變分不等式。再者,源自社會計算的逆變分不等式中的函式一般沒有顯式表達式,只能對給定的自變數,觀測到相應的函式值,而且這種觀測通常是代價不菲的。因此,求解源自實際生活的逆變分不等式需要只用函式值且少用函式值的方法。. 平衡問題的求解是一個疊代過程。對於源自管理科學的逆變分不等式,疊代就是一個逐步調整政策、解決矛盾、趨向最優平衡的過程。解決實際問題要求矛盾在調整過程中越來越緩和,體現在算法上則要求對'矛盾'給出合理的度量,給出矛盾在疊代過程中越來越緩和的單調型算法。
結題摘要
管理科學和工程技術計算是最最佳化理論與方法的兩大主要套用領域。本項目在求解管理科學中逆變分不等式和數據科學中結構型凸最佳化問題的一階方法上做了一些有益的工作。 社會計算中的許多問題一般歸結為一個最優平衡問題,它的數學形式是一個逆變分不等式。人們要求調控變數的波動儘可能小,而狀態要滿足社會需求。這類問題的函式一般沒有顯式表達式,只能對給定的自變數,通過代價不菲的觀測到相應的函式值。本項目針對管理科學中的這類逆變分不等式,提出了只用函式值且少用函式值的求解方法,是以套用為驅動的方法。結構型最佳化問題大量出現在數據科學中。求解結構型最佳化問題的一階方法與變分不等式求解的只用函式值的方法與有許多共同之處。基於求解變分不等式的基礎,對求解數據科學中的問題,做了以下工作: 1. 成功地套用交替方向法求解了矩陣完整化、圖像處理等數據科學中的重要問題; 2. 在交替方向法被認為是求解數據科學問題有效手段的時刻, 基於主持人對分裂算法長期研究的積累,證明了交替方向法的 O(1/t) 的計算複雜性,受到學界重視;3. 提出了一類收斂性證明非常簡單的 PPA意義下的收縮算法,為圖像數據科學採用,受到著名圖像科學工作者的肯定;4. 對多個可分離運算元的問題,首先提出了有理論保證的預測-校正分裂算法,被包括美國 UCLA 的課題組在求解降維問題時採用。上述研究結果,均有論文在SIAM 系列刊物發表,並受到廣泛關注,目前有 3 篇 SIAM 系列論文同時在SIAM的most frequently download paper 中。項目主持人正受 Foundations and Trends of Optimization之邀,整理這方面的成果。