為什么開篇第一件事是介紹凸優(yōu)化呢招刹，原因很簡單恬试，就是它很重要！

凸優(yōu)化屬于數(shù)學最優(yōu)化的一個子領域疯暑，所以其理論本身也是科研領域一門比較復雜高深的研究方向训柴，常被應用于運籌學、管理科學妇拯、運營管理幻馁、工業(yè)工程、系統(tǒng)工程越锈、信號處理仗嗦、統(tǒng)計學等，我們主要關注其在機器學習中的應用甘凭。

類比于計算機程序由數(shù)據(jù)結構和算法組成一樣稀拐，任何的AI問題可歸結于以下公式：

模型：目標函數(shù)，旨為實現(xiàn)目標的途徑丹弱，方法有神經(jīng)網(wǎng)絡钩蚊、SVM、邏輯回歸等
優(yōu)化：本質為機器學習中的訓練蹈矮，為了更準確的接近目標得到最優(yōu)的解砰逻，優(yōu)化方法有SGD、AdaGrad泛鸟、Adam蝠咆、EM等

模型（目標函數(shù)）好建，優(yōu)化才是機器學習的核心北滥，而任何一個優(yōu)化問題可以寫成如下的一個標準形式：

min f (x)
s.t. : gi (x) ≤ 0, i = {1,.....,m}
hj (x) = 0, j = {1,.....,t}

常見的優(yōu)化問題有：

1. 線性回歸（Linear Regression）
2. 邏輯回歸（Logistic Regression）
3. SVM（Support Vector Machine）
4. 協(xié)同過濾（Collaborative Filtering）
5. K均值（K-means）

當我們拿到一個AI問題時刚操，在用上述的標準化形式確定目標函數(shù)之后，首先要做的就是判斷目標函數(shù)的類型再芋，確定其優(yōu)化的方向菊霜。我們通常會通過以下４個維度來考量其類別：

1. 凸函數(shù)　Or　非凸函數(shù)

如果目標函數(shù)是一個凸函數(shù)，就意味著這個函數(shù)有一個全局最優(yōu)解（也就是極值點）济赎，可以直接通過算法確定出來鉴逞，凸函數(shù)的局部最優(yōu)解就是其全局最優(yōu)解是凸優(yōu)化最大的一個優(yōu)勢，非常經(jīng)典的邏輯回歸就是一個凸優(yōu)化問題司训，而神經(jīng)網(wǎng)絡則是比較復雜的非凸優(yōu)化問題构捡。對于非凸函數(shù)，它存在很多的局部最優(yōu)解壳猜，導致我們就很難在局部最優(yōu)解中找到全局最優(yōu)解勾徽，所以在這種優(yōu)化問題中，我們的目標只是尋找到更好的局部最優(yōu)解统扳。

我們在解決問題時喘帚，希望盡量構造出來的目標函數(shù)是凸函數(shù)畅姊。對于部分的非凸函數(shù)，可以盡量通過一些變換轉化凸函數(shù)吹由，最后對得到的解做一些優(yōu)化來得到更好的局部最優(yōu)解涡匀。至于更加復雜的非凸函數(shù)優(yōu)化問題，可采用預訓練（可在優(yōu)化前得到較理想的初始化位置）溉知、選擇合適的優(yōu)化器來得到更好的結果陨瘩。

2. 連續(xù)函數(shù)　Or　非連續(xù)函數(shù)

大部分的機器學習模型都是連續(xù)函數(shù)，只有少部分是非連續(xù)函數(shù)级乍，而且這部分問題優(yōu)化起來比較難舌劳，有興趣可自行探索。

3. 帶條件　Or　不帶條件

不帶條件的目標函數(shù)優(yōu)化起來比較簡單玫荣；帶條件的略復雜一些甚淡，經(jīng)常可以通過拉格朗日的方法可以把條件放到目標函數(shù)中一起優(yōu)化捅厂。

4. 平滑　Or　不平滑

大部分的機器學習模型都是平滑的函數(shù)贯卦，在做梯度下降優(yōu)化時，函數(shù)中的每個點都有梯度焙贷。而對于不平滑的函數(shù)撵割，比如說L1正則就有一個頂點，在頂點處是沒有梯度的辙芍，對于這種問題啡彬，通常會采用次梯度（subGradient）的方法來處理。

在以上４種類型中故硅，判斷目標函數(shù)是否為凸函數(shù)是最重要的庶灿。本章節(jié)我們先來介紹凸函數(shù)優(yōu)化問題。

要理解凸優(yōu)化吃衅，首先要知道兩個概念：凸集往踢、凸函數(shù)

凸集（Convex Set）的定義：

假設對于任意的x,y∈C，并且任意參數(shù)α∈[0,1]徘层，我們有αx + (1 - α)y∈C峻呕，則集合為凸集。簡單來說惑灵，凸集就是過集合內(nèi)C內(nèi)任意兩點之間的線段均在集合C內(nèi)山上。

例子：

1. 所有的Rn
2. 所有的正數(shù)集合Rn+
3. 范數(shù)||x|| ≤ 1
4. 線性方程組式的所有解: Ax = b
5. 不等式的所有解: Ax ≤ b
6. 兩個凸集的交集

凸函數(shù)（Convex Function）的定義:

函數(shù)的定義域D(f)為凸集，對于定義域里任意x,y英支，且0 ≤θ ≤ 1函數(shù)滿足

f (tx1 + (1-t)x2) ≤ tf (x1) + (1-t)f (x2)

例子：

1. 線性函數(shù)：f (x) = bTx + c
2. 二次函數(shù)：f (x) = xTAx + bTx + c（A為半正定矩陣）
3. exp x, -logx, xlogx
4. 范數(shù)函數(shù)

那么如何來判斷凸函數(shù)呢？首先其定義域必須是凸集哮伟，值域可以用以下方法判斷：

1. 對于一元函數(shù)f(x)干花，我們可以通過其二階導數(shù)f″(x) 的符號來判斷妄帘。如果函數(shù)的二階導數(shù)總是非負，即f″(x) ≥ 0 池凄，則f(x)是凸函數(shù)
2. 對于多元函數(shù)f(X)抡驼，我們可以通過其Hessian矩陣（Hessian矩陣是由多元函數(shù)的二階導數(shù)組成的方陣）的正定性來判斷。如果Hessian矩陣是半正定矩陣肿仑，則f(X)是凸函數(shù)

凸優(yōu)化(Convex Optimization)

凸優(yōu)化就是對凸函數(shù)的優(yōu)化致盟，凸優(yōu)化必須要滿足三個條件：

1. 目標函數(shù)的最終要求是最小化（最大化問題取負可轉化為最小化）
2. 目標函數(shù)是一個凸函數(shù)（凹函數(shù)取負可轉化為凸函數(shù)）
3. 約束條件所形成的可行域集合是一個凸集

凸函數(shù)優(yōu)化主要以下幾點優(yōu)勢：

1. 凸優(yōu)化問題的局部最優(yōu)解就是全局最優(yōu)解，這一點尤為重要尤慰，因為在優(yōu)化領域最頭疼的就是局部最優(yōu)解沒辦法保證解的質量馏锡，而凸函數(shù)就不存在這個問題。
2. 雖然實際中由于噪聲或者各種約束條件的存在伟端，大部分的問題都是非凸的杯道，但是很多非凸問題都可以被等價轉化為凸優(yōu)化問題或者被近似為凸優(yōu)化問題（例如拉格朗日對偶問題）。
3. 當一個問題被歸為一個凸優(yōu)化問題時责蝠，基本可以確定該問題是可被求解的党巾。

在實際解決實際優(yōu)化問題時，可按照以下思路進行：

1. 確定參數(shù)霜医、變量
2. 確定目標函數(shù)
3. 約束條件（s.t.）
4. 判斷目標函數(shù)類型
5. 設計解決方案

下面來看兩個經(jīng)典的凸優(yōu)化問題

１．交通問題

問題描述：如下圖所示齿拂，假設有北京和上海兩個衣服倉庫，分別存有500肴敛、300件衣服创肥，現(xiàn)要從兩個倉庫中把衣服分別運往三個城市，三個城市的需求分別為300值朋、200叹侄、250件，北京運輸?shù)饺齻€城市的代價分別為5昨登、3趾代、6，上海運輸?shù)饺齻€城市的代價分別為7丰辣、2撒强、3。求解最合適的運輸方案笙什，使得運輸代價最小飘哨。

image

接下來按照解題思路，求解該問題

1. 確定參數(shù)琐凭、變量

設從北京發(fā)往三個城市的衣服數(shù)量分別為B1芽隆，B2，B3；從上海發(fā)往三個城市的衣服數(shù)量分別為S1胚吁，S2牙躺，S3

2. 確定目標函數(shù)

minimize 5B1+ 3B2 + 6B3 + 7S1 + 2S2 + 3S3

3. 約束條件（s.t.）

B1 +S1 = 300
B2+S2 = 200
B3+S3 = 250
B1 +B2 +B3 ≤ 500
S1+S2 +S3≤ 300
B1,B2,B3 ,S1,S2,S3 ≥ ０

4. 判斷目標函數(shù)類型

目標函數(shù)和條件均為線性函數(shù)，該問題為典型的線性規(guī)劃問題(Linear Programming)

5. 設計解決方案

明確了目標函數(shù)腕扶、約束條件孽拷、函數(shù)類型之后，就可以對該函數(shù)進行優(yōu)化半抱。該問題為經(jīng)典的線性規(guī)劃問題脓恕，有很多現(xiàn)成的優(yōu)化方案，這里就不在贅述窿侈，例如可參考cvxopt的Linear Programming( http://cvxopt.org/userguide/coneprog.html#linear-programming )炼幔，我們只需要將條件轉換為對應向量，作為輸入就好棉磨。

２．投資組合問題

問題描述：將一筆錢分別投資到m支股票中江掩，如何分配可得到最大化收益( 假設每只股票的收益服從正太分布N(ri, ei2))

接下來按照解題思路，求解該問題

1. 確定參數(shù)乘瓤、變量

股票：1,2,3,4,5,......,m
第 i 只股票的配置權重（百分比）：Ｗi
第 i 只股票的收益：Si ~ N(ri, ei2)
則最后的投資組合為：

其中上式中环形，均值為該投資組合的收益，方差為風險

2. 確定目標函數(shù)

目的：最大化收益 ＋ 最小化風險
則目標函數(shù)為：

其中λ為超參數(shù)衙傀，代表風險偏好

3. 約束條件（s.t.）

所有股票配置的權重加起來等于1抬吟，也就是：

4. 判斷目標函數(shù)類型

目標為二次方，條件為線性统抬，該函數(shù)為凸二次規(guī)劃（Convex Quadratic Programming）問題火本。

5. 設計解決方案

可以參考cvxopt的Quadratic Programming( http://cvxopt.org/userguide/coneprog.html#quadratic-programming )比較標準式。

注：這里只構造了基礎的投資模型聪建，切不可按此投資股票钙畔，因為在實際投資中，要考慮更多的問題金麸，比如：基本面風險擎析、消息面風險、股票成本等等（更何況大A股呢）挥下。