学习优化算法需要哪些数学基础？

Doris232 · 发表于 2021-7-4 06:38

比如电气工程领域的优化控制，能量优化管理，系统优化运行等方面。

LiteralliJeff · 发表于 2021-7-4 06:40

答主从事电力系统优化方向，从应用的角度谈一下优化算法吧。
优化问题可以分成凸（convex）问题和非凸问题。凸问题都是可以找到最优解的，只是算力问题，小问题可以用现有的解法器非常快的找到最优解，大型问题则一般要用一些定制的分解算法。非凸问题则要具体情况具体讨论，如果只是带有整数变量的话一般也可以找到不错的解。
电力系统这边常用的优化就是线性规划（LP），二次规划（QP），和整数规划（MIP）。LP和QP常用在解最优调度上，MIP用来做日前机组组合（unit commitment）。这几种问题都是有很成熟的算法，比如多边形法（simplex）和branch&bound法，和解法器（solver），比如Gurobi和Cplex。此外还有一种电力系统专有的问题是交流潮流计算（ACOPF），属于非凸问题，可以用梯度下降法找到次优解，而工业界这些年来也找到了许多启发式算法来提高解的速度和质量。最近10年以Caltech Steven Low为代表的网络控制研究领域也提出了一些ACOPF的凸优化近似解法，比如用到了正定规划（semi-definite programming），只是假设具有局限性，目前看来并不被工业界认可。
下面再讲一下优化分解算法（decomposition），根据答主的经验，电气领域的优化研究主要就是建模和分解大型优化问题，问题的维度主要体现在空间维度（spatial），时间维度（temporal），和不确定性上（uncertainty）。常用的分解算法有primal / dual分解法，这个可以参考斯坦福Stephen Boyd的课件，思路就是利用问题本身的结构通过固定偶和变量（coupling variable）把一个大问题分拆成可以独立平行解决的小问题（subproblem），再把小问题的结果汇总起来update coupling variable（使用梯度/次梯度法，或者平面切割法），以此循环来解决整个问题（master problem），在与平行计算的结合基础上通常可以带来级数级别的速度提升，比如原来需要数小时甚至数日才能解决的问题通过分解+平行计算，可以在数分钟内解决。这类分解算法常用于空间分拆和情景分拆（scenario decomposition）。
另一种常用的分解算法就是动态规划（dynamic programming），用来解决长时间尺度下带有不确定性的优化控制问题，比如水电规划的经典算法就是stochastic dual dynamic programming。这方面Gatech的Alex Shapiro写过一些不错的资料。
最后从学习上在搞懂一些基本的经典优化算法远离比如梯度下降和多边形法外，答主觉得优化在电力方面的应用主要体现在对primal和dual问题之间关联的以及KKT condition的理解，比如primal约束对应的dual是该约束的sub-gradient也就是该约束的price，很多优化分解问题都可以通过这种对这种关系的理解来解决。另一个难点在于对multi-stage decision和uncertainty的理解，比如要理解nonanticipatory control和model predictive control的区别，这个问题甚至可以延伸到当前大火的机器学习上（优化控制上的approximate dynamic programming），这方面答主看过不少资料，感觉还是Shapiro写的最好。

RedZero9 · 发表于 2021-7-4 06:45

首先不太明白题主问题和下面的补充说明“比如”是什么关系？下面列那些明显不是学习优化算法需要的数学基础啊？题主意思是不是说你学习优化算法重点关注的最终应用领域？一个强调数学基础，一个强调具体应用，题主到底重点在那里？建议修改题目或说明。
我就从字面上大体回答一下问题标题。一般研究生水平主要需要的数学基础大体就是分析学相关，线性代数相关，数值分析相关，一点点拓扑相关，统计和机器学习相关，和计算科学基础相关。
这些都是内功心法，最后应用到哪里其实关系不大，目前并没有什么算法大类是只用于电力系统或一定不用于电力系统或明显在电力系统获得更多青睐的。
讲电力系统流行的话，可以多看二阶锥等凸优化、凸松弛方法，和人工智能相关的方法（包括随机梯度、动态规划、强化学习、贝叶斯优化、一些大尺度优化算法这些），ADMM这种可以分布式支撑并行的方法，还有模型预测控制这种突出不确定性处理能力和工程可操作性的方法，等等。
内功心法和行业熟悉度到位了，上面这些其实不需要知乎来告诉你。多看同行论文，你会比回答这个问题的大部分人了解现状。

yukamu · 发表于 2021-7-4 06:54

题外话就是，优化本身就是数学的一个分支，所以其本身就是数学基础，而且用到的其他数学基础的知识不多。
优化一般需要高数和线性代数的知识，尤其是线代的知识。我先介绍一下重点需要了解的知识。但是其实用到的地方不多。高数主要是利用导数和微分求解梯度，利用泰勒展开(多维)对目标函数进行估计，利用极限计算收敛速度。线性代数更重要一点，因为优化的研究对象一般是多变量函数，多变量及关系式可以用向量和矩阵表示。所以要熟悉向量和矩阵的计算。其中最重要的是向量和矩阵导数的计算(矩阵乘法，向量和矩阵求导)，特别需要关注的是梯度（向量的一阶导）和Hessian矩阵（向量的二阶导）的计算。这个要特别熟悉，因为大多数优化算法通过计算梯度获取一个搜索方向，然后沿着搜索方向不断迭代找到最优解。矩阵向量计算中最重要的一些概念就是：标量函数关于向量的导数，向量函数关于标量的导数，向量函数关于向量的导数，矩阵的导数等。
学习优化理论的书籍英文书有两本，Stephen Boyd 的 Convex Optimization和剑桥出版社的Numerical Optimization. 前一本书更加偏向介绍基础理论，配合Boyd大佬的公开课可以更好的学习（网易公开课和B站搜作者应该就可以了）推荐可以从这本书和教学视频入门。。后一本书更加偏向算法实现层面，更加丰富，不仅仅限于凸优化，而且给出了很多种优化算法及其改进的伪代码。里面的算法没必要全部都学，遇到需要解决的问题的时候就可以翻阅选择其中合适的算法。中文书可以看袁亚湘院士的《最优化理论与算法》，这里面提到了一些线性规划和整数规划，也许在研究实际问题中更重要。这些书的附录里面一般都会给出涉及到的高数和线代知识。所以没必要再全部去重温高数和线代课本。
优化是的实践性很强，而且不像其他数学那样很多公式。算法和理论学会之后，更重要的是怎么去根据实际问题构建相应的目标函数，并选用合适的算法去求解。学习优化最好的方法就是搞清楚理论之后，根据伪代码手撸一遍，这样才会清楚目标函数的形式应该是什么样，算法中每个参数的意义是什么，算法怎么样一步一步求得最优解。
如果你是想要研究优化解决诸如交通规划，金融分析，电力优化，可以按照上述流程学习。但如果是搞深度学习的话，那就没必要这么复杂，直接参考花书《Deep Learning》中的优化部分即可。其实深度学习的本质也可以看做是求解一个优化问题。只不过深度学习更关注的是利用网络结构构建一个目标函数模型，优化并不是最重要的部分。而且由于深度学习模型参数（即优化里的自变量维度）太多，很难找到真正的最优解，基本上只用了最简单的一些优化方法（随机梯度下降，Adam等）。
---------------分割线，以下为故事会内容-----------
最后，再介绍一个有趣的方向。大家一直认为深度学习是炼丹，调一些网络结构和参数就能的到好的效果，但是并不了解其中的原理。深度学习的炼丹还只是炼丹的小儿科。优化也有一个门类，叫智能优化算法。这些算法可以不在乎目标函数的形式（甚至不需要数学表达式），只要能给出自变量和因变量的一个映射关系，即一个黑箱子，我们就可以进行优化。其中经典的有模拟退火，遗传算法，粒子群算法，蚁群算法等。当科学家发现可以这么求解以后，真正的炼丹开始了。首先是跟深度学习一样，先调一调控制这些算法的超参数，然后是自适应地调节参数，再是自适应地调节自适应参数（此处可以套娃）。接下来是更改各种算法的流程，加入新的迭代机制。随后科学家们根据前面算法的研究过程，观察生物作出最优选择背后的原理，发掘出新的算法。例如从蜜蜂修筑蜂巢的行为发掘出蜂群算法。自从这个大门打开以后，智能优化像打开了了潘多拉盒子一样，各种新的算法层出不穷，科学家们绞尽脑汁水论文，基本上世界上的任何生物现象都可以研究出一种优化算法。然后每种算法可以跟以前改进一样再来一遍，又可以研究出很多改进算法。最流氓的是，几种算法排列组合一起就又是新的改进了。到现在为止，其他新型算法有灰狼，鱼群，细胞免疫，章鱼，布谷鸟，麻雀，天牛须。针对这些算法的改进机制也是百花齐放。不是优化想象能力低，是生物现象不够丰富。
想想这才是炼丹的真正境界吧，宇宙间万事万物都可以为我所用，从中发掘出一种优化算法。

rustum · 发表于 2021-7-4 06:59

如题，学习优化算法需要哪些数学知识？
需要学习的数学知识挺多的，基础的要学习线性代数、矩阵论、数值分析等教材，还可以看看凸优化、优化设计等相关书籍，当然还得具备一定的编程能力，因为在学习的过程中如果能实时仿真出来的话对于加深理解，增加学习效率是非常有帮助的。
优化是一个很广泛的概念，可以说在各个领域都有优化问题。
比如在机械学科中有零部件的结构优化、动力学优化、拓扑优化、有限元优化等，由于这些优化问题与很多因素有关，因此通常建模为多目标优化问题，可以通过交替优化法、智能算法、响应面方法和人工神经网络等方法来求解。
在计算机视觉、图像处理信号处理中，很多问题是非凸的，有些非凸优化问题可以直接求解，比如前几年很火的压缩感知，然而，也有很多非凸问题的求解很困难，在实际中一般将其放缩到凸优化问题来求解。凸问题的求解就有非常完备的理论体系，学习的话可以看看Nesterov那本凸优化教材。
在无线通信中，大部分是约束非凸优化问题，我见到的大部分的方法是将其松弛为半定规划(SDP)或二次约束二次规划问题(QCQP)，也有用压缩感知等来进行信道估计、信号检测、无线传感器网络优化等。
优化算法的话就有很多了，随便一举就有很多，比如梯度下降法、近端梯度法、共轭梯度法、牛顿迭代法、拟牛顿法、坐标下降法、模拟退火算法、遗传算法、粒子群算法等。现在机器学习中常用到的有随机梯度法、动量法、adam算法，近似消息传递算法等。
最后，我想分享一个微信公号：优化与算法。该算法适合于搞优化的工科本硕博朋友，里面的推文覆盖范围包括优化算法、机器学习、计算机视觉、图像处理、5G/6G前沿等技术领域，很多推文详细解释算法原理，并提供完整的仿真代码，可以说是干货满满，本人在学习过程中也受益良多。感兴趣的朋友可以关注一下。

Mecanim · 发表于 2021-7-4 07:07

谢邀，因为不懂电气。分享一下我学数据结构的精力。本科阶段我不是好学生，大二数据结构基本上没学过，但是课程设计有个机票预订管理系统。我想了一下，稍微高级一点肯定有个转机的问题。这里该如何计算呢？哪怕用本办法暴力破解似乎也无从下手，光看教程数据结构路径计算有Dijstra和Floyd算法，根本看不明白。原理不明白，数学也不明白，C代码更不明白。直到重新复习了线性代数，学习了人工智能路径计算和运筹学。当然因为算法是纯抽象纯数学的部分，和实际没有关联。
个人感觉题主面临的问题既包含数学层面也包含物理层面，如果是纯数学层面最大流，最短路径等图论方法能够解决。物理层面就需要仿真和实验了。能量优化更多类似参数调优这样的。既有工程数学拉丁方这样的快速设计方案的部分，也有更多物理测量层面的实时反馈，才能优化运行。

fwalker · 发表于 2021-7-4 07:15

优化算法分为很多种，例如梯度下降、牛顿法、演化算法等。具体到某一工程领域的时候就需要具体问题具体分析了。我本身不是电气工程专业，但勉强算是电气工程的兄弟专业。这里谈一下我对电气工程优化问题的观察。针对电气领域的优化问题，首先电气领域的相关知识是必不可少的；其次需要复杂网络的相关知识，复杂网络本身就是交叉学科的产物，学习它的过程中，就要求具有不低的线代、矩阵论基础；第三是控制论的相关知识，这里同时也包含一定地对复变函数的要求。另外据我的观察，电气领域好像演化算法，例如粒子群优化、模拟退火使用的多一些（存疑）。演化算法的学习就相对简单一些，本身并不需要很高的数学基础，属于拿过来就能用的工具，不过，同样地，根据不同的问题，要依据本专业的相关知识来设计进化算子，设计精巧的、高效的算子这一点应该是优化问题的难点所在了。

Ilingis · 发表于 2021-7-4 07:23

我就是想请问一下题主，在学习凸优化的时候，matlab的cvx的工具箱申请的许可证是直接用的学校的邮箱吗？我们学校没有授权，我想尽办法也没获得许可证

franciscochonge · 发表于 2021-7-4 07:29

一般convex optimization课里都会提到SGD，momentum，adam等算法。所以我稍微偏一点点，提点convex optimization的材料。
主要还是线代的东西居多，少量的概率和微积分。一学期下来感觉在干的事情就是不断迭代，然后考虑boundary能哪些条件下以多快的速度压到多低…
Stanford Engineering EverywhereEE364B - Convex Optimization II

non-convex optimization的东西就太杂了，不大好说。以后有机会上到了再补充。

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