在数学中一个非凸的最优化问题是什么意思？

作者：王业磊
链接：https://www.zhihu.com/question/20343349/answer/17347657
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

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

$f$ 是凸函数是指对于定义域 $chi$ 中任意两点 $x_{1},x_{2}in chi$ ，有 $f(t x_{1}+(1-t) x_{2}) ge t f(x_{1})+(1-t)f( x_{2}),tin[0,1]$ ，直观上就是 $f$ 向下凸出，如下图示意。

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

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

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