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

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

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



  

   三十三、伴随灵敏度分析

   伴随灵敏度分析可以避免冗余信息的计算,在下面的例子中,我们想要求解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} A1=U1L1,然后依次将b1~bm代入下式即可得到这一系列方程组的解

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

在这里插入图片描述

   但如果我们事先知道需要使用那些数据,那么我们能不能仅把需要使用的变量求出来?比如我们的目标是求每个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=cTA1bi=biTATc

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

在这里插入图片描述

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

   假设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} dpjdgdpdg=pjg+i=1Nxigpjxi=gp+gxxp

在这里插入图片描述

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

   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}] Apjx+Axpj=bpjxpj=A1[bpjApjx]

在这里插入图片描述

在这里插入图片描述

   我们使用矩阵相乘交换顺序的思想,把解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

相关文章

Vue3 的 shallowRef 和 shallowReactive:优化性能

大家对 Vue3 的 ref 和 reactive 都很熟悉,那么对 shallowRef 和 shallowReactive 是否了解呢? 在编程和数据结构中,“shallow”(浅层)通常指对数据结构的最外层进行操作,而不递归地处理其内部或嵌套的数据。这种处理方式关注的是数据结构的第一层属性或元素,而忽略更深层次的嵌套内容。 1. 浅层与深层的对比 1.1 浅层(Shallow) 定义

基于人工智能的图像分类系统

目录 引言项目背景环境准备 硬件要求软件安装与配置系统设计 系统架构关键技术代码示例 数据预处理模型训练模型预测应用场景结论 1. 引言 图像分类是计算机视觉中的一个重要任务,目标是自动识别图像中的对象类别。通过卷积神经网络(CNN)等深度学习技术,我们可以构建高效的图像分类系统,广泛应用于自动驾驶、医疗影像诊断、监控分析等领域。本文将介绍如何构建一个基于人工智能的图像分类系统,包括环境

HDFS—存储优化(纠删码)

纠删码原理 HDFS 默认情况下,一个文件有3个副本,这样提高了数据的可靠性,但也带来了2倍的冗余开销。 Hadoop3.x 引入了纠删码,采用计算的方式,可以节省约50%左右的存储空间。 此种方式节约了空间,但是会增加 cpu 的计算。 纠删码策略是给具体一个路径设置。所有往此路径下存储的文件,都会执行此策略。 默认只开启对 RS-6-3-1024k

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题,本文将一起从代码层去分析为什么没有建立索引? 开源ERP项目地址:https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置

使用opencv优化图片(画面变清晰)

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化,使其看起来更清晰,同时保持尺寸不变,通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多,主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器:相机传

便携式气象仪器的主要特点

TH-BQX9】便携式气象仪器,也称为便携式气象仪或便携式自动气象站,是一款高度集成、低功耗、可快速安装、便于野外监测使用的高精度自动气象观测设备。以下是关于便携式气象仪器的详细介绍:   主要特点   高精度与多功能:便携式气象仪器能够采集多种气象参数,包括但不限于风速、风向、温度、湿度、气压等,部分高级型号还能监测雨量和辐射等。数据采集与存储:配备微电脑气象数据采集仪,具有实时时钟、数据存

MySQL高性能优化规范

前言:      笔者最近上班途中突然想丰富下自己的数据库优化技能。于是在查阅了多篇文章后,总结出了这篇! 数据库命令规范 所有数据库对象名称必须使用小写字母并用下划线分割 所有数据库对象名称禁止使用mysql保留关键字(如果表名中包含关键字查询时,需要将其用单引号括起来) 数据库对象的命名要能做到见名识意,并且最后不要超过32个字符 临时库表必须以tmp_为前缀并以日期为后缀,备份

软件设计师备考——计算机系统

学习内容源自「软件设计师」 上午题 #1 计算机系统_哔哩哔哩_bilibili 目录 1.1.1 计算机系统硬件基本组成 1.1.2 中央处理单元 1.CPU 的功能 1)运算器 2)控制器 RISC && CISC 流水线控制 存储器  Cache 中断 输入输出IO控制方式 程序查询方式 中断驱动方式 直接存储器方式(DMA)  ​编辑 总线 ​编辑

SWAP作物生长模型安装教程、数据制备、敏感性分析、气候变化影响、R模型敏感性分析与贝叶斯优化、Fortran源代码分析、气候数据降尺度与变化影响分析

查看原文>>>全流程SWAP农业模型数据制备、敏感性分析及气候变化影响实践技术应用 SWAP模型是由荷兰瓦赫宁根大学开发的先进农作物模型,它综合考虑了土壤-水分-大气以及植被间的相互作用;是一种描述作物生长过程的一种机理性作物生长模型。它不但运用Richard方程,使其能够精确的模拟土壤中水分的运动,而且耦合了WOFOST作物模型使作物的生长描述更为科学。 本文让更多的科研人员和农业工作者