《非凸可行問題的近似算法》是依託北京科技大學，由趙金玲擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：非凸可行問題的近似算法
- 依託單位：北京科技大學
- 項目負責人：趙金玲
- 項目類別：青年科學基金項目
項目摘要,結題摘要,
項目摘要
目前，國內外學者對於分裂可行、凸可行等所涉集合或約束為凸的可行類問題已進行了深入的研究，並取得了許多研究成果；但是，由於技術和方法等所限，大量存在的非凸可行問題卻尚未引起廣泛研究，僅有少量研究成果。本項目主要研究非凸可行問題的鬆弛和近似算法。研究內容包括秩約束線性矩陣不等式（LMI）和秩約束雙線性矩陣不等式（BMI）問題的SDP鬆弛、SOCP鬆弛和其它近似算法，作出相應的收斂性分析，給出逼近界，並進行數值試驗對各種算法進行比較；以及建立其它非凸可行問題的SDP鬆弛、SOCP鬆弛等近似算法，並針對非凸可行問題自身的特點，研究新的求解方法。這一課題的研究，對於非凸最佳化問題的可行解、圖像重構、醫療影像、逼近理論領域，以及控制理論中包括魯棒控制和系統穩定性等在內的許多問題的更好解決，都有著重大的影響。因而，本項目的研究既具有重要的理論意義，又具有廣泛的套用前景。
結題摘要
可行類問題在研究最最佳化問題的可行解、圖像重構、醫療影像、可調強度放射性治療、逼近理論領域，以及控制理論中包括魯棒控制和系統穩定性等在內的許多領域中都有著廣泛的套用。在本項目執行期內，我們深入研讀和討論了大量有關於凸可行問題、分裂可行問題、多集分裂可行問題以及非凸可行問題的文獻資料，拘阿並主要致力於多集分裂可行問題的投影算法研究與改進。受到文獻[P. Tseng, A modified forward–backward splitting method for maximal monotone mappings, SIAM J. Control Optim. 38 (2000): 431–446]中求解極大單調運算元零點問主局店題的改進Forward- backward分裂方法的啟發，改進了由C. Byrne提出的求解分裂可行問題的經典而有效的CQ算法，加快收斂套促店速度；同時考慮到CQ算法中疊代步長是固定的，其取值範圍受到矩陣譜半徑的限制，而譜半徑，即最大特徵值的獲取在數值計算中一直被認為是有困難的，故而我們把固定步長改進為自適應步長（變步長臘遷悼設）的形式，給出了算法收斂性證明，並對之進行了初步的數值檢驗，並進一步將這樣的方法推廣套用於多集分裂可行問題上。此後，我們考慮到投影算法的收斂速度問題，將主要精力集中於多集分裂可行問題的有關算法的搜尋方向與搜尋步長的改造上。首先，由於自適應投影算法中，每步疊代為求得合適的疊代步長都需要不少的計算量，故而我們將當前疊代點及其像點分別向各凸集進行投影盛艱騙，將從各點到相應投影點的方向進行凸組合以得到疊代方向，進而利用該方向直接計算出疊代步長，這種直接計算步長的方法避免了算法疊代中大量的內循環，從而使得算法效率得到改善，我們也從理論上驗證了這樣計算步長的方式相應於當前疊代方向是最好的；與此同才台淚時，我們還在疊代步中引入了鬆弛因子，以期進一步提高算法的收斂速度。初步的數值試驗結果表明，我們的算法是簡單而且有效的。此外，我們也針對特定的多集分裂可行問題研究了這一算法相應的鬆弛投影算法，通過引入向包含各凸集的半空間投影使得該算法更具有實用性。相應研究婚蘭旋探結果均已發表。 總體來說，本項目組老師和學生總計發表SCI檢索論文8篇和中文核心期刊論文2篇（均已作資助標註）；曾多次參加學術會議進行交流活動；此外，項目負責人三年內還指導了7名本科生做畢業設計，並協助指導了3名研究生。
