《Convex Optimization》notes 3— Convexity II: Optimization basics
前言 : 《Convex Optimization》這一系列的文章是想分享我學習 Ryan Tibshirani 在 CMU 教學的課程 Convex Optimization 與網路上查資料整理而成的筆記。希望可以給自己的學習歷程留下一些什麼，也希望對想了解這方面知識的人有一些幫助。
Convexity II: Optimization basics
Convexity 的哩哩扣扣在此告一段落，接下來我們開始進入最佳化的介紹。回顧一下過去的所提的最佳化問題。我們稱 f 為目標函數(criterion/objective function)；稱 gi 為不等式限制函數(inequality constraint function)；稱符合各種條件的點為可行點(feasible point)。而目標函數f的最小值為最優值(optimal value)。
在這個命題下有個有趣的事情值得提及：為什麼限制條件的等式 Ax=b 一定要是 Affine 而不能是某個一般性的函數 hi=0 呢？這是因為考慮一個函數 hi=0，我們可以寫成 hi 小於等於 0 且 hi 大於等於 0，但在最佳化問題中我們考慮的限制條件 hi 必須為 Convex，在這個情況下唯一能滿足這些條件的 hi，只剩下 Affine 而已了。
Convex Optimization Problem 中有個性質值得介紹一下：解集合為一個 Convex set。我們可以證明如下：假設一個凸優最佳化問題有兩個解 x,y，則當 t 在 0 跟 1 之間時，我們可以根據定義得到
因此 tx+(i-t)y，亦即兩者之間的所有點都為解，故解集合為 Convex set。
另一個重要的性質是：若 f 為 Strictly Convex，則解集合為唯一 ( 意思是問題只有一個解 )。我們可以用反證法，假設仍然有兩個不同的解 x,y，則 f(tx+(i-t)y)＜tf(x)+(1-t)f(y)=tf*+(1-t)f*=f* ( 第一個為嚴格小於，是因為 Strict Convexity 的性質 )，這個意思是我們找到有一個解 tx+(i-t)y 會讓 f 更小，這明顯跟前提 x,y 是兩個不同的解矛盾 ( 若 x,y 為解，則會讓 f 為最優值)，因此 x,y 為同一點。
範例吧！考慮如下的Lasso問題，我們可以得到以下的討論。首先Criterion可以寫成
由於XTX為一個半正定矩陣 ( positive semidefinite ) 故 Criterion 為 Convex。而由於 norm 必為 Convex 所以 ∥β∥ ≦ s 亦為 Convex。
再來考慮解是否為唯一：當 n ≧ p 且 X 有 full rank column 時，則其 Criterion 的 Hessian 為 ▽²f(β) = 2XTX，如果這個是 Strictly Positive Definite 則若且唯若 XTX 為可逆，意即是 X 有線性獨立的 Columns，故解為唯一。反之 p > n 時則 XTX 不可能可逆，因此不能保證解是唯一。
看另一個例子。考慮相當經典的支持向量機 ( SVM ) 問題如下，Criterion 為 Convex 因為我們可以看作 Criterion 為 β 平方和 ( Convex ) 加上 ξi 的線性組合 ( Convex )。接著討論 ( β₀, β, ξi ) 是否唯一，由於原命題的Criterion中包含了 ξi 的線性組合，並不是 Strict Convex，因此目前我們仍然不能說這個解是否為唯一。
回顧最佳化問題，我們其實可以把它寫成這個更一般的形式 minf(x) subject to x 屬於某個集合 C，其中 C 為 Feasible Set。由於原本的限制條件為 Convex 所以 C 為一個 Convex Set。另外考慮 Indicator 函式 IC(x)，當 x 在 C 中時IC(x) 為 0，當 x 不在 C 中時 IC(x) 為無窮大，則我們可以更進一步將原命題改成沒有限制的形式 min f(x) + IC(x)。
我們可以來看一些應用。考慮只有等式限制的 Convex 問題
min f(x) subject to Ax = b
根據 first-order optimality，有一個解 x 滿足 Ax=b，且有個 y 滿足 Ay=b 的話，則 ▽f(x)T(y-x) ≧ 0。令 v=y-x，則 ▽f(x)Tv ≧ 0 且 Av=A(y-x)=b-b=0，故 v 在 null(A) 之中。又由線性代數可知 row(A) 為 null(A)〦，因此可知 v 與 ▽f(x) 的內積 ▽f(x)Tv 為 0。
接著回顧一下 SVM 問題，我們可以將限制條件 ξi≧0 與 yi(xiTβ+β0)≧1-ξi 改寫成 ξi≧max｛0, yi(xiTβ+β0)｝。又我們可以說當找到最佳解時，一定只會有等號而不會有嚴格大於的情況存在。這是因為如果有嚴格大於存在，則這會讓 Criterion 並沒有被最小化 ( 可以找到更小的 ξi 滿足限制條件且讓 Criterion 更小 )，顯然矛盾。
將這個最佳的 ξi 代回去原式即可得到 SVM 的另一種形式。
當我們遇到最佳化問題時，如果我們有一個單調遞增 ( Monotone Increasing ) 函數 h ，我們很常可以將原本的 Criterion 轉換成新的 Criterion 來簡化問題而解不會改變。一個常見的例子是 Maximum Likelihood 問題，即 Max likelihood(Θ) <=> max log likelihood(Θ)
有時候，我們也可藉由改變變數來簡化問題，如果有一個一對一的函數 φ，則 min f(x) subject to x 屬於 C <=> min f(φ(y)) subject to φ(y) 屬於 C。
利用改變變數的特性有時可以簡化最佳化問題，像是消除限制條件中的等式。假設我們有一個解 x0 滿足 Ax0=b 以及另一個 M 矩陣滿足其 Columns 可以 span null(A)，則由線性代數我們可以將任何一個 Feasible 的 x 表示成 My+x0，進而改寫原本的問題。
當然這不一定是好方法，因為光是找到這樣一個 M 可能就有計算上的困難，而且 M 有可能是個非常 dense 的矩陣，反而原本的 A 可能稀疏許多 ( 日後會提到稀疏矩陣相較 dense 矩陣友善了許多 )，因此這樣子的轉換不一定對解題有幫助。
在面對最佳化問題，我們還可以引入 Slack 變數。有的時候不想看到限制條件的不等式時，我們可以引入 Slack 變數使得 gi(x)+si=0 對於 si>=0，看起來會比較簡單。不過要注意的是使用 Slack 變數時，如果原本的不等式不是 Affine 時，我們會失去原本的 Convexity 的性質。
最後一個提到的是 Relaxation。當我們遇到一個問題 min f(x) subject to x 屬於 C 時，我們永遠可以找到一個包含 C 的集合 C ’，而在 min f(x) subject to x 屬於 C ’ ，而在 C 這個新的問題裡面，其最佳解一定會小於或等於原問題的最佳解。這叫做 Relaxation。這件事情也相當的直觀，因為假設新的問題的最佳解大於原問題的最佳解時，那就直接取原問題的最佳解就好了，顯然矛盾，因此得證。
