優化相關-凸優化

• 凸優化相關
• • 凸函數的定義
  • 凸優化問題的定義
  • • 1.無約束優化
    • 2.帶約束優化
  • 凸優化問題的求解
• 拉格朗日乘子法和KKT條件
• • 統計學習方法-李航
  • 以下是瑞典皇家理工學院-KKT課件(表達上有一定偏差，但個人傾向以李航為準)：
• 拉格朗日對偶性
• • 1.原始問題
  • 2.對偶問題
  • 證明：對偶問題的解是原始問題解的下界
• 參考

凸優化相關

凸函數的定義

為了避免陷入局部最優，人們盡可能使用凸函數作為優化問題的目標函數。

• 凸集定義：歐式空間中，對于集合中的任意兩點的連線，連線上任意一點都在集合中，我們就說這個集合是凸集；
• 凸函數定義：對于任意屬于[0,1]的a和任意屬于凸集的兩點x, y，有$f(ax+(1?a)y)\le a?f(x)+(1?a)?f(y)$，幾何上的直觀理解就是兩點連線上某點的函數值，大于等于兩點之間某點的函數值；
• 凸函數的性質：凸函數的任一局部極值點也是全局極值點；

• 半正定矩陣的定義：特征值大于等于0的實對稱矩陣；
• 半正定矩陣的充要條件：行列式（n階順序主子式）等于0，行列式的i階順序主子式>=0，i從1到n-1；
• 凸函數的充要條件：如果f(x)在開凸集S上具有二階連續偏導數，且f(x)的海塞矩陣（二階偏導的矩陣）在S上處處半正定，則f(x)為S上的凸函數。

凸優化問題的定義

1.無約束優化

無約束優化問題中，如果f(x)是凸函數，那么可以直接通過f(x)的梯度等于0來求得全局極小值點。

2.帶約束優化

考慮帶約束的優化問題，可以描述為如下形式：

其中f(x)是目標函數，g(x)為不等式約束，h(x)為等式約束。

• 若f(x)，h(x)，g(x)三個函數都是線性函數，則該優化問題稱為線性規劃；若任意一個是非線性函數，則稱為非線性規劃；
• 若目標函數f(x)為二次函數，約束g(x), h(x)全為線性函數，稱為二次規劃；
• 若f(x)為凸函數，g(x)為凸函數，h(x)為線性函數，則該問題稱為凸優化。注意這里不等式約束若為$g(x)\le 0$則要求g(x)為凸函數，若$g(x)\ge 0$則要求g(x)為凹函數；
• 凸優化的性質：局部最優也是全局最優，KKT條件就是極小值點（而且是全局極小）存在的充要條件；不是凸優化的話，KKT條件是極小值點的必要不充分條件（滿足KKT條件的點，也不一定是極小值點，但極小值點一定滿足KKT條件）。

凸優化問題的求解

• 對于無約束的優化問題，直接令梯度等于0求解；
• 對于含有約束的優化問題：
• • 對于含有等式約束的優化問題，拉格朗日乘子法，構造拉格朗日函數，令偏導為0求解；
• • 對于含有不等式約束的優化問題，同樣構造拉格朗日函數，利用KKT條件求解；
• 對于含有約束的優化問題，還可以轉化為對偶問題來求解

拉格朗日乘子法和KKT條件

統計學習方法-李航

針對帶約束的原始問題

構造拉格朗日函數：
$$L(x,\alpha ,\beta )=f(x)+\sum _{i=1}^k{\alpha }_i{c}_i(x)+\sum _{j=1}^l{\beta }_j{h}_j(x),$$
其中${\alpha }_i$, ${\beta }_i$是拉格朗日乘子，${\alpha }_i\ge 0$.

當原始問題滿足凸優化條件時，使用如下KKT條件求解最優值：

以下是瑞典皇家理工學院-KKT課件(表達上有一定偏差，但個人傾向以李航為準)：

當優化問題時凸優化時，針對帶不等式約束的原始問題如下求解：

不是凸優化的話，還需要附加多一個正定的條件才能變成充要條件，如下圖所示：

對于同時有多個等式約束和多個不等式約束，構造的拉格朗日函數就是在目標函數后面把這些約束相應的加起來，KKT條件也是如此，如下圖所示：

拉格朗日對偶性

約束最優化問題中，常利用拉格朗日對偶性將原始問題轉換為對偶問題，通過解對偶問題得到原始問題的解。（實質上利用了對偶問題一定是凸函數，而凸函數容易優化）

但是要明確，對偶問題的解不一定直接等于原問題的解（弱對偶），對偶問題有三點性質：

• 強對偶-原始、對偶問題同解 ；
• 弱對偶-原始、對偶問題不同解，但對偶問題的解是原始解的下界；
• 對偶問題一定是凸函數，但原始問題不一定是；

1.原始問題

將求帶約束的$minf(x)$轉換為求對應拉格朗日函數上界的最小值，由于參數不同，可能會有多個上界。

2.對偶問題

證明：對偶問題的解是原始問題解的下界

如上，$d^{?}\le p^{?}$稱為弱對偶，對于所有優化問題都成立。

$d^{?}=p^{?}$稱為強對偶，滿足某些條件才成立，這時可以用解對偶問題替代原始問題。

滿足如下條件時，對偶問題的解與原始問題解相同（即強對偶成立）。注意：這里的條件只是強對偶成立的一種情況，對于非凸的問題也有可能是強對偶）

當強對偶成立時，對偶問題的解也即是原始問題解：

---

參考

拉格朗日對偶性
拉格朗日乘子法和KKT條件
機器學習原理-拉格朗日乘子法和KKT條件
瑞典皇家理工學院（KTH）“統計學習基礎”
統計學習方法-李航

總結

以上是生活随笔為你收集整理的数学基础修炼手册-数学分析-凸优化的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。