《結構低秩矩陣最佳化問題的多階段凸鬆弛法研究》是依託華南理工大學，由潘少華擔任項目負責人的面上項目。
基本介紹
- 中文名：結構低秩矩陣最佳化問題的多階段凸鬆弛法研究
- 項目類別：面上項目
- 項目負責人：潘少華
- 依託單位：華南理工大學
項目摘要,結題摘要,
項目摘要
結構低秩矩陣最佳化問題在統計、控制與系統辨識、信號與圖像處理、機器學習、以及組合最佳化等諸多領域中有著廣泛套用．本課題擬從結構低秩矩陣最佳化問題的等價MPEC入手，通過鬆弛其廣義互補約束誘導的精確罰來開展該類非凸非光滑最佳化問題的多階段凸鬆弛法研究，包括(1)研究將MPEC的廣義互補約束罰到目標函式上所誘導的罰問題在全局意義下的精確性；(2)將MPEC的精確罰問題鬆弛為系列易處理的非光滑凸矩陣最佳化問題，設計多階段凸鬆弛方法；(3)研究每階段凸鬆弛問題的(近似)最優解與真實解(或原問題最優解)的誤差和近似秩界，分析多階段凸鬆弛方法的收斂速率；(4)設計求解凸鬆弛問題的有效收斂算法，研究其收斂速率；(5)編寫多階段凸鬆弛算法的程式代碼，進行數值試驗．該研究成果將為結構低秩矩陣最佳化問題和可分離非光滑凸矩陣最佳化問題提供有效的計算工具，豐富低秩矩陣最佳化和非光滑凸矩陣最佳化的理論，具有重要理論意義和套用價值．
結題摘要
結構低秩矩陣最佳化問題在統計、控制與系統辨識、信號與圖像處理、機器學習、量子計算以及組合最佳化等諸多領域中有著廣泛套用。本課題從低秩矩陣最佳化問題的等價 MPEC 形式入手，藉助其平衡約束誘導的全局精確罰開展了求解這類非凸非光滑矩陣最佳化問題的多階段凸鬆弛法的研究。 主要研究內容包括：(1)研究了等價 MPEC 的平衡約束所誘導的罰問題的全局精確懲罰性以及錐約束最佳化及廣義方程的平穩性；(2)將全局精確罰鬆弛為系列易於處理的凸矩陣最佳化問題設計了相應的多階段凸鬆弛法；(3)對所提出的多階段凸鬆弛法，建立了統計理論保證；(4)研究了求解每階段凸鬆弛問題的塊分裂算法的疊代複雜界和收斂速率；(5)編寫了多階段凸鬆弛法的程式代碼，並進行了大量數值試驗究。取得了如下幾方面的重要成果：(一)通過研究錐約束最佳化及廣義方程的平穩性，對秩(正則)極小化問題，在適當的條件下證實了等價MPEC問題在全局最優解集上是部分一致平穩的，並藉助此性質建立了將其平衡約束加到目標函式而誘導的罰問題是全局精確罰；(二)根據全局精確罰的特殊結構，通過交替解全局精確罰問題提出了解這類NP-難矩陣最佳化的多階段凸鬆弛算法，並針對結構低秩矩陣恢復問題，建立了每階段凸鬆弛問題的最優解與真實解的誤差界和近似秩界、以及多階段凸鬆弛法統計意義下的收斂率；(三)根據每階段凸鬆弛問題的可分離塊結構，建立了求解子問題的半鄰近交替方向乘子法的遍歷疊代複雜界，並通過數值試驗證實了多階段凸鬆弛法會產生高質量的解。本課題的研究既豐富了低秩矩陣最佳化和非光滑凸矩陣最佳化的理論，也為處理組合最佳化問題提供了新思路，具有重要理論意義和套用價值。
