完整定義
凸優化是數學優化的一個子領域,研究的是在凸集合上最小化凸函數的問題。由於凸優化問題的任何局部最小值也是全局最小值,因此它們相對容易解決。許多機器學習問題可以被表述或近似為凸優化問題。
白話說明
你有沒有想過,為什麼有些最佳化問題比較好解?
你可以把凸優化想成「地形很單純的找最低點」:你往下走時,不太容易被假的小山谷騙住,找到的解通常就是全局最佳。
它很重要,因為很多機器學習和工程問題都要靠最佳化來找答案,凸優化因為穩定、可解,成了很多方法的基礎。
記住這句
地形是凸的,找到小谷底就放心。
比喻:凸優化就像在一個碗狀的山谷裡找最低點 -- 不管你從哪裡開始走,只要一直往下坡走,最終一定能走到最低點,不用擔心會走到一個「假的」最低點。
容易混淆
凸優化 vs 非凸優化 vs 一般最小化
凸優化:地形單純,局部最小值就是全局最小值
非凸優化:地形複雜,可能有很多假谷底
一般最小化:只是一個總稱,不一定保證好解
最關鍵的區別:凸優化能保證找到的局部解就是全局解。
實際案例
廣告預算分配
前:想把預算切到最好,但搜尋空間太亂
後:把問題寫成凸優化,較容易穩定找到最佳配置
模型訓練中的正則化
前:損失函數不好調,參數更新常卡住
後:加入凸形式的目標和約束,讓求解更穩定
演算法與應用
凸優化常搭配梯度下降、目標函數、正則化與損失函數一起看
很多線性模型、支援向量機和資源配置問題,都會受惠於凸結構
它的價值在於可解性和可分析性,讓工程上比較知道會收斂到哪裡
中英對照與常見說法
- 說法
- 凸優化
- 出現場合
- 台灣常見用語
- 說法
- 凸最佳化
- 出現場合
- 台灣學術界較嚴謹的譯法
- 說法
- 凸优化
- 出現場合
- 簡體寫法
- 說法
- Convex Optimization
- 出現場合
- 英文原名
為什麼凸這件事這麼重要
一個最佳化問題如果是凸的,它有一個極強的性質:任何局部最低點都是全域最低點。
這句話的實務意義是,只要演算法找到一個「往哪個方向走都不會更低」的點,就可以確定沒有更好的解了,不需要擔心卡在局部低點,也不需要多次隨機起始重跑。
非凸問題沒有這個保證。深度學習的損失函數幾乎都是非凸的,所以訓練結果會依初始值不同而不同,也沒有辦法證明訓練出來的模型是最好的。
判斷凸性的直觀方法:函數圖形上任取兩點連一條線,線段永遠不會落在函數圖形下方,就是凸函數。集合裡任取兩點的連線都完全落在集合內,就是凸集合。
主要優勢
有全域最優保證。 這是最核心的價值,前面已經說明。
收斂速度有理論保證。 凸問題的演算法可以事先估算需要多少次迭代才能達到指定精度,非凸問題做不到。
有成熟的求解器可用。 線性規劃、二次規劃、二階錐規劃、半正定規劃都有高度最佳化的商用與開源求解器,問題只要能寫成標準形式就能直接丟進去。
有對偶理論。 可以從對偶問題得到最優值的下界,用來判斷目前的解離最優還有多遠,這在大規模問題上很實用。
典型應用領域
常被忽略的一點是:很多非凸問題可以透過鬆弛(relaxation)轉成凸問題求近似解。L0 範數(非零元素個數)的最佳化是非凸且難解的,鬆弛成 L1 範數之後就變成凸問題,這正是 Lasso 與壓縮感知的理論基礎。這種「先鬆弛成凸的再解」是最佳化領域最常用的手法之一。
- 領域
- 機器學習
- 具體問題
- 線性迴歸、脊迴歸、Lasso、支援向量機、邏輯斯迴歸
- 領域
- 訊號處理
- 具體問題
- 濾波器設計、壓縮感知
- 領域
- 金融
- 具體問題
- 投資組合最佳化(馬可維茲模型)
- 領域
- 控制
- 具體問題
- 模型預測控制
- 領域
- 網路與營運
- 具體問題
- 資源配置、排程、最短路徑
情境判斷
Q1(直覺題): 如果一個問題是凸的,是不是通常比較好解?
是,通常更容易穩定找到全局最優。
Q2(判斷題): 只要用了梯度下降,就代表你在做凸優化嗎?
不一定。梯度下降可以用在凸問題,也可以用在非凸問題。
常見問題
不一定,但通常比較容易數值求解。
不是,很多深度學習問題其實是非凸的。
因為它穩定、可證明、可預測,工程上很實用。
最常被推薦的是 Stephen Boyd 與 Lieven Vandenberghe 的《Convex Optimization》,作者在史丹佛的書頁提供電子版與相關課程資料。中文學習者也可以搭配國內大學開設的凸優化課程講義一起讀。
求最小值的問題要同時符合三個條件:目標函數是凸函數,不等式限制式的函數是凸函數,等式限制式是仿射(線性)函數。只要有一項不成立,例如目標函數有好幾個谷底,通常就不是凸優化問題。
出現在這些考古題
官方公告試題的逐題解析裡,這 1 題把凸優化列為延伸術語。
相關術語
- 梯度下降Gradient Descent最常見的求解方式之一
- 目標函數Objective Function凸不凸通常就是看它的形狀
- 損失函數Loss Function很多優化問題都從這裡開始
- 正則化Regularization常讓問題更穩定,也可能讓它更接近凸
- 演算法Algorithm理解求解方法,才能看懂凸優化怎麼落地
- 拉格朗日乘數Lagrange Multiplier
- 支持向量機Support Vector Machine
- 線性迴歸法Linear Regression
本頁內容有提到,或屬於同一組主題的術語
來源
參考來源:en.wikipedia.org
其他格式:Markdown 版本