《若干組合幾何全局最佳化問題的機械化算法》是依託上海大學，由曾振柄擔任項目負責人的面上項目。
基本介紹
- 中文名：若干組合幾何全局最佳化問題的機械化算法
- 項目類別：面上項目
- 項目負責人：曾振柄
- 依託單位：上海大學
中文摘要,結題摘要,
中文摘要
組合幾何定理的機械化證明需要構造聯繫離散點集合的度量性質和凸性等組合性質的代數化表示, 其中的全局最最佳化問題還涉及大量空間複雜度極高的符號計算問題. 本項目圍繞若干有代表性的問題, 探索有創造性的方法, 包括基於度量方程的代數化, 奇點隔離, 矩形剖分等算法; 研究這些算法在並行和GPU計算設備上的有效實現方法,包括帶計算過程和搜尋路徑的訊息傳遞擴展方法、支持動態任務分配的負載均衡策略、單純複合形網路拓撲上的計算節點小組重組技術等; 研究組合搜尋和複雜結式計算中出現的中間過程膨脹壓縮等大數據處理方法, 試驗形式代換、數值插值、模運算、用可控制誤差的近似計算替代符號計算等新方法. 通過本項目研究逐步建立組合幾何機械化的理論和算法基礎，不僅有希望得到一些困難的組合幾何公開問題, 還可為其他專門方向的數學機械化研究提供在並行/GPU計算機上利用並行符號計算的一些有效的參考經驗.
結題摘要
本項目研究了一類組合幾何全局最最佳化問題的機械化求解算法及其實現方法. 這類組合幾何最佳化問題, 包含較多的幾何不變數之間的等式和不等式約束條件, 轉化為代數問題之後, 由於計算複雜度高的限制, 以及求解的目標是無計算誤差的證明, 不能直接用現有的最佳化方法和現有的計算機軟體解決. 為此, 本項目以幾個具體的、以前未解決的組合幾何全局最最佳化問題為切入研究對象, 探討了基於度量方程的代數化表示、奇點隔離、矩形剖分、符號數值混合計算、並行計算等方法在全局最最佳化機械化求解中的套用，一方面解決了若干有影響和難度的公開問題，包括正方形內9點Heilbronn分布、球面上歐氏度量意義下的Fermat-Torricelli點構造、Vasc不等式猜想、平面上經過給定小正方形區域的最小多項式的最低次數以及有限點集距離空間的若相容分割距離分解快速計算等問題，另一方面建立了隱函式方程插值、稀疏插值、基於Dixon結式的多元結式消元方法、基於機率的算法等處理複雜計算問題的符號-數值計算新方法，並且在共享記憶體集群計算機、帶通用圖形處理器(GPGPU)等不同架構的並行計算機上具體實現了這些方法。項目還研究了超幾何函式的化簡計算和凸體混合體積的估計問題，設計了Ramsey問題機械化證明、置換群Cayley圖直徑計算等組合數學的代數方程表示方法，通過研究多元稀疏插值，發現了關於分拆數p(n)的漸近表達式的一個新的猜測，改進了Hardy-Ramanujan的經典結果。此外，還將項目中建立的方法用於不變式生成、程式安全性驗證等套用問題的研究。在期刊和國際會議發表論文20餘篇，國內外報告論文10餘篇。約10篇已完成尚未發表。項目培養畢業博士研究生4名、碩士研究生5名，在讀研究生14名。項目顯著促進了與國內外同行之間的學術交流。項目獲得的結果將推動組合數學機械化研究，有望在人工智慧領域與組合、最佳化有關的算法設計中得到套用。
