數(shù)據(jù)科學優(yōu)化方法 課件 第9、10章 罰函數(shù)方法、近端方法

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

Method

in

Data

Science第9章罰函數(shù)方法9.1二次罰函數(shù)方法9.2障礙函數(shù)方法9.3增廣Lagrange函數(shù)方法9.4數(shù)值實驗引入無約束最優(yōu)化問題引入無約束最優(yōu)化問題負梯度方法牛頓方法引入無約束最優(yōu)化問題負梯度方法牛頓方法復雜問題簡單化引入？約束優(yōu)化問題的求解往往比較麻煩，能否將將約束最優(yōu)化問題轉化為一系列無約束最優(yōu)化問題，利用無約束優(yōu)化問題的方法進行求解？

罰函數(shù)方法就是這樣一類方法將約束以罰函數(shù)形式加到目標函數(shù)中第9章罰函數(shù)方法9.1二次罰函數(shù)方法9.2障礙函數(shù)方法9.3增廣Lagrange函數(shù)方法9.4數(shù)值實驗二次罰函數(shù)方法將約束優(yōu)化問題轉化為無約束優(yōu)化問題，目標函數(shù)由以下兩部分組成原約束優(yōu)化問題的目標函數(shù)每個約束對應的約束函數(shù)：如果當前點??滿足約束，則該項為0；如果不滿足，則該項為正二次罰函數(shù)方法對于僅含有等式約束的最優(yōu)化問題

二次罰函數(shù)方法二次罰函數(shù)方法二次罰函數(shù)方法二次罰函數(shù)方法二次罰函數(shù)方法對于僅含有等式約束的最優(yōu)化問題

定義如下二次罰函數(shù)第二項為懲罰項，是懲罰參數(shù).

(9.2)二次罰函數(shù)方法僅非可行點的懲罰項非零，也稱為外點罰函數(shù)方法.罰函數(shù)的極小點與約束優(yōu)化問題的極小點不同，且常為約束優(yōu)化問題的非可行點.對非可行點，增大懲罰參數(shù)的值，迫使二次罰函數(shù)的極小點不斷接近原問題的可行域.

二次罰函數(shù)方法二次罰函數(shù)方法二次罰函數(shù)方法二次罰函數(shù)方法例9.1考慮等式約束最優(yōu)化問題

二次罰函數(shù)方法

由

，得求解這個方程組，得于是有易知最優(yōu)解為

該問題的二次罰函數(shù)為解：二次罰函數(shù)方法下圖給出了二次罰函數(shù)在不同下的等高線，其中三角形表示原問題的最優(yōu)解，實心點表示二次罰函數(shù)的最優(yōu)解.

二次罰函數(shù)方法從圖中可以看出隨著

的增大，

的極小點會趨于原問題的最優(yōu)解

定義如下二次罰函數(shù)其中對于一般的約束優(yōu)化問題二次罰函數(shù)方法二次罰函數(shù)方法算法9.1：二次罰函數(shù)方法的計算步驟給定初始點

，

，

.以

為初始點，極小化

，當

，則停止迭代，得近似極小點

.若

，則停止迭代，得近似解

；否則，選擇新的懲罰參數(shù)

.

，

，轉至步驟2.

二次罰函數(shù)方法算法9.1的第2步為內層子迭代，可選用某一合適的無約束最優(yōu)化方法求解二次罰函數(shù)的極小點.為了加快算法的收斂，用上一輪的解作為這一輪子迭代的初始點(熱啟動,

warm-start).

根據(jù)每一輪內存子迭代中極小化二次罰函數(shù)的困難程度自適應選擇懲罰參數(shù).當極小化二次罰函數(shù)計算量很大時，可以選擇讓略大于，例如;當極小化二次罰函數(shù)較為容易，可以讓

快速增

加，例如.

二次罰函數(shù)方法在第2步中，若二次罰函數(shù)不存在極小點，則增大懲罰參數(shù)后重新求解.二次罰函數(shù)方法假設每個

都是二次罰函數(shù)

的全局極小點，且

，則迭代序列

的任何極限點

都是問題(9.1)的全局最優(yōu)解.定理9.1下面討論二次罰函數(shù)方法的收斂性.這里只考慮等式約束最優(yōu)化問題(9.1)，其二次懲罰函數(shù)為二次罰函數(shù)方法證明：設是問題(9.1)的全局最優(yōu)解，則對于所有滿足

的，有因為

是的全局極小點，則有，從而有整理上式，得假設是的一個極限點，則存在一個無限子序列滿足二次罰函數(shù)方法對(9.6)兩邊取極限，令，，可得因此有，故是問題(9.1)的可行點.進一步，對(9.5)兩邊取極限，令，由和的非負性，可得由是問題(9.1)的可行點和是問題(9.1)的全局最優(yōu)解可知

也是問題(9.1)的全局最優(yōu)解.二次罰函數(shù)方法在算法9.1中，若在第2步有，且

，對

的任何極限點

，線性無關，則

是等式約束最優(yōu)化問題(9.1)的KKT點，且

其中

是

對應的Lagrange乘子.定理9.2定理9.1要求找到二次罰函數(shù)的全局極小點，在很多情況下這是非常困難的.下面的定理給出了如果每一步都求

的局部近似極小點，則在一定條件下，序列的任何極限點收斂到問題(9.1)的KKT點.二次罰函數(shù)方法證明：對求導得由算法9.1的第2步中極小化

的終止準則，有利用三角不等式，整理上式有對上式兩邊取極限，令，由于，可得因為線性無關，故

因此，是問題(9.1)的可行點.二次罰函數(shù)方法下面證明

是問題(9.1)的KKT點.令，則式(9.8)可以寫成當充分大時，矩陣列滿秩，故非奇異.式(9.11)兩邊左乘，整理可得二次罰函數(shù)方法由于，且，故令，由式(9.11)可得因此，

是問題(9.1)的KKT點，是對應的Lagrange乘子.二次罰函數(shù)方法從二次罰函數(shù)方法的收斂性分析可以看出，懲罰參數(shù)序列

一定要滿足

，但這將導致算法9.1中第2步對無約束最優(yōu)化問題的求解變得越來越困難.原因在于隨著

的增大，Hesse矩陣

會變得越來越病態(tài)算法的數(shù)值困難二次罰函數(shù)方法令

，有若

充分接近

的極小點且定理9.2的條件滿足，則有矩陣

的秩為

，這里假設

.當

時，

的特征值有

個趨于無窮大，其余的保持有界，這會導致等高線變?yōu)橐粋€“很扁”的橢圓，不利于數(shù)值優(yōu)化的穩(wěn)定性.

第9章罰函數(shù)方法9.1二次罰函數(shù)方法9.2障礙函數(shù)方法9.3增廣Lagrange函數(shù)方法9.4數(shù)值實驗障礙函數(shù)方法相同點兩者都是把約束優(yōu)化問題轉化為無約束優(yōu)化問題.

不同點二次罰函數(shù)方法是由可行域外逼近約束優(yōu)化問題的最優(yōu)解的，障礙函數(shù)方法則是由可行域內部逼近約束優(yōu)化問題的最優(yōu)解.

二次罰函數(shù)方法可以解決等式和不等式約束優(yōu)化問題，而障礙函數(shù)方法則適宜解決不等式約束優(yōu)化問題.

與二次罰函數(shù)方法對比障礙函數(shù)方法障礙函數(shù)方法障礙函數(shù)方法障礙函數(shù)方法障礙函數(shù)方法障礙函數(shù)方法障礙函數(shù)方法考慮含有不等式約束的最優(yōu)化問題

定義如下對數(shù)障礙函數(shù)定義如下倒數(shù)障礙函數(shù)

其中是障礙參數(shù)，是自然對數(shù).我們將對數(shù)障礙函數(shù)和倒數(shù)障礙函數(shù)統(tǒng)稱為障礙函數(shù).

障礙函數(shù)方法由于障礙函數(shù)的極小點序列始終在可行域內，因此障礙函數(shù)也被稱為內點罰函數(shù).

當

在可行域內遠離可行域邊界時，障礙項數(shù)值較小；當

從可行域內部接近可行域邊界時，至少某個約束接近于起作用，此時障礙項會無限增大，以防止迭代點躍出可行域.

障礙函數(shù)方法當

在可行域內遠離可行域邊界時，障礙項數(shù)值較小；當

從可行域內部接近可行域邊界時，至少某個約束接近于起作用，此時障礙項會無限增大，以防止迭代點躍出可行域.

障礙函數(shù)方法障礙函數(shù)方法由于帶不等式約束的優(yōu)化問題(9.12)的解可能落在邊界上，為了使障礙函數(shù)的極小點序列能夠接近可行域邊界，允許，以降低障礙項的大小.

障礙函數(shù)方法障礙函數(shù)方法障礙函數(shù)方法障礙函數(shù)方法障礙函數(shù)方法障礙函數(shù)方法障礙函數(shù)方法障礙函數(shù)方法例9.2考慮不等式約束最優(yōu)化問題

障礙函數(shù)方法下圖給出了對數(shù)障礙函數(shù)在不同下的等高線，從圖中可以看出隨著

的減小，對數(shù)障礙函數(shù)的極小值會越來越接近最優(yōu)解

該問題的最優(yōu)解為

該問題的對數(shù)障礙函數(shù)為

解：障礙函數(shù)方法障礙函數(shù)方法算法9.2：障礙函數(shù)方法的計算步驟給定初始內點滿足

以

為初始點，極小化

，當

，則停止迭代，得近似極小點

若滿足收斂準則，則停止迭代，得近似解

；否則，選擇新的障礙參數(shù)

，，轉至步驟2.

障礙函數(shù)方法算法9.2的第3步中的收斂準則如下：

倒數(shù)障礙函數(shù)

對數(shù)障礙函數(shù)

可按如下方式確定新的障礙參數(shù)：當極小化障礙罰函數(shù)較為困難，可以讓略小于，例如；否則，可以讓快速減小，例如障礙函數(shù)方法假設嚴格可行內點區(qū)域非空，

是不等式約束的優(yōu)化問題的局部極小點，對應的Lagrange乘子滿足KKT條件，且約束規(guī)范條件LICQ、嚴格互補條件和二階充分最優(yōu)化性條件在點處成立，則有以下結論

(1)對充分小的，如果是

鄰域內的局部極小點，則存在連續(xù)可微的向量函數(shù)

，使得

(2)對(1)中定義的函數(shù)

，當，對應的Lagrange乘子估計收斂到，其中

(3)對充分小的，的Hesse矩陣是正定的.定理9.3障礙函數(shù)方法類似二次罰函數(shù)方法，當時，障礙函數(shù)方法中的無約束最優(yōu)化問題的求解會變得越來越困難.以對數(shù)障礙函數(shù)為例，在點處的Hesse矩陣

為令，由Lagrange函數(shù)的定義，有因此，當

，矩陣越來越病態(tài).算法的數(shù)值困難第9章罰函數(shù)方法9.1二次罰函數(shù)方法9.2障礙函數(shù)方法9.3增廣Lagrange函數(shù)方法9.4數(shù)值實驗增廣Lagrange函數(shù)方法？從前面的討論，可知二次罰函數(shù)方法存在算法的數(shù)值困難，其根本原因在于時，會引起無約束最優(yōu)化問題的病態(tài)性。那么能否構造一個函數(shù)，其不需要取無窮大的值，其極小點就是原問題的最優(yōu)解？

那么如何構造這樣的函數(shù)呢？這就是本節(jié)要介紹的增廣Lagrange函數(shù)方法增廣Lagrange函數(shù)方法9.3.1增廣Lagrange函數(shù)的思想9.3.2等式約束最優(yōu)化問題的增廣Lagrange函數(shù)方法9.3.3一般約束最優(yōu)化問題的增廣Lagrange函數(shù)方法增廣Lagrange函數(shù)的思想由于我們想要構造的函數(shù)是無約束最優(yōu)化問題的目標函數(shù)，因此可以根據(jù)無約束最優(yōu)化問題的最優(yōu)性條件去構造這樣的函數(shù).在這里考慮等式約束最優(yōu)化問題增廣Lagrange函數(shù)的思想設想要構造的函數(shù)為，其中是給定的參數(shù)。我們希望求解無約束優(yōu)化問題：，得到原問題的最優(yōu)解.在處，應滿足如下條件一階充分條件

二階充分條件增廣Lagrange函數(shù)的思想目前已知的函數(shù)滿足這兩個條件嗎？如果不滿足的話，該如何改造，使其滿足這兩個條件？二次罰函數(shù)因為是可行點，故.對約束強起作用情形，，故不是無約束最優(yōu)化問題的解.注：這一結果表明在懲罰參數(shù)給定的情形下，一般不可能通過求二次罰函數(shù)的極小點得到原問題的最優(yōu)解.增廣Lagrange函數(shù)的思想Lagrange函數(shù)如果點是它的KKT點，對應的Lagrange乘子為，則在點

處條件

自然滿足.一般情況下，在點

處僅約束的切線方向（即線性化可行方向）滿足條件，其他方向則無法滿足該條件.增廣Lagrange函數(shù)的思想增廣Lagrange函數(shù)的思想Lagrange函數(shù)為此，我們對Lagrange函數(shù)進行改造，使其在點

附近，沿線性化可行方向

的函數(shù)值保持不變，沿其他方向的函數(shù)值變大，使改造后函數(shù)在點處的Hesse矩陣對任意非零方向

均滿足條件.增廣Lagrange函數(shù)的思想增廣Lagrange函數(shù)的思想Lagrange函數(shù)為此，我們對Lagrange函數(shù)進行改造，使其在點

附近，沿線性化可行方向

的函數(shù)值保持不變，沿其他方向的函數(shù)值變大，使改造后函數(shù)在點處的Hesse矩陣對任意非零方向

均滿足條件.為了實現(xiàn)這一目標，當變量不滿足約束時，加大的函數(shù)值，而這正是構造罰函數(shù)的思想.增廣Lagrange函數(shù)方法9.3.1增廣Lagrange函數(shù)的思想9.3.2等式約束最優(yōu)化問題的增廣Lagrange函數(shù)方法9.3.3一般約束最優(yōu)化問題的增廣Lagrange函數(shù)方法考慮等式約束的最優(yōu)化問題

定義如下增廣Lagrange函數(shù)該函數(shù)可以視為在標準的Lagrange函數(shù)基礎上增加了二次罰函數(shù)，故又稱為乘子罰函數(shù).

等式約束最優(yōu)化問題的增廣Lagrange函數(shù)方法例9.3考慮等式約束最優(yōu)化問題

等式約束最優(yōu)化問題的增廣Lagrange函數(shù)方法它的增廣Lagrange函數(shù)為該問題的全局最優(yōu)解為，對應的Lagrange乘子為.假設在第步迭代有，當前的Lagrange乘子估計值為.

解：等式約束最優(yōu)化問題的增廣Lagrange函數(shù)方法下圖給出了增廣Lagrange函數(shù)的等高線.與第一節(jié)中所示的二次罰函數(shù)的等高線圖相比，的極小點更接近原問題的最優(yōu)解.注：該例子表明，在Lagrange函數(shù)而非目標函數(shù)中增加二次懲罰項效果更優(yōu).等式約束最優(yōu)化問題的增廣Lagrange函數(shù)方法設在第步，，，求增廣Lagrange函數(shù)關于的極小點由無約束最優(yōu)化問題的一階最優(yōu)性條件，可得結合KKT條件，可推出

由此，得到的迭代公式等式約束最優(yōu)化問題的增廣Lagrange函數(shù)方法當

充分大時，二次罰函數(shù)方法的約束函數(shù)與乘子滿足如下關系而增廣Lagrange函數(shù)方法的約束函數(shù)和乘子滿足如下關系比較這兩個式子可以發(fā)現(xiàn)，當充分接近，增廣Lagrange函數(shù)得到的迭代點比二次罰函數(shù)得到的迭代點

更接近可行點.等式約束最優(yōu)化問題的增廣Lagrange函數(shù)方法增廣Lagrange函數(shù)方法與二次罰函數(shù)方法的區(qū)別將原問題轉換為二次罰函數(shù)的問題以后應該如何求解？

算法9.3：增廣Lagrange函數(shù)方法的計算步驟給定初始點

以

為初始點，極小化

，當

時停止，得近似極小點

若，則停止迭代，得近似解

；否則，更新

選擇新的懲罰參數(shù)

4.

，轉至步驟2.

等式約束最優(yōu)化問題的增廣Lagrange函數(shù)方法設是等式約束最優(yōu)化問題(9.1)的局部最優(yōu)解，且在點

處約束規(guī)范條件LICQ成立,是對應的Lagrange乘子，在處二階充分條件

成立，則存在，對任意，是增廣Lagrange函數(shù)的嚴格局部極小點；反之，若

是的局部極小點，則是等式約束最優(yōu)化問題(9.1)的局部最優(yōu)解.定理9.4等式約束最優(yōu)化問題的增廣Lagrange函數(shù)方法雖然在實際應用中，我們通常并不知道的精確值，但上述定理表明只要是的一個好的估計，即使不很大，

關于的極小點也是原問題局部最優(yōu)解

的一個好的估計.等式約束最優(yōu)化問題的增廣Lagrange函數(shù)方法證明：我們通過證明當充分大時，在點處滿足無約束優(yōu)化問題的二階充分條件從而推出是增廣Lagrange函數(shù)的嚴格局部極小點.由于

是問題(9.1)的局部最優(yōu)解，由KKT條件及

的可行性可知等式約束最優(yōu)化問題的增廣Lagrange函數(shù)方法因此有說明(9.18)成立，以及其中為約束函數(shù)在點處的梯度矩陣，即等式約束最優(yōu)化問題的增廣Lagrange函數(shù)方法若(9.19)不成立，則對任意的正整數(shù)，存在，使得于是，可得由于向量在單位圓周上，故一定存在極限點(9.21)表明又由(9.20)，可得令得而這與二階充分條件相矛盾，因此，當充分大時，(9.19)成立.等式約束最優(yōu)化問題的增廣Lagrange函數(shù)方法反之，已知是可行點，對任意的可行點

，設其充分接近

，則有由于

和

的可行性，可知則對與

充分接近的可行點

，有從而，

是問題(9.1)的局部最優(yōu)解.等式約束最優(yōu)化問題的增廣Lagrange函數(shù)方法增廣Lagrange函數(shù)方法9.3.1增廣Lagrange函數(shù)的思想9.3.2等式約束最優(yōu)化問題的增廣Lagrange函數(shù)方法9.3.3一般約束最優(yōu)化問題的增廣Lagrange函數(shù)方法一般約束最優(yōu)化問題的增廣Lagrange函數(shù)方法核心思想：對于一般的約束最優(yōu)化問題，我們可以通過引入松弛變量，將不等式約束轉化為等式約束，再用求解等式約束最優(yōu)化問題的增廣Lagrange函數(shù)方法予以求解.引入松弛變量，則一般約束最優(yōu)化問題變?yōu)槿缦滤沙趩栴}若先不考慮松弛變量的非負約束，上述松弛問題就是等式約束最優(yōu)化問題.一般約束最優(yōu)化問題的增廣Lagrange函數(shù)方法對應的增廣Lagrange函數(shù)為其中因此，帶松弛變量非負約束的增廣Lagrange函數(shù)最優(yōu)化問題為該問題等價于一般約束最優(yōu)化問題的增廣Lagrange函數(shù)方法如果可以從問題中解析求解出，將其代入，消去，得到這樣問題就可以化簡為一般約束最優(yōu)化問題的增廣Lagrange函數(shù)方法下面來求解由于是關于的凸函數(shù)，故關于的穩(wěn)定點就是極小點.令，即解得考慮到松弛變量非負，則問題的解為一般約束最優(yōu)化問題的增廣Lagrange函數(shù)方法從而或將式(9.26)代入中，消去，得一般約束最優(yōu)化問題的增廣Lagrange函數(shù)方法由此得到化簡后的增廣Lagrange函數(shù)其中由下式給出一般約束最優(yōu)化問題的增廣Lagrange函數(shù)方法Lagrange乘子的迭代公式和方法停止準則由等式約束最優(yōu)化問題的乘子迭代公式，有

由

一般約束最優(yōu)化問題的增廣Lagrange函數(shù)方法由等式約束最優(yōu)化問題的終止準則，有消去，得到化簡后的終止準則

第9章罰函數(shù)方法9.1二次罰函數(shù)方法9.2障礙函數(shù)方法9.3增廣Lagrange函數(shù)方法9.4數(shù)值實驗數(shù)值實驗在本小節(jié)中，我們通過數(shù)值實驗比較罰函數(shù)方法和增廣Lagrange函數(shù)方法的有效性迭代步長滿足Wolfe非精確線搜索準則內層迭代采用BFGS方法求解

閾值

數(shù)值實驗該問題的最優(yōu)解為初始點取為問題1數(shù)值實驗該問題的最優(yōu)解為

初始點取為問題2數(shù)值實驗該問題的最優(yōu)解為初始點取為問題3數(shù)值實驗表9.1給出了用不同罰函數(shù)方法和增廣Lagrange函數(shù)方法求解這三個問題所需的外迭代次數(shù)、函數(shù)調用次數(shù)、算法終止時的懲罰參數(shù)以及數(shù)值實驗二次罰函數(shù)方法對于問題1失效，迭代過程中出現(xiàn)矩陣病態(tài)的情形，導致迭代失敗.從表中結果可以發(fā)現(xiàn)，用增廣Lagrange函數(shù)方法得到的解的絕對誤差不低于二次罰函數(shù)方法或障礙函數(shù)方法得到的解的絕對誤差.對問題3，增廣Lagrange函數(shù)方法迭代終止時的懲罰參數(shù)

遠大于障礙罰函數(shù)方法迭代終止時的懲罰參數(shù).對問題2，增廣Lagrange函數(shù)方法迭代終止時的懲罰參數(shù)

遠小于二次罰函數(shù)方法迭代終止時的懲罰參數(shù).數(shù)據(jù)科學優(yōu)化方法Optimization

Method

in

Data

Science第10章近端方法10.1近端算子10.2近端極小化方法10.3近端梯度方法10.4加速近端梯度方法引入？前面章節(jié)我們討論的最優(yōu)化問題中目標函數(shù)都是光滑的的，對于目標函數(shù)非光滑的復合最優(yōu)化問題，該如何求解呢？

近端方法就是這樣一類方法引入近端方法是求解凸優(yōu)化問題的一類重要方法，具有以下幾個優(yōu)點適用范圍很廣容易并行化易于理解、推導和實現(xiàn)適用于一些難以求解的最優(yōu)化問題第10章近端方法10.1近端算子10.2近端極小化方法10.3近端梯度方法10.4加速近端梯度方法近端算子10.1.1定義10.1.2解釋10.1.3性質定義設為非空凸集，的上圖為定義設為非空凸集，為上的凸函數(shù)當且僅當為凸集定理定義設函數(shù)，若它的上圖為閉集，則稱函數(shù)

為閉函數(shù).定義

閉函數(shù)設函數(shù)，若其有效域非空,即則稱為正常函數(shù).定義

正常函數(shù)定義設是一個正常閉凸函數(shù)，則它的上圖為非空閉凸集.定義正常閉凸函數(shù)的近端算子（proximaloperator）

定義為定義10.1.近端算子注：式子右邊極小化的函數(shù)為強凸函數(shù)，且不是處處取無窮大，因此對任意，該函數(shù)均有唯一極小點.定義在實際應用中，我們經(jīng)常會遇到函數(shù)，其中，其近端算子可寫為也常被稱為帶參數(shù)的函數(shù)的近端算子.定義圖10.1

不同點上的近端算子定義是

極小點和附近點的一個折中

有時被稱為點關于

的近端點.在

中，參數(shù)是這兩項間的相對權重.近端算子10.1.1定義10.1.2解釋10.1.3性質解釋

廣義投影次微分算子的分解負梯度步廣義投影

當是如下示性函數(shù)其中是一個非空閉集，的近端算子就是集合上的歐氏投影，其定義如下廣義投影

可將近端算子視為一個廣義投影

廣義投影

可將近端算子視為一個廣義投影

次微分算子的分解對于凸函數(shù)，其次梯度和次微分算子的定義如下定義10.2次梯度和次微分設是凸函數(shù)，若在點處，有則稱為在點處的次梯度，

在點

處的次梯度集合記為,稱

為

的次微分算子.次微分算子的分解若

在點

處可微，則，由此稱為從

到的梯度映射.梯度映射為點到點的映射.次微分算子的分解次微分算子

將每個點映射為一個集合.不難證明，次梯度集合

是一個閉凸集.次微分算子的分解定義10.3.次可微若在點處有次梯度，則稱在點處次可微.進一步，若在定義域內任意點處都有次梯度，則稱

為次可微函數(shù).次微分算子的分解命題10.1若是正常凸函數(shù)，則是的（全局）極小點當且僅當.次微分算子的分解設是正常閉凸函數(shù)，且在定義域內次可微，則有定理10.1給出了近端算子和次微分算子之間的關系定理10.1我們稱映射為帶參數(shù)的次微分算子的分解.定理表明近端算子是次微分算子的分解.注：雖然

是一個點到集合的映射，但次微分算子的分解卻是一個點到點的映射.次微分算子的分解證明：若，則由次微分算子定義可知將移到右邊，兩邊同時除以，可得上式等價于由于右側括號內為強凸函數(shù)，故次微分算子的分解上述推導過程反之亦成立，由此說明當且僅當

因為有唯一值，所以也有唯一值，從而等式成立.負梯度步

函數(shù)

的近端算子可以解釋為極小化函數(shù)

或與

相關的某個函數(shù)的負梯度步，以下從三個不同角度進行討論Moreau包絡近似梯度步函數(shù)近似的近端算子Moreau包絡

定義10.4Moreau包絡對于函數(shù)

，其參數(shù)為的Moreau包絡（Moreauenvelope）或Moreau-Yosida正則化定義為Moreau包絡

Moreau包絡

Moreau包絡是函數(shù)的一個光滑逼近函數(shù).由于

和

的極小點完全相同，故極小化兩者是等價的由于極小化是光滑最優(yōu)化問題，故在很多實際問題中，極小化

會更加容易.Moreau包絡

函數(shù)

的近端算子

函數(shù)

的Moreau包絡Moreau包絡

Moreau包絡

可以視為極小化（與

的極小點相同）的一個步長為

的負梯度步.近似梯度步

若

在點處二階連續(xù)可微，且Hesse矩陣是正定的，則當，有于是，當較小時，收斂到

的負梯度步，其步長為.對于較小的

，近端算子可以近似認為是極小化

的一個負梯度步.函數(shù)近似的近端算子

一階連續(xù)可微由泰勒定理可知，

在點處的一階近似為于是，函數(shù)

一階近似的近端算子為這就是一個標準的步長為的負梯度步.負梯度步可以視為函數(shù)一階近似的近端算子.考慮函數(shù)近似的近端算子，及它們和極小化的負梯度步之間的關系函數(shù)近似的近端算子

二階連續(xù)可微

在點處的二階近似為于是，函數(shù)

二階近似的近端算子為上式右邊就是LM方法的迭代步.LM步可以視為函數(shù)二階近似的近端算子.近端算子10.1.1定義10.1.2解釋10.1.3性質性質若關于兩個變量是可分的，即，則有若

是完全可分的，即，則有注：對于可分函數(shù)，通過計算每個子函數(shù)近端算子就可以得到原函數(shù)的近端算子.該性質是近端方法并行化的關鍵所在！性質若

，則有若，其中為正交矩陣，則有若

，則有若

，則有其中第10章近端方法10.1近端算子10.2近端極小化方法10.3近端梯度方法10.4加速近端梯度方法近端極小化方法近端極小化（ProximalMinimization）方法與不動點定理有很緊密聯(lián)系，為此本節(jié)先介紹不動點定理.設是正常閉凸函數(shù)，則點是函數(shù)

的極小點當且僅當即

是

的一個不動點.定理10.2.不動點定理注：該定理給出了判斷某點是不是正常閉凸函數(shù)極小點的充要條件.近端極小化方法證明：首先證明若是的極小點，則有為了敘述簡便，假定

在定義域內次可微，對于非次可微函數(shù)，結論依然成立.由于

是

的極小點，故對任意，有，進而有由于上式對任意

均成立，故是函數(shù)的極小點，即近端極小化方法接下來證明若則

是

的極小點.由于

極小化

，故其中，是

在處的次梯度集合.由此得到故

是

的極小點.近端極小化方法若存在極小值，那么會收斂到

的某個極小點，會收斂到

的極小值.算法10.1：近端極小化方法的計算步驟給定初始點

，

，

若滿足終止準則，則停止迭代計算

，轉至步驟2

近端極小化方法在第步迭代中，近端極小化方法需求解如下復合最優(yōu)化問題目標函數(shù)的第二項可以解釋為以上一步迭代點為中心的二次正則項，增加該項是為了避免下一個迭代點

與當前迭代點

相差太遠.隨著迭代的進行，

會越來越接近

，從而二次正則項會逐漸趨于0，故二次正則項的作用會越來越小.近端極小化方法近端極小化方法提供了一套通過在原目標函數(shù)基礎上增加二次正則項，以提高某些迭代方法的收斂性，且其最終結果不會受到正則項影響的方法框架.近端最小化方法例9.1考慮無約束最優(yōu)化問題其中

為半正定矩陣.近端最小化方法應用近端極小化方法，第步迭代公式為只要，迭代點最終會收斂到線性方程組

的解，即二次函數(shù)的極小點.注：上述迭代公式就是參數(shù)下的LM方法迭代公式.解：第10章近端方法10.1近端算子10.2近端極小化方法10.3近端梯度方法10.4加速近端梯度方法近端梯度方法？近端梯度方法是眾多梯度方法中的一種，尤其適合求解目標函數(shù)中存在不可微部分的復合最優(yōu)化問題近端梯度方法近端梯度方法常用來解決如下最優(yōu)化問題其中和都是正常閉凸函數(shù)，其中可微,

不可微.該問題的目標函數(shù)拆分成兩部分，其中一部分是可微的.由于同一個目標函數(shù)的拆分方式可能不唯一，故同一個問題可能存在近端梯度方法的多種實現(xiàn)方式.近端梯度方法近端梯度方法的第步迭代公式為在一些情況下，近端梯度方法可以退化為如下方法投影梯度方法近端極小化方法標準梯度下降方法近端梯度方法近端梯度方法每次迭代都在求解目標函數(shù)近似函數(shù)的極小點近端梯度方法當為-光滑函數(shù)，且步長，可以證明近端梯度方法收斂，其收斂速度為事實上，只要步長，方法就是收斂的.如果

未知，則可以采用線搜索確定步長.近端梯度方法當

，第5步中不等式右側函數(shù)小于等于左側函數(shù)，參數(shù)常取為0.5.算法10.2：帶線搜索的近端梯度方法的計算步驟給定初始點

，

，

，

若滿足終止準則，則停止迭代令

計算

若，則令轉至步驟4.6.

，

，，轉至步驟2.近端梯度方法

從兩個不同角度來理解近端梯度方法MM方法不動點近端梯度方法

MM是一類迭代優(yōu)化方法，利用函數(shù)凸性尋找極小點.MM本身并不是一種特定的優(yōu)化方法，而是一種構造優(yōu)化方法的框架.近端梯度方法、梯度下降方法和牛頓方法都可由MM方法推出.近端梯度方法

MM方法的基本思想找到一個目標函數(shù)的替代函數(shù)，求這個替代函數(shù)的極小點每迭代一次，根據(jù)得到的極小點構造下一次迭代的新替代函數(shù)經(jīng)過多次迭代，迭代點會越來越接近目標函數(shù)的極小點近端梯度方法近端梯度方法設極小化的目標函數(shù)為，MM方法的第步迭代公式為其中，是的替代函數(shù)，給定，該函數(shù)是凸函數(shù)，且滿足這就是MM方法整體的框架.近端梯度方法下面將MM方法用到最優(yōu)化問題中，考慮如下的