凸优化-非凸优化

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

简单的测试一个集合是不是凸的，只要任意取集合中的俩个点并连线，如果说连线段完全被包含在此集合中，那么这个集合就是凸集，例如左图所示。
凸优化有个非常重要的定理，即任何局部最优解即为全局最优解。由于这个性质，只要设计一个较为简单的局部算法，例如贪婪算法（Greedy Algorithm）或梯度下降法（Gradient Decent），收敛求得的局部最优解即为全局最优。因此求解凸优化问题相对来说是比较高效的。这也是为什么机器学习中凸优化的模型非常多，毕竟机器学习处理大数据，需要高效的算法。
而非凸优化问题被认为是非常难求解的，因为可行域集合可能存在无数个局部最优点，通常求解全局最优的算法复杂度是指数级的（NP难）。如下图：

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

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

Reference

• 人工智能|数据科学|运筹学交叉 https://zhuanlan.zhihu.com/p/27429666
• 凸优化概况https://blog.csdn.net/ctrigger/article/details/92802699
• 运筹学https://zhuanlan.zhihu.com/p/25579864?refer=operations-research
• KKT（主要是针对带约束的可微分的优化问题）