Strong convexity and implications
在討論無(wú)約束凸優(yōu)化問(wèn)題(1)的時(shí)候，我們會(huì)假設(shè)
是一個(gè)凸二次可微的函數(shù)祭犯⊙筘ぃ考慮一個(gè)起始點(diǎn)
薄疚，記%20%5Cleq%20f(x%5E%7B(0)%7D)%5Cright%5C%7D%5Ctag%7B0%7D)
顯然
是一個(gè)閉集。此外麻蹋，我們?cè)O(shè)%3Df(x%5E*))
為最優(yōu)值跛溉。
有時(shí)候焊切，我們還會(huì)給目標(biāo)函數(shù)加上兩個(gè)更強(qiáng)的條件扮授。
簡(jiǎn)而言之，在閉集上专肪，
的Heisen矩陣的特征值有下確界
刹勃。如果這個(gè)條件被滿足，由Taylor展開(kāi)：%3Df(x)%2B%5Cnabla%20f(x)%5E%7BT%7D(y-x)%2B%5Cfrac%7B1%7D%7B2%7D(y-x)%5E%7BT%7D%20%5Cnabla%5E%7B2%7D%20f(z)(y-x)%20%5Ctag%7B1%7D)
其中
是線段![[x,y]](https://math.jianshu.com/math?formula=%5Bx%2Cy%5D)
上的一點(diǎn)嚎尤。
繼而荔仁，我們有：
%20%5Cgeq%20f(x)%2B%5Cnabla%20f(x)%5E%7BT%7D(y-x)%2B%5Cfrac%7Bm%7D%7B2%7D%5C%7Cy-x%5C%7C_%7B2%7D%5E%7B2%7D%5Ctag%7B2%7D)
這給出了函數(shù)的一個(gè)更好的下界。
另一個(gè)條件芽死，在閉集上乏梁，的Heisen矩陣的特征值有上確界
（因?yàn)殚]集，保證了上確界存在）关贵。通過(guò)式(1)遇骑，我們可以得到類(lèi)似式(2)的結(jié)論：%20%5Cleq%20f(x)%2B%5Cnabla%20f(x)%5E%7BT%7D(y-x)%2B%5Cfrac%7BM%7D%7B2%7D%5C%7Cy-x%5C%7C_%7B2%7D%5E%7B2%7D%5Ctag%7B3%7D)
這其實(shí)就給出了函數(shù)的一個(gè)上界。
綜合這兩個(gè)條件：%20%5Cpreceq%20M%20I%20%5Cquad%20%2C%5Cforall%20x%20%5Cin%20S%20%5Ctag%7B4%7D)
接下來(lái)我們來(lái)推導(dǎo)揖曾，加上這兩個(gè)條件落萎，有什么用。
注意到(2)式的右邊是一個(gè)關(guān)于
的凸函數(shù)炭剪，在
時(shí)最小练链，從而：
上式說(shuō)明，當(dāng)
模長(zhǎng)很小很小的時(shí)候奴拦，)
跟最優(yōu)值
的距離也很小很小媒鼓。雖然這個(gè)結(jié)論看起來(lái)很顯然，但是我們從數(shù)學(xué)的角度證明了它错妖！%5C%7C_%7B2%7D%20%5Cleq(2%20m%20%5Cepsilon)%5E%7B1%20%2F%202%7D%20%5CLongrightarrow%20f(x)-p%5E%7B%5Cstar%7D%20%5Cleq%20%5Cepsilon%5Ctag%7B5%7D)
利用(5)式隶糕，我們可以通過(guò)梯度的模長(zhǎng)，來(lái)控制與最優(yōu)解之間的距離站玄。
類(lèi)似的推導(dǎo)能得到更強(qiáng)的結(jié)論：
對(duì)于第二種情況：
%20%5Cpreceq%20M%20I%20%5CRightarrow%20p%5E%7B%5Cstar%7D%20%5Cleq%20f(x)-%5Cfrac%7B1%7D%7B2%20M%7D%5C%7C%5Cnabla%20f(x)%5C%7C_%7B2%7D%5E%7B2%7D%5Ctag%7B6%7D)
總結(jié)一下枚驻，在一個(gè)閉集上，理想情況下株旷，凸函數(shù)的Heisen矩陣的特征值是“可控的”再登，我們從數(shù)學(xué)上推導(dǎo)出當(dāng)某處的梯度模長(zhǎng)很接近0的時(shí)候尔邓，其實(shí)離最優(yōu)解和最優(yōu)值不遠(yuǎn)了，這個(gè)“接近”的程度可以由估計(jì)式給出锉矢。盡管大部分時(shí)候我們沒(méi)有辦法確定
和梯嗽，但是只要梯度足夠小，還是可以保證非常接近最優(yōu)解的沽损。
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
