机器人中的数值优化（二十一）—— 伴随灵敏度分析、线性方程组求解器的分类和特点、优化软件

2023-10-10 02:45
文章标签 分析 特点 优化 分类 软件 机器人 数值 线性方程组 求解 二十一 灵敏度 伴随

本文主要是介绍机器人中的数值优化（二十一）—— 伴随灵敏度分析、线性方程组求解器的分类和特点、优化软件，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

   本系列文章主要是我在学习《数值优化》过程中的一些笔记和相关思考，主要的学习资料是深蓝学院的课程《机器人中的数值优化》和高立编著的《数值最优化方法》等，本系列文章篇数较多，不定期更新，上半部分介绍无约束优化，下半部分介绍带约束的优化，中间会穿插一些路径规划方面的应用实例

  

   三十三、伴随灵敏度分析

   伴随灵敏度分析可以避免冗余信息的计算，在下面的例子中，我们想要求解Ax=b1、Ax=b2 … Ax=bm等一系列方程组，第一种求解思路是将A矩阵进行LU分解, A = L U A=LU A=LU，求逆后可得到 A − 1 = U − 1 L − 1 A^{-1}=U^{-1}L^{-1} A−1=U−1L−1,然后依次将b1~bm代入下式即可得到这一系列方程组的解

   x i = U − 1 L − 1 b i x_i=U^{-1}L^{-1}b_i xi​=U−1L−1bi​

在这里插入图片描述

   但如果我们事先知道需要使用那些数据，那么我们能不能仅把需要使用的变量求出来？比如我们的目标是求每个xi的平均值ai，比如所有x1的平均值a1，那么我们是不是不需要求出每个xi的具体值，而仅仅需要他们的平均值ai。

   a i = c T x i = c T A − 1 b i = b i T A − T c a_{i}=c^{T}x_{i}=c^{T}A^{-1}b_{i}=b_{i}^{T}A^{-T}c ai​=cTxi​=cTA−1bi​=biT​A−Tc

   之前需要先算 A − 1 b i A^{-1}b_{i} A−1bi​ 部分，再算 c T A − 1 b i c^TA^{-1}b_i cTA−1bi​,现在可以先算 A − T c A^{-T}c A−Tc,再算 b i T A − T c b_i^TA^{-T}c biT​A−Tc，我们不需要对每个bi求一个线性方程组了，仅需要求一个方程组 q ≡ A − T c q\equiv A^{-T}c q≡A−Tc，求出 q q q之后，再与bi做一个点积即可， a i = b i T q a_i=b_i^Tq ai​=biT​q

在这里插入图片描述

   伴随灵敏度分析的思想是在计算矩阵相乘的时候考虑那个先乘，那个后乘。线性方程组有一个伴随线性方程组，伴随灵敏度分析允许优化一小部分设计参数，而不是全部参数。

   假设x是一个线性方程组的解，它的维度很大，它是一个完备的参数，从x可以获得所有我们想要的信息，但我们不能直接处理这么大维度的优化，我们需要设一组设计参数 p = ( p 1 , p 2 , . . . , p M ) \mathbf{p}=(p_{1},p_{2},...,p_{M}) p=(p1​,p2​,...,pM​)，我们要算的是一些目标函数 g ( p , x ) g(\mathbf{p},\mathbf{x}) g(p,x)关于参数 p 1 , p 2 , … , p M p_{1},p_{2},\ldots,p_{M} p1​,p2​,…,pM​的梯度

   d g d p j = ∂ g ∂ p j + ∑ i = 1 N ∂ g ∂ x i ∂ x i ∂ p j d g d p = g p + g x x p \begin{aligned}\frac{dg}{dp_j}&=\frac{\partial g}{\partial p_j}+\sum_{i=1}^N\frac{\partial g}{\partial x_i}\frac{\partial x_i}{\partial p_j}\\\\\frac{dg}{d\mathbf{p}}&=g_\mathbf{p}+g_\mathbf{x}\mathbf{x_p}\end{aligned} dpj​dg​dpdg​​=∂pj​∂g​+i=1∑N​∂xi​∂g​∂pj​∂xi​​=gp​+gx​xp​​

在这里插入图片描述

   一般认为 ∂ g ∂ p j 和 ∂ g ∂ x i \frac{\partial g}{\partial p_j}和\frac{\partial g}{\partial x_i} ∂pj​∂g​和∂xi​∂g​是容易获得的， ∂ x i ∂ p j \frac{\partial x_{i}}{\partial p_{j}} ∂pj​∂xi​​是不知道的

   A p j x + A x p j = b p j ⇒ x p j = A − 1 [ b p j − A p j x ] A_{p_j}\mathbf{x}+A\mathbf{x}_{p_j}=b_{p_j}\quad\Rightarrow\quad\mathbf{x}_{p_j}=A^{-1}[b_{p_j}-A_{p_j}\mathbf{x}] Apj​​x+Axpj​​=bpj​​⇒xpj​​=A−1[bpj​​−Apj​​x]

在这里插入图片描述

在这里插入图片描述

   我们使用矩阵相乘交换顺序的思想，把解m次 N 2 N^2 N2复杂度的方程组，转换为解一次就可以了

在这里插入图片描述

   应用示例一：

在这里插入图片描述

   应用示例二：

   当路径上选取的优化点变密集后，安全性会更好，那么我们能不能，不选取那么多的优化点，而同样使其有较好的安全性

在这里插入图片描述

   对于任意阶样条，我们可以解耦线段的数目和约束的数目。所有的路径点和持续时间都是我们轨迹的设计参数(决策变量)。样条系数是由路点确定的线性方程组的解。

   A ( T ) c ( p , T ) = b ( p ) \mathbf{A(T)c(p,T)=b(p)} A(T)c(p,T)=b(p)

   A和b构成了样条系数的线性方程组。这很自然地符合伴随敏感性分析的模型。

在这里插入图片描述

   三十四、线性方程组求解器的分类和特点

在这里插入图片描述

   线性方程组求解器可分为两大类或三小类，两大类即直接求解和迭代求解，直接求解可以得到Ax=b的精确解，迭代求解随着迭代次数的增多，所得到的近似解与精确解的误差也逐渐减小。三小类是因为有的求解器会利用矩阵的稀疏结构，而有的求解器不利用，因此，直接法又分为稠密法和稀疏直接法。

   （1）稠密法

   具有简单数据结构，不需要索引数据结构等特殊的数据结构，采用矩阵的直接表示，主要是O(N3)分解算法

   （2）稀疏直接法

   当矩阵中有很多0元素时，我们可以仅储存非0元素的位置和具体的值，使其占较少的内存。

   因子分解成本取决于问题结构（1D低成本；2D可接受成本；3D高成本；不容易给出一般规则，NP难以排序以获得最佳稀疏性）

   （3）迭代法

   迭代求取近似解，仅需要知道 y = A x ( m a y b e y = A T x ) y=Ax\mathrm{~(maybe~}y=A^Tx) y=Ax (maybe y=ATx)，良好的收敛性取决于预条件。

在这里插入图片描述

–

   当我们求解Ax=b时，如果是稠密的矩阵，尽可能的根据矩阵的对称性、半正定性、带状结构等特点，以此来挑选不同的稠密求解器，比如使用LAPACK/ScaLAPACK库，或者Eigen库

在这里插入图片描述

   若，我们知道矩阵的非零元素比零元素少很多，可以选用稀疏直接法中的求解器，看看能不能提前把矩阵预分解

在这里插入图片描述

   如果问题比较大，如 1 0 5 10^5 105，此时采用稠密法会有问题，可以用CG方法处理正定对称矩阵，还有一系列迭代法可以处理对称不定或非对称的矩阵。

在这里插入图片描述

   因式分解有很多种方法，比如

   L U , L L T / L L H , L D L T / L D L H , Q R , L Q , Q R Z , generalized QR and RQ \begin{aligned}LU,LL^T /LL^H,LDL^T/LDL^H,QR,LQ,QRZ,\end{aligned}\text{generalized QR and RQ} LU,LLT/LLH,LDLT/LDLH,QR,LQ,QRZ,​generalized QR and RQ

   除了因式分解，还有对称/Hermitian和非对称特征值、奇异值分解、广义特征值与奇异值分解

在这里插入图片描述

   LU分解其实就是高斯消元法，把一个矩阵进行高斯消元，进行一些行变换

   A = P L U A=PLU A=PLU

在这里插入图片描述

   稀疏LU分解法不仅需要做行变换，还需要做列变换。

在这里插入图片描述

   Cholesky分解：

在这里插入图片描述

   稀疏Cholesky分解：

在这里插入图片描述

   LDL分解：

在这里插入图片描述

   稀疏矩阵：

在这里插入图片描述

在这里插入图片描述

   稀疏矩阵分解：

在这里插入图片描述

   稀疏排序会对虚实化的稀疏性产生巨大的影响：

在这里插入图片描述

   选择产生最小二乘分解的排序的一般问题是困难的，但是，几个简单的启发式方法是非常有效的。例如嵌套排序方法，可以起作用。

在这里插入图片描述

在这里插入图片描述

   迭代法：

在这里插入图片描述

   三十五、优化软件

   1、swMATH

   里面包含优化、线性代数、大规模矩阵运算等丰富的资源

   链接：https://zbmath.org/software/

在这里插入图片描述

   2、gamsworld

   gamsworld收录了很多的工具，在这里可以找到锥规划等性能测评的手段

   链接：https://gamsworld.org/

   链接：https://github.com/GAMS-dev/gamsworld

在这里插入图片描述

   3、DECISION TREE FOR OPTIMIZATION SOFTWARE

   可以根据优化问题的结构，查找某个问题有哪些现有的方案

   链接：http://plato.asu.edu/guide.html

在这里插入图片描述

   4、Mathematical Software

   里面包含优化、非线性求解器等丰富的资源

   链接：https://arnold-neumaier.at/software.html

在这里插入图片描述

   5、neos solvers

   neos solvers是比较有名的求解器

   链接：https://neos-server.org/neos/solvers/index.html

在这里插入图片描述

   6、netlib

   里面几乎包含所有的线性求解办法

   链接：https://netlib.org/

在这里插入图片描述

   7、GAMS

   里面包含一些数学库，不仅仅是优化

   链接：https://gams.nist.gov/

在这里插入图片描述

   8、HSL Software

   专门的线性方程组求解器，包含很多源代码

   链接：https://www.hsl.rl.ac.uk/catalogue/

在这里插入图片描述

   9、autodiff

   收集了一些求微分的方法的网站

   链接：https://www.autodiff.org/

在这里插入图片描述

   10、Local Optimization Software

   链接：https://arnold-neumaier.at/glopt/software_l.html

在这里插入图片描述

   11、Global Optimization Software

   链接：https://arnold-neumaier.at/glopt/software_g.html

在这里插入图片描述

   参考资料：

   1、数值最优化方法（高立 编著）

   2、机器人中的数值优化

这篇关于机器人中的数值优化（二十一）—— 伴随灵敏度分析、线性方程组求解器的分类和特点、优化软件的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/177384。

相关文章

MySQL索引的优化之LIKE模糊查询功能实现

MySQL索引的优化之LIKE模糊查询功能实现

《MySQL索引的优化之LIKE模糊查询功能实现》：本文主要介绍MySQL索引的优化之LIKE模糊查询功能实现,本文通过示例代码给大家介绍的非常详细,感兴趣的朋友一起看看吧... 目录一、前缀匹配优化二、后缀匹配优化三、中间匹配优化四、覆盖索引优化五、减少查询范围六、避免通配符开头七、使用外部搜索引擎八、分
阅读更多...
Java程序进程起来了但是不打印日志的原因分析

Java程序进程起来了但是不打印日志的原因分析

《Java程序进程起来了但是不打印日志的原因分析》：本文主要介绍Java程序进程起来了但是不打印日志的原因分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java程序进程起来了但是不打印日志的原因1、日志配置问题2、日志文件权限问题3、日志文件路径问题4、程序
阅读更多...
Java字符串操作技巧之语法、示例与应用场景分析

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字
阅读更多...
Python 迭代器和生成器概念及场景分析

Python 迭代器和生成器概念及场景分析

《Python迭代器和生成器概念及场景分析》yield是Python中实现惰性计算和协程的核心工具,结合send()、throw()、close()等方法,能够构建高效、灵活的数据流和控制流模型,这... 目录迭代器的介绍自定义迭代器省略的迭代器生产器的介绍yield的普通用法yield的高级用法yidle
阅读更多...
C++ Sort函数使用场景分析

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序
阅读更多...
Python通过模块化开发优化代码的技巧分享

Python通过模块化开发优化代码的技巧分享

《Python通过模块化开发优化代码的技巧分享》模块化开发就是把代码拆成一个个“零件”,该封装封装,该拆分拆分,下面小编就来和大家简单聊聊python如何用模块化开发进行代码优化吧... 目录什么是模块化开发如何拆分代码改进版：拆分成模块让模块更强大：使用 __init__.py你一定会遇到的问题模www.
阅读更多...
SpringBoot首笔交易慢问题排查与优化方案

SpringBoot首笔交易慢问题排查与优化方案

《SpringBoot首笔交易慢问题排查与优化方案》在我们的微服务项目中,遇到这样的问题：应用启动后,第一笔交易响应耗时高达4、5秒,而后续请求均能在毫秒级完成,这不仅触发监控告警,也极大影响了用户体... 目录问题背景排查步骤1. 日志分析2. 性能工具定位优化方案：提前预热各种资源1. Flowable
阅读更多...
kotlin中const 和val的区别及使用场景分析

kotlin中const 和val的区别及使用场景分析

《kotlin中const和val的区别及使用场景分析》在Kotlin中,const和val都是用来声明常量的,但它们的使用场景和功能有所不同,下面给大家介绍kotlin中const和val的区别,... 目录kotlin中const 和val的区别1. val:2. const:二 代码示例1 Java
阅读更多...
SpringBoot3实现Gzip压缩优化的技术指南

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N
阅读更多...
Go标准库常见错误分析和解决办法

Go标准库常见错误分析和解决办法

《Go标准库常见错误分析和解决办法》Go语言的标准库为开发者提供了丰富且高效的工具,涵盖了从网络编程到文件操作等各个方面,然而,标准库虽好,使用不当却可能适得其反,正所谓工欲善其事,必先利其器,本文将... 目录1. 使用了错误的time.Duration2. time.After导致的内存泄漏3. jsO
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2