《多重齊次多項式最佳化的近似算法及其套用》是依託杭州電子科技大學，由凌晨擔任項目負責人的面上項目。
基本介紹
- 中文名：多重齊次多項式最佳化的近似算法及其套用
- 項目類別：面上項目
- 項目負責人：凌晨
- 依託單位：杭州電子科技大學
項目摘要,結題摘要,
項目摘要
多重齊次多項式最佳化有廣泛而重要套用，受到普遍重視。我們將採用最佳化方法(如對偶、鬆弛、分解等)與張量計算理論相結合的技術，以多重二次多項式最佳化為切入口，逐步展開對有較高次數或重數但結構有一定特殊性的多重齊次多項式最佳化研究：(1)建立多重齊次多項式最佳化的全局最最佳化理論，包括解的存在性和結構理論、誤差界估計與最優性條件等。(2)利用適當轉化技術和多重線性、半定鬆弛，在將多重齊次(二次)多項式最佳化轉成多重線性或多重半定規劃基礎上，設計求解原問題全局最優解的(近似)算法並分析計算複雜性；針對一些雖形式特殊但套用背景強烈的問題，藉助張量計算工具，研究多項式存儲問題，建立可求偏大規模問題的快速有效算法。（3）研究係數非負的多重齊次多項式最佳化與張量特徵值（或奇異值）問題，包括更一般的Perron-Frobenius 定理及相關算法與收斂分析。(4)研究多重齊次多項式最佳化模型與算法在複雜網路通訊設計中套用。
結題摘要
多重齊次多項式最佳化與張量分析、計算關係密切。第一，研究單位球面約束的高次齊次多項式最佳化和多重線性多項式最佳化，在係數張量為對稱時，證明了上述兩問題的最優值相同。證明了對稱張量的最佳對稱秩-1逼近和最佳秩-1逼近相同，給出了相應算法。進一步，研究單純形約束多重二次規劃的最優值近似界和近似解，給出了形式簡單、計算成本低的最優值下界，給出了近似解的相對近似率，建立了原問題與半定規劃的等價關係。第二，針對張量特徵值問題，研究張量determinant性質，及張量特徵值(或奇異值)與多項式最佳化的關係，給出若干性質。研究張量的兩類特徵值互補問題，其中包括解的存在性與拓撲性質、解的個數與值的估計、多項式最佳化等價形式及相關數值算法。第三，研究若干可求解特殊最佳化問題的數值算法、理論分析並用於張量特徵值互補問題：(1)鬆弛的投影方法、(2)子問題具有顯式解的可執行分裂算法、(3)分散式Douglas-Rachford分裂算法。第四，針對與半定規劃、張量正定和協正定判別等關係密切的半無限規劃，利用積分“聚積”技術和高效積分計算，設計算法並進行收斂性分析和數值計算。第五，針對一般非光滑約束方程組，設計數值算法、分析收斂性、進行數值試驗，並用於求解隨機非線性互補問題。
