凸優化筆記(1)Why凸優化以及幾個基本概念

本文主要參考卡耐基梅隆大學(CMU)的Dr. Ryan Tibshirani教授2017年在Convex Optimization(Course 10-725/36-725)課上(課程網站鏈接：Convex Optimization)的Lecture Notes。以及參考了現任職牛津大學的Dr. Paul Goulart，以前在ETH任教時Convex Optimization課的Lecture Notes。如有錯誤疏漏，煩請指出。如需轉載，請聯繫筆者，zhu.hathaway@gmail.com。

在統計學和機器學習領域，基本上你想做的絕大部分事情都是一種優化問題。所以，面對具體應用的問題，你要做的事情可以概括為如下圖所示：

所以，學習Optimization，就是學習

1. 如何把具體問題寫成或者formulate成為一個優化問題
2. 現有演算法是如何具體解算上圖中的問題P
3. 面對不同的具體問題如何選擇已有演算法或者甚至設計發明適合的演算法去解決

絕大部分情況下，你只需要做上述的第1個，就是把問題轉換成凸優化問題，並寫成標準形式，剩下就交給計算機去解算(利用已有的一些優化工具箱)。第2個和第3個是做研究的人通常要做的事情。

Optimization問題是十分前沿的問題，現有演算法還有很大的優化提升空間，而且還有很多問題沒有得到很好解決，尤其是在Statistics與Machine Learning領域。

Convexity：歷史上，優化問題通常聚焦在linear programming(線性規劃)。最初人們認為，優化問題是線性還是非線性，是不同的優化問題的根本區別(linear programming的歷史請參照華盛頓大學數學系的talks notes: Fast Times in Linear Programming: Early Success, Revolutions, and Mysteries--by Dr. Margaret Wright[牆裂推薦讀完])：

而現在人們認為，優化問題是凸還是非凸才是不同的優化問題之間的根本區別。因為有些問題，雖然是非線性，但是好解（因為是凸的），而有些非線性問題，卻非常難解（非凸的）。

Convex Set: 集合C是 的子集，如果集合C滿足 ，推出 for all ，那麼集合C就是凸集。

Convex Function: 如果函數 滿足

1. 【 是f的定義域】
2. ，for

Optimization Problem:

其中 ，也就是所有函數 的交集。 稱作是決策變數(decision variable)， 稱作目標函數(objective function)，是個標量； 稱作不等式約束(inequality constraint)，是個標量； 稱作等式約束(equality constraint)，是個標量。我們面對具體的問題，要做的就是怎麼把問題寫成如同上式中的形式，並且設計演算法尋找 ，使得 在滿足那些約束的前提下讓objection function最小。如果某個點 ，也就是 在函數 的定義域，且把 代入到函數 中分別都滿足 和 ，那麼 就稱作該優化問題的feasible point(可行解)。feasible point可能壓根不存在，也可能存在一個或者多個甚至無窮多個。如果存在多個或者無窮多個feasible point，我們需要找到這些feasible point中，能讓 最小的那個點 ，那 就是該優化問題的optimal(最優解)。顯然這裡函數 可以是 的任意形式的函數(線性或者非線性)，而某些形式會讓問題好求解，某些形式會讓問題特別難解，甚至至今人們都沒有找到解決辦法，需要站在前沿的學者們去研究和解決。不等式約束 (m個)和等式約束 (r個)，根本上說是約束了可行的求解域，如下圖所示：

以上定義了什麼是優化問題，那麼問題來了，什麼又是凸優化問題呢？

Convex Optimization Problem: 如果上述優化問題中的函數 是凸的，而且 是affine的，即 ，那麼該問題就是一個凸優化問題。【為什麼等式約束 需要是affine的？因為我們在剛才介紹凸集的例圖中可以知道，直線是凸集，而曲線是非凸集。affine的等式約束保證了可行域依然是凸集，因為直線->凸集，不是affine的約束那麼就是曲線了->非凸集】

所以某個問題是凸優化問題，必須滿足以下四個條件：

1. 
2. objective function-> 是凸函數
3. ->m個inequality constraints是convex function
4. ->r個equality constraints是affine的

我們說了，不等式約束 (m個)和等式約束 (r個)，根本上說是約束了可行的求解域。那麼凸優化問題中： 導致的可行域是凸的， 是affine的，最終的可行域 就一定是凸的嗎？答案是Yes，因為凸集的交集一定是凸集，而凸集的並集不一定是凸集。如下圖所示的集合X與Y都是凸集，可以看出他們的交集還是凸集，而他們的並集卻不是凸集：

為什麼要研究或者把問題轉化為凸優化問題：因為對於凸優化問題，Local minima意味著Global minima。如下圖所示，左圖是一個凸優化問題，右圖是個非凸優化問題：

上圖中的左圖，因為問題是凸的，所以不管系統的起始點是在圖中的紅圓圈、藍圓圈、綠圓圈、黃圓圈還是紫圓圈，只要沿著下降的方向走(你站在某一個點在決定你的下一步怎麼走時，下降的方向通常有多個，你可以選取其中任意一個，只要它是下降的)，永遠都會收斂到同一個最低點，而且這個最低點就是全局最低點。

而上圖中的右圖，因為問題是非凸的，如果系統起始點在紅線和黃線的圓圈處，你沿著下降的方向走，收斂到右圖中右邊的local minima。而如果系統起始於綠線、藍線和紫線的圓圈處，沿著下降的方向走，最終收斂到右圖中左邊的local minima。而這兩個local minima不是同一個點。也就是說，你最終的收斂到哪裡，依賴於你的系統起始於哪裡。而且這兩個local minima肯定有一個大，一個小。這是一種非常不好的性質。非凸問題的難點就是面對這種不好的性質，怎麼依然找到全局最優解，或者盡量小的那個局部最優解。因為大家都希望不管你起始點在哪裡，都能收斂到最小的那個local minima(顯然最小的那個local minima就是全局的minima)，而不是聽天由命，一會兒收斂到較大的那個local minima，一會兒收斂到較小的那個local minima。

Remarks:

其實對於一個優化問題，存在四種情況：

1. 目標函數 是凸的，可行域 是凸的
2. 目標函數 是凸的，可行域 是非凸的
3. 目標函數 是非凸的，可行域 是凸的
4. 目標函數 是非凸的，可行域 是非凸的

只有第一種情況滿足Local minima意味著Global minima，而其他三種情況收斂到哪裡都依賴於你的起始點在哪裡