凸优化和非凸优化

  14094人阅读  评论(2)  收藏  举报
  分类:
数学中最优化问题的一般表述是求取 x^{*}\in \chi ,使 f(x^{*} )=min\{f(x):x\in \chi \} ,其中 x 是n维向量, \chi x 的可行域, f \chi 上的实值函数。
凸优化 问题是指 \chi 闭合的凸集 f \chi 上的 凸函数 的最优化问题,这两个条件任一不满足则该问题即为非凸的最优化问题

其中,\chi 凸集是指对集合中的任意两点x_{1},x_{2}\in \chi,有tx_{1}+(1-t)x_{2}\in \chi,t\in[0,1],即任意两点的连线段都在集合内,直观上就是集合不会像下图那样有“凹下去”的部分。至于闭合的凸集,则涉及到闭集的定义,而闭集的定义又基于开集,比较抽象,不赘述,这里可以简单地认为闭合的凸集是指包含有所有边界点的凸集。



注意中国大陆数学界某些机构关于函数凹凸性定义和国外的定义是相反的。Convex Function在某些中国大陆的数学书中指凹函数。Concave Function指凸函数。但在中国大陆涉及经济学的很多书中,凹凸性的提法和其他国家的提法是一致的,也就是和数学教材是反的。举个例子,同济大学高等数学教材对函数的凹凸性定义与本条目相反,本条目的凹凸性是指其上方图是凹集或凸集,而同济大学高等数学教材则是指其下方图是凹集或凸集,两者定义正好相反。

为什么要求是凸函数呢? 因为如果是下图这样的函数,则无法获得全局最优解。

为什么要求是凸集呢?因为如果可行域不是凸集,也会导致局部最优


实际建模中判断一个最优化问题是不是凸优化问题一般看以下几点:
  • 目标函数f如果不是凸函数,则不是凸优化问题
  • 决策变量x中包含离散变量(0-1变量或整数变量),则不是凸优化问题
  • 约束条件写成g(x)\le0时,g如果不是凸函数,则不是凸优化问题
之所以要区分凸优化问题和非凸的问题原因在于凸优化问题中局部最优解同时也是全局最优解,这个特性使凸优化问题在一定意义上更易于解决,而一般的非凸最优化问题相比之下更难解决。

非凸优化问题如何转化为凸优化问题的方法:
1)修改目标函数,使之转化为凸函数
2)抛弃一些约束条件,使新的可行域为凸集并且包含原可行域



----------------------------------------------------------------------------------------------------------------------------------------------------------


关于凸优化的一些简单概念

  38642人阅读  评论(2)  收藏  举报
  分类:

http://www.cnblogs.com/tornadomeet/p/3300132.html


没有系统学过数学优化,但是机器学习中又常用到这些工具和技巧,机器学习中最常见的优化当属凸优化了,这些可以参考Ng的教学资料:http://cs229.stanford.edu/section/cs229-cvxopt.pdf,从中我们可以大致了解到一些凸优化的概念,比如凸集,凸函数,凸优化问题,线性规划,二次规划,二次约束二次规划,半正定规划等,从而对凸优化问题有个初步的认识。以下是几个重要相关概念的笔记。

 

  凸集的定义为:

  

  其几何意义表示为:如果集合C中任意2个元素连线上的点也在集合C中,则C为凸集。其示意图如下所示:

  

  常见的凸集有:

  n维实数空间;一些范数约束形式的集合;仿射子空间;凸集的交集;n维半正定矩阵集;这些都可以通过凸集的定义去证明。

 

  凸函数的定义为:

  

  其几何意义表示为函数任意两点连线上的值大于对应自变量处的函数值,示意图如下:

  

  凸函数的一阶充要条件为:

  

  其中要求f一阶可微。

  二阶充要条件为:

  

  其中要求f二阶可微,表示二阶导数需大于0才是凸函数。

     按照上面的两个定义,如果f(x)=x^2肯定是凸函数,而g(x) = -x^2是非凸函数。也就是说开口向下的函数是非凸函数,但是对于这种情况可以通过添加负号变成凸函数,从而求解。



   常见的凸函数有:指数函数族;非负对数函数;仿射函数;二次函数;常见的范数函数;凸函数非负加权的和等。这些可以采用上面2个充要条件或者定义去证明。

 

  凸优化问题(OPT)的定义为:

  

  即要求目标函数是凸函数,变量所属集合是凸集合的优化问题。或者目标函数是凸函数,变量的约束函数是凸函数(不等式约束时),或者是仿射函数(等式约束时)。

  对于凸优化问题来说,局部最优解就是全局最优解。

  常见的凸优化问题包括:

  线性规划(LP):该问题是优化下面的式子:

   

  其中那个不常见的奇怪符号表示按元素小于等于,后面出现类似符号可以类似理解。

  二次规划(QP):该问题是优化下面的式子:

   

  二次约束的二次规划(QCQP):该问题是优化下面的式子:

   

  半正定规划(SDP):该问题是优化下面的式子:

  

  按照文章说SDP在机器学习领域应用很广,最近很流行,不过我好像没太接触到过。

 

  参考资料:

     http://cs229.stanford.edu/section/cs229-cvxopt.pdf

==========================================================================================

为什么凸优化这么重要?

看到好多人都在学习凸优化,但是有感觉有多少问题多符合凸优化条件的呢?为什么非得是凸优化这么重要?现有的优化方法不是都能解决吗?那凸优化又有什么用呢?
按时间排序 默认排序

11 个回答


Logo

学大模型,用大模型上飞桨星河社区!每天8点V100G算力免费领!免费领取ERNIE 4.0 100w Token >>>

更多推荐