《非對稱臨近點算法的理論和套用研究》是依託南京師範大學，由蔡邢菊擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：非對稱臨近點算法的理論和套用研究
- 項目類別：青年科學基金項目
- 項目負責人：蔡邢菊
- 依託單位：南京師範大學
項目摘要,結題摘要,
項目摘要
臨近點算法是一類非常經典的求解最佳化問題、變分不等式問題、包含問題的算法，自其出現以來一直受到廣泛的重視，已經取得了非常重要的進展。本項目擬將經典臨近點算法中的臨近點項推廣到非對稱的形式，研究其基礎理論、算法設計以及在特殊結構問題上的套用。首先，從理論上證明非對稱臨近點算法的全局收斂性，分析其計算複雜性以及收斂速度。其次，利用推廣後算法的靈活性，為一些特定結構的最佳化問題（如帶有線性約束的可分凸規劃問題等）量身定製一些分解算法。同時，為使算法更加實用，引入寬鬆、實用的非精確準則，使得子問題容易求解，從而降低每步疊代的計算量。最後，將算法套用到交通規劃中的流量分配、寡頭競爭和圖像處理等問題中。本項目的研究結果將為當前最佳化領域中的一些熱點問題（如多塊可分凸規劃）的研究提供新的思路，為一些實際套用問題提供更有效的求解方法。
結題摘要
針對大規模稀疏最佳化中的可以寫成多個可分運算元的模型，本研究旨在設計一些高效的，子問題求解簡單的分解算法和臨近算法，並研究其複雜性和收斂速度。 算法設計方面： 利用有限記憶，通過構造新的下降方向，為變分不等式問題設計的新的投影類算法。該算法可以看出是共軛梯度法的一種推廣，它每次不僅僅利用當前疊代點梯度信息，還要考慮之前 步的梯度信息。數值實驗表明，新的算法較原有的投影梯度法有顯著的改善;對三塊可分凸最佳化問題直接推廣交替方向法的收斂性進行分析。若沒有強凸條件，直接推廣的交替方向法不收斂，我們最近給出了交替方向法收斂的一個充分條件，即當函式中有一個是強凸的。這是迄今為止最好的條件;我們又提出一個線性化的塊交替方向法，即非精確求解每一個子問題，得到一個預測點，再進行校正，算法能夠使子問題非常容易求解，計算效率得到提高;對兩塊的可分凸最佳化問題，提出一個新的臨近交替方向法，使得子問題容易求解，並能達到O(1/t)計算複雜度;提出一類非線性的PPA算法，這樣的鄰近點算法中的非線性臨近項不要求是一個函式的梯度，使得算法有更好的適應度，可以根據問題的結構選取合適的臨近項，我們還提出了一個非精確的版本;向前向後分裂算法中的參數大小直接影響算法的效率，我們增加一個簡單的鬆弛步，使得原來的算法的參數可以擴大一倍，並提出了這個算法的不精確版本，在一定的條件下，算法是線性收斂的。 算法的套用研究：大規模稀疏最佳化問題在統計，圖像處理等方面有很廣泛的套用，目前交替方向法是一個非常有效的算法。我們對統計中的Dantzig Selector問題利用交替方向法求解，使子問題求解非常容易，問題求解規模大；並對最佳化問題中常見的基本問題，點在橢球上的投影，通過引入一個變數，變成一個可分的凸最佳化問題，用交替方向法求解可以得到線性收斂率。
