计算机学科，如何学习优化算法/最优化理论相关知识？

xiangtingsl · 发表于 2021-12-15 06:55

最优化的学习，大致有一个脉络。
首先你得有一些基本的知识，线性代数、矩阵论、概率论，也不需要太深入，但是基本的东西要熟练掌握。
然后你得学习一些关于优化的基本知识，比如凸集、凸函数、常见函数的求导、次梯度的概念和用法以及拉格朗日乘子法等等。这部分内容既可以通过最优化的书籍来获取，也可以通过读一些综述性的论文来得到。前者就不说了，书很多。后者我推荐[1,2,3]，其中[1,2]都是非常通俗好读的论文，[3]要难一些也更细一些。
在掌握了基本的知识以后，就可以展开调研和研究了。这时候你就要考察移动群智感知这个问题需要什么知识。它需要哪一类优化知识？Nonsmooth optimization？Nonconvex optimization？Online optimization？Robust optimization？Stochastic optimization？Distributed optimization？然后根据你的调研结果补充相应的知识，因为不同的研究方向需要的知识也不一样。比如nonsmooth optimization，你就得掌握次梯度、proximal mapping这些东西。再比如Distributed optimization，你就得了解图论的东西，图的连通性之类的。
当你对研究领域认识的比较深刻以后，你就要思考就要做什么研究了。做算法还是做收敛性收敛速率？做算法需要什么核心知识，做收敛性收敛速度需要什么核心知识？比如Online optimization，它的收敛性是针对Regret来说的，这显然就和其他分支有根本性的不同了，那么你就要先观察别人是怎么做的，他们的核心手段是什么。再比如Distributed optimization，它的目的之一是达到consensus状态，这和其他优化分支是很不同的，那么大家用到了什么手段来做？
当你了解了所在领域的核心之后，你就应该很清楚朝哪里发力了，因为一个分支与其他分支的不同点往往也就是发力点。比如stochastic optimization，你搞stochastic，那就有variance啊，所以这个分支很重视variance reduction [4]。再比如nonconvex optimization，nonconvex就没有理论保证了嘛，那么好，你就需要研究什么时候是可以避开驻点的[5]。
这样一层层递进下来，基本上对最优化研究就有比较清晰的脉络了。
[1]Parikh N, Boyd S. Proximal algorithms[J]. Foundations and Trends in Optimization, 2014, 1(3): 127-239.
[2]Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations and Trends in Machine learning, 2011, 3(1): 1-122.
[3]Komodakis N, Pesquet J C. Playing with duality: An overview of recent primal-dual approaches for solving large-scale optimization problems[J]. IEEE Signal Processing Magazine, 2015, 32(6): 31-54.
[4]Johnson R, Zhang T. Accelerating stochastic gradient descent using predictive variance reduction[C]. Advances in neural information processing systems. 2013: 315-323.
[5]Jin C, Ge R, Netrapalli P, et al. How to escape saddle points efficiently[C]. Proceedings of the 34th International Conference on Machine Learning-Volume 70. JMLR. org, 2017: 1724-1732.

Doris232 · 发表于 2021-12-15 06:58

最优化的学习，大致有一个脉络。
首先你得有一些基本的知识，线性代数、矩阵论、概率论，也不需要太深入，但是基本的东西要熟练掌握。
然后你得学习一些关于优化的基本知识，比如凸集、凸函数、常见函数的求导、次梯度的概念和用法以及拉格朗日乘子法等等。这部分内容既可以通过最优化的书籍来获取，也可以通过读一些综述性的论文来得到。前者就不说了，书很多。后者我推荐[1,2,3]，其中[1,2]都是非常通俗好读的论文，[3]要难一些也更细一些。
在掌握了基本的知识以后，就可以展开调研和研究了。这时候你就要考察移动群智感知这个问题需要什么知识。它需要哪一类优化知识？Nonsmooth optimization？Nonconvex optimization？Online optimization？Robust optimization？Stochastic optimization？Distributed optimization？然后根据你的调研结果补充相应的知识，因为不同的研究方向需要的知识也不一样。比如nonsmooth optimization，你就得掌握次梯度、proximal mapping这些东西。再比如Distributed optimization，你就得了解图论的东西，图的连通性之类的。
当你对研究领域认识的比较深刻以后，你就要思考就要做什么研究了。做算法还是做收敛性收敛速率？做算法需要什么核心知识，做收敛性收敛速度需要什么核心知识？比如Online optimization，它的收敛性是针对Regret来说的，这显然就和其他分支有根本性的不同了，那么你就要先观察别人是怎么做的，他们的核心手段是什么。再比如Distributed optimization，它的目的之一是达到consensus状态，这和其他优化分支是很不同的，那么大家用到了什么手段来做？
当你了解了所在领域的核心之后，你就应该很清楚朝哪里发力了，因为一个分支与其他分支的不同点往往也就是发力点。比如stochastic optimization，你搞stochastic，那就有variance啊，所以这个分支很重视variance reduction [4]。再比如nonconvex optimization，nonconvex就没有理论保证了嘛，那么好，你就需要研究什么时候是可以避开驻点的[5]。
这样一层层递进下来，基本上对最优化研究就有比较清晰的脉络了。
[1]Parikh N, Boyd S. Proximal algorithms[J]. Foundations and Trends in Optimization, 2014, 1(3): 127-239.
[2]Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations and Trends in Machine learning, 2011, 3(1): 1-122.
[3]Komodakis N, Pesquet J C. Playing with duality: An overview of recent primal-dual approaches for solving large-scale optimization problems[J]. IEEE Signal Processing Magazine, 2015, 32(6): 31-54.
[4]Johnson R, Zhang T. Accelerating stochastic gradient descent using predictive variance reduction[C]. Advances in neural information processing systems. 2013: 315-323.
[5]Jin C, Ge R, Netrapalli P, et al. How to escape saddle points efficiently[C]. Proceedings of the 34th International Conference on Machine Learning-Volume 70. JMLR. org, 2017: 1724-1732.

JoshWindsor · 发表于 2021-12-15 07:01

凸优化是比较建议你最先去看的。我觉得这个课中科大老师讲的很好，网上也有他的视频。我的建议是先把这个凸优化的基础知识稍微掌握一下，这样可能在看论文的时候不会那么吃力。然后就看论文，从论文中学习是最快的，效率也是最高的，先泛读，把目前做的比较好的列一个benchmarktable。然后复现最好的作为baseline，然后都paper，想点子。

super1 · 发表于 2021-12-15 07:02

建议可以先从实践出发，然后再深入理论。目前工业界和学术界都已有很多优化算法相关的工具，如gurobi，cplex，deap，等凸优化，整数规划，演化算法工具，试着用这些工具解决你的问题，找到难点，然后再考虑理论优化。当然，你所在的研究组可能已有很多相关工作，可以先搞明白这些工作，跑跑代码。

		自动登录	找回密码
密码			立即注册