1，首先大家需要知道Convex VS Non-Convex的概念吧？

数学定义就不写了，介绍个直观判断一个集合是否为Convex的方法，如下图：

简单的测试一个集合是不是凸的，只要任意取集合中的俩个点并连线，如果说连线段完全被包含在此集合中，那么这个集合就是凸集，例如左图所示。

先补充一点：举几个常见的nonconvex例子，通常2次以上的polynomial不论出现在目标函数或约束条件里，都是noconvex，更不用说什么sin、cos函数了；2次函数在目标函数，如果不是SDP（半正定）的话，也是nonconvex。

2，凸优化-相对简单

凸优化有个非常重要的定理，即任何局部最优解即为全局最优解。由于这个性质，只要设计一个较为简单的局部算法，例如贪婪算法（Greedy Algorithm）或梯度下降法（Gradient Decent），收敛求得的局部最优解即为全局最优。因此求解凸优化问题相对来说是比较高效的。这也是为什么机器学习中凸优化的模型非常多，毕竟机器学习处理大数据，需要高效的算法。

3，非凸优化-非常困难

而非凸优化问题被认为是非常难求解的，因为可行域集合可能存在无数个局部最优点，通常求解全局最优的算法复杂度是指数级的（NP难）。如下图：

最经典的算法要算蒙特卡罗投点法了，大概思想便是随便投个点，然后在附近区域（可以假设convex）用2中方法的进行搜索，得到局部最优值。然后随机再投个点，再找到局部最优点。如此反复，直到满足终止条件。

假设有1w个局部最优点，你至少要投点1w次吧？并且你还要假设每次投点都投到了不同的区域，不然你只会搜索到以前搜索过的局部最优点。

再补充一点：数学规划模型里面如果有整数变量，这个问题通常被称为 highly nonconvex(极度非凸)，如下图：

实心黑点组成的集合，是一个离散集，按照1中判断一个集合是否为凸集的技巧，我们很容易验证这个离散集是非凸的。因此整数规划问题也是一个非凸优化问题，并且它也是NP难的。

因此数学规划里最难的一类问题，叫做混合整数非线性规划(mixed integer nonlinear programming)。

那么整数规划的求解思路呢，也遵循了科学研究的本质，即被分解为求解一个个的线性规划问题。感兴趣的朋友可以搜索分支定界法。

举个最简单的例子：
min x_1+x_2^3
s.t. x_1^2-x_2>=2
x_1>=0, x_2 is binary.