什麼是 凸優化（Convex Optimization）？

凸優化是一種數學優化方法，旨在尋找凸函數在凸集合上的最小值。其優點是局部最小值即為全局最小值，易於求解。

核心概念

凸優化的核心在於「凸」的概念。一個集合是凸的，如果集合中任意兩點的連線上的所有點都屬於該集合。一個函數是凸的，如果其圖形上任意兩點的連線位於圖形上方。更嚴格地說，對於函數f(x)和任意兩點x1, x2，以及0 <= t <= 1，滿足f(tx1 + (1-t)x2) <= tf(x1) + (1-t)f(x2)。

凸優化問題的一般形式是：

minimize f(x)

subject to x ∈ C

其中f(x)是凸函數，C是凸集合。

常見的凸函數包括線性函數、二次函數、指數函數等。常見的凸集合包括線性子空間、超平面、半空間、球等。

凸優化的重要性在於，對於凸優化問題，任何局部最小值都是全局最小值。這意味著我們可以通過局部搜索算法找到全局最優解，而無需擔心陷入局部最優解的陷阱。

運作原理

凸優化的求解方法有很多種，常見的方法包括：

• 梯度下降法： 沿著函數梯度的反方向迭代更新變量，直到收斂到最小值。
• 牛頓法： 利用函數的二階導數（Hessian矩陣）來加速收斂。
• 內點法： 將約束條件加入目標函數中，形成一個無約束的凸優化問題，然後使用梯度下降法或牛頓法求解。
• 次梯度法： 用於求解不可微的凸函數。
• 對偶方法： 將原始問題轉換為對偶問題，然後求解對偶問題。對偶問題通常更容易求解，並且可以提供原始問題的下界。

這些方法各有優缺點，適用於不同的問題。例如，梯度下降法簡單易實現，但收斂速度較慢；牛頓法收斂速度快，但計算量大；內點法適用於約束條件較多的問題；對偶方法適用於原始問題難以求解的問題。

在實際應用中，我們通常會使用現成的凸優化求解器，例如CVX、Gurobi、Mosek等。這些求解器已經實現了各種凸優化算法，並且經過了大量的測試和優化，可以高效地求解各種凸優化問題。

實際應用

凸優化在機器學習、信號處理、控制理論等領域有著廣泛的應用。以下是一些具體的例子：

• 線性迴歸： 最小化均方誤差可以表述為一個凸優化問題。
• 支持向量機（SVM）： 尋找最大間隔超平面可以表述為一個凸優化問題。
• 邏輯迴歸： 最大化似然函數可以表述為一個凸優化問題。
• 正則化： 將正則化項加入目標函數中可以提高模型的泛化能力，並且通常可以將問題表述為一個凸優化問題。
• 圖像處理： 圖像去噪、圖像分割等問題可以表述為凸優化問題。
• 控制理論： 設計最優控制器可以表述為凸優化問題。
• 投資組合優化： 在給定的風險水平下最大化收益可以表述為凸優化問題。

總之，只要問題可以表述為在凸集合上最小化凸函數，就可以使用凸優化方法求解。

常見誤區

• 誤區一：所有優化問題都是凸優化問題。 實際上，大多數優化問題都是非凸的。凸優化問題只佔優化問題的一小部分，但由於其易於求解，因此在實際應用中非常重要。
• 誤區二：凸優化問題一定有解。 凸優化問題可能無解，例如目標函數無下界，或者約束條件不相容。
• 誤區三：凸優化問題的解是唯一的。 凸優化問題的解可能不唯一，例如目標函數是線性函數，並且約束集合是一個多面體。
• 誤區四：凸優化問題很容易求解。 雖然凸優化問題的局部最小值就是全局最小值，但求解大規模的凸優化問題仍然具有挑戰性。需要選擇合適的算法和求解器，並且進行適當的參數調整。
• 誤區五：所有機器學習模型都可以用凸優化求解。 雖然許多機器學習模型可以表述為凸優化問題，但也有很多模型是非凸的，例如深度神經網路。對於非凸模型，需要使用其他的優化方法，例如梯度下降法。

總之，理解凸優化的概念和原理，以及其局限性，對於在實際應用中正確使用凸優化方法至關重要。

常見問題