paper 110：凸优化和非凸优化

数学中最优化问题的一般表述是求取 $x^{*}in chi$ ，使 $f(x^{*} )=min{f(x):xin 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,tin[0,1]$ ，即任意两点的连线段都在集合内，直观上就是集合不会像下图那样有“凹下去”的部分。至于闭合的凸集，则涉及到闭集的定义，而闭集的定义又基于开集，比较抽象，不赘述，这里可以简单地认为闭合的凸集是指包含有所有边界点的凸集。

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

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

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

实际建模中判断一个最优化问题是不是凸优化问题一般看以下几点：

目标函数 $f$ 如果不是凸函数，则不是凸优化问题
决策变量 $x$ 中包含离散变量（0-1变量或整数变量），则不是凸优化问题
约束条件写成 $g(x)le0$ 时， $g$ 如果不是凸函数，则不是凸优化问题

之所以要区分凸优化问题和非凸的问题原因在于凸优化问题中局部最优解同时也是全局最优解，这个特性使凸优化问题在一定意义上更易于解决，而一般的非凸最优化问题相比之下更难解决。

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

凸优问题另一种解释：

简单的说，优化问题中，目标函数为凸函数，约束变量取值于一个凸集中的优化问题称为凸优化，举个简单例子，设S为凸集，f(x)为S上凸函数，则问题min f(x) s.t. x属于S为一个凸优化。

若两点在一个点集中，那么连接这两点的线段上所有点也在这个点集中，这样的点集就称为凸集。

凸函数是一个定义在某个向量空间的凸子集C（区间）上的实值函数f，而且对于凸子集C中任意两个向量x1,x2,f((x1+x2)/2)≤(f(x1)+f(x2))/2。

如果其二阶导数在区间上恒大于等于0，就称为凸函数。（下凸）

什么是凸集？

凸集：http://en.wikipedia.org/wiki/Convex_set

什么是凸函数？

凸函数：http://en.wikipedia.org/wiki/Convex_function

什么是凸优化：

同时满足如下两个条件的优化问题称为凸优化：

1）目标函数(objective fucntion)是凸函数；

2）可行集合(feasible set)必须是凸集；

即在凸集上寻找凸函数的全局最值的过程称为凸优化。