《完全正最佳化的若干問題研究》是依託上海交通大學，由範金燕擔任項目負責人的面上項目。
基本介紹
- 中文名：完全正最佳化的若干問題研究
- 項目類別：面上項目
- 項目負責人：範金燕
- 依託單位：上海交通大學
項目摘要,結題摘要,
項目摘要
完全正最佳化是最最佳化領域的新興研究方向，它在組合最佳化、數理統計、信號處理等領域有著很廣泛的套用。完全正最佳化的研究在國際上還處於起步階段，關於它的研究成果還比較少。由於完全正矩陣判定的NP-難性，對於完全正矩陣和完全正張量的處理較為複雜，沒有直接的方法，所以完全正最佳化的研究具有相當大的難度和挑戰性。本項目將研究以下幾個完全正最佳化問題：完全正矩陣錐內點的判定和表示；線性矩陣束與完全正矩陣錐之間的距離問題；矩陣的完全正逼近；以及完全正張量的判定和非負分解、完全正張量的填充問題和張量的最佳完全正逼近問題。我們將從多項式最佳化的角度出發，將完全正最佳化問題轉化為矩最佳化問題，利用序列線性矩陣不等式逼近完全正矩陣錐和完全正張量錐，設計半正定鬆弛算法，討論算法的漸進收斂性和有限收斂性。我們的研究將為解決完全正最佳化問題提供新的視角和方法，為完全正最佳化在實際領域中的套用提供理論保證。
結題摘要
完全正最佳化在組合最佳化、數理統計、信號處理等領域有廣泛的套用。完全正矩陣錐的處理沒有直接的方法，通常是用一些簡單易處理的凸錐來逼近，但這樣往往得不到問題的最優解。我們從多項式最佳化的角度，利用序列線性矩陣不等式逼近完全正矩陣錐，提出的半正定鬆弛等級算法框架總能夠得到問題的全局最優值和最優解。1.我們將矩陣的最佳完全正逼近問題轉化為矩變數錐和範數錐約束的線性最佳化問題，構造了一個半正定鬆弛等級算法求解。算法在一般性條件下，有限步終止。文章被SIAM J.Matrix Anal.Appl.選為“特推論文”（Featured Article）。2.對於線性矩陣束與完全正矩陣錐之間的距離問題，我們給出了半定鬆弛算法，分析了算法的收斂性質。同時，給出了完全正矩陣判定的一個新模型。3.我們解決了完全正張量的判定和分解問題，提出的半正定算法能判定一個張量是否為完全正張量，如果不是，給出判定準則，如果是，則給出它的一個完全正分解。在CP-秩和CP-秩分解方面也取得了一些進展：給出了二維完全正張量的充分必要條件；提出了計算其CP-秩和CP-秩分解的半正定鬆弛算法；並進一步刻畫了CP-秩分解唯一的條件。我們還解決了極小核值完全正張量填充問題。4.我們證明了張量特徵互補問題的互補特徵值的個數有限，且每個互補特徵值對應的互補特徵向量存在且唯一（除了相差一個常數倍），並提出了計算其全部互補特徵對的半正定算法。5.我們還研究了非線性方程組的自適應LM方法，能大幅度降低Jacobi矩陣的計算量和總計算量，給出了非精確LM方法的一般性框架和複雜度。6.此外，我們考慮了Celis-Dennis-Tapia問題和二次約束二次規劃問題的子空間性質，並給出了子空間的選取方法，當子空間的維數遠遠小於原空間的維數時，問題的計算量將大幅度降低。在本項目支持下，出版了專著《非線性方程組數值方法》，在國際學術期刊上發表論文20篇，其中Math.Program.1篇、SIAM J.Matrix Anal.Appl.1篇、J.Sci.Comput.2篇、Math.Oper.Res.1篇、Comput.Optim.Appl.3篇、J.Global Optim.2篇。這些結果豐富了完全正最佳化理論和非線性方程組理論，為實際領域的完全正最佳化問題和非線性方程組問題提供了新的方法及其理論保證。
