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

2024-07-22

[摘要] 比如电气工程领域的优化控制，能量优化管理，系统优化运行等方面。答主从事电力系统优化方向，从应用的角度谈一下优化算法吧。优化问题可以分成凸（convex）问题和非凸问题。凸问题都是可以找到最优解的，只是算力问题，小问题可以用现有的解法器非常快的找到最优解，大型问题则一般要用一些定制的分解算法。非凸问题

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

答主从事电力系统优化方向，从应用的角度谈一下优化算法吧。

优化问题可以分成凸（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写的最好。

首先不太明白题主问题和下面的补充说明“比如”是什么关系？下面列那些明显不是学习优化算法需要的数学基础啊？题主意思是不是说你学习优化算法重点关注的最终应用领域？一个强调数学基础，一个强调具体应用，题主到底重点在那里？建议修改题目或说明。

我就从字面上大体回答一下问题标题。一般研究生水平主要需要的数学基础大体就是分析学相关，线性代数相关，数值分析相关，一点点拓扑相关，统计和机器学习相关，和计算科学基础相关。

这些都是内功心法，最后应用到哪里其实关系不大，目前并没有什么算法大类是只用于电力系统或一定不用于电力系统或明显在电力系统获得更多青睐的。

讲电力系统流行的话，可以多看二阶锥等凸优化、凸松弛方法，和人工智能相关的方法（包括随机梯度、动态规划、强化学习、贝叶斯优化、一些大尺度优化算法这些），ADMM这种可以分布式支撑并行的方法，还有模型预测控制这种突出不确定性处理能力和工程可操作性的方法，等等。

内功心法和行业熟悉度到位了，上面这些其实不需要知乎来告诉你。多看同行论文，你会比回答这个问题的大部分人了解现状。

如题，学习优化算法需要哪些数学知识？

需要学习的数学知识挺多的，基础的要学习线性代数、矩阵论、数值分析等教材，还可以看看凸优化、优化设计等相关书籍，当然还得具备一定的编程能力，因为在学习的过程中如果能实时仿真出来的话对于加深理解，增加学习效率是非常有帮助的。

优化是一个很广泛的概念，可以说在各个领域都有优化问题。

比如在机械学科中有零部件的结构优化、动力学优化、拓扑优化、有限元优化等，由于这些优化问题与很多因素有关，因此通常建模为多目标优化问题，可以通过交替优化法、智能算法、响应面方法和人工神经网络等方法来求解。

在计算机视觉、图像处理信号处理中，很多问题是非凸的，有些非凸优化问题可以直接求解，比如前几年很火的压缩感知，然而，也有很多非凸问题的求解很困难，在实际中一般将其放缩到凸优化问题来求解。凸问题的求解就有非常完备的理论体系，学习的话可以看看Nesterov那本凸优化教材。

在无线通信中，大部分是约束非凸优化问题，我见到的大部分的方法是将其松弛为半定规划(SDP)或二次约束二次规划问题(QCQP)，也有用压缩感知等来进行信道估计、信号检测、无线传感器网络优化等。

优化算法的话就有很多了，随便一举就有很多，比如梯度下降法、近端梯度法、共轭梯度法、牛顿迭代法、拟牛顿法、坐标下降法、模拟退火算法、遗传算法、粒子群算法等。现在机器学习中常用到的有随机梯度法、动量法、adam算法，近似消息传递算法等。

最后，我想分享一个微信公号：优化与算法。该算法适合于搞优化的工科本硕博朋友，里面的推文覆盖范围包括优化算法、机器学习、计算机视觉、图像处理、5G/6G前沿等技术领域，很多推文详细解释算法原理，并提供完整的仿真代码，可以说是干货满满，本人在学习过程中也受益良多。感兴趣的朋友可以关注一下。

题外话就是，优化本身就是数学的一个分支，所以其本身就是数学基础，而且用到的其他数学基础的知识不多。

优化一般需要高数和线性代数的知识，尤其是线代的知识。我先介绍一下重点需要了解的知识。但是其实用到的地方不多。高数主要是利用导数和微分求解梯度，利用泰勒展开(多维)对目标函数进行估计，利用极限计算收敛速度。线性代数更重要一点，因为优化的研究对象一般是多变量函数，多变量及关系式可以用向量和矩阵表示。所以要熟悉向量和矩阵的计算。其中最重要的是向量和矩阵导数的计算(矩阵乘法，向量和矩阵求导)，特别需要关注的是梯度（向量的一阶导）和Hessian矩阵（向量的二阶导）的计算。这个要特别熟悉，因为大多数优化算法通过计算梯度获取一个搜索方向，然后沿着搜索方向不断迭代找到最优解。矩阵向量计算中最重要的一些概念就是：标量函数关于向量的导数，向量函数关于标量的导数，向量函数关于向量的导数，矩阵的导数等。

学习优化理论的书籍英文书有两本，Stephen Boyd 的 Convex Optimization和剑桥出版社的Numerical Optimization. 前一本书更加偏向介绍基础理论，配合Boyd大佬的公开课可以更好的学习（网易公开课和B站搜作者应该就可以了）推荐可以从这本书和教学视频入门。。后一本书更加偏向算法实现层面，更加丰富，不仅仅限于凸优化，而且给出了很多种优化算法及其改进的伪代码。里面的算法没必要全部都学，遇到需要解决的问题的时候就可以翻阅选择其中合适的算法。中文书可以看袁亚湘院士的《最优化理论与算法》，这里面提到了一些线性规划和整数规划，也许在研究实际问题中更重要。这些书的附录里面一般都会给出涉及到的高数和线代知识。所以没必要再全部去重温高数和线代课本。

优化是的实践性很强，而且不像其他数学那样很多公式。算法和理论学会之后，更重要的是怎么去根据实际问题构建相应的目标函数，并选用合适的算法去求解。学习优化最好的方法就是搞清楚理论之后，根据伪代码手撸一遍，这样才会清楚目标函数的形式应该是什么样，算法中每个参数的意义是什么，算法怎么样一步一步求得最优解。

如果你是想要研究优化解决诸如交通规划，金融分析，电力优化，可以按照上述流程学习。但如果是搞深度学习的话，那就没必要这么复杂，直接参考花书《Deep Learning》中的优化部分即可。其实深度学习的本质也可以看做是求解一个优化问题。只不过深度学习更关注的是利用网络结构构建一个目标函数模型，优化并不是最重要的部分。而且由于深度学习模型参数（即优化里的自变量维度）太多，很难找到真正的最优解，基本上只用了最简单的一些优化方法（随机梯度下降，Adam等）。

---------------分割线，以下为故事会内容-----------

最后，再介绍一个有趣的方向。大家一直认为深度学习是炼丹，调一些网络结构和参数就能的到好的效果，但是并不了解其中的原理。深度学习的炼丹还只是炼丹的小儿科。优化也有一个门类，叫智能优化算法。这些算法可以不在乎目标函数的形式（甚至不需要数学表达式），只要能给出自变量和因变量的一个映射关系，即一个黑箱子，我们就可以进行优化。其中经典的有模拟退火，遗传算法，粒子群算法，蚁群算法等。当科学家发现可以这么求解以后，真正的炼丹开始了。首先是跟深度学习一样，先调一调控制这些算法的超参数，然后是自适应地调节参数，再是自适应地调节自适应参数（此处可以套娃）。接下来是更改各种算法的流程，加入新的迭代机制。随后科学家们根据前面算法的研究过程，观察生物作出最优选择背后的原理，发掘出新的算法。例如从蜜蜂修筑蜂巢的行为发掘出蜂群算法。自从这个大门打开以后，智能优化像打开了了潘多拉盒子一样，各种新的算法层出不穷，科学家们绞尽脑汁水论文，基本上世界上的任何生物现象都可以研究出一种优化算法。然后每种算法可以跟以前改进一样再来一遍，又可以研究出很多改进算法。最流氓的是，几种算法排列组合一起就又是新的改进了。到现在为止，其他新型算法有灰狼，鱼群，细胞免疫，章鱼，布谷鸟，麻雀，天牛须。针对这些算法的改进机制也是百花齐放。不是优化想象能力低，是生物现象不够丰富。

想想这才是炼丹的真正境界吧，宇宙间万事万物都可以为我所用，从中发掘出一种优化算法。

沙丁鱼优化算法(Sardine optimization algorithm,SOA)由Zhang HongGuang等人于2023年提出，该算法模拟沙丁鱼的生存策略，具有搜索能力强，求解精度高等特点。

沙丁鱼主要以浮游生物为食，这些生物包括细菌、腔肠动物、软体动物、原生动物、十足目、幼小藤壶、鱼卵、甲藻、桡足类等。沙丁鱼的季节饵料组成会随着水文条件的变化而改变。在上升流剧烈的时期，饵料组成以浮游植物为主；而在上升流微弱的时期，饵料组成则以浮游动物为主。沙丁鱼是一种滤食动物，它们通过鳃过滤海水，捕获通过鳃的浮游生物。此外，沙丁鱼拥有一双透镜眼，这极大地提高了它们的视力和图像亮度，因此它们能够利用视力追踪在水中过滤的猎物。除了像大多数鱼类一样借助快速的游动逃避捕食者外，沙丁鱼还利用群体行为来躲避捕猎者。例如，当遇到捕食沙丁鱼的海豚时，沙丁鱼会聚成大群来对抗海豚的捕食。在没有外部威胁或障碍物时，鱼群通常会聚成接近球形的形态，以便协同躲避。

参考文献：

[1]Zhang, H., Tang, M., Liu, Y. et al. Sardine Optimization Algorithm with Agile Locality and Globality Strategies for Real Optimization Problems. Arab J Sci Eng 48, 9787–9825 (2023). https://doi.org/10.1007/s13369-022-07350-y

微电网优化模型介绍：

微电网多目标优化调度模型简介_IT猿手的博客-CSDN博客

close all;
clear ; 
clc;
global P_load; %电负荷
global WT;%风电
global PV;%光伏
%%
TestProblem=1;
[lb,ub,dim,fobj]=GetFunInfo(TestProblem);
SearchAgents_no=50; % Number of search agents
Max_iteration=50; % Maximum number of iterations
[Xbest,Best_score,Convergence_curve]=SOA(SearchAgents_no,Max_iteration,lb,ub,dim,fobj);


%% 画结果图
figure(1)
semilogy(Convergence_curve,'b-','linewidth',2);
legend('SOA');
xlabel('迭代次数')
ylabel('运行成本与环境保护成本之和')