數(shù)據(jù)科學(xué)優(yōu)化方法 課件 第11、12章 坐標(biāo)下降方法、交替方向乘子方法+附錄A 數(shù)學(xué)基礎(chǔ)

數(shù)據(jù)科學(xué)優(yōu)化方法Optimization

Method

in

Data

Science第11章坐標(biāo)下降方法11.1隨機(jī)坐標(biāo)下降方法11.2加速隨機(jī)坐標(biāo)下降方法11.3循環(huán)坐標(biāo)下降方法11.4求解可分正則最優(yōu)化問題的隨機(jī)坐標(biāo)下降方法引入？坐標(biāo)下降（CD）方法是一種非梯度優(yōu)化方法.基本思想是通過求解一系列簡(jiǎn)單的子問題達(dá)到最終優(yōu)化目標(biāo)函數(shù)的目的

方法每次迭代時(shí)，在當(dāng)前迭代點(diǎn)處沿一個(gè)坐標(biāo)軸方向進(jìn)行一維搜索，以求得目標(biāo)函數(shù)在該方向的局部極小點(diǎn).

坐標(biāo)下降方法廣泛應(yīng)用在統(tǒng)計(jì)和機(jī)器學(xué)習(xí)領(lǐng)域.引入本章前三節(jié)考慮如下的無約束最優(yōu)化問題

其中，為光滑凸函數(shù).有時(shí)還需要具有強(qiáng)凸性，即存在常數(shù)使得（11.1）（11.2）設(shè)

,若對(duì)于任意的和,有則稱為目標(biāo)函數(shù)的分量Lipschitz常數(shù).(11.3)定義11.1分量Lipschitz常數(shù)引入基于方法收斂性分析的需要，定義以下幾種Lipschitz常數(shù).設(shè)為函數(shù)的分量Lipschitz常數(shù)，則稱為的坐標(biāo)Lipschitz常數(shù).定義11.2坐標(biāo)Lipschitz常數(shù)(11.4)標(biāo)準(zhǔn)的Lipschitz常數(shù)滿足如下不等式由矩陣范數(shù)與跡的關(guān)系，可以得到假設(shè)1為L(zhǎng)ipschitz連續(xù)可微的凸函數(shù)，且在集合

上可以取得極小值.存在有限值,使得由定義的的水平集是有界的，即(11.5)引入第11章坐標(biāo)下降方法11.1隨機(jī)坐標(biāo)下降方法11.2加速隨機(jī)坐標(biāo)下降方法11.3循環(huán)坐標(biāo)下降方法11.4求解可分復(fù)合最優(yōu)化問題的隨機(jī)坐標(biāo)下降方法隨機(jī)坐標(biāo)下降方法隨機(jī)坐標(biāo)下降算法的基本原理隨機(jī)選擇的一個(gè)分量作為迭代方向一種最簡(jiǎn)單的情形是從中等概率隨機(jī)抽取2.更新變量隨機(jī)坐標(biāo)下降方法算法11.1：隨機(jī)坐標(biāo)下降方法給定初始點(diǎn)，若滿足終止準(zhǔn)則，則停止迭代從中等概率隨機(jī)抽取下標(biāo)計(jì)算,轉(zhuǎn)至步驟2.隨機(jī)坐標(biāo)下降算法的收斂性假定假設(shè)1成立，且為光滑凸函數(shù),最優(yōu)值為,算法11.1中步長(zhǎng)，則對(duì)任意，有進(jìn)一步，若目標(biāo)函數(shù)是強(qiáng)凸函數(shù)，則對(duì)任意，有

定理11.1隨機(jī)坐標(biāo)下降方法(11.6)(11.7)注：符號(hào)表示關(guān)于隨機(jī)下標(biāo)取期望，表示關(guān)于所有隨機(jī)下標(biāo)取期望.隨機(jī)坐標(biāo)下降方法設(shè)是一個(gè)光滑函數(shù)，則對(duì)任意兩點(diǎn)，有引理4.1.光滑函數(shù)的性質(zhì)1證明：由引理4.1可得隨機(jī)坐標(biāo)下降方法上式兩邊關(guān)于隨機(jī)下標(biāo)取期望，可得上式兩邊同時(shí)減去，然后關(guān)于隨機(jī)下標(biāo)

取期望，可得隨機(jī)坐標(biāo)下降方法(11.8)令，結(jié)合Cauchy-Schwarz不等式，可得(11.9)由于為凸函數(shù)，故對(duì)于任意有(11.10)后一個(gè)不等式成立是因?yàn)?，故屬?11.5)定義的集合.式子（11.10）兩邊關(guān)于所有隨機(jī)下標(biāo)取期望，有隨機(jī)坐標(biāo)下降方法將上式代入（11.9），整理得因此上式兩邊關(guān)于求和，可得從而（11.6）成立.隨機(jī)坐標(biāo)下降方法設(shè)為定義在非空開凸集上的可微函數(shù)，則為上的強(qiáng)凸函數(shù)當(dāng)且僅當(dāng),有強(qiáng)凸函數(shù)一階判定條件若

是強(qiáng)凸函數(shù)，將（11.2）兩邊關(guān)于

取極小值，令，

可得由此得到隨機(jī)坐標(biāo)下降方法兩邊關(guān)于所有隨機(jī)下標(biāo)取期望，然后代入(11.8)，可得若上述證明中步長(zhǎng)更改為更加精細(xì)的步長(zhǎng)，如，定理11.1的結(jié)論同樣成立隨機(jī)坐標(biāo)下降方法若上述證明中步長(zhǎng)更改為更加精細(xì)的步長(zhǎng)，如，定理11.1的結(jié)論同樣成立收斂速度的比較隨機(jī)坐標(biāo)下降方法(11.11)考慮函數(shù)為光滑凸函數(shù)的情形.

當(dāng)負(fù)梯度下降法步長(zhǎng)取時(shí)，由推論（4.1），負(fù)梯度方法的收斂速度為當(dāng)隨機(jī)坐標(biāo)下降方法步長(zhǎng)取時(shí)，隨機(jī)坐標(biāo)下降方法的收斂速度為收斂速度的比較隨機(jī)坐標(biāo)下降方法由于，因此隨機(jī)坐標(biāo)下降算法的收斂速率一般慢于負(fù)梯度算法！只有當(dāng)上述不等式成立時(shí)，才具有相同的速度.

直觀的解釋是只使用梯度的一個(gè)分量進(jìn)行更新會(huì)降低收斂速度.隨機(jī)坐標(biāo)下降方法有放回vs無放回隨機(jī)坐標(biāo)下降方法除了從中有放回的抽取將要更新的下標(biāo)，另一種自然的想法是無放回抽樣:將次連續(xù)迭代視為一期（epoch）,每一期的迭代方向?yàn)榈囊粋€(gè)隨機(jī)重排，這樣每一期遍歷更新全部的坐標(biāo)然后繼續(xù)下一輪.第11章坐標(biāo)下降方法11.1隨機(jī)坐標(biāo)下降方法11.2加速隨機(jī)坐標(biāo)下降方法11.3循環(huán)坐標(biāo)下降方法11.4求解可分正則最優(yōu)化問題的隨機(jī)坐標(biāo)下降方法加速隨機(jī)坐標(biāo)下降方法假設(shè)已知強(qiáng)凸參數(shù)和分量Lipschitz常數(shù)算法11.2：加速隨機(jī)坐標(biāo)下降方法給定初始點(diǎn)，，，若滿足終止準(zhǔn)則，則停止迭代.求解二次方程,為該方程的最大根，令,.4.計(jì)算.加速隨機(jī)坐標(biāo)下降方法假設(shè)已知強(qiáng)凸參數(shù)和分量Lipschitz常數(shù)算法11.2：加速隨機(jī)坐標(biāo)下降方法5.從中等概率隨機(jī)抽取，令6.計(jì)算.7.計(jì)算.8.,轉(zhuǎn)步2.注：加速隨機(jī)坐標(biāo)下降方法的迭代方向結(jié)合了新梯度信息和歷史迭代方向.將上述算法中的全部替換為，算法依然有效.加速隨機(jī)坐標(biāo)下降方法假定假設(shè)1成立，且問題（11.1）中的為光滑,

強(qiáng)凸函數(shù),令則對(duì)任意有

（11.12）（11.13）定理11.2加速隨機(jī)坐標(biāo)下降方法注：當(dāng)為強(qiáng)凸函數(shù)時(shí)，隨著迭代次數(shù)的增加，不等式（11.12）右邊的第一項(xiàng)逐漸占據(jù)主要地位，因此加速隨機(jī)坐標(biāo)下降算法的速度更快.對(duì)于一般的凸函數(shù),（11.13）也成立.對(duì)比隨機(jī)坐標(biāo)下降算法收斂速度由

提升到了.第11章坐標(biāo)下降方法11.1隨機(jī)坐標(biāo)下降方法11.2加速隨機(jī)坐標(biāo)下降方法11.3循環(huán)坐標(biāo)下降方法11.4求解可分正則最優(yōu)化問題的隨機(jī)坐標(biāo)下降方法循環(huán)坐標(biāo)下降方法循環(huán)坐標(biāo)下降方法中每次迭代的下標(biāo)是按照順序循環(huán)產(chǎn)生的，例如（11.14）循環(huán)坐標(biāo)下降方法記循環(huán)輪數(shù)為，表示第T次循環(huán)下的第k個(gè)迭代點(diǎn).算法11.3：循環(huán)坐標(biāo)下降方法給定初始點(diǎn)，.若滿足終止準(zhǔn)則，則停止迭代.令.按照（11.14）生成.5.計(jì)算.6.令7.，轉(zhuǎn)至步驟2.循環(huán)坐標(biāo)下降方法設(shè)問題（11.1）中為光滑函數(shù),算法11.3的步長(zhǎng)取為,則對(duì)于任意的有引理11.1（11.15）循環(huán)坐標(biāo)下降方法證明：由的光滑性和可知，對(duì)于任意的有于是（11.16）對(duì)(11.16)兩邊關(guān)于從到求和，可得（11.17）循環(huán)坐標(biāo)下降方法由于，故對(duì)任意，有從而循環(huán)坐標(biāo)下降方法因此，對(duì)任意，有循環(huán)坐標(biāo)下降方法對(duì)最后一個(gè)不等式兩邊關(guān)于從到求和，可得將上式代入式（11.17），即可得到式（11.15）.循環(huán)坐標(biāo)下降方法假定假設(shè)1成立，問題（11.1）中的是凸函數(shù)，算法（11.3）的步長(zhǎng)

，則對(duì)任意，有

引理11.2（11.18）循環(huán)坐標(biāo)下降方法證明：由的凸性可知，對(duì)于任意的，有于是,由Cauchy-schwarz不等式可得整理得到將上式代入式（11.15），便可得到式（11.18）.循環(huán)坐標(biāo)下降方法設(shè)為非負(fù)實(shí)值序列且對(duì)于某些整數(shù)和有則對(duì)任意的有引理11.3循環(huán)坐標(biāo)下降方法證明：對(duì)任意，有最后一個(gè)不等號(hào)成立是因?yàn)槭菃握{(diào)非增序列.由此可得循環(huán)坐標(biāo)下降方法假定假設(shè)1成立，問題（11.1）中的為光滑凸函數(shù),算法11.3的步長(zhǎng)，則對(duì)任意的，有進(jìn)一步，若是還是強(qiáng)凸函數(shù)，則對(duì)任意，有定理11.3（11.19）（11.20）循環(huán)坐標(biāo)下降方法證明：由的光滑性，有因?yàn)?，故由上式可得又由引?1.2，可知令，則由引理11.3可得到式(11.19).循環(huán)坐標(biāo)下降方法若是強(qiáng)凸函數(shù)，將(11.2)兩邊關(guān)于取極小值，可得（11.21）結(jié)合式(11.21)和引理11.1，可得循環(huán)坐標(biāo)下降方法從而由此得到式（11.20）.循環(huán)坐標(biāo)下降方法注：在實(shí)際應(yīng)用中，可以被替換為其他取值更大的量，只需其滿足條件（11.3）

和（11.4）即可.不同的

會(huì)得到不同的收斂速度，例如當(dāng)時(shí)，式（11.19)的上界變?yōu)槭諗克俣鹊谋容^循環(huán)坐標(biāo)下降方法考慮函數(shù)為光滑凸函數(shù)的情形.

當(dāng)負(fù)梯度下降法步長(zhǎng)取，迭代次數(shù)

負(fù)梯度方法的收斂速度為當(dāng)循環(huán)坐標(biāo)下降方法步長(zhǎng)取，約為負(fù)梯度方法上界的倍！第11章坐標(biāo)下降方法11.1隨機(jī)坐標(biāo)下降方法11.2加速隨機(jī)坐標(biāo)下降方法11.3循環(huán)坐標(biāo)下降方法11.4求解可分復(fù)合最優(yōu)化問題的隨機(jī)坐標(biāo)下降方法本節(jié)考慮如下最優(yōu)化問題

（11.22）（11.23）其中常見的可分正則化函數(shù)包括范數(shù)：等.其中為光滑、強(qiáng)凸函數(shù)，是正則函數(shù)、凸函數(shù)，可能是非光滑的，為正則化參數(shù).假設(shè)是可分的，即求解可分復(fù)合最優(yōu)化問題的坐標(biāo)下降方法求解可分復(fù)合最優(yōu)化問題的坐標(biāo)下降方法算法11.4：求解可分正則最優(yōu)化問題(11.22)的隨機(jī)坐標(biāo)下降方法的計(jì)算步驟給定初始點(diǎn)，若滿足終止準(zhǔn)則，則停止迭代從中等概率隨機(jī)抽取下標(biāo)計(jì)算

.計(jì)算

，轉(zhuǎn)至步驟2.求解可分復(fù)合最優(yōu)化問題的坐標(biāo)下降算法用近端算子描述，步驟4可以簡(jiǎn)寫為當(dāng)正則化項(xiàng)不存在時(shí)，上述公式退化為普通的隨機(jī)坐標(biāo)下降方法.

在第步迭代中，步驟4中子問題是這樣形成的：在當(dāng)前迭代點(diǎn)處沿第個(gè)坐標(biāo)軸方向?qū)δ繕?biāo)函數(shù)進(jìn)行線性近似，并增加一個(gè)權(quán)重為

的二次項(xiàng)以及正則項(xiàng).該子問題等價(jià)于求解可分正則最優(yōu)化問題的坐標(biāo)下降算法對(duì)于可分復(fù)合最優(yōu)化問題（11.22），設(shè)是光滑、強(qiáng)凸函數(shù),為可分凸函數(shù)，且目標(biāo)函數(shù)只在達(dá)到極小值，算法11.4中,則對(duì)于任意的有定理11.4（11.24）注：當(dāng)為凸但非強(qiáng)凸函數(shù)時(shí)，可得到類似于式（11.6）的結(jié)論.求解可分復(fù)合最優(yōu)化問題的坐標(biāo)下降算法證明：由于是強(qiáng)凸函數(shù)，是可分凸函數(shù)，故是凸函數(shù)，且滿足（11.25）定義函數(shù)函數(shù)關(guān)于是可分的，且在點(diǎn)處達(dá)到極小，其中

是算法11.4中第4步子問題的解。由式（11.2），有求解可分復(fù)合最優(yōu)化問題的坐標(biāo)下降算法兩邊關(guān)于取極小值，可得其中第三個(gè)不等式由（11.25）得到，令，便得到最后一個(gè)不等式.（11.26）求解可分復(fù)合最優(yōu)化問題的坐標(biāo)下降算法由的定義和算法11.4的迭代過程，可得等式兩邊關(guān)于下標(biāo)取期望，可得求解可分復(fù)合最優(yōu)化問題的坐標(biāo)下降算法上式兩邊同時(shí)減去，并結(jié)合(11.26)，有求解可分復(fù)合最優(yōu)化問題的坐標(biāo)下降算法兩邊關(guān)于隨機(jī)下標(biāo)取期望，可得由此推出(11.24).

求解可分復(fù)合最優(yōu)化問題的坐標(biāo)下降算法例11.1考慮如下Lasso問題（11.27）其中,,，正則化參數(shù)

.求解可分復(fù)合最優(yōu)化問題的坐標(biāo)下降算法解：應(yīng)用隨機(jī)坐標(biāo)下降方法，設(shè)第步抽到下標(biāo)，求解關(guān)于分量的極小化問題其中為軟閾值函數(shù).其中，以及.經(jīng)整理，可得的迭代公式數(shù)據(jù)科學(xué)優(yōu)化方法Optimization

Method

in

Data

Science第12章交替方向乘子方法12.1方法基礎(chǔ)12.2ADMM方法的一般形式和理論性質(zhì)12.3一致性問題

12.4共享問題12.5數(shù)值實(shí)驗(yàn)引入？交替方向乘子方法（ADMM）是一種求解可分凸優(yōu)化問題的重要方法.ADMM方法將原始問題分解為若干個(gè)可以求解的子問題，并行求解每一個(gè)子問題，從而得到原問題的解.

ADMM方法可用來求解大規(guī)模優(yōu)化問題第12章交替方向乘子方法12.1方法基礎(chǔ)12.2ADMM方法的一般形式和理論性質(zhì)12.3一致性問題

12.4共享問題12.5數(shù)值實(shí)驗(yàn)

考慮等式約束的凸優(yōu)化問題方法基礎(chǔ)其中，,為凸函數(shù).（12.1）s.t.方法基礎(chǔ)12.1.1對(duì)偶上升方法12.1.2增廣Lagrange函數(shù)和乘子方法對(duì)偶上升方法問題（12.1）的Lagrange函數(shù)以及相應(yīng)的對(duì)偶函數(shù)分別為其中為L(zhǎng)agrange乘子或?qū)ε甲兞?（12.1）的對(duì)偶問題為（12.2）對(duì)偶上升法求解原理由對(duì)偶原理，當(dāng)為嚴(yán)格凸函數(shù)時(shí)，原問題（12.1）與對(duì)偶問題（12.2)同解,即其中對(duì)偶上升方法由此推出對(duì)偶上升方法的第步迭代公式（12.3）（12.4）其中為步長(zhǎng).(12.3)是的極小化步，（12.4）是對(duì)偶變量的更新步.在合適步長(zhǎng)下，對(duì)偶函數(shù)將隨著迭代進(jìn)行而逐漸上升，即，故該方法被稱為對(duì)偶上升.定義，則對(duì)偶上升方法對(duì)偶上升方法的收斂性如果步長(zhǎng)選擇合適,可以證明在一定條件下，與分別收斂到原問題與對(duì)偶問題的最優(yōu)解.對(duì)偶上升方法存在的問題對(duì)偶上升法的收斂條件在實(shí)際中難以滿足，因此對(duì)偶上升方法經(jīng)常無法使用。例如，當(dāng)為仿射函數(shù)時(shí)，對(duì)于大部分，Lagrange函數(shù)關(guān)于無下界，從而導(dǎo)致最小化步失效.對(duì)偶上升方法對(duì)偶分解考慮可分目標(biāo)函數(shù)其中，為的子向量.令，得，Lagrange函數(shù)為對(duì)于可分的目標(biāo)函數(shù)，對(duì)偶上升方法很容易實(shí)現(xiàn)并行化對(duì)偶上升方法由Lagrange函數(shù)的可分性可以得到如下并行迭代公式上述對(duì)偶上升方法也被稱之為對(duì)偶分解（DualDecompositon）方法.（12.5）（12.6）對(duì)偶上升方法對(duì)偶分解方法的一次迭代包括“廣播”和“收集”兩步廣播步：每一個(gè)節(jié)點(diǎn)利用“廣播”得到的，執(zhí)行的極小步（12.5）并上傳本地結(jié)果.收集步：中央服務(wù)器利用收集的信息更新得到新的對(duì)偶變量.方法基礎(chǔ)12.1.1對(duì)偶上升方法12.1.2增廣Lagrange函數(shù)和乘子方法增廣Lagrange函數(shù)和乘子方法問題（12.1）的增廣Lagrange函數(shù)為其中為懲罰參數(shù)，為標(biāo)準(zhǔn)的Lagrange函數(shù).（12.7）（12.1）s.t.增廣Lagrange函數(shù)和乘子方法該問題的對(duì)偶函數(shù)為稱為增廣對(duì)偶函數(shù).增廣Lagrange函數(shù)可以視為如下最優(yōu)化問題的Lagrange函數(shù).由于任意可行解都滿足，故該問題等價(jià)于原問題（12.1）. s.t.（12.8）增廣Lagrange函數(shù)和乘子方法對(duì)問題（12.8）應(yīng)用對(duì)偶上升法可得如下迭代公式（12.9）（12.10）該方法稱為乘子方法.增廣Lagrange函數(shù)和乘子方法乘子方法和對(duì)偶上升方法的區(qū)別乘子方法在極小化步使用的是增廣Lagrange函數(shù)在對(duì)偶變量的更新公式中，乘子方法使用懲罰參數(shù)代替步長(zhǎng)，不再隨迭代的進(jìn)行逐漸增大乘子方法相比于對(duì)偶上升法收斂條件更一般，允許目標(biāo)函數(shù)取值正無窮或非嚴(yán)格凸等.增廣Lagrange函數(shù)和乘子方法乘子方法步長(zhǎng)的解釋由KKT條件可知，問題（12.1）的最優(yōu)解滿足下式其中為對(duì)應(yīng)的Lagrange乘子，由于極小化,于是有乘子方法在迭代過程中始終滿足KKT條件的第一個(gè)等式.隨著迭代進(jìn)行逐漸趨于，從而滿足等式約束，進(jìn)而得到問題（12.1）的最優(yōu)解.增廣Lagrange函數(shù)和乘子方法乘子方法的優(yōu)點(diǎn)乘子方法相比于對(duì)偶上升算法在收斂性上有了極大的改善二次懲罰項(xiàng)的引入會(huì)使得增廣Lagrange函數(shù)不再可分，從而導(dǎo)致的極小化步難以并行化.乘子方法的不足第12章交替方向乘子方法12.1方法基礎(chǔ)12.2ADMM方法的一般形式和理論性質(zhì)12.3一致性問題

12.4共享問題12.5數(shù)值實(shí)驗(yàn)本節(jié)考慮如下的等式約束優(yōu)化問題ADMM方法的一般形式和理論性質(zhì)（12.11）其中為優(yōu)化變量，，，和均為凸函數(shù).注：本節(jié)考慮的優(yōu)化問題中，優(yōu)化變量與目標(biāo)函數(shù)都拆分成了兩部分.

ADMM方法的一般形式和理論性質(zhì)12.2.1迭代公式12.2.2收斂性分析12.2.3最優(yōu)性條件

12.2.4終止準(zhǔn)則12.2.5懲罰參數(shù)的選擇迭代公式問題（12.11）的增廣Lagrange函數(shù)為由此得到乘子方法的迭代公式ADMM方法將聯(lián)合優(yōu)化改為交替優(yōu)化，迭代公式為（12.12）（12.13）（12.14）（12.15）（12.13)、（12.14）、（12.15）分別稱為極小化步、極小化步式和對(duì)偶變量更新步.迭代公式ADMM迭代公式標(biāo)準(zhǔn)化形式定義原始?xì)埐顒t原Lagrange函數(shù)可以改寫為由此得到ADMM迭代公式的標(biāo)準(zhǔn)化形式（12.16）（12.17）（12.18）迭代公式例12.1考慮經(jīng)典Lasso問題其中，,正則化參數(shù).迭代公式解：先將Lasso問題改寫成如下的約束最優(yōu)化問題其中，.應(yīng)用（12.16）-（12.18）可得如下ADMM迭代公式（12.19）迭代公式如果，可利用Shermann-Morrision-Woodbury公式計(jì)算.ADMM方法的一般形式和理論性質(zhì)12.2.1迭代公式12.2.2收斂性分析12.2.3最優(yōu)性條件

12.2.4終止準(zhǔn)則12.2.5懲罰參數(shù)的選擇收斂性分析假設(shè)1

和為正

常閉凸函數(shù).假設(shè)2

Lagrange函數(shù)至少有一個(gè)鞍點(diǎn).假設(shè)1成立的充要條件是和的上圖為非空閉凸集.該假設(shè)蘊(yùn)含著更新步式（12.16）和（12.17）可解.若假設(shè)2成立,則存在使得由此可知，為原問題（12.11）的解，為對(duì)偶問題的最優(yōu)解，且原問題和對(duì)偶問題的最優(yōu)解相等.收斂性分析假定假設(shè)1和假設(shè)2成立，則ADMM方法具有如下收斂結(jié)果：殘差收斂.，其中目標(biāo)函數(shù)值收斂.其中表示最優(yōu)化問題（12.11）的最優(yōu)值.對(duì)偶變量收斂.定理12.1下面先證明三個(gè)引理，然后推出定理12.1結(jié)論.收斂性分析假定假設(shè)1和假設(shè)2成立，設(shè)為的一個(gè)鞍點(diǎn),則有

（12.20）引理12.1收斂性分析證明：由于是的一個(gè)鞍點(diǎn)，可得由假設(shè)1可知取有限值，由此可推出(否則).于是又因?yàn)?，?

綜上可得收斂性分析假定假設(shè)1成立，則有

引理12.2(12.21)收斂性分析由于，將帶入上式，整理得由此知是極小值點(diǎn).證明：由ADMM方法的迭代公式可知，是的極小點(diǎn).因?yàn)楹投际钦ｉ]凸函數(shù)，故為的極小點(diǎn)的充要條件為收斂性分析于是有(12.22)同理，有將帶入上式，整理可得說明是的極小點(diǎn)，由此得到(12.23)將（12.22）和（12.23）相加，利用整理后化簡(jiǎn)得到（12.21）.收斂性分析假定假設(shè)1和假設(shè)2成立，定義李雅普洛夫函數(shù)（Lyapunovfunction）則有引理12.3(12.24)收斂性分析證明：將不等式（12.20）和（12.21）相加，然后將得到的不等式兩邊同乘2，整理得(12.25)(12.24)可由（12.25）改寫得到.首先改寫（12.25）的左邊第一項(xiàng).利用，改寫得將帶入前兩項(xiàng)，可得整理后得(12.26)收斂性分析接下來改寫（12.25）的剩余項(xiàng)，即其中來自（12.26).將代入最后一項(xiàng)，整理得進(jìn)而有將上式和（12.26）應(yīng)用到（12.25），結(jié)合的定義，可得(12.27)收斂性分析為了證明（12.24）成立，只需證明（12.27）右邊的交叉項(xiàng)

非正.由引理12.2的證明過程可知是

的極小值點(diǎn)，是的極小值點(diǎn).

由此可得將上述兩個(gè)不等式相加可得將帶入上式，得到

引理12.3得證.收斂性分析假定假設(shè)1和假設(shè)2成立，則ADMM方法具有如下收斂結(jié)果：殘差收斂.，其中目標(biāo)函數(shù)值收斂.其中表示最優(yōu)化問題（12.11）的最優(yōu)值.對(duì)偶變量收斂.定理12.1收斂性分析證明：由引理12.3可知，序列單調(diào)遞減，又因?yàn)?，故序列和均有界，?duì)（12.24）兩邊關(guān)于求和，有由此可得，，進(jìn)一步有.

另一方面由于，，故由引理12.1可知，由引理12.2知，從而可得.收斂性分析注：ADMM方法只證明能保證收斂到最優(yōu)值，并不能保證迭代點(diǎn)列會(huì)收斂到全局最優(yōu)解.ADMM方法收斂速度較慢，但是在大部分問題可以以一個(gè)較快速度給出中等精度解.

定理對(duì)目標(biāo)函數(shù)和約束的要求可以適度放寬.ADMM方法的一般形式和理論性質(zhì)12.2.1迭代公式12.2.2收斂性分析12.2.3最優(yōu)性條件

12.2.4終止準(zhǔn)則12.2.5懲罰參數(shù)的選擇最優(yōu)性條件問題（12.11）是凸優(yōu)化問題，點(diǎn)為該問題極小點(diǎn)當(dāng)且僅其當(dāng)滿足一階最優(yōu)性條件（KKT條件）其中式(12.28)表示原始問題可行條件，(12.29)和（12.30）表示對(duì)偶可行條件.(12.28)(12.29)(12.30)最優(yōu)性條件由于是的極小點(diǎn)，故有即在迭代過程中迭代序列始終滿足（12.30）.最優(yōu)性條件

由于為的極小點(diǎn)，故有上式等價(jià)于因此，可以視為對(duì)偶條件式（12.29）的殘差，稱為對(duì)偶?xì)埐?最優(yōu)性條件

問題（12.11）的最優(yōu)性條件有三個(gè).ADMM方法產(chǎn)生的序列滿足最后一個(gè)條件.另外兩個(gè)條件分別等價(jià)于隨著迭代次數(shù)，原始?xì)埐?/p>

和對(duì)偶?xì)埐钰呌?這兩點(diǎn)在定理12.1中得到證明.ADMM方法的一般形式和理論性質(zhì)12.2.1迭代公式12.2.2收斂性分析12.2.3最優(yōu)性條件

12.2.4終止準(zhǔn)則12.2.5懲罰參數(shù)的選擇終止準(zhǔn)則

由最優(yōu)性條件的分析可以給出如下的終止準(zhǔn)則終止準(zhǔn)則其中與分別為原始可行條件（12.28）與對(duì)偶可行條件（12.29）的閾值.這兩個(gè)閾值可以通過絕對(duì)準(zhǔn)則和相對(duì)準(zhǔn)則來確定，如其中和分別表示相對(duì)閾值和絕對(duì)閾值，為約束變量的個(gè)數(shù)，是優(yōu)化變量的維度。ADMM方法的一般形式和理論性質(zhì)12.2.1迭代公式12.2.2收斂性分析12.2.3最優(yōu)性條件

12.2.4終止準(zhǔn)則12.2.5懲罰參數(shù)的選擇懲罰參數(shù)選擇

為了提高方法的收斂性，減少對(duì)于懲罰參數(shù)取值的依賴性，實(shí)踐中通常會(huì)采用變懲罰參數(shù).

當(dāng)較大時(shí)，違反原始可行條件會(huì)帶來較大懲罰，因而產(chǎn)生較小的原始?xì)埐?/p>

當(dāng)較大時(shí)，對(duì)偶?xì)埐钭兇髴土P參數(shù)選擇

為了實(shí)現(xiàn)殘差和能夠快速收斂到0，可以采用如下設(shè)置其中，為參數(shù)，常取，

注：使用可變懲罰參數(shù)時(shí),標(biāo)準(zhǔn)化對(duì)偶變量，需要在更新后重新標(biāo)準(zhǔn)化.第12章交替方向乘子方法12.1方法基礎(chǔ)12.2ADMM方法的一般形式和理論性質(zhì)12.3一致性問題

12.4共享問題12.5數(shù)值實(shí)驗(yàn)一致性問題12.3.1全局一致性問題12.3.2一致性問題的一般形式

考慮以單一優(yōu)化變量的若干函數(shù)和為目標(biāo)函數(shù)的最優(yōu)化問題全局一致性問題（12.31）其中，為凸函數(shù)，稱為局部損失函數(shù).

全局一致性問題

全局一致性問題的定義為了實(shí)現(xiàn)分布式計(jì)算，可以改寫原問題為如下約束優(yōu)化問題其中被稱為局部變量，被稱為全局變量.由于約束條件是所有局部變量等于全局變量，因此該問題被稱為全局一致性問題.s.t.（12.32）全局一致性問題該問題的增廣Lagrange函數(shù)為ADMM方法的迭代公式為（12.33）（12.34）（12.35）全局一致性問題令，和，則（12.34）和（12.35）可以改寫為（12.36）（12.37）將（12.36）代入式（12.37）得，意味著全局一致性問題全局一致性問題①②③④⑤全局一致性問題帶正則項(xiàng)的全局一致性問題在問題（12.32）目標(biāo)函數(shù)的基礎(chǔ)上增加正則項(xiàng)，就可得到帶正則項(xiàng)的全局一致性問題s.t.（12.38）全局一致性問題ADMM方法迭代公式其標(biāo)準(zhǔn)化形式為（12.39）（12.40）（12.41）全局一致性問題全局一致性問題例12.2機(jī)器學(xué)習(xí)領(lǐng)域的很多問題可歸結(jié)為如下無約束最優(yōu)化問題（12.42）其中變量，為特征矩陣，為輸出向量，為凸損失函數(shù)，為凸正則函數(shù).

全局一致性問題其中為第個(gè)樣本的損失函數(shù)，為第個(gè)樣本的特征向量，為第個(gè)樣本的輸出向量.通常假設(shè)正則函數(shù)也是可加的，例如取1或2

范數(shù).

假設(shè)損失函數(shù)是可加的，例如于是有全局一致性問題解：考慮樣本量遠(yuǎn)大于樣本維度的情形.可以通過分割數(shù)據(jù)集，并將分割后的數(shù)據(jù)集分給多個(gè)節(jié)點(diǎn)進(jìn)行分布式優(yōu)化以提高效率.先將特征矩陣和輸出向量按行劃分為份其中，，表示第i個(gè)子數(shù)據(jù)集.全局一致性問題將問題（12.42）改寫為如下一致性問題由（12.39）-（12.41）得到該問題的標(biāo)準(zhǔn)迭代公式s.t.（12.43）全局一致性問題當(dāng)，時(shí),（12.42）變成了Lasso問題，此時(shí)ADMM標(biāo)準(zhǔn)化迭代公式為全局一致性問題①②④⑤③一致性問題12.3.1全局一致性問題12.3.2一致性問題的一般形式

一致性問題的一般形式考慮一致性問題的一般形式其中，，(表示元素個(gè)數(shù))。其中允許有重疊。為了簡(jiǎn)便，記為

，稱為局部變量，定義局部變量下標(biāo)到全局變量下標(biāo)的映射局部變量與全局變量一致等價(jià)于（12.44）一致性問題的一般形式定義，滿足，則一致性問題（12.44）可改寫為如下約束最優(yōu)化問題（12.45）該問題的增廣Lagrange函數(shù)為一致性問題的一般形式ADMM迭代公式為（12.46）（12.47）（12.48）

一致性問題的一般形式（12.49）其中即為與對(duì)應(yīng)的局部變量數(shù)量。于是的更新結(jié)果為所有與對(duì)應(yīng)的的平均值。將（12.49）代入（12.48）可得由于全局變量的更新公式可分，故式（12.47）可改寫為分量形式一致性問題的一般形式由此可知，(12.47)時(shí)對(duì)全局變量的每個(gè)分量進(jìn)行局部平均，而非全局平均.于是（12.47）進(jìn)一步簡(jiǎn)化為一致性問題的一般形式通過在問題（12.45）目標(biāo)函數(shù)的基礎(chǔ)上增加正則項(xiàng)，可得到帶正則項(xiàng)的一致性問題s.t.（12.50）ADMM方法的迭代公式推導(dǎo)留作課后練習(xí).第12章交替方向乘子方法12.1方法基礎(chǔ)12.2ADMM方法的一般形式和理論性質(zhì)12.3一致性問題

12.4共享問題12.5數(shù)值實(shí)驗(yàn)共享問題是另一類常見的無約束最優(yōu)化問題.

該問題的一般形式如下共享問題（12.51）其中，為局部損失函數(shù)，為個(gè)優(yōu)化變量和的函數(shù)，稱為共享目標(biāo)函數(shù).共享問題的目標(biāo)是通過調(diào)整的值極小化局部損失函數(shù)與共享目標(biāo)函數(shù)的和.共享問題將問題（12.51）改寫為約束最優(yōu)化問題形式其中.ADMM方法的標(biāo)準(zhǔn)迭代公式為其中s.t.（12.52）（12.53）（12.54）（12.55）共享問題現(xiàn)關(guān)注（12.54），令，則（12.54）等價(jià)于求解如下約束最優(yōu)化問題s.t.（12.56）共享問題固定，關(guān)于極小化目標(biāo)函數(shù)，可得其中.s.t.（12.56）（12.57）共享問題通過極小化的目標(biāo)函數(shù)其中，，.式（12.58）表明對(duì)偶變量均相等，故可替換為統(tǒng)一變量表示.即可得到的更新值.將（12.57）應(yīng)用在上，帶入（12.55）得（12.58）共享問題共享問題的ADMM最終迭代公式為（12.59）（12.60）（12.61）在實(shí)際應(yīng)用中，更新步(12.59)可由個(gè)節(jié)點(diǎn)并行執(zhí)行，將更新后的上傳到中心服務(wù)器，由中心服務(wù)器計(jì)算得到、和，再將其傳給個(gè)節(jié)點(diǎn).共享問題共享問題的ADMM最終迭代公式為（12.59）（12.60）（12.61）共享問題①②③④共享問題（12.42）例12.3考慮最優(yōu)化問題（12.42），數(shù)據(jù)集具有特征維度遠(yuǎn)大于樣本量的高維特性.（此情形在生物醫(yī)學(xué)領(lǐng)域、保險(xiǎn)金融領(lǐng)域比較常見）其中為可分的正則函數(shù).共享問題解：先對(duì)數(shù)據(jù)作如下的分塊:令優(yōu)化變量其中

，

;相應(yīng)的，將特征矩陣也進(jìn)行相應(yīng)的劃分,其中.由正則函數(shù)的可分性以及問題（12.42）可改寫為令，上述問題可以轉(zhuǎn)換為如下共享問題s.t.（12.62）共享問題由共享問題的ADMM標(biāo)準(zhǔn)迭代公式，得問題（12.62）的迭代公式為其中.在實(shí)際中每個(gè)節(jié)點(diǎn)計(jì)算，然后將更新后的上傳到服務(wù)器.然后由服務(wù)器求平均，以此更新

和，并將更新后的和傳給

個(gè)節(jié)點(diǎn).第12章交替方向乘子方法12.1方法基礎(chǔ)12.2ADMM方法的一般形式和理論性質(zhì)12.3一致性問題

12.4共享問題12.5數(shù)值實(shí)驗(yàn)本小節(jié)以Lasso問題為例比較近端梯度方法、加速近端梯度方法、隨機(jī)坐標(biāo)下降方法和ADMM方法的有效性.

數(shù)值實(shí)驗(yàn)數(shù)值實(shí)驗(yàn)問題1考慮一個(gè)由行，列構(gòu)成的特征矩陣，其中，特征矩陣的每一列都經(jīng)過標(biāo)準(zhǔn)化處理，即2范數(shù)為1.真實(shí)解有100個(gè)非零分量，每一個(gè)非零分量從標(biāo)準(zhǔn)正態(tài)分布中隨機(jī)產(chǎn)生.響應(yīng)變量由線性回歸模型生成：其中.設(shè)置參數(shù)，收斂閾值，正則化參數(shù)，初始化變量設(shè)置為和.初始點(diǎn)設(shè)置為.數(shù)值實(shí)驗(yàn)圖12.1（a）迭代過程中原始?xì)埐睿ㄉ希┖蛯?duì)偶?xì)埐睿ㄏ拢┑亩稊?shù)變化，虛線分別表示（上）和（下）；（b）迭代過程中的變化.由上圖可以看出，經(jīng)過15次迭代之后ADMM算法近似滿足收斂準(zhǔn)則.數(shù)值實(shí)驗(yàn)問題2其中.正則化參數(shù).步長(zhǎng)ADMM算法的懲罰參數(shù)為，收斂閾值，初始化所有變量為0.對(duì)于隨機(jī)坐標(biāo)下降算法，這里考慮隨機(jī)塊坐標(biāo)下降，每次抽取200個(gè)特征進(jìn)行，步長(zhǎng)設(shè)置為0.01.

考慮一個(gè)由

行，列構(gòu)成的特征矩陣，矩陣的元素均從中產(chǎn)生.真實(shí)解有100個(gè)非0分量，每個(gè)非0分量均從

隨機(jī)產(chǎn)生.響應(yīng)變量由線性回歸模型產(chǎn)生：數(shù)值實(shí)驗(yàn)從圖（12.2）可以看出，近端梯度方法、加速近端梯度方法和ADMM方法能在100步內(nèi)收斂，隨機(jī)坐標(biāo)下方法因?yàn)橹桓虏糠痔卣鳎諗克俣容^慢.

數(shù)值實(shí)驗(yàn)考慮Python編程語言中的機(jī)器學(xué)習(xí)庫(kù)scikit-learn中的糖尿病人數(shù)據(jù)集：diabetes。該數(shù)據(jù)集共有442個(gè)樣本，10個(gè)特征(年齡、性別、BMI等)，響應(yīng)變量為一年后疾病發(fā)展情況的定量指標(biāo).

Lasso問題為其中為特征矩陣.這里應(yīng)用坐標(biāo)下降法來求解上述Lasso問題.

問題3數(shù)值實(shí)驗(yàn)圖12.310個(gè)特征系數(shù)的變化路徑如圖12.3所示，當(dāng)正則化參數(shù)較大時(shí)，所有系數(shù)均壓縮為0；隨著的增大，各個(gè)系數(shù)也逐漸增大.實(shí)際中可以通過交叉檢驗(yàn)選擇合適懲罰值.數(shù)據(jù)科學(xué)優(yōu)化方法Optimization

Method

in

Data

Science數(shù)學(xué)基礎(chǔ)A.1線性代數(shù)A.2微積分A.3凸分析線性代數(shù)A.1.1向量和矩陣A.1.2特征值和特征向量A.1.3內(nèi)積和范數(shù)向量和矩陣維列向量：或者其中表示向量的第個(gè)分量，部分章節(jié)也使用表示分量.維實(shí)向量構(gòu)成的空間記為.列向量的轉(zhuǎn)置為行向量：向量和矩陣

矩陣：

其中，表示矩陣的第行第列元素，表示矩陣的對(duì)角元素.矩陣構(gòu)成的空間記為.向量和矩陣矩陣的轉(zhuǎn)置：顯然.若對(duì)任意的有，則稱矩陣為上三角矩陣若對(duì)于任意的有，則稱矩陣

為下三角矩陣向量和矩陣常見的矩陣類型方陣：如果，即矩陣的行數(shù)等于矩陣的列數(shù);

只有對(duì)角元為1，其余元素均為0的方陣稱為單位陣，

記為.對(duì)稱陣:若,且;正定陣（半正定陣）：若，且為對(duì)稱陣，若對(duì)于任意的,有().向量和矩陣常見的矩陣類型負(fù)定陣（半負(fù)定陣）:若，且為對(duì)稱陣，若對(duì)于任意的,有（).

非奇異陣/可逆矩陣:若且.可逆矩陣一定存在逆矩陣,使得.正交陣：若，且.線性代數(shù)A.1.1向量和矩陣A.1.2特征值和特征向量A.1.3內(nèi)積和范數(shù)特征值和特征向量特征值的性質(zhì)與應(yīng)用設(shè)，存在標(biāo)量(可能是復(fù)數(shù)）和非零向量滿足，則稱為矩陣的特征值，為矩陣的特征向量.若矩陣的特征值全部非零，則為非奇異矩陣；實(shí)對(duì)稱矩陣的特征值均為實(shí)數(shù)，且具有個(gè)互相正交的特征向量；矩陣的跡滿足；矩陣的行列式等于特征值的積，即特征值和特征向量對(duì)稱矩陣是正定(半正定)，當(dāng)且僅當(dāng)

的所有特征根是正的(非負(fù)的)。定理A.1線性代數(shù)A.1.1向量和矩陣A.1.2特征值和特征向量A.1.3內(nèi)積和范數(shù)內(nèi)積與范數(shù)常用的向量范數(shù)向量的內(nèi)積與正交性兩個(gè)向量與的內(nèi)積為.如果，則稱與正交的.

內(nèi)積與范數(shù)范數(shù)的等價(jià)性上面介紹的三種范數(shù)滿足如下不等式范數(shù)的性質(zhì)非負(fù)性：，且，當(dāng)且僅當(dāng)齊次性：，三角不等式：內(nèi)積與范數(shù)設(shè),則有其中等號(hào)成立當(dāng)且僅當(dāng)存在，使得.定理A.2

Cauchy-Schwarz不等式導(dǎo)出范數(shù):根據(jù)已經(jīng)定義好的向量范數(shù)可以誘導(dǎo)出一種相應(yīng)的矩陣范數(shù)，其定義如下

內(nèi)積與范數(shù)當(dāng)取向量的，，時(shí)導(dǎo)出的矩陣范數(shù)分別稱為矩陣的1范數(shù)、2范數(shù)和無窮范數(shù)矩陣的Frobenius范數(shù)也是一種常用的矩陣范數(shù)，其定義如下：內(nèi)積與范數(shù)以上四種范數(shù)都滿足相容性，即矩陣的條件數(shù)是判斷一個(gè)矩陣是否病態(tài)的重要指標(biāo)，其定義為實(shí)踐中常用二條件數(shù)

附錄A數(shù)學(xué)基礎(chǔ)A.1線性代數(shù)A.2微積分A.3凸分析微積分A.2.1序列和極限A.2.2歐式空間拓?fù)浣Y(jié)構(gòu)A.2.3連續(xù)函數(shù)A.2.4導(dǎo)數(shù)與梯度A.2.5中值定理和泰勒定理序列和極限收斂序列的定義若序列滿足，對(duì)于所有的都有則稱序列收斂到，記作極限點(diǎn)設(shè)，則得到的子序列.子序列的收斂點(diǎn)被稱為序列的極限點(diǎn)或者聚點(diǎn).注：一個(gè)序列可以有多個(gè)極限點(diǎn)，收斂的序列只有一個(gè)極限點(diǎn).序列和極限有界序列單調(diào)收斂定理對(duì)于序列，若存在常數(shù),使得對(duì)于所有的都有，則稱序列有下界.類似的，若滿足則稱序列有上界.若序列滿足對(duì)于所有的，都有，則稱序列單調(diào)不減.類似的若滿足，則稱序列單調(diào)不增.若序列單調(diào)不減（增）且有上（下）界，那么序列必收斂.微積分A.2.1序列和極限A.2.2歐式空間拓?fù)浣Y(jié)構(gòu)A.2.3連續(xù)函數(shù)A.2.4導(dǎo)數(shù)與梯度A.2.5中值定理和泰勒定理歐式空間拓?fù)浣Y(jié)構(gòu)鄰域給定任意，若為包含的開集，則稱為點(diǎn)的鄰域.以為球心，為半徑的球記為.

常見點(diǎn)集設(shè)，則為有界集：若存在實(shí)數(shù)，使得有

開集：若對(duì)于任意的，存在使得

閉集：若對(duì)于中的所有點(diǎn)列，其極限點(diǎn)都屬于微積分A.2.1序列和極限A.2.2歐式空間拓?fù)浣Y(jié)構(gòu)A.2.3連續(xù)函數(shù)A.2.4導(dǎo)數(shù)與梯度A.2.5中值定理和泰勒定理連續(xù)函數(shù)連續(xù)函數(shù)設(shè)函數(shù)在點(diǎn)的某個(gè)鄰域內(nèi)有定義，若有，則稱函數(shù)在點(diǎn)處連續(xù)若函數(shù)在定義域內(nèi)的所有點(diǎn)都連續(xù),則稱

為定義域內(nèi)的連續(xù)函數(shù)設(shè)若存在常數(shù),使得對(duì)任意的,有則稱為L(zhǎng)ipchitz連續(xù)函數(shù)，其中為L(zhǎng)ipschitz常數(shù).定義A.1

Lipschitz連續(xù)函數(shù)微積分A.2.1序列和極限A.2.2歐式空間拓?fù)浣Y(jié)構(gòu)A.2.3連續(xù)函數(shù)A.2.4導(dǎo)數(shù)與梯度A.2.5中值定理和泰勒定理導(dǎo)數(shù)與梯度導(dǎo)數(shù)與梯度設(shè)函數(shù)，若存在且有限，則稱函數(shù)在點(diǎn)處一階可導(dǎo)，上述極

限稱為在處的一階導(dǎo)數(shù)，記為或.類似地由導(dǎo)函數(shù)可以定義二階導(dǎo)數(shù).梯度：考慮元函數(shù)，在

處的梯度定義為導(dǎo)數(shù)與梯度Hesse矩陣多元函數(shù)的二階偏導(dǎo)數(shù)矩陣稱為Hesse矩陣，定義為可微函數(shù)與連續(xù)可微函數(shù)若函數(shù)在任意點(diǎn)處的一階偏導(dǎo)數(shù)