软件X 11：基于梯度下降的优化问题的开放获取算法工具箱

软件X 11（2020）100371原始软件出版物OPTool-迭代算法丹尼尔·西尔维斯特澳门大学科技学院电子及电脑工程系、里斯本大学中国系统与机器人研究所（ISR）、澳门大学科技学院电子及电脑工程系、澳门大学系统与机器人研究所（ISR）、澳门大学系统与机器人研究所（ISR）。Rovisco Pais，1，1049-001 Lisboa，葡萄牙ar t i cl e i nf o文章历史记录：2019年7月31日收到收到修订版2019年10月28日接受2019年保留字：优化问题控制理论形式化类顺降算法a b st ra ct目前最先进的迭代优化算法的可微成本函数是分散在整个文献中，这阻碍了他们的比较，为具体的程序在手。根据不同的研究领域，理论上的最优参数和收敛速度在不同的配方。因此，该工具箱旨在为各种基于梯度下降的算法提供基准测试软件，并实现函数以尽可能返回最佳参数。研究人员可以专注于新算法的开发，并将其与文献中的算法进行测试，并在一个通用框架下提供。该软件的结构是定制的，使得新的贡献，可以很容易地通过一个功能的设计，实现一个单一的步骤的算法添加。在文献中的例子说明了易用性。©2019作者由爱思唯尔公司出版这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）中找到。代码元数据当前代码版本v1.2用于此代码版本的代码/存储库的永久链接https://github.com/ElsevierSoftwareX/SOFTX_2019_250法律代码许可证GNU GPL v3使用的代码版本控制系统无使用Matlab的软件代码语言、工具和服务编译要求，操作环境依赖只需将文件夹放在Matlab路径中如果可用，链接到开发人员文档/手册https://github.com/danielmsilvestre/OPTool/docs问题支持电子邮件dsilvestre@isr.tecnico.ulisboa.pt1. 动机和意义工程中的许多问题可以通过优化技术来解决。机器人路径规划、图像处理和碰撞检测等任务可以通过使用例如[1]中的工作来最小化受约束的函数来实现。计算PageRank，如[2]或者在无线传感器网络中的接入协议中实现去冗余化[3]也可以被看作是优化的解决方案。在文献中，有许多可能的算法和高效的求解器可供选择。为特定问题选择合适的解决方案是一项艰巨的任务电子邮件地址：dsilvestre@isr.tecnico.ulisboa.pt。https://doi.org/10.1016/j.softx.2019.100371因为它们不容易比较。例如，在[4]中，提出了一个工具箱来帮助用户根据成本函数和约束的特性选择应该使用的优化大多数算法在某些操作中使用步长参数或权重。上述软件不提供比较算法性能和选择这些参数的最佳值因此，拥有可以作为基准测试工具的软件至关重要。在[5]中，作者介绍了一种遵循相同原则的特征选择算法软件。代码结构以类似的方式设计，但集合的目标问题是不同的（特征选择与最小化功能），因此，实现的算法。作为对这项工作的补充，本文件的贡献可归纳为：2352-7110/©2019作者。由爱思唯尔公司出版这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表SoftwareX期刊主页：www.elsevier.com/locate/softx∇=∇−∇=2=2D. Silvestre / SoftwareX 11（2020）100371一个工具箱实现了最常见的算法，以更容易地比较它们的复杂性;基于控制理论结果的最优参数计算在本节的其余部分，我们介绍了主题的主要概念和科学背景。感兴趣的读者可以参考[2，3]，以获得有关优化算法设计的最新进展的参考资料，例如[6]中使用的积分二次约束（IQCs）。让x表示描述问题的变量，以及度量解决方案x的质量的成本函数f。我们希望选择x，使得f（x）的值是所有可能值中的最小值。优化被写为：其他方法可以在文献中找到。 在最优化求解器的范畴中：梯度下降、Heavy-ball、Nesterov、Momentum、快速迭代收缩阈值保持算法（FISTA）、下降快速迭代软阈值算法（DFISTA）、第二Nesterov、Barzilai-Borwein、随机下降、Cauchy-Barzilai-Borwein和 General Barzilai-Borwein 。 在 线 性 方 程 求 解 器 中 ， 实 现 了 ：Jacobi，加权Jacobi，尽量减少Xf（x）（1）方程（CGNE）和改进的双共轭梯度（IBiCG）。请参阅软件包文档中的参考和添加-在本文中，我们假设函数f是可微的，即，那里存在F。在这种情况下，获得分布式解决方案的常用算法，即，其中，状态x的部分被划分到不同的处理单元上，并被传送到它们的邻居，遵循梯度下降的思想，其中最有效的方法之一是Nesterov方法：梯度：x（k+1）=x（k）− βf（x（k））信息[8]。此外，由于大多数方法，例如（2）中的方法，具有诸如β和γ的参数，这些参数说明了被设计。为此，用户应该向求解器提供包含所有这些值或者，这些数据结构可以由专门为二次函数定制的函数getparameters（A，b，r，methods）x（k+1）=（k）− βf（（k））（二）形式f（x）=0的问题。5x<$Qx−p<$x+r，其中Q=A<$A涅斯捷罗夫：（k）=（1+γ）x（k）- γx（k−1）和pAb.如果在（2）中模拟这两种方法，则其中一个条目将具有一个结构，该结构具有用于其中β、γ是参数。在（2）中，x（k）是迭代k处的估计，f（x）是f在点x处的梯度，并且f（x）是计算动量项的内部变量。梯度算法是最简单的版本，其中新的估计对应于沿最陡下降方向的一步f（x（k））和a步长为β。Nesterov方法增加了一个由前两次迭代之差给出的动量项。其他实现的算法引入了遵循梯度给出的下降方向的思想的变体。本质上，收敛及其速度取决于β，γ的选择值。在适当的参数选择下，算法收敛到全局最小值，只要f是凸的。 当情况不是这样时，收敛发生在f 0，可以是最小值、最大值或鞍点。如果我们将函数f指定为二次函数，即，f（x）=1<$Mx−梯度下降，而数组的第二个条目将包含Nesterov方法的β和γ结构将参数计算与求解器任务分离后，用户可以将自己的数据结构传递给函数optSolver或linSolver，或者访问和更改函数getparameters给出的建议参数。变量方法包含标识用户要计算参数的算法的所有字符串。该软件还配备了quadSolver功能，可以执行模拟并将结果存储在文件中，从而节省了调用optSolver和或linSolver，如果用户正在使用这两个类的算法解决二次问题。2.1. 软件构架b*2，算法是线性的，2f是x的线性函数。在这个实现中，主要目标是产生一个尽可能简单和可扩展的代码，以便其他研究人员将问题解决为方程f（x）0的解，导致使用迭代算法来求解以下形式的线性方程的可能性Ax=b（3）对于一般函数f，可以采用非线性方程求解器，例如[7]中实现的非线性方程求解器。下一节详细介绍了OPTool的组织结构、算法和2. 软件描述OPTool工具箱实现了一个求解器，该求解器可以运行迭代算法的集合，前提是用户提供一个函数来获得给定当前迭代的下一次迭代。这是accom-plished通过传递一个单元数组的所有功能处理用户想比较在模拟。作为一个例子，如果用户有兴趣在（2）中运行梯度下降和Nesterov方法，则包含这两个函数句柄的单元数组将被传递给求解器。OPTool目前实现实现并测试他们的算法。因此，软件的架构由求解器（优化的线性方程）组成，该求解器接收：如最大迭代次数、初始状态、停止前的容差等;算法的参数和函数处理器到实现一次迭代的函数。软件架构如图所示。1.一、添加新算法需要两个步骤：（i）实现返回下一个近似解的值的函数，以及（ii）向getParameters添加与已实现算法类似的if子句，其中从（i）给出函数处理程序以及如何获得算法的最佳参数。不需要进行其他更改，因此有利于未来的发展由于求解器已经包含了执行投影或应用一般函数到下一个近似值，研究人员在其算法的行为中具有更大的自由度，并且可以将相同的变换应用于所有模拟方法，而不必校正提供每个算法的下一次迭代的函数的代码。··n联系我们n0−11 0···0n=：=∈⎣⎦n.D. Silvestre/SoftwareX 11（2020）1003713Fig. 1. OPTool架构。2.2. 软件功能OPTool软件由三个主要求解器功能组成：linSolver、optSolver和quadSolver。前两种算法分别用于求解线性方程组和一般优化算法.它们都接受实现每个算法的下一次迭代的函数处理程序的向量，以及描述要解决的问题的变量和其他模拟常数。quadSolver函数旨在为同一个二次问题调用linSolver和optSolver。在软件包中，两个文件夹线性方程求解器和优化算法存储的所有功能，为每一个实施，mented算法。如果用户想将软件扩展到自己设计的算法，他/她需要实现一个功能它提供了x的下一个估计。该软件的主要贡献是计算图二. 在20节点网络的PageRank情况下，每个测试算法的误差演变其中x（k）Rn且k0 1 <$x（k）1。PageRank问题也可以用公式表示为优化问题或线性方程的解。在前者中，PageRank是对以下优化问题的解决方案minimize1<$（（1−m）A−In）x+m1n<$2每种算法的最优参数，只要x2n2参 数 的 选 择 允 许 将 它 们 视 为 LTI 系 统 。为 此 ， 在OptimalParameters文件夹中有一个函数getParameters，它检索linSolver和optSolver所需的数据结构，并为每个算法调用返回其最佳参数的特定函数。其中一些是从文献中找到的表达式直接实现，而其他人则探索LTI视图。最后，辅助函数的文件夹实现了生成无标度对应网络拓扑的邻接矩阵、在单纯形上的投影和归一化为1（在PageRank示例中使用）的方法，以及基于规定的概率向量随机选择更新节点或计算谱半径的函数。网络生成遵循3. 说明性实例其对应于（1）中的格式。如果将其看作矩阵形式的线性方程的解，我们得到：（In−（1−m）A）x=m1n（ 6）对应于（3）中的线性方程视图。在[2]中，表明PageRank的标准幂方法等价于应用于（6）的Jacobi方法。随机Barabási-Albert生成的网络的PageRank的解决方案包含在OPTool中，工具箱产生的误差图如图所示。2，其中如果每个节点都知道最佳参数，则显示PageRank的更好替代方案。在无线传感器网络（ WSN ）的上下文中，在介质访问控制（MAC）层实现公平的多址接入调度的发射机的解扰可以例如使用时间同步信道跳跃（TSCH）来完成[10]。问题可以用公式[3]表示为（1）：搜索引擎是一种允许用户提供查询的工具尽量减少f（φ）：=1<$Dφ− v1+e2（七）以及获取与 到 的 信息 他们 正在寻找。这些工具的一个关键任务是某种等级-φ2n n2选择有意义的链接首先呈现的机制。最著名的算法之一是Google的PageRank，最初在[9]中提出，根据页面的相对重要性和链接数量对页面进行排名。其中φ是每个发射机的相位偏移，v =1/n，1n是1的向量，en=（0，0，. . .，0，1），以及⎡−1 1 0 0···0⎤⎢ ⎥每一个特定的页面。在[9]中，提出了排名是下面的矩阵M∈Rn×n的特征向量：nD=0。. ... ....（八）. ⎥M：=（1−m）A+mS（4）其中m（0，1）是定义邻接矩阵A与矩阵S1n1（1n是1的n一个典型的选择是m0的情况。15 [9]。标准公式可以通过以下公式有效地计算：Power方法：0···0 0−1 11··· 0 0 0− 1在这种情况下，考虑到D的非常特殊的结构，（3）中的线性方程观点产生了很差的结果。使用OPTool，在[3]中可以对梯度下降进行基准测试（相当于被称为脉冲耦合振荡器（PCO）的标准算法），与Nesterov和Gauss-Seidel算法相对x（k+1）=Mx（k）=（1−m）Ax（k）+m1n（五）将其误差绘制为迭代次数的函数，如图3.第三章。4D. Silvestre/SoftwareX 11（2020）100371两个出版物已经使用这个工具箱来产生他们的模拟和新的研究正在进行的电力网络，也将受益于该软件。有两个不同的团体-控制和优化-感兴趣– and is expected that OPTool can accelerate research in thistopic by facilitating an easy alternative (the other being eachindividual implementing the desired algorithms from scratch)来自Google的PageRank的情况被包括作为示例，其中该软件比较四种线性方程算法以表明，如果最佳参数已知，则连续过度松弛优于Jacobi方法，该Jacobi方法等效于当前用作解决排名问题的最先进算法的幂方法。未来的工作将集中在优化初始估计，以实现更快的收敛有趣的问题。将探索各种位置，即计算执行算法的LTI模型的范数作为初始图三. 20节点网络的基于PCO的Nesterov和Gauss-Seidel算法的误差范数的对数演化4. 影响如第3节所示，OPTool软件包允许提出问题，例如当前最先进的算法是否是解决给定问题的最佳算法，并比较其他解决方案。此外，它激励了这些算法作为LTI系统的研究，并将该领域的其他技术引入优化算法的设计，所有这些都可以通过简单地实现给出下一次迭代的函数和如何选择参数的函数来模拟。该软件已经被用于两个问题：[2]中的PageRank和[3]中的媒体访问控制中的解压缩。从电力网络到图像处理的许多其他问题都是未来可能的工作。目前，一阶优化算法的研究主要集中在快速算法和抗噪声能力上通过适当地添加下一次迭代函数，这些情况可以在工具箱中进行微小更改进行测试。由于该软件是在其第一个版本，它的使用一直相当有限的研究人员实现自己的模拟没有共享一个共同的平台。该工具箱旨在汇集社区的实施做法。5. 结论本文介绍了一个Matlab工具箱OPTool，它可以实现线性方程和优化算法的迭代求解。主要的重点是创建一个平台，通过将求解器代码与实现下一次迭代的函数分离，该平台可扩展到新的算法实现。我们已经证明，这些方法共享一个共同的解释，通过将它们视为来自控制理论的LTI或LTV系统，激励这个工具箱，其中输入是要优化的函数的梯度。借助于线性系统理论的标准技术，可以选择最佳参数，这些参数已添加到工具箱中状态致谢D. Silvestre获得了澳门大学MYRG 2016 -00097- FST项目的支持 ， 以 及 葡 萄 牙 Fun-dação para a Ciência e a Tecnologia（FCT）通过系统与机器人研究所（ISR）在机器人与工程系统实验室（LARSyS）项目UID/EEA/50009/2019下的支持。竞合利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作引用[1]Montanari M，Petrinic N. OpenGJK for C，C++和Matlab：三维空间中凸体 之 间 距 离 查 询 的 可 靠 解 决 方 案 。 SoftwareX 2018;7 ： 352-5.http://dx.doi.org/10.1016/j.softx.2018.10.002网站。[2]放大图片作者：Silvestre D，Hespanha J，Silvestre C.一种基于异步高斯-赛德尔迭代的PageRank算法。2018年度美国控制会议（ACC）。2018年，第484-9页。http://dx.doi.org/10.23919/ACC.2018的网站。8431212[3]放大图片作者：Silvestre D，Hespanha J，Silvestre C.基于Gauss-Seidel迭代的分散介质访问控制解扰。在：2019年美国控制会议（ACC）。2019年，第4049-54页。http://dx.doi.org/10的网站。23919/ACC.2019.8814471。[4]Popova O，Popov B，Romanov D，Evseeva M. Optimel：用于选择最佳方法 的 软 件 。 SoftwareX 2017;6 ： 231-6. http://dx.doi.org/10.1016/j 的 网 站 。softx.2017.08.001网站。[5]Reis MS，Estrela G，Ferreira CE，Barrera J.M.S.：特征选择算法和成本函数的基准标记框架。SoftwareX2017;6：193-7.http://dx.doi.org/10.1016/j.softx.2017.07.005网站。[6]Lessard L，Recht B，Packard A.积分二次约束优化算法的分析与设计。SIAMJ Optim 2016;26（1）：57-95. http://dx.doi.org/10.1137/15M1009597网站。[7]放 大 图 片 作 者 ： J. SIR-AN 高 效 求 解 方 程 组 。 SoftwareX 2018;7 ： 59-62.http://dx.doi.org/10.1016/j.softx.2018.01.003网站。[8]西尔维斯特湾OPTool-文档v1.2。https://github.com/danielmsilvestre/OPTool/blob/master/docs/optool-documentation.pdf。[9]Brin S，Page L.大规模超文本网络搜索引擎的剖析。计算机网络综合业务数字网系统1998;30（1）：107-17. http://dx.doi.org/10的网站。1016/S0169-7552（98）00110-X。[10]放大图片Tinka A，Watteyne T，Pister K. 一种时间同步跳频信道的分散调度算法。In：Zheng J，Simplot-Ryl D，Le-ung VCM，editors. Ad Hoc网络。Berlin，Heidelberg：Springer BerlinHeidelberg; 2010，p. 201-16