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

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

Method

in

Data

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

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

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

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

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

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

二次罰函數(shù)方法

由

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

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

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

的增大，

的極小點(diǎn)會(huì)趨于原問題的最優(yōu)解

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

，

，

.以

為初始點(diǎn)，極小化

，當(dāng)

，則停止迭代，得近似極小點(diǎn)

.若

，則停止迭代，得近似解

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

.

，

，轉(zhuǎn)至步驟2.

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

warm-start).

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

快速增

加，例如.

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

都是二次罰函數(shù)

的全局極小點(diǎn)，且

，則迭代序列

的任何極限點(diǎn)

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

的，有因?yàn)?/p>

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

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

，對(duì)

的任何極限點(diǎn)

，線性無關(guān)，則

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

其中

是

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

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

的終止準(zhǔn)則，有利用三角不等式，整理上式有對(duì)上式兩邊取極限，令，由于，可得因?yàn)榫€性無關(guān)，故

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

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

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

一定要滿足

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

的增大，Hesse矩陣

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

，有若

充分接近

的極小點(diǎn)且定理9.2的條件滿足，則有矩陣

的秩為

，這里假設(shè)

.當(dāng)

時(shí)，

的特征值有

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

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

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

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

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

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

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

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

當(dāng)

在可行域內(nèi)遠(yuǎn)離可行域邊界時(shí)，障礙項(xiàng)數(shù)值較小；當(dāng)

從可行域內(nèi)部接近可行域邊界時(shí)，至少某個(gè)約束接近于起作用，此時(shí)障礙項(xiàng)會(huì)無限增大，以防止迭代點(diǎn)躍出可行域.

障礙函數(shù)方法當(dāng)

在可行域內(nèi)遠(yuǎn)離可行域邊界時(shí)，障礙項(xiàng)數(shù)值較??；當(dāng)

從可行域內(nèi)部接近可行域邊界時(shí)，至少某個(gè)約束接近于起作用，此時(shí)障礙項(xiàng)會(huì)無限增大，以防止迭代點(diǎn)躍出可行域.

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

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

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

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

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

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

解：障礙函數(shù)方法障礙函數(shù)方法算法9.2：障礙函數(shù)方法的計(jì)算步驟給定初始內(nèi)點(diǎn)滿足

以

為初始點(diǎn)，極小化

，當(dāng)

，則停止迭代，得近似極小點(diǎn)

若滿足收斂準(zhǔn)則，則停止迭代，得近似解

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

，，轉(zhuǎn)至步驟2.

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

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

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

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

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

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

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

，使得

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

，當(dāng)，對(duì)應(yīng)的Lagrange乘子估計(jì)收斂到，其中

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

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

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

那么如何構(gò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ù)的思想由于我們想要構(gòu)造的函數(shù)是無約束最優(yōu)化問題的目標(biāo)函數(shù)，因此可以根據(jù)無約束最優(yōu)化問題的最優(yōu)性條件去構(gòu)造這樣的函數(shù).在這里考慮等式約束最優(yōu)化問題增廣Lagrange函數(shù)的思想設(shè)想要構(gòu)造的函數(shù)為，其中是給定的參數(shù)。我們希望求解無約束優(yōu)化問題：，得到原問題的最優(yōu)解.在處，應(yīng)滿足如下條件一階充分條件

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

處條件

自然滿足.一般情況下，在點(diǎn)

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

附近，沿線性化可行方向

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

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

附近，沿線性化可行方向

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

均滿足條件.為了實(shí)現(xiàn)這一目標(biāo)，當(dāng)變量不滿足約束時(shí)，加大的函數(shù)值，而這正是構(gòu)造罰函數(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ù)可以視為在標(biāo)準(zhǔn)的Lagrange函數(shù)基礎(chǔ)上增加了二次罰函數(shù)，故又稱為乘子罰函數(shù).

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

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

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

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

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

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

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

以

為初始點(diǎn)，極小化

，當(dāng)

時(shí)停止，得近似極小點(diǎn)

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

；否則，更新

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

4.

，轉(zhuǎn)至步驟2.

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

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

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

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

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

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

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

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

，設(shè)其充分接近

，則有由于

和

的可行性，可知?jiǎng)t對(duì)與

充分接近的可行點(diǎn)

，有從而，

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

由

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

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

閾值

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

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

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

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

Method

in

Data

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

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

為閉函數(shù).定義

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

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

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

不同點(diǎn)上的近端算子定義是

極小點(diǎn)和附近點(diǎn)的一個(gè)折中

有時(shí)被稱為點(diǎn)關(guān)于

的近端點(diǎn).在

中，參數(shù)是這兩項(xiàng)間的相對(duì)權(quán)重.近端算子10.1.1定義10.1.2解釋10.1.3性質(zhì)解釋

廣義投影次微分算子的分解負(fù)梯度步廣義投影

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

可將近端算子視為一個(gè)廣義投影

廣義投影

可將近端算子視為一個(gè)廣義投影

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

在點(diǎn)

處的次梯度集合記為,稱

為

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

在點(diǎn)

處可微，則，由此稱為從

到的梯度映射.梯度映射為點(diǎn)到點(diǎn)的映射.次微分算子的分解次微分算子

將每個(gè)點(diǎn)映射為一個(gè)集合.不難證明，次梯度集合

是一個(gè)閉凸集.次微分算子的分解定義10.3.次可微若在點(diǎn)處有次梯度，則稱在點(diǎn)處次可微.進(jìn)一步，若在定義域內(nèi)任意點(diǎn)處都有次梯度，則稱

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

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

因?yàn)橛形ㄒ恢?，所以也有唯一值，從而等式成?負(fù)梯度步

函數(shù)

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

或與

相關(guān)的某個(gè)函數(shù)的負(fù)梯度步，以下從三個(gè)不同角度進(jìn)行討論Moreau包絡(luò)近似梯度步函數(shù)近似的近端算子Moreau包絡(luò)

定義10.4Moreau包絡(luò)對(duì)于函數(shù)

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

Moreau包絡(luò)

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

和

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

會(huì)更加容易.Moreau包絡(luò)

函數(shù)

的近端算子

函數(shù)

的Moreau包絡(luò)Moreau包絡(luò)

Moreau包絡(luò)

可以視為極小化（與

的極小點(diǎn)相同）的一個(gè)步長(zhǎng)為

的負(fù)梯度步.近似梯度步

若

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

的負(fù)梯度步，其步長(zhǎng)為.對(duì)于較小的

，近端算子可以近似認(rèn)為是極小化

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

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

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

一階近似的近端算子為這就是一個(gè)標(biāo)準(zhǔn)的步長(zhǎng)為的負(fù)梯度步.負(fù)梯度步可以視為函數(shù)一階近似的近端算子.考慮函數(shù)近似的近端算子，及它們和極小化的負(fù)梯度步之間的關(guān)系函數(shù)近似的近端算子

二階連續(xù)可微

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

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

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

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

，則有若

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

的極小點(diǎn)當(dāng)且僅當(dāng)即

是

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

在定義域內(nèi)次可微，對(duì)于非次可微函數(shù)，結(jié)論依然成立.由于

是

的極小點(diǎn)，故對(duì)任意，有，進(jìn)而有由于上式對(duì)任意

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

是

的極小點(diǎn).由于

極小化

，故其中，是

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

是

的極小點(diǎn).近端極小化方法若存在極小值，那么會(huì)收斂到

的某個(gè)極小點(diǎn)，會(huì)收斂到

的極小值.算法10.1：近端極小化方法的計(jì)算步驟給定初始點(diǎn)

，

，

若滿足終止準(zhǔn)則，則停止迭代計(jì)算

，轉(zhuǎn)至步驟2

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

與當(dāng)前迭代點(diǎn)

相差太遠(yuǎn).隨著迭代的進(jìn)行，

會(huì)越來越接近

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

為半正定矩陣.近端最小化方法應(yīng)用近端極小化方法，第步迭代公式為只要，迭代點(diǎn)最終會(huì)收斂到線性方程組

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

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

未知，則可以采用線搜索確定步長(zhǎng).近端梯度方法當(dāng)

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

，

，

，

若滿足終止準(zhǔn)則，則停止迭代令

計(jì)算

若，則令轉(zhuǎn)至步驟4.6.

，

，，轉(zhuǎn)至步驟2.近端梯度方法

從兩個(gè)不同角度來理解近端梯度方法MM方法不動(dòng)點(diǎn)近端梯度方法

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

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