AITerms 登入
最佳化機器學習數學基礎

凸優化(Convex Optimization)是什麼?

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

完整定義

凸優化是數學優化的一個子領域,研究的是在凸集合上最小化凸函數的問題。由於凸優化問題的任何局部最小值也是全局最小值,因此它們相對容易解決。許多機器學習問題可以被表述或近似為凸優化問題。

白話說明

你有沒有想過,為什麼有些最佳化問題比較好解?

你可以把凸優化想成「地形很單純的找最低點」:你往下走時,不太容易被假的小山谷騙住,找到的解通常就是全局最佳。

它很重要,因為很多機器學習和工程問題都要靠最佳化來找答案,凸優化因為穩定、可解,成了很多方法的基礎。

記住這句

地形是凸的,找到小谷底就放心。

比喻:凸優化就像在一個碗狀的山谷裡找最低點 -- 不管你從哪裡開始走,只要一直往下坡走,最終一定能走到最低點,不用擔心會走到一個「假的」最低點。

容易混淆

凸優化 vs 非凸優化 vs 一般最小化

凸優化:地形單純,局部最小值就是全局最小值

非凸優化:地形複雜,可能有很多假谷底

一般最小化:只是一個總稱,不一定保證好解

最關鍵的區別:凸優化能保證找到的局部解就是全局解。

實際案例

廣告預算分配

前:想把預算切到最好,但搜尋空間太亂

後:把問題寫成凸優化,較容易穩定找到最佳配置

模型訓練中的正則化

前:損失函數不好調,參數更新常卡住

後:加入凸形式的目標和約束,讓求解更穩定

演算法與應用

凸優化常搭配梯度下降、目標函數、正則化與損失函數一起看

很多線性模型、支援向量機和資源配置問題,都會受惠於凸結構

它的價值在於可解性和可分析性,讓工程上比較知道會收斂到哪裡

中英對照與常見說法

說法
凸優化
出現場合
台灣常見用語
說法
凸最佳化
出現場合
台灣學術界較嚴謹的譯法
說法
凸优化
出現場合
簡體寫法
說法
Convex Optimization
出現場合
英文原名

為什麼凸這件事這麼重要

一個最佳化問題如果是凸的,它有一個極強的性質:任何局部最低點都是全域最低點。

這句話的實務意義是,只要演算法找到一個「往哪個方向走都不會更低」的點,就可以確定沒有更好的解了,不需要擔心卡在局部低點,也不需要多次隨機起始重跑。

非凸問題沒有這個保證。深度學習的損失函數幾乎都是非凸的,所以訓練結果會依初始值不同而不同,也沒有辦法證明訓練出來的模型是最好的。

判斷凸性的直觀方法:函數圖形上任取兩點連一條線,線段永遠不會落在函數圖形下方,就是凸函數。集合裡任取兩點的連線都完全落在集合內,就是凸集合。

主要優勢

有全域最優保證。 這是最核心的價值,前面已經說明。

收斂速度有理論保證。 凸問題的演算法可以事先估算需要多少次迭代才能達到指定精度,非凸問題做不到。

有成熟的求解器可用。 線性規劃、二次規劃、二階錐規劃、半正定規劃都有高度最佳化的商用與開源求解器,問題只要能寫成標準形式就能直接丟進去。

有對偶理論。 可以從對偶問題得到最優值的下界,用來判斷目前的解離最優還有多遠,這在大規模問題上很實用。

典型應用領域

常被忽略的一點是:很多非凸問題可以透過鬆弛(relaxation)轉成凸問題求近似解。L0 範數(非零元素個數)的最佳化是非凸且難解的,鬆弛成 L1 範數之後就變成凸問題,這正是 Lasso 與壓縮感知的理論基礎。這種「先鬆弛成凸的再解」是最佳化領域最常用的手法之一。

領域
機器學習
具體問題
線性迴歸、脊迴歸、Lasso、支援向量機、邏輯斯迴歸
領域
訊號處理
具體問題
濾波器設計、壓縮感知
領域
金融
具體問題
投資組合最佳化(馬可維茲模型)
領域
控制
具體問題
模型預測控制
領域
網路與營運
具體問題
資源配置、排程、最短路徑

情境判斷

Q1(直覺題): 如果一個問題是凸的,是不是通常比較好解?

是,通常更容易穩定找到全局最優。

Q2(判斷題): 只要用了梯度下降,就代表你在做凸優化嗎?

不一定。梯度下降可以用在凸問題,也可以用在非凸問題。

常見問題

出現在這些考古題

官方公告試題的逐題解析裡,這 1 題把凸優化列為延伸術語。

相關術語

本頁內容有提到,或屬於同一組主題的術語

來源

參考來源:en.wikipedia.org

其他格式:Markdown 版本