7.優(yōu)化算法及其收斂性

一、梯度下降法

梯度下降法

考慮無約束優(yōu)化問題：

$\min_{x \in \mathbb{R}^n} f(x)$

其中羽峰， $f: \mathbb{R}^n \rightarrow \mathbb{R}$ 為可微凸函數(shù)梅屉，且 $\text{dom}(f) = \mathbb{R}^n$ 鳞贷。

記：
$f^* = \inf_{x \in \mathbb{R}^n} f(x), \quad x^* = \arg\min_{x \in \mathbb{R}^n} f(x).$

梯度下降法迭代格式為：
$x_k = x_{k-1} - \alpha_k \nabla f(x_{k-1}), \quad k = 1, 2, \ldots$

其中搀愧， $\alpha_k > 0$ 為搜索步長(zhǎng)咱筛， $x_0$ 為初始迭代點(diǎn)眷蚓。

梯度下降法解釋

梯度下降法每步迭代中反番，考慮二次近似函數(shù):

$f(y) \approx Q(y) = f\left(x_{k-1}\right) - \nabla f\left(x_{k-1}\right)^T\left(y - x_{k-1}\right) + \frac{1}{2\alpha}\left\|y - x_{k-1}\right\|^2$

上式中前兩項(xiàng)可視為目標(biāo)函數(shù)的線性近似，最后一項(xiàng)則是臨近二次項(xiàng)投队。極小化以上函數(shù)可得 $x_k$ ：

$x_k = \operatorname{argmin}_y Q(y)$

函數(shù)在某點(diǎn)近似成二次函數(shù)

二敷鸦、次梯度法

可微凸函數(shù)最優(yōu)性條件：
$\nabla f(x^*)^T(x - x^*) \geq 0, \quad \forall x \in X.$
可推廣至次梯度情形扒披。
我的理解是：上面的大于等于號(hào)應(yīng)該只有在 $x$ 在 $X$ 的邊界時(shí)候取到[意思是在該點(diǎn)碟案，不管向著那個(gè)方向走颇蜡，函數(shù)值都是增加的]风秤。倘若 $x$ 在 $X$ 的內(nèi)部缤弦，上面的不等式應(yīng)該是嚴(yán)格取到等號(hào)的。

定理：凸函數(shù)極小值點(diǎn)與次梯度的關(guān)系
$x^*$ 為凸函數(shù) $f: \mathbb{R}^n \to \mathbb{R}$ 在凸集 $X \subseteq \mathbb{R}^n$ 的極小點(diǎn)的充要條件為：存在一個(gè)次梯度 $g \in \partial f(x^*)$ 滿足：
$g^T(z - x^*) \geq 0, \quad \forall z \in X.$

Theorem (投影算子非擴(kuò)張性質(zhì))
設(shè) $X$ 為非空閉凸集， $P$ 為投影算子抢韭，以下結(jié)論成立：
$\left\|P_{X}(x)-P_{X}(y)\right\|\leq\|x-y\|, \forall x, y \in \mathbb{R}^n.$

Theorem (次梯度相鄰迭代點(diǎn)距離不等式)
設(shè) $\{x_k\}$ 為次梯度方法產(chǎn)生的點(diǎn)列刻恭，有以下結(jié)論成立：
‘1. 對(duì)所有的 $y \in X$ 以及 $k \geq 0$ 鳍贾，有：
$\|x_{k+1} - y\|^2 \leq \|x_k - y\|^2 - 2\alpha_k (f(x_k) - f(y)) + \alpha_k^2 \|g_k\|^2.$

若 $f(y) < f(x_k)$ 骑科，且 $\alpha_k \in \left(0, \frac{2(f(x_k) - f(y))}{\|g_k\|^2}\right)$ 咆爽，有：
$\|x_{k+1} - y\| < \|x_k - y\|.$

證明：(1) 由投影算子非擴(kuò)張性質(zhì)置森，對(duì)所有 $y \in X$ 與 $k$ 凫海，

$\|x_{k+1} - y\|^2 = \|P_X(x_k - \alpha_k g_k) - y\|^2$

$\leq \|x_k - \alpha_k g_k - y\|^2 = \|x_k - y\|^2 - 2\alpha_k g_k^T (x_k - y) + \alpha_k^2 \|g_k\|^2$

$\leq \|x_k - y\|^2 - 2\alpha_k (f(x_k) - f(y)) + \alpha_k^2 \|g_k\|^2,$

三行贪、臨近點(diǎn)算法

Proximal算法基本原理

考慮極小化閉凸函數(shù) $f: \mathbb{R}^n \rightarrow \mathbb{R}$ 建瘫，Proximal算法迭代格式為:

$x_{k+1}=\operatorname{argmin}_{x\in \mathbb{R}^n}\left\{f(x)+\frac{1}{2 c_k}\left\|x-x_k\right\|^2\right\}$

其中： $x_k$ 為第 $k$ 步迭代點(diǎn)暖混； $c_k$ 為正則化參數(shù)(>0)拣播。(去約束收擦、去不可微性塞赂、強(qiáng)凸化)。

注意：

正則化程度主要由參數(shù) $c_k$ 控制圆存；
下一迭代點(diǎn) $x_{k+1}$ 盡可能要靠近前一個(gè)迭代點(diǎn) $x_k$ 沦辙；
二次項(xiàng) $\left\|x-x_k\right\|^2$ 使得目標(biāo)函數(shù)在一個(gè)緊水平集上極小化強(qiáng)凸函數(shù)讹剔。

容易驗(yàn)證：從非最優(yōu)點(diǎn) $x_k$ 出發(fā)延欠，目標(biāo)函數(shù)值是遞減的由捎，即：

$f\left(x_{k+1}\right)+\frac{1}{2 c_k}\left\|x_{k+1}-x_k\right\|^2\leq f\left(x_k\right)$

四、增廣拉格朗日算法

考慮約束優(yōu)化問題：

$\text{minimize} \quad f(x) \quad \text{subject to} \quad x \in X, Ax = b$

其中： $f: \mathbb{R}^n \to (-\infty, \infty]$ 是凸函數(shù)涧窒， $X$ 是凸集碌宴， $A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m$ 贰镣。

MC/MC對(duì)偶框架下碑隆，原問題與：

$p(u) = \inf_{x \in X, Ax - b = u} f(x)$

對(duì)偶問題函數(shù)為：

$q(\lambda) = \inf_{x \in X} \left\{ f(x) + \lambda^T (Ax - b) \right\}$

五上煤、ADMM算法

ADMM算法迭代格式:

關(guān)于 $x$ 極小化 $L_c(x, z, \lambda)$ :

$x_{k+1} \in \operatorname{argmin}_{x \in \mathbb{R}^n} L_c\left(x, z_k, \lambda_k\right)$
關(guān)于 $z$ 極小化 $L_c(x, z, \lambda)$ :

$z_{k+1} \in \operatorname{argmin}_{z \in \mathbb{R}^m} L_c\left(x_{k+1}, z, \lambda_k\right)$
拉格朗日乘子更新:

$\lambda_{k+1} = \lambda_k + c\left(A x_{k+1} - z_{k+1}\right)$

六劫狠、近似點(diǎn)梯度算法

鄰近算子

鄰近算子是處理非光滑問題的一個(gè)非常有效的工具独泞，也與許多算法設(shè)計(jì)密切聯(lián)系苔埋。首先介紹鄰近算子的定義组橄。

定義：（鄰近算子）對(duì)于一個(gè)凸函數(shù) $h$ ，定義它的鄰近算子為：

$\operatorname{prox}_h(x) = \operatorname{argmin}_{u \in \operatorname{dom}(h)} \left\{ h(u) + \frac{1}{2} \|u - x\|^2 \right\}$

可以看到羽资，鄰近算子的目的是求解一個(gè)距離 $x$ 不太遠(yuǎn)的點(diǎn)削罩，使得 $h(x)$ 函數(shù)值也相對(duì)較小弥激。

幾個(gè)臨近算子的例子

下面例子中均為正實(shí)數(shù)愿阐。
- $\ell_1$ 范數(shù):
  $h(x) = \|x\|_1, \quad \text{prox}_{th}(x) = \text{sign}(x) \max\{|x| - t, 0\}.$
- $\ell_2$ 范數(shù):
  $h(x) = \|x\|_2, \quad \text{prox}_{th}(x) = \begin{cases} (1 - \frac{t}{\|x\|_2})x, & \|x\|_2 \geq t \\ 0, & \text{otherwise} \end{cases}$
- 二次函數(shù):
  $h(x) = \frac{1}{2} x^T A x + b^T x + c, \quad \text{prox}_{th} = (I + tA)^{-1}(x - tb).$

近似點(diǎn)梯度算法的思想和迭代形式

近似點(diǎn)梯度法的思想非常簡(jiǎn)單：針對(duì) $f(x)$ 中的兩部分 $g$ （光滑部分）與 $h$ （非光滑部分）分別做梯度下降與鄰近算子以蕴，則近似點(diǎn)梯度算法的迭代公式為：

$x_{k+1} = \operatorname{prox}_{t_k h}\left(x_k - t_k \nabla g\left(x_k\right)\right)$

其中： $t_k > 0$ 為第 $k$ 步迭代的步長(zhǎng)丛肮，可以是常數(shù)或者用某種線性搜索方法計(jì)算得出宝与。

當(dāng) $h(x) = 0$ 時(shí)，近似點(diǎn)梯度算法變?yōu)樘荻认陆邓惴ǎ?/p>
$x_{k+1} = x_k - t_k g\left(x_k\right).$
當(dāng) $h(x) = I_C(x)$ 時(shí)咆瘟，迭代公式變?yōu)橥队疤荻确ā?/p>

七袒餐、Nesterov加速算法

通常梯度下降算法在極小化凸目標(biāo)函數(shù)的收斂率為 $\mathcal{O}(1/k)$ . Nesterov在1983提出了針對(duì)光滑目標(biāo)函數(shù)的改進(jìn)的一階算法谤狡，收斂速度能夠達(dá)到 $\mathcal{O}(1/k^2)$ . 相較于牛頓算法墓懂，Nesterov加速算法更加適合數(shù)據(jù)量大的優(yōu)化問題類型拒贱。

以梯度下降法為例，對(duì) $x_k$ 進(jìn)行一步梯度迭代得到輔助點(diǎn) $v_{k+1}$ 闸天，即：

$v_{k+1} = x_k - t_k \nabla f(x_k)$

將相鄰兩步迭代的輔助點(diǎn) $v_k$ 與 $v_{k+1}$ 加權(quán)得到下一個(gè)迭代點(diǎn) $x_{k+1}$ 苞氮。

Nesterov加速算法

迭代格式為：

$x_{k+1} = (1 - \gamma_k) v_{k+1} + \gamma_k v_k$

這里： $\lambda_0 = 0, \lambda_k = \frac{1 + \sqrt{1 + 4\lambda_{k-1}^2}}{2}, \gamma_k = \frac{1 - \lambda_k}{\lambda_{k+1}}$ 笼吟。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末贷帮，一起剝皮案震驚了整個(gè)濱河市撵枢，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌潜必，老刑警劉巖磁滚，帶你破解...
沈念sama閱讀 217,542評(píng)論 6贊 504
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件垂攘，死亡現(xiàn)場(chǎng)離奇詭異坝疼，居然都是意外死亡钝凶，警方通過查閱死者的電腦和手機(jī)唁影，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,822評(píng)論 3贊 394
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門据沈，熙熙樓的掌柜王于貴愁眉苦臉地迎上來锌介，“玉大人，你說我怎么就攤上這事隆敢》餍” “怎么了惶室？”我有些...
開封第一講書人閱讀 163,912評(píng)論 0贊 354
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵皇钞，是天一觀的道長(zhǎng)夹界。經(jīng)常有香客問我，道長(zhǎng)也拜，這世上最難降的妖魔是什么慢哈？我笑而不...
開封第一講書人閱讀 58,449評(píng)論 1贊 293
?港島之戀（遺憾婚禮）
正文為了忘掉前任卵贱，我火速辦了婚禮，結(jié)果婚禮上兰绣，老公的妹妹穿的比我還像新娘编振。我一直安慰自己踪央，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 67,500評(píng)論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著液斜，像睡著了一般少漆。火紅的嫁衣襯著肌膚如雪检疫。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 51,370評(píng)論 1贊 302
城市分裂傳說
那天夺溢，我揣著相機(jī)與錄音，去河邊找鬼烛谊。笑死风响，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的丹禀。我是一名探鬼主播状勤，決...
沈念sama閱讀 40,193評(píng)論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼鞋怀，長(zhǎng)吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來了持搜？” 一聲冷哼從身側(cè)響起密似，我...
開封第一講書人閱讀 39,074評(píng)論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤葫盼，失蹤者是張志新（化名）和其女友劉穎残腌，沒想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體贫导，經(jīng)...
沈念sama閱讀 45,505評(píng)論 1贊 314
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡抛猫，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,722評(píng)論 3贊 335
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了孩灯。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片闺金。...
茶點(diǎn)故事閱讀 39,841評(píng)論 1贊 348
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖峰档，靈堂內(nèi)的尸體忽然破棺而出败匹，到底是詐尸還是另有隱情，我是刑警寧澤面哥，帶...
沈念sama閱讀 35,569評(píng)論 5贊 345
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布哎壳，位于F島的核電站毅待，受9級(jí)特大地震影響尚卫，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜尸红，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,168評(píng)論 3贊 328
男人毒藥：我在死后第九天來索命
文/蒙蒙一吱涉、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧外里，春花似錦怎爵、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,783評(píng)論 0贊 22
一樁弒父案鳖链，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至墩莫，卻和暖如春芙委，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背狂秦。一陣腳步聲響...
開封第一講書人閱讀 32,918評(píng)論 1贊 269
情欲美人皮
我被黑心中介騙來泰國(guó)打工灌侣，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人裂问。一個(gè)月前我還...
沈念sama閱讀 47,962評(píng)論 2贊 370
代替公主和親
正文我出身青樓侧啼，卻偏偏與公主長(zhǎng)得像牛柒，于是被迫代替她去往敵國(guó)和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子痊乾，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,781評(píng)論 2贊 354