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

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

Method

in

Data

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

方法每次迭代時，在當前迭代點處沿一個坐標軸方向進行一維搜索，以求得目標函數(shù)在該方向的局部極小點.

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

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

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

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

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

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

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

取極小值，令，

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

當負梯度下降法步長取時，由推論（4.1），負梯度方法的收斂速度為當隨機坐標下降方法步長取時，隨機坐標下降方法的收斂速度為收斂速度的比較隨機坐標下降方法由于，因此隨機坐標下降算法的收斂速率一般慢于負梯度算法！只有當上述不等式成立時，才具有相同的速度.

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

強凸函數(shù),令則對任意有

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

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

，則對任意，有

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

和（11.4）即可.不同的

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

當負梯度下降法步長取，迭代次數(shù)

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

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

.計算

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

在第步迭代中，步驟4中子問題是這樣形成的：在當前迭代點處沿第個坐標軸方向?qū)δ繕撕瘮?shù)進行線性近似，并增加一個權(quán)重為

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

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

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

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

Method

in

Data

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

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

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

12.4共享問題12.5數(shù)值實驗

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

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

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

12.2.4終止準則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）分別稱為極小化步、極小化步式和對偶變量更新步.迭代公式ADMM迭代公式標準化形式定義原始殘差則原Lagrange函數(shù)可以改寫為由此得到ADMM迭代公式的標準化形式（12.16）（12.17）（12.18）迭代公式例12.1考慮經(jīng)典Lasso問題其中，,正則化參數(shù).迭代公式解：先將Lasso問題改寫成如下的約束最優(yōu)化問題其中，.應用（12.16）-（12.18）可得如下ADMM迭代公式（12.19）迭代公式如果，可利用Shermann-Morrision-Woodbury公式計算.ADMM方法的一般形式和理論性質(zhì)12.2.1迭代公式12.2.2收斂性分析12.2.3最優(yōu)性條件

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

和為正

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

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

（12.20）引理12.1收斂性分析證明：由于是的一個鞍點，可得由假設1可知取有限值，由此可推出(否則).于是又因為，故.

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

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

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

的極小值點，是的極小值點.

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

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

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

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

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

由于為的極小點，故有上式等價于因此，可以視為對偶條件式（12.29）的殘差，稱為對偶殘差.最優(yōu)性條件

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

和對偶殘差趨于.這兩點在定理12.1中得到證明.ADMM方法的一般形式和理論性質(zhì)12.2.1迭代公式12.2.2收斂性分析12.2.3最優(yōu)性條件

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

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

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

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

當較大時，違反原始可行條件會帶來較大懲罰，因而產(chǎn)生較小的原始殘差

當較大時，對偶殘差變大懲罰參數(shù)選擇

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

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

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

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

全局一致性問題

全局一致性問題的定義為了實現(xiàn)分布式計算，可以改寫原問題為如下約束優(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）得，意味著全局一致性問題全局一致性問題①②③④⑤全局一致性問題帶正則項的全局一致性問題在問題（12.32）目標函數(shù)的基礎(chǔ)上增加正則項，就可得到帶正則項的全局一致性問題s.t.（12.38）全局一致性問題ADMM方法迭代公式其標準化形式為（12.39）（12.40）（12.41）全局一致性問題全局一致性問題例12.2機器學習領(lǐng)域的很多問題可歸結(jié)為如下無約束最優(yōu)化問題（12.42）其中變量，為特征矩陣，為輸出向量，為凸損失函數(shù)，為凸正則函數(shù).

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

范數(shù).

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

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

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

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

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

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

，

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

和，并將更新后的和傳給

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

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

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

考慮一個由

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

隨機產(chǎn)生.響應變量由線性回歸模型產(chǎn)生：數(shù)值實驗從圖（12.2）可以看出，近端梯度方法、加速近端梯度方法和ADMM方法能在100步內(nèi)收斂，隨機坐標下方法因為只更新部分特征，收斂速度較慢.

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

Lasso問題為其中為特征矩陣.這里應用坐標下降法來求解上述Lasso問題.

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

Method

in

Data

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

矩陣：

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

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

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

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

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

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

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

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

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

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

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

開集：若對于任意的，存在使得

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

為定義域內(nèi)的連續(xù)函數(shù)設若存在常數(shù),使得對任意的,有則稱為Lipchitz連續(xù)函數(shù)，其中為Lipschitz常數(shù).定義A.1

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

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

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