非凸優化基石：Lipschitz Condition

之所以需要寫一下這個，一是因為這個Conditon 確實特別重要，二是我以後寫的東西需要利用到這個Condtion推島出的一些Thereom, 所以需要先鋪墊一些基礎知識。

如果有啥沒說對的地方，歡迎批評指。能力有限，也就拼拼湊湊一些簡單的東西了，大牛見笑了。

本章分三部分：

Part I : Definition of Lipschitz Continuous

Part II: 直觀解釋

Prat III: 證明

%------------------------正文開始----------------------------------------------------------

Part I : Definition of Lipschitz Continuous

今天就分享一個定義： Lipschitz continuous

在絕大多數的非凸優化的論文里，一般不出現Lipschitz continuous, 一般出現的都是 Lipschitz continuous gradient 或者 Lipschitz continuous Hessian, 那他們是什麼意思呢？

其實Lipschitz continuous gradient 和 Lipschitz continuous Hessian 都是從Lipschitz continuous 延伸出來的概念。

如果函數的導函數是Lipschitz continuous，那麼我們說函數符合Lipschitz continuous gradient ；如果函數的Hessien是Lipschitz continuous，那麼我們說函數符合Lipschitz continuous Hessian.

所以 Lipschitz continuous gradient意味著：

而 Lipschitz continuous Hessian意味著：

你可以一直往上構造，構造出更高階的 Lipschitz continuous condition.

Part II: 直觀解釋

先上結論：

Lipschitz continuous： 函數被一次函數上下夾逼

Lipschitz continuous gradient ：函數被二次函數上下夾逼

Lipschitz continuous Hessian ：函數被三次函數上下夾逼

在我看來，Lipschitz continuous 用在函數值上是為了不讓函數值變化的太快；用在導函數上，是為了不讓導函數變化的太快；用在Hessian上，是為了讓Hessian不變化的太快。但他們都導致了一個很有意思的結果：這個Lipschitz continuous不管用在什麼上，都使的函數被多項式上下夾逼，一方面便於我們處理，另一方面至少我們能控制一下函數的包絡信息。

如圖所示（示意圖，可能不是很嚴謹，見諒）：

解釋：

（1）首先我們看看如果函數符合Lipschitz continuous會怎麼樣呢？我們看Defintion 1, 直接把絕對值去掉，就可以得到下面兩個不等式。

說明如果函數是是Lipschitz continuous，固定,對於這個關於的函數，那麼這個函數的上方和下方是被一個一次函數Bounded！

為了對Lipschitz continuous gradient 和 Lipschitz continuous Hessian 做出合理的直觀解釋，我得先拋出兩個特別重要的Theorem（證明在Part III 有興趣的人看看就好）

（2）如果函數是Lipschitz continuous gradient，那麼下面這個Theorem 1 成立

去掉絕對值，你會得到下面兩個不等式

說明如果函數是是Lipschitz continuous gradient，固定,對於這個關於的函數，那麼這個函數的上方和下方是被一個二次函數Bounded！

（3） 如果函數是Lipschitz continuous Hessian，那麼下面這個Theorem 2 成立

去掉絕對值，你會得到下面兩個不等式

說明如果函數是是Lipschitz continuous Hessian，固定,對於這個關於的函數，那麼這個函數的上方和下方是被一個三次函數Bounded！

在回頭看看我貼的圖，是不是順眼多了~~

%--------------------------------------------止步於此即可------------------------------------------------

如果能記住Lipschitz condition ,Theorem 1 和 Theorem 2 的公式，再在直觀上有一些些了解，那麼花這點時間看這文章就值了，如果沒記住，那麼請返回去背一下，畢竟記住點什麼才算是真的學到了點什麼。

如果認為看Proof是最好的理解和記憶方式，請勇敢的翻下去~~

%-----------------------------------------------------------------------------------------------------------------------

Part III： Proof of Theorem 1 and Theorem 2

(1) Proof of Theorem 1 （證明來自Nesterov <Introductory Lectures on Convex Programming>截圖過來的）

1> 等式（1）中第三項，梯度向量與向量內積之後是一個數，是一個關於的一元函數，整個積分是一個一元積分,不要被符號嚇到了

2> 不等式（2）用了Cauthy-Schwar inequality:

（2） Proof of Theorem 2 （證明來自Nesterov <Cubic Regularization of Newton and its Global Performance>）

1> 等式（2）中，向量與向量內積之後是一個數，是一個關於的一元函數，整個積分是一個一元積分,不要被符號嚇到了。

2>不等式（3）是用Cauthy-Schwar inequality: 之後，再套用不等式（1）得到的結果。

%-------------------------------------------------------------------------------------------------------

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

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

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

推薦閱讀：