投影梯度下降（Projected gradient descent）

對于上面有條件的優(yōu)化問題憾赁，可以采用這樣的的一種思路：

采用梯度下降的思路，更新 $x^t$ 蜕乡，再將這樣的更新值向定義域C 作投影空民，以此來獲得該優(yōu)化問題在一定條件下的優(yōu)化。

$投影定理：\\ 假設空間集合C是封閉的凸集合酪呻，那么當且僅當：\\ (x-x_C)^T(z-x_C) \leq0, \quad \forall z \in C \\ 那么x_C是x在集合C上的投影該式子可以進一步拓展：\\ 將x換成x^t-\eta^t▽f(x^t), z換成x^*\\ 那么我們有：\\ (x^t-x_c-\eta^t▽f(x^t))(x^*-x_c)\leq 0 \\ \implies (g_c(x^t)-▽f(x^t))(x^*-x_c) \leq0\\ \implies ▽f(x^t)^T(x_c-x^*) \leq g_c(x^t)(x_c-x^*) \\ 其中减宣，g_c(x)=L(x-x^*), \eta^t= \frac{1}{L}$

梯度方向

$-▽f(x^t)^T(x^{t+1}-x^t) \geq 0$

$x^{t+1}-x^t和最速梯度下降方向是正相關。$

投影的非拓展性

$\forall x,z \quad ||P_C(x)-P_C(z)|_2 \leq ||x-z||_2 總是成立的$

收斂性

$對于無約束條件的優(yōu)化問題玩荠，我們知道：\\ ||x^{t}-x^||_2 \leq( \frac{K-1}{K+1})||x^t-x^||_2$

投影梯度下降的收斂性：

$||x^{t+1}-x^*||_2=||P_C(x^t-\eta^t▽f(x^t))-x^*||_2\\ \leq||x^t-\eta^t▽f(x^t)-x^*||_2 \leq (\frac{K-1}{K+1})||x^t-x^*||_2 \\ 部分證明在梯度下降中漆腌，此處些許省略。$

對于u-strongly convex 和 L-smooth 的函數f(x)

如果步長 $\eta^t$ 取為 $\frac{1}{L}$ 阶冈，那么我們有這樣的式子：

$||x^t-x^*||_2^2 \leq (1- \frac{\mu}{L})^t||x^0-x^*||_2^2$

$下面證明：\\ x^+:=P_C(x-\frac{1}{L}▽f(x))闷尿，g_C(x):=L(x-x^+) \quad 在上面已經證明了：\\ ▽f(x)^T(x+-x^*) \leq g_C(x)^T(x^+-x^*),以下證明將用到該式。\\ 證明：\\ 0 \leq f(x^+)-f(x^*)=f(x^+)-f(x)+f(x)-f(x^*)\\ \implies 0 \leq ▽f(x)^T(x^+-x)+ \frac{L}{2}||x^+-x||^2_2+▽f(x)^T(x-x^*)- \frac{\mu}{2}||x-x^*||^2_2 (前面是L-smooth性質女坑，后面是u-convex性質)\\ \implies 0 \leq ▽f(x)^T(x^+-x^*)+ \frac{1}{2L}||g_C(x)||^2_2+▽f(x)^T(x-x^*)- \frac{\mu}{2}||x-x^*||^2_2\quad \\ 由于： ▽f(x)^T(x^+-x^*) \leq g_C(x)^T(x^+-x^*)=g_C(x)^T(x-x^*)- \frac{1}{L}||x-x^*||^2_2 \\ \implies 0 \leq L(x-x^+)(x-x^*)- \frac{1}{L}||g_C(x)||^2_2+ \frac{1}{2L}||g_C(x)||_2^2- \frac{\mu}{2}||x-x^*||^2_2 \\ \implies 0 \leq L(x-x^+)(x-x^*)- \frac{1}{2L}||L(x-x^*-(x^+-x^*))||^2_2- \frac{\mu}{2}||x-x^*||^2_2 \\ 展開合并最后可以得到：\\ (L-u)||x-x^*||_2^2 \geq L||x^+-x^*||_2^2\\ \implies ||x^+-x^*||_2^2 \leq (1- \frac{\mu}{L})||x-x^*||_2^2 \\ 直接循環(huán)推導填具，可以得到最后的收斂式子$

總結

對于投影梯度遞降法來說：

1）如果處理的是一個convex&smooth 問題，那們一般設置步長是 $\eta^t=\eta \equiv \frac{1}{L}$

收斂速率是 $O(\frac{1}{t})$ 匆骗，循環(huán)的復雜度是 $O(\frac{1}{\varepsilon})劳景，其中\(zhòng)varepsilon 為誤差精度要求$

2）對于strongly-convex&smooth 問題誉简，其步長依舊是 $\eta^t=\eta \equiv \frac{1}{L}$ ，收斂速率是 $O((1- \frac{1}{K})^t)$ 盟广，循環(huán)復雜度是 $O(K*log \frac{1}{\varepsilon})闷串，其中K為條件數$

?著作權歸作者所有,轉載或內容合作請聯系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個濱河市衡蚂，隨后出現的幾起案子窿克，更是在濱河造成了極大的恐慌，老刑警劉巖毛甲，帶你破解...
沈念sama閱讀 211,042評論 6贊 490
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件年叮，死亡現場離奇詭異，居然都是意外死亡玻募，警方通過查閱死者的電腦和手機只损，發(fā)現死者居然都...
沈念sama閱讀 89,996評論 2贊 384
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來七咧，“玉大人跃惫，你說我怎么就攤上這事“埃” “怎么了爆存？”我有些...
開封第一講書人閱讀 156,674評論 0贊 345
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長蝗砾。經常有香客問我先较，道長，這世上最難降的妖魔是什么悼粮？我笑而不...
開封第一講書人閱讀 56,340評論 1贊 283
?港島之戀（遺憾婚禮）
正文為了忘掉前任闲勺，我火速辦了婚禮，結果婚禮上扣猫，老公的妹妹穿的比我還像新娘菜循。我一直安慰自己，他們只是感情好申尤，可當我...
茶點故事閱讀 65,404評論 5贊 384
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布癌幕。她就那樣靜靜地躺著，像睡著了一般昧穿。火紅的嫁衣襯著肌膚如雪序芦。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 49,749評論 1贊 289
城市分裂傳說
那天粤咪，我揣著相機與錄音谚中，去河邊找鬼。笑死，一個胖子當著我的面吹牛宪塔，可吹牛的內容都是我干的磁奖。我是一名探鬼主播，決...
沈念sama閱讀 38,902評論 3贊 405
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼某筐，長吁一口氣：“原來是場噩夢啊……” “哼比搭！你這毒婦竟也來了？” 一聲冷哼從身側響起南誊，我...
開封第一講書人閱讀 37,662評論 0贊 266
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤身诺，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后抄囚，有當地人在樹林里發(fā)現了一具尸體霉赡，經...
沈念sama閱讀 44,110評論 1贊 303
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內容為張勛視角年9月15日...
茶點故事閱讀 36,451評論 2贊 325
?白月光啟示錄
正文我和宋清朗相戀三年幔托，在試婚紗的時候發(fā)現自己被綠了穴亏。大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點故事閱讀 38,577評論 1贊 340
活死人
序言：一個原本活蹦亂跳的男人離奇死亡重挑，死狀恐怖嗓化，靈堂內的尸體忽然破棺而出，到底是詐尸還是另有隱情谬哀，我是刑警寧澤刺覆，帶...
沈念sama閱讀 34,258評論 4贊 328
?日本核電站爆炸內幕
正文年R本政府宣布，位于F島的核電站史煎，受9級特大地震影響隅津，放射性物質發(fā)生泄漏。R本人自食惡果不足惜劲室，卻給世界環(huán)境...
茶點故事閱讀 39,848評論 3贊 312
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望结窘。院中可真熱鬧很洋，春花似錦、人聲如沸隧枫。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,726評論 0贊 21
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽官脓。三九已至协怒，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間卑笨，已是汗流浹背孕暇。一陣腳步聲響...
開封第一講書人閱讀 31,952評論 1贊 264
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留，地道東北人妖滔。一個月前我還...
沈念sama閱讀 46,271評論 2贊 360
代替公主和親
正文我出身青樓隧哮，卻偏偏與公主長得像，于是被迫代替她去往敵國和親座舍。傳聞我的和親對象是個殘疾皇子沮翔，可洞房花燭夜當晚...
茶點故事閱讀 43,452評論 2贊 348

投影梯度下降（Projected gradient descent）

梯度方向

投影的非拓展性

收斂性

總結

推薦閱讀更多精彩內容