为什么 Non-Convex Optimization 受到了越来越大的关注？

为什么非凸优化（NonConvex Optimization）受到了越来越大的关注？

非凸优化（NonConvex Optimization）近年来确实成为了优化领域乃至人工智能、机器学习、深度学习等众多热门领域的研究热点。其日益增长的关注度背后是多方面原因的综合作用，我们可以从以下几个关键角度来详细阐述：

1. 现实世界问题的复杂性与非凸性的普遍存在：

最根本的原因在于，现实世界中的许多优化问题本质上就是非凸的。 传统的凸优化（Convex Optimization）虽然有理论上的完备性和高效的求解算法，但其适用范围受到严格限制。当问题具有非凸性时，凸优化方法往往失效或给出次优解。

非线性关系: 许多现实系统中的变量之间存在非线性关系，这些非线性关系很容易导致目标函数或约束条件的非凸性。例如：
机器学习中的神经网络: 深度学习模型，尤其是具有多层和非线性激活函数的神经网络，其损失函数在高维参数空间中通常是高度非凸的。
工程设计: 航空航天中的结构优化、化学工程中的反应器设计、通信系统中的信号编码等，都可能涉及复杂的物理模型和约束，导致非凸优化问题。
金融建模: 投资组合优化、风险管理等问题中，回报与风险之间的关系往往是非线性的，可能导致非凸性。
机器人学: 路径规划、运动控制等问题也常常面临非凸的障碍物规避和关节限制。
多模态特性: 非凸函数往往具有多个局部最优解，而不仅仅是唯一的全局最优解。在许多应用中，我们可能更关心找到一个“足够好”的解（即接近全局最优解），即使它不是理论上的全局最优解。
离散变量与混合变量: 实际问题中经常包含离散变量（如选择某个项目）或混合变量（同时包含连续和离散变量），这也会引入非凸性。

2. 机器学习和深度学习的爆炸式发展：

这是推动非凸优化研究最直接和强大的动力。

深度学习模型: 现代深度学习模型，如卷积神经网络（CNNs）、循环神经网络（RNNs）和Transformer，参数量巨大，结构复杂。训练这些模型的过程就是求解一个极其复杂的非凸优化问题，目标是最小化模型的损失函数。
模型训练的挑战:
局部最优解: 如何避免在训练过程中陷入糟糕的局部最优解，找到接近全局最优解的参数是核心挑战。
鞍点: 非凸函数中存在大量的鞍点，优化算法很容易在鞍点附近停滞，阻碍收敛。
平坦区域: 函数值变化缓慢的区域也会导致收敛速度减慢。
通用优化算法的需求: 由于深度学习模型的多样性，研究人员需要能够处理各种非凸损失函数和模型结构的通用优化算法。这促使了对SGD及其变种（Adam, RMSprop等）的深入研究和改进，以及对更先进的全局优化方法的探索。

3. 计算能力的提升与算法的发展：

过去，由于计算资源的限制，解决非凸优化问题往往是难以想象的。然而，随着：

硬件进步: GPU、TPU等并行计算硬件的飞速发展，使得处理大规模非凸优化问题成为可能。
大数据: 大规模数据集的可用性，也为训练复杂的非凸模型提供了基础。
算法创新:
随机梯度下降（SGD）及其变种: 尽管SGD理论上只能保证收敛到局部最优解，但在实践中，其随机性反而有助于跳出局部最优并探索更广阔的参数空间，因此在深度学习中取得了巨大成功。
二阶方法与近似二阶方法: 虽然直接使用牛顿法等二阶方法在大型问题上计算量过大，但像LBFGS这样的拟牛顿法以及近似二阶方法（如利用Hessian矩阵的低秩近似）在求解非凸问题上表现出更好的收敛速度。
全局优化技术: 诸如模拟退火（Simulated Annealing）、遗传算法（Genetic Algorithms）、粒子群优化（Particle Swarm Optimization）等启发式算法，虽然不保证最优性，但能够有效地探索全局搜索空间，并在某些场景下找到比局部搜索更好的解。
鞍点与梯度下降行为的理论分析: 新的研究正在深入理解非凸优化中的鞍点和梯度下降的行为，并开发新的技术来加速收敛或规避鞍点。
新的优化器设计: 不断有新的优化器被提出，旨在提高在非凸函数上的收敛性能和鲁棒性。

4. 理论研究的深入与新发现：

虽然非凸优化问题的全局最优性难以保证，但近年来在理论研究方面也取得了重要的进展：

“好”的局部最优解: 研究表明，在某些特定类型的非凸问题中（例如，在深度学习的某些正则化设置下），随机梯度下降等算法更有可能收敛到“好”的局部最优解，这些解与全局最优解具有相似的性能。
鞍点分析的突破: 对鞍点动力学的理解不断加深，出现了一些新的算法，可以有效地避开或穿过鞍点。
理论保证的扩展: 尽管无法获得全局最优性的理论保证，但在特定条件下，一些算法对于非凸问题仍然能够提供一定的收敛性或渐近最优性的理论分析。

5. 应用领域的拓展与跨界影响：

非凸优化的成功不仅限于机器学习，它也在影响着其他许多领域：

科学计算: 物理模拟、化学反应模拟等。
经济学: 宏观经济模型、博弈论等。
信号处理: 图像恢复、去噪等。
控制理论: 鲁棒控制、自适应控制等。
运筹学: 物流优化、生产调度等。

这些领域的研究人员越来越多地发现其问题的非凸性，并寻求更强大的优化工具来解决它们。

总结：

非凸优化之所以受到越来越大的关注，是因为它解决了现实世界中许多复杂问题的核心挑战。深度学习的蓬勃发展将非凸优化推到了聚光灯下，而计算能力的提升和算法的创新则为我们提供了解决这些问题的可能性。随着研究的深入，我们对非凸函数的理解和驾驭能力也在不断增强，这使得非凸优化成为一个充满活力和潜力的研究领域，并将继续在科学和工程的各个分支中发挥越来越重要的作用。

总而言之，非凸优化不是一个被“新发现”的问题，而是随着技术发展和应用需求的增长，其重要性和解决它的能力都在不断提升，从而受到了前所未有的关注。

简单总结下我知道的几类能够快速得到globally optimal solutions的nonconvex optimization:

1. Geometric Programming

https:// stanford.edu/~boyd/pape rs/pdf/gp_tutorial.pdf

思路: 通过变量代换将nonconvex problem转化为convex problem。这个例子说明(non)convexity是coordinate dependent的。

2. Compressed Sensing

参考Donoho, Candes 和Tao的一系列发表在TIT上的文章。具体的我也不懂，就不乱说了。

3. Quadratically Constrained Quadratic Programming (inequality constraints数量小于等于2)

https:// web.iem.technion.ac.il/ images/user-files/becka/papers/13.pdf

思路: 考虑dual problem，证明strong duality。当inequality constraint数量为1的时候一个重要的特例是Trust region subproblem。

4. Large-scale Separate Nonconvex Optimization Problem

http://www. mit.edu/~dimitrib/Duali ty_Gap.pdf

思路: 通过Shapley-Folkman Theorem证明了当separate terms趋于无穷的时候，duality gap趋于0，因此可以通过求解dual problem来得到原问题的optimal solution。一个通信中重要的应用是

http://www. comm.utoronto.ca/~weiyu /01658226.pdf

5. Singular Value Decomposition及其应用

先来两个小例子热热身

(Principle component analysis)

令 的SVD为, 则第一个问题的最优解是

第二个问题的最优解是

在通信和信号处理里面非常重要的一类问题有下面的形式

其中 是matrix increasing且concave的, 是任意的Hermitian matrix. 注意到当 时，这个问题退化成上面的第3类问题。当 是一个任意的满足matrix increasing以及concave的函数时，我们可以对 做SVD: , 然后通过manifold optimization来刻画出unitary matrices 和 的结构，最后优化 .

这是目前想到的比较重要的几类，有空继续更新。

非凸优化本就该受到高度的关注，原因就如同上面“月光宝盒。。。”说的一样，现实问题中凸问题测度为0，绝大多数优化问题都是非凸的。所以我觉得问题应该是，为什么非凸优化现在才开始受到越来越多的关注。 凸优化与梯度方法紧密联系在一起，并不是因为梯度方法有多强，而是因为凸优化有多简单。其实优化的原理很简单，寻找关于最优解的信息，然后走向最优解。凸优化之所以简单，那就是每一个局部点的（负）梯度方向都指向最优解，因此求导就知道该往哪个方向走。而非凸、尤其是有大量局部极值的非凸优化问题，梯度与最优解不再有什么关系，最多是指向局部极值，因此梯度方法在有许多局部极值的非凸问题上不再有效。 上面有人讲了很多凸放松的例子，比如用L1范式代替L0、用nuclear norm代替rank等等，只有在很有限的范围下，这样的放松不会改变问题，更一般的情况，非凸问题进行凸放松，往往会改变原始问题。这是数学家最爱做的事，把不能解决的问题拉到能解决的范围。虽然优化变得好解了，然而离我们的目标可能更远了。 关于深度神经网络，似乎用梯度效果不错，是不是梯度方法就够了，可见最近ICML'17上的文章 “Failures of Gradient-Based Deep Learning“。 所以，优化是学习最重要的部分吗？我觉得不是，学习可以看作“表示+评价+优化”，优化只是学习的实施工具，泛化才是最关键的问题，如何设计更好的数据表示、更好的模型结构、更好的目标，以取得更好的泛化能力，是更需要考虑的问题。 然而，当我们只有梯度这一种实施工具的时候，表示得想着线性、模型要顾着简单、目标最好是凸的，削足适履，牺牲了设计机器学习系统的自由，失去了更多的可能性。 非凸优化的研究，是否是在凸优化的基础上继续往前走就可以解决，凸优化是否是非凸优化的基础，我感觉不会。两者是性质差别巨大，会搭积木也不是会盖大楼的基础，不同的问题需要有不同的方法。 顺便推销一下，其实有另一类优化方法——“非梯度优化”，更适合非凸优化问题。可见 https://www.zhihu.com/question/38677354/answer/151325951 这一类方法已显示出很好可用性，但还有很多富有挑战的问题有待研究。（打个广告）欢迎尝试非梯度优化python工具包 ZOOpt https://github.com/eyounx/ZOOpt 其中示例有非凸损失分类器学习、直接策略优化强化学习、L0范数稀疏回归直接求解等。梯度与非梯度的混合，可能更具潜质。 欢迎加入非梯度优化和学习的研究！ for more possibilities! for freedom!

为什么 Non-Convex Optimization 受到了越来越大的关注？

为什么NFT(Non-Fungible Token)在国内明显不如Defi热呢？

什么是非独立同分布（Non-IID）数据，有没有很简单的解释方法？

为什么近几年来自由主义在世界逐渐走弱？

为什么俄乌战争假消息满天飞？

为什么没有枪的政府能指挥有枪的军队？

为什么很多人都说传武就是杀人技？

为什么说近代历史人物只有袁世凯和汪精卫不能翻案？

为什么俄罗斯被个别网友称作俄爹？如何反驳？

为什么民国短短二三十年却能出现大批大师级人物？

为什么航空航天待遇不好，但国家在航空航天技术上依然取得飞速发展？

为什么很多人讨厌吴京?

为什么最近忽然冒出来这么多支持乌克兰的？

为什么《是大臣》《是首相》的编剧没当过公务员、没太多亲身经历，也能写出这么好的政治剧剧本？

为什么剧组里，男的可以坐镜头箱，女的却不可以？

为什么印度在俄乌战争中不表态，而且在安理会上对俄罗斯决案弃权？

为什么那么多公知都是高校知识分子？

为什么诸多短视频app内容的字幕中，要把 “死” “钱” “血”等字打上马赛克？

为什么最近有很多的素食主义者带节奏，他们想干什么？

为什么伊朗可以爆发伊斯兰革命逆世俗化？