凸優化第四章凸優化問題 4.2凸優化

4.2凸優化

1. 标準形式的凸優化問題
2. 局部最優解與全局最優解
3. 可微函數

   

   的最優性準則
4. 等價的凸問題
5. 拟凸優化

标準形式的凸優化問題

是凸函數，等式限制是仿射函數。則此優化問題是凸優化問題。

也可以寫成

重要性質：凸優化問題的可行集也是凸集。

證明：可行集是滿足不等式限制和等式限制的點的集合，首先不等式限制函數

是凸函數，滿足不等式限制

的x，相當于是

的0-下水準集，凸函數的下水準集是凸集，是以滿足每個不等式限制的x均是凸集，同時滿足這些不等式限制的x是這些凸集的交集仍為凸集。對于等式限制，滿足每個仿射函數的x是凸集，同時滿足多個仿射函數的x是凸集的交集也是凸集。同時考慮不等式限制和等式限制，可知凸優化問題的可行集也是凸集。

例子：

首先判斷可行集，由兩個限制函數可推出

，可知可行集是凸集。

是凸函數。但是這不是一個凸優化問題，因為其不等式限制函數不是凸函數，等式限制函數也不是仿射函數。

但可以得到其等價的凸優化問題：

局部最優解與全局最優解

凸優化問題的基礎性質:局部最優解也是全局最優解。

證明：

假設x是局部最優解，且存在一個可行點y，

。

因為x是局部最優解，故存在一些R，

因為凸優化問題的可行集是凸集，故取

都屬于可行集。

因為

，故

，此時令

。可知

此時

而根據凸函數性質：

與上式沖突。故凸優化問題中局部最優解就是全局最優解。

可微函數

的最優性準則

當

是可微凸函數時，根據凸函數一階條件，可知

如果x是最優解，對任意的y屬于可行集，首先滿足

，同時滿足

。是以x是最優解的充要條件就是對任意的y屬于可行集，

等價于

，故幾何上如果

，

在可行集上定義了一個支撐超平面。

1）對于無限制問題：

可行集就是

的定義域，是以x是最優解的充要條件就是

。

證明：因為

可微，是以其定義域是開的，是以與x足夠近的點都可行，取

,t為很小正數時，y可行，于是

，要想滿足

，隻能

。

2)對于隻有等式限制的問題:

可行解的最優性條件：對任意的y屬于可行集，即

,

，因為x,y都是可行解，令

,N(A)表示矩陣A的零空間，

,

将x,y代入最優條件：

，即線性函數非負，故

又因為

上述最優性條件也可以拉格朗日乘子法得到，令

，令其為0，得到最優性條件。

3)對于非負象限的極小化問題:

當x為最優解時，最優性條件：

。而

是y的線性函數，在

時，如果

時，函數無下界，即最優條件不可能恒成立，故

。

于是最優條件寫成：

是以要使上式恒成立要求

，而

且

，是以隻能是

即

等價的凸問題

保持問題凸性的轉換有：消除等式限制、引入等式限制、引入松弛變量、上境圖問題形式、極小化部分變量

消除等式限制

等價于

是Ax=b的特解，F的列可以長成A的零空間。

引入等式限制

等價于

引入松弛變量

等價于

上境圖形式

凸優化問題的上境圖形式：

極小化部分變量

極小化凸函數的部分變量将保持凸性不變，

等價于

拟凸優化

拟凸優化的标準形式

是凸函數，等式限制是仿射函數，

是拟凸函數。則此優化問題是拟凸優化問題。

拟凸優化問題的局部最優解不一定是全局最優解。

如上圖

是局部最優解但是不是全局最優解。

用一族凸函數不等式表示拟凸函數的下水準集

選擇一族凸函數

，t是凸函數的編号，這些函數滿足：

，即拟凸函數的t下水準集是凸函數

的0下水準集。

并且，對于每個x，

都是t的非增函數。

注意：t固定時，每個

是x的凸函數。

例子：

，其中p是凸函數，q是凹函數，在定義域上，

。

則可取

說明：（1）

是凸的：p是凸的，q是凹的，但-q是凸的，是以

是凸的。

（2）滿足：

求解拟凸優化的二分法

思想：有一個區間，包含最優解，取區間的中點，判斷最優解在上半區間還是下半區間，然後更新區間，不斷将區間縮小為原來的一般直到找到足夠小的區間。

算法：

給定

，容忍度

重複一下步驟:

1. 

2. 求解凸可行性問題
3. 如果問題可行，u=t，否則l=t

直到