從Nesterov的角度看：我們為什麼要研究凸優化？

01-26

Contribution: 本文唯一的貢獻是用自己的話翻譯了Nesterov的文章《Introductory Lectures on Convex Programming》中關於凸函數是如何被定義出來的段落。

你可能不認識 Nesterov, 但是你一定用過 Nesterov 的演算法「Nesterovs Accelerated Gradient Dsecent」 (AGD).

正文開始：

以往學習凸優化，介紹凸函數的時候，教科書都會直接拋出下面凸函數的定義

$f(y) geqslant f(x ) + langle f^{prime}(x ), y - x angle$ (1)

而當我看Nesterov介紹凸函數的時候，便被他所展現的思維方式所驚艷，一個先從我們想研究什麼函數集的性質開始，一步一步推算出公式（1）的過程。

Part I: 我們想研究什麼樣的函數集？

對於 First Order Method, Gradient Descent(GD)。我們知道 GD 只能保證找到一個 First Order Stationary Point 就是

$qquad f^{prime}(x_T) = 0$

但是找到的這個點 $x_T$ 是不是函數 $f$ 的最小值點我們就不得而知了。因為導函數為0的點，可以是Saddle Point, Local Minima, Local Maxima。

所以我們想研究這樣一類的函數 $mathcal{F}$ ，我們希望First Order Method 能幫我們找到最小值, 那麼第一個Assumption 就是
也就是說如果 $f^{prime}(x_T) = 0$ ，那麼 $forall x, f(x) geqslant f(x_T)$ .
其次我們希望所有的線性函數在我們的集合 $mathcal{F}$ 里，所以有了第二條Assumption
再次我們希望集合 $mathcal{F}$ 的函數的conical combination，依然在集合 $mathcal{F}$ 里，所以我們的第三條Assumption是

現在我們看看在 Assumption 1， Assumption 2，Assumption 3的情況下，我們能得到什麼呢？

如果 $f in mathcal{F}$ , 固定點 $x_0 in R^n$ , 我們構造函數 $phi$

$phi(y) = f(y) - langle f^{prime}(x_0), y angle$

那麼 $phi in mathcal{F}$ , 因為 $phi$ 可以看成 $phi(y) = f(y) + igg{ - langle f^{prime}(x_0), y angleigg}$ , 而且 $f in mathcal{F}$ ，線性函數 $igg{ - langle f^{prime}(x_0), y angleigg} in mathcal{F}$ ,所以這兩個函數相加由Assumption 3，可得 $phi$ 依然在我們的函數集 $mathcal{F}$ 里。

而且對 $phi$ 求導可得

$phi^{prime}(y) = f^{prime}(y) - f^{prime}(x_0)$

所以

$phi^{prime}(y) |_{y = x_0} = f^{prime}(y)|_{y = x_0} - f^{prime}(x_0) = 0$

聯繫 $phi in mathcal{F}$ 和 Assumption 1, 我們知道 $x_0$ 是全局最小值點，所以對於任意 $y in R^n$ , 我們有

$phi(y) geqslant phi(x_0) = f(x_0) - langle f^{prime}(x_0), x_0 angle$

由定義我們知道 $phi(y) = f(y) - langle f^{prime}(x_0), y angle$ 代入上式可得

$f(y) - langle f^{prime}(x_0), y angle geqslant f(x_0) - langle f^{prime}(x_0), x_0 angle$

換一下位置即可得到

$f(y) geqslant f(x_0) + langle f^{prime}(x_0), y - x_0 angle$

由於 $x_0$ 是任意的，所以這個式子對任意 $x$ 都成立，所以

$f(y) geqslant f(x ) + langle f^{prime}(x ), y - x angle$ （1）

是不是看起來特別熟悉？這就是廣為人知的凸函數的定義了。我們通過想研究的函數集的三個性質推導出了函數集 $mathcal{F}$ 的函數一定滿足公式（1）。

Part II: 通過凸函數公式（1）我們能否推導出 Assumption 1， Assumption 2，Assumption 3？如果可以，我就可以說我們希望研究的函數集合 $mathcal{F}$ 是等價於凸函數集合的！！

$mathcal{F} Leftrightarrow { ext{Convex Function Set}}$

1> 公式（1） $Rightarrow$ Assumption 1

如果 $f^{prime}(x^*) = 0$ , 由公式（1），我們知道，對於任意 $y$ 我們有 $f(y) geqslant f(x^* ) + langle f^{prime}(x^* ), y - x_0 angle = f(x^*)$

這樣就證明了導函數為0的點 $x^*$ 都是全局最小值。便證明滿足公式（1）的函數集合一定符合Assumption 1。

2> 公式（1） $Rightarrow$ Assumption 2

我們只需要證明線性函數是凸函數即可，任意線性函數都是如下形式

$f(x) = langle a, x angle + b$

所以 $f^{prime}(x) = a$ , 對於任意 $y$ , $f(y) = langle a, y angle + b$ , 所以

$f(y) - f(x) = langle a, y-x angle$

我們直接可以得到 $f(y) geqslant f(x)+langle a, y-x angle$ ，便證明滿足公式（1）的函數集合一定符合Assumption 2。

3> 公式（1） $Rightarrow$ Assumption 3

假設存在函數 $f_1(x)$ , $f_2(x)$ 都滿足公式（1），那麼我們有

$f_1(y) geqslant f_1(x ) + langle f_1^{prime}(x ), y - x_0 angle$ , $f_2(y) geqslant f_2(x ) + langle f_2^{prime}(x ), y - x_0 angle$

第一個不等式乘以 $alpha$ ，第二個不等式乘以 $eta$ ，相加可得

$alpha f_1(y) + eta f_2(y)geqslant alpha f_1(x ) + eta f_2(x) + langle alpha f_1^{prime}(x ), y - x angle + langle eta f_2^{prime}(x ), y - x angle$

化簡一下

$alpha f_1(y) + eta f_2(y)geqslant alpha f_1(x ) + eta f_2(x) + langle alpha f_1^{prime}(x ) + eta f_2^{prime}(x ), y - x angle$

我們就證明了凸函數的加權相加依然是凸函數也就是滿足公式（1）的函數集合一定符合Assumption 3。

所以結論就是，當我們考慮凸函數這個函數的時候，其實就是在考慮滿足Assumption 1， Assumption 2，Assumption 3的函數，所以以後不要看到凸函數就想到

$f(y) geqslant f(x ) + langle f^{prime}(x ), y - x angle$

還要想到，嗯，凸函數集合嘛，等價於這個函數滿足三個假設

（1）導函數0的點是全局最小值點

（2）線性函數是凸函數

（3 ) 凸函數的conical combination，依然是凸函數

不得不膜拜一下Nesterov，這樣想都行！！

--------------------------------------------------------------------------------------------------------------------------

謝謝你看到最後，但願這些對你有幫助，有啟發的話，點個讚唄，只收藏不點贊鼓勵一下，人家都沒有寫下去的熱情了。

以後想一起學習凸優化，非凸優化的可以關注我和專欄啦，我會寫一些我看到的有意思的觀點和思路的，哈哈！

歡迎隨意轉載分享，Idea worth spreading!