非凸兩塊優(yōu)化問(wèn)題乘子交替方向法的收斂性

非凸兩塊優(yōu)化問(wèn)題乘子交替方向法的收斂性

0bregmanadmm算法的收斂性【研究意義】采用乘子迭代法（admm）求解大規(guī)模分布式計(jì)算的問(wèn)題非常有效。admm不僅可以分散式收集和存儲(chǔ)這些數(shù)據(jù)集，還可以在并行和分布環(huán)境中解決這些問(wèn)題。admm適合解決分布不規(guī)則優(yōu)化問(wèn)題，特別是在統(tǒng)計(jì)分析、機(jī)械學(xué)習(xí)和相關(guān)領(lǐng)域的大型問(wèn)題。這一點(diǎn)越來(lái)越重要。[前沿研究發(fā)展]admm思想最早起源于20世紀(jì)50年代。該算法于20世紀(jì)70年代中期由glwnski和marrocco獲得。其中L在凸情形下,ADMM的收斂性已被充分認(rèn)識(shí)并提出如下改進(jìn)的ADMM其中Δφ是關(guān)于強(qiáng)凸函數(shù)φ的Bregman距離.當(dāng)φ=0時(shí),算法(0.4)為傳統(tǒng)ADMM.在罰參數(shù)充分大且目標(biāo)函數(shù)二階連續(xù)可微的條件下,文獻(xiàn)[7]證明算法產(chǎn)生點(diǎn)列的聚點(diǎn)是問(wèn)題(0.3)的穩(wěn)定點(diǎn).文獻(xiàn)[8]分析如下BregmanADMM算法的收斂性【本研究切入點(diǎn)】最近,文獻(xiàn)[9]在矩陣A列滿秩,增廣拉格朗日函數(shù)滿足KL性質(zhì)(參見(jiàn)定義1.1)且罰參數(shù)大于某個(gè)常數(shù)的條件下,分析了傳統(tǒng)ADMM算法(0.1)求解非凸問(wèn)題(0.3)的全局收斂性.我們考慮如下兩分塊極小化問(wèn)題【擬解決的關(guān)鍵問(wèn)題】本文在不要求矩陣A列滿秩,B不一定是單位陣,在L1連續(xù)風(fēng)特性iii下面,給出本文理論分析所需的一些概念與性質(zhì).λ(i)φ(0)=0;(ii)φ在0處連續(xù),在區(qū)間(0,η)上一階連續(xù)可微;(iv)對(duì)于任意的則稱函數(shù)f在點(diǎn)x滿足上述性質(zhì)(i)、(ii)、(iii)的函數(shù)全體記為Φ引理1.22admm算法的收斂性分析進(jìn)一步,可得本文的收斂性建立在如下假設(shè)條件下.假設(shè)2.1假設(shè)以下條件成立首先,證明{L證明由增廣拉格朗日函數(shù)的定義,可得利用y由引理1.2和式(2.2)中第二式可得把上式代入式(2.4)可得由δ>0及n的任意性可得上式結(jié)合式(2.7)可得兩式相減,可得利用不等式(a+b+c)由F的性質(zhì)可得x由式(2.9)和式(2.10)可得引理2.3存在ζ>0,對(duì)于任意k有證明由增廣拉格朗日函數(shù)定義,可得進(jìn)一步結(jié)合式(2.2)可得令ζ:=ζ引理2.4設(shè)序列{w(iii)L證明(i)式由S(w由函數(shù)L由上式及式(2.13)可得(iii)對(duì)于任意點(diǎn)(x最后,給出非凸問(wèn)題(0.5)的ADMM算法(0.1)的收斂性分析.定理2.1若L(ii)序列{w因此,對(duì)于任意的k>k由于S(w由函數(shù)φ的凹性,可得即利用不等式由上式可得所以由式(2.7)可得另一方面,由式(2.9)、式(2.10)可得所以進(jìn)一步可知序列w3l由條件轉(zhuǎn)化本文針對(duì)非凸兩分塊優(yōu)化問(wèn)題,在不要求矩陣A列滿秩,B不一定是單位陣,在L由算法(0.1)中每個(gè)子問(wèn)題的最優(yōu)性條件,有故把上式代入式(2.5