凸優化演算法原理及講解
凸優化演算法是最優化問題中非常重要的一類,也是被研究的很透徹的一類。
對於機器學習來說,如果要優化的問題被證明是凸優化問題,則說明此問題可以被比較好的解決。
求解一個一般性的最優化問題的全域性極小值是非常困難的,至少要面臨的問題是:函式可能有多個區域性極值點,另外還有鞍點問題。
對於第一個問題,我們找到了一個梯度為0的點,它是極值點,但不是全域性極值,如果一個問題有多個區域性極值,則我們要把所有區域性極值找出來,然後比較,得到全域性極值,這非常困難,而且計算成本相當高。
第二個問題更嚴重,我們找到了梯度為0的點,但它連區域性極值都不是,典型的是這個函式,在0點處,它的導數等於0,但這根本不是極值點:
梯度下降法和牛頓法等基於導數作為判據的優化演算法,找到的都導數/梯度為0的點,而梯度等於0只是取得極值的必要條件而不是充分條件。
如果我們將這個必要條件變成充分條件,即:問題將會得到簡化。
如果對問題加以限定,是可以保證上面這個條件成立的。
其中的一種限制方案是:
對於目標函式,我們限定是凸函式對於優化變數的可行域(注意,還要包括目標函式定義域的約束),我們限定它是凸集。
同時滿足這兩個限制條件的最優化問題稱為凸優化問題,這類問題有一個非常好性質,那就是區域性最優解一定是全域性最優解。
凸優化演算法原理及講解
凸優化方法是數學優化方法中具有代表性的一種,凸優化被廣泛運用在影象處理,自動控制系統,估計和訊號處理,通訊網路,資料探勘,電路設計等很多方面,特別是在現在的人工智慧時代,機器學習和深度學習具有很高的熱度和應用價值,從某種意義上講,凸優化也可看做是機器學習中的一部分。