凸集的定义为: ![](http://images.cnitblog.com/blog/381513/201309/03232233-55d7ceb633ac455a9577dd2c818bd6a2.png)
其几何意义表示为:如果集合C中任意2个元素连线上的点也在集合C中,则C为凸集。其示意图如下所示:
![](http://images.cnitblog.com/blog/381513/201309/03232243-1206b69427214f38875b19493cf9bc19.png)
常见的凸集有:
n维实数空间;一些范数约束形式的集合;仿射子空间;凸集的交集;n维半正定矩阵集;这些都可以通过凸集的定义去证明。
凸函数的定义为:
![](http://images.cnitblog.com/blog/381513/201309/03232329-0a9a1809666447fdbd8b062093176d13.jpg)
其几何意义表示为函数任意两点连线上的值大于对应自变量处的函数值,示意图如下:
![](http://images.cnitblog.com/blog/381513/201309/03232337-acbd9d29270a4164bef0ae5223f96c5a.jpg)
凸函数的一阶充要条件为:
![](http://images.cnitblog.com/blog/381513/201309/03232349-418dabb9c80e44039fec75ba3f38c4a3.jpg)
其中要求f一阶可微。
二阶充要条件为:
![](http://images.cnitblog.com/blog/381513/201309/03232400-d601ab44d3884aee8a918a8fa3b4535a.jpg)
其中要求f二阶可微,表示二阶导数需大于0才是凸函数。
按照上面的两个定义,如果f(x)=x^2肯定是凸函数,而g(x) = -x^2是非凸函数。也就是说开口向下的函数是非凸函数,但是对于这种情况可以通过添加负号变成凸函数,从而求解。
常见的凸函数有:指数函数族;非负对数函数;仿射函数;二次函数;常见的范数函数;凸函数非负加权的和等。这些可以采用上面2个充要条件或者定义去证明。
凸优化问题(OPT)的定义为:
![](http://images.cnitblog.com/blog/381513/201309/03232419-35c2e5aeb6b64d3fb867bc90fe74990f.jpg)
即要求目标函数是凸函数,变量所属集合是凸集合的优化问题。或者目标函数是凸函数,变量的约束函数是凸函数(不等式约束时),或者是仿射函数(等式约束时)。
对于凸优化问题来说,局部最优解就是全局最优解。
常见的凸优化问题包括:
线性规划(LP):该问题是优化下面的式子:
![](http://images.cnitblog.com/blog/381513/201309/03232449-20db6916bb6d49b5a9a833f839f87844.jpg)
其中那个不常见的奇怪符号表示按元素小于等于,后面出现类似符号可以类似理解。
二次规划(QP):该问题是优化下面的式子:
![](http://images.cnitblog.com/blog/381513/201309/03232500-a88e73f428444a33ab1984c1116dc3cd.jpg)
二次约束的二次规划(QCQP):该问题是优化下面的式子:
![](http://images.cnitblog.com/blog/381513/201309/03232512-cf27889c9138489d8248699167610756.jpg)
半正定规划(SDP):该问题是优化下面的式子:
![](http://images.cnitblog.com/blog/381513/201309/03232535-bf6f69905b9c410a95f19bf6c0a77775.jpg) |