精华内容
下载资源
问答
  • 非线性优化

    2019-08-16 17:14:37
    非线性优化 非线性优化与最小二乘的关系见:非线性最小二乘 非线性优化问题又有那些要素呢 非线性优化一般采用迭代的方法,认为估计问题是一个凸函数(初值很重要),通过迭代增量参数X,不断使残差平方和最小.直到,...

    非线性优化

    非线性优化与最小二乘的关系见:非线性最小二乘
    非线性优化问题又有那些要素呢

    非线性优化一般采用迭代的方法,认为估计问题是一个凸函数(初值很重要),通过迭代增量参数X,不断使残差平方和最小.直到,增量X小到一定程度(因为假设凸函数,凸函数在接近极值的地方,导数很小)时,或达到迭代次数时,结束.(注:迭代停止跟整个残差平方的值达到什么程度无关)

    增量DX

    添加一个增量使得||f(Xk+DXk)||2最小.即在参数上添加一个增量使得残差平方和减小.
    因此参数估计问题成了每次迭代增量Dx怎么取的问题.
    解Dx的方法有很多,最快速,牛顿法.
    有代表性的是高斯牛顿法.
    线搜索方法和LM算法都是高斯牛顿法的变形.

    稀疏与矩阵求逆

    有些参数只和少量观测值相关,且有时观测量非常非常多,这就导致求解Dx算法中求H矩阵的逆变的困难,通常是将其看成稀疏矩阵,用QR或者Cholesky方法求逆.

    非线性优化(梯度下降)的求解过程

    俗话说,饭得一口一口吃,不能一口吃个胖子。这里要注意的一点就是,虽然我们不能直接找到函数值为最小点。但是,非线性函数的导数是存在的,也就可以计算出每一点的导数。也就是说,既然不能直接找到极值点,我们就应该一步一步的逐渐逼近函数的极值点。​

    我们将原问题找f(x)的最小值(此处x为n维向量,不是一维的),变为找到f(x+Δx)的最小值,再依此迭代多次,逼近f(x)的最小值。此时,x变为已知,而未知是Δx的大小(当然也可以理解为方向,因为n维向量表示了一个方向)。也就是说,我们希望找到一个Δx,使得函数f(x+Δx)在点x处取得最小值。那么,一个自然的想法就是将f(x+Δx)对Δx求导,再另f’(x+Δx)=0就可以找到Δx的值。然而,这其实又回到了上面说的问题,即求f’(x+Δx)=0和f’(x)=0是一样不可求的。那么怎么办呢?​

    这就要祭出一个大杀器——泰勒级数展开​(有人称为线性化,其实不太准确。在一阶泰勒的情况下却是是线性的,但是如果加了高阶则不是线性了。)

    泰勒展开提供了求解函数梯度的方法,得到了梯度之后,通过最快速,高斯牛顿等方法,就可以计算出每次迭代的步长

    非线性优化到底在研究什么?​

    说到这里,你可能会疑惑,既然非线性优化好像通过上面的方法都可以求解,那么为什么还有那么多数学家在研究这个问题。或者说,是不是世间所有问题,都可以通过这个方法求解呢?要想回答这个问题,我们需要重新来审视一下上面的求解过程。​

    (1)其实这个过程有个重要的前提,那就是f(x)是连续可导。如果f(x)这个函数不可导,或者不可微呢?比如说,在SLAM中需要处理姿态估计的问题。而姿态是通过旋转矩阵和平移向量表示的,这显然是不连续的。但是,由于旋转矩阵是一个李群,那么我们可以将其映射到其李代数上。而且,李代数是可以求导的。所以我们就还可以利用非线性优化的方法对姿态进行估计。也就是说对于不连续的函数,我们可以想办法将其变得连续,从而继续用这种方法。​

    (2)上面的解法求得的只是局部最优解,而不能确定是否是全局最优解。因为,这种方法可以说是一种“近视眼”的方法,它只看到下一时刻,在邻域内的最小值,而不能全局的寻找。所以,很容易陷入到局部最优中,或者说最终求出的最优值是跟初始位置极度相关的。即使初始值在同一个未知,也很有可能落入到两个不同的局部最优值中,也就是说这个解是很不稳定的。所以,如何解决这个问题,至今仍然存在很大的挑战。​​

    比如凸优化就可以在一定程度上解决这个问题。凸优化的思想是,如果局部最优就是全局最优,就不存在这个问题了。那么如何将一个非凸的问题转换成凸的呢?或者什么问题就是凸的,什么是非凸的呢?​​

    在此,只是粗浅的举了两个例子,其实非线性优化中存在的问题还有很多很多。而且我们在这里只讨论了无约束的情况,而优化问题真实情况往往是存在对变量的约束的。本文只是希望破除我们心中对非线性优化的恐惧,勇敢的迈进非线性优化这道大门。

    参考:https://blog.csdn.net/yu132563/article/details/81239276

    展开全文
  • matlab 非线性优化问题你的目标函数变量是10个,约束函数中变量是12个,这是不允许的。另外,约束函数中的for循环有问题。非线性最优化的不同算法各适用于什么情况1 无约线性最优化问题常用算法:梯度下降法)、共轭...

    matlab 非线性优化问题

    6dc7148e5a19f0320fcdc0fea4370786.png

    你的目标函数变量是10个,约束函数中变量是12个,这是不允许的。另外,约束函数中的for循环有问题。

    非线性最优化的不同算法各适用于什么情况

    42e8cebb3d55e7cb1cfa84ead44ed134.png

    1 无约线性最优化问题常用算法:

    梯度下降法)、共轭梯度变尺度法和加速法.其中,前三个要用到函数的一阶导数或二阶导数,适用于函数表达式导数存在且求导简单的情况,而步长加速法则相反,适用于函数表达示复杂,甚至无解析表达式,或导数不存在情况.

    2 约束非线性最优化问题常法:

    按照是否化成无约束问题可分为 可行方向法、制约函数法(外点法和内点法),其中内点法适用于目标函数在可行域外性质复杂情况,外点法则相反.后者根据罚函数或障碍函数的构造不同,又有不同的变形.

    请数模高手解释一下优化问题中的线性和非线性的概念

    8433c6a800333ec3e1e7d31a631c7d67.png

    问题用高等数学的理论来解释是的:如果说A与B线性关系说明的B随着A的值的相应的变化而变化的以看作AB之间是简单函数的关系,例如一元一次、二次方程、三角函数等等这样的方程;但如果说之间是非线性关系,则说明AB之间没有一定的变化关系,往往不能根据的变化而确定的值。 线性就是正比例,形如y=kx的函数

    除线性之外的都是非线性 线性就是符合y=kx+b

    线性顾名思义就是直线,那么非线性的就是曲线

    相关标签推荐:

    延展阅读:

    展开全文
  • 非线性优化与g2o

    2017-07-13 19:36:23
    非线性优化
  • 非线性优化算法:各种非线性编程算法的MATLAB实现
  • 实验四 用 MATLAB 求解非线性优化问题 一实验目的 了解 Matlab 的优化工具箱利用 Matlab 求解非线性优化问题 二相关知识 非线性优化包括相当丰富的内容 们这里就 Matlab 提供的一些函数来介 绍相关函数的用法及其所...
  • Matlab遗传算法工具箱在非线性优化中的应用-Matlab遗传算法工具箱在非线性优化中的应用.pdf 摘 要:投影寻踪是一种降维处理技术,通过它可以将多维分析问题通过投影方向转化为一维问题分析。应用该法的关 键在于...
  • 【优化3】非线性优化

    2016-11-14 19:28:33
    非线性优化

    凸集和凸函数

    这里写图片描述
    这里写图片描述
    这里写图片描述

    SOCP

    这里写图片描述

    Guideline

    这里写图片描述

    展开全文
  • 用 MATLAB求解非线性优化问题 实验四 用 MATLAB 求解非线性优化问题 一实验目的 了解 Matlab 的优化工具箱利用 Matlab 求解非线性优化问题 二相关知识 非线性优化包括相当丰富的内容我们这里就 Matlab 提供的一些...
  • 国交大非线性优化课程讲义,讲解了常用非线性规划问题的求解过程
  • 基于梯度理论的非线性优化研究,张璐,,在生产实践中,非线性优化方法应用广泛,基于梯度搜索理论的共轭梯度法是一种寻找最优解的有效方法。我们将其应用到目前同样被广
  • 非线性优化算法总结

    2021-01-12 19:08:43
    非线性优化算法总结 文章目录非线性优化算法总结一、非线性最小二乘问题二、最速梯度下降法和牛顿法三、高斯牛顿法四、LM( Levenberg-Marquadt)法 一、非线性最小二乘问题 最小二乘法形式如下式: 这里Target...

    非线性优化算法总结


    一、非线性最小二乘问题

    最小二乘法形式如下式:
    在这里插入图片描述
    这里Target(θ)函数为目标函数,在机器学习中就是损失函数,
    在这里插入图片描述
    这个函数为预测值,在机器学习中就是模型输出值,yi是真实值或理论值。
    那么 非线性最小二乘 就很容易理解了,目标参数函数和参数的关系是非线性。这里要优化的参数为θ。

    对于矩阵形式,这里我们简单一点:直接把简单的非线性最小二乘问题定义为:

    在这里插入图片描述
    这里要优化的参数就是X。其中自变量x∈Rn,f(x)是任意的非线性函数,并设它的维度为m,即f(x)∈Rm.如果 f 是个数学形式上很简单的函数,那问题也许可以用解析形式来求。令目标函数的导数为零,然后求解 x 的最优值,就和一个求二元函数的极值一样:
    在这里插入图片描述

    解此方程,就得到了导数为零处的极值。它们可能是极大、极小或鞍点处的值,只要挨个儿比较它们的函数值大小即可。但是导数不一定可以直接求解x,这个导函数可能是一个复杂的非线性方程。这种情况下一般采用迭代来求解,从一个初始值出发,不断地更新当前的优化变量,使目标函数下降。具体步骤可以表示为 :
    在这里插入图片描述
    这让求解导函数为零的问题,变成了一个不断寻找梯度并下降的过程。直到某个时刻增量非常小,无法再使函数下降。此时算法收敛,目标达到了一个极小,我们完成了寻找极小值的过程。

    二、最速梯度下降法和牛顿法

    首先,我们将目标函数在X附近进行泰勒展开:
    在这里插入图片描述
    这里如果看不懂的话就复习一下高数中的泰勒展开式和简单矩阵求导。这里的J(x)是f(x)关于x的导数(雅可比矩阵),H(x)是二阶导数(海森矩阵)。我们可以选择保留泰勒公式的一阶导数和二阶导数,如果保留一阶导数,则增量的解就是:
    在这里插入图片描述
    它的直观意义非常简单,只要我们找到梯度然后沿着反向梯度方向前进即可。当然,我们还需要该方向上取一个步长 λ,求得最快的下降方式。这种方法被称为最速梯度下降法或是一阶梯度法。
    在这里插入图片描述

    另一方面,如果保留二阶梯度信息,那么增量方程为:
    在这里插入图片描述
    对Δx求导数并令它等于0,则
    在这里插入图片描述
    就得到了增量的解:
    在这里插入图片描述
    这种方法称为牛顿法或二阶梯度法,它的迭代公式可以表示为:
    在这里插入图片描述
    这两种方法只要把函数在迭代点附近进行泰勒展开,并针对更新量作最小化即可。由于泰勒展开之后函数变成了多项式,所以求解增量时只需解线性方程即可,避免了直接求导函数为零这样的非线性方程的困难。这两种方法也存在它们自身的问题。最速梯度下降法过于贪心,容易走出锯齿路线,反而增加了迭代次数。而牛顿法则需要计算目标函数的 H 矩阵,这在问题规模较大时非常困难,我们通常倾向于避免 H 的计算。

    三、高斯牛顿法

    Gauss Newton 是最优化算法里面最简单的方法之一。它的思想是将 f(x) 进行一阶的
    泰勒展开(请注意不是对下面的目标函数 进行展开)在这里插入图片描述
    而是如下展开:
    在这里插入图片描述
    这里 J(x) 为 f(x) 关于 x 的导数,实际上是一个 m × n 的矩阵,也是一个雅可比矩阵。根据前面的框架,当前的目标是为了寻找下降矢量 ∆x,使得 ∥f (x + ∆x)∥2 达到最小。为了求 ∆x,我们构建 一个线性的最小二乘问题:
    在这里插入图片描述
    根据极值条件,将上述目标函数对 ∆x 求导,并令导数为零。由于这里考虑的是 ∆x 的导数(而不是 x),我们最后将得到一个线性的方程。为此,先展开目标函数的平方项:
    在这里插入图片描述
    求上式关于 ∆x 的导数,并令其为零:在这里插入图片描述
    在这里插入图片描述
    我们要求解的变量是 ∆x,这是一个线性方程组,我们称它为增量方程或高斯牛顿方程 (Gauss Newton equations) 或者正规方程 (Normal equations)。我们把左边的系数定义为 H,右边定义为 g,那么上式变为:
    在这里插入图片描述
    在这里插入图片描述
    对比牛顿法可见,高斯牛顿法用 J矩阵的转置乘以J矩阵作为牛顿法中二阶 H 矩阵的近似,从而省略了计算 H 的过程。求解增量方程是整个优化问题的核心所在。原则上,它要求近似的矩阵H是可逆的(而且是正定的),而实际计算中得到的JTJ却是半正定的。也就是使用高斯牛顿法会出现JTJ为奇异或者病态情况,此时增量的稳定性较差,导致算法不收敛。即使H非奇异也非病态,如果求得的Δx非常大,也会导致我们采用的局部近似不够正确,这样以来可能不能保证收敛,哪怕是还有可能让目标函数更大。即使高斯牛顿法具有它的缺点,但是很多非线性优化可以看作是高斯牛顿法的一个变种,这些算法结合了高斯牛顿法的优点并修正其缺点。例如LM算法,尽管它的收敛速度可能比高斯牛顿法更慢,但是该方法健壮性更强,也被称为阻尼牛顿法。

    四、LM( Levenberg-Marquadt)法

    由于 高斯牛顿方法中采用的近似二阶泰勒展开只能在展开点附近有较好的近似效果,所以我们很自然地想到应该给 ∆x 添加一个信赖区域(Trust Region),不能让它太大而使得近似不准确。非线性优化种有一系列这类方法,这类方法也被称之为信赖区域方法 (Trust Region Method)。在信赖区域里边,我们认为近似是有效的;出了这个区域,近似可能会出问题。一个比较好的方法是根据我们的近似模型跟实际函数之间的差异来确定这个范围:如果差异小,我们就让范围尽可能大;如果差异大,我们就缩小这个近似范围。因此,考虑使用:
    在这里插入图片描述
    来判断泰勒近似是否够好。ρ 的分子是实际函数下降的值,分母是近似模型下降的值。如果 ρ 接近于 1,则近似是好的。如果 ρ 太小,说明实际减小的值远少于近似减小的值,则认为近似比较差,需要缩小近似范围。反之,如果 ρ 比较大,则说明实际下降的比预计的更大,我们可以放大近似范围。LM算法表示如下:
    在这里插入图片描述
    上面算法中,μ表示信赖区域的半径,那么信赖区域就是一个球形区域,该约束认为只有在球内才是有效的,带上矩阵D后就是一个椭球区域。在 LM 算法中,我们需要解下面的式子那样的一个子问题来获得梯度。
    在这里插入图片描述

    这个子问题是带不等式约束的优化问题采用拉格朗日乘子法将上述问题转化为一个无约束问题:
    在这里插入图片描述
    这里 λ 为 拉格朗日 乘子。仔细看上面的式子,我们根据加号把它分为左右两部分,回想前面的高斯牛顿算法,你会发现加号左边是一个高斯牛顿算法中的最小二乘问题,这一部分对Δx求梯度,得到增量方程:
    在这里插入图片描述
    加号右边对Δx求梯度,得到:
    在这里插入图片描述
    我们把这两部分合并:得到增量的线性方程:
    在这里插入图片描述
    可以看到,增量方程相比于 高斯牛顿,多了一项。如果考虑它的简化形式,即 D = I,那么相当于求解:
    在这里插入图片描述
    当参数 λ 比较小时,H 占主要地位,这说明二次近似模型在该范围内是比较好的,LM 方法更接近于 高斯牛顿法。另一方面,当 λ 比较大时,λI 占据主要地位,LM更接近于最速梯度下降法这说明附近的二次近似不够好。LM 的求解方式,可在一定程度上避免线性方程组的系数矩阵的非奇异和病态问题,提供更稳定更准确的增量 ∆x。
    总而言之,非线性优化问题的框架,分为 Line Search 和 Trust Region 两类。Line Search 先固定搜索方向,然后在该方向寻找步长,以最速下降法和 高斯牛顿法为代表。而 Trust Region 则先固定搜索区域,再考虑找该区域内的最优点。此类方法以 LM 为代表。实际问题中,我们通常选择 高斯牛顿或 LM 之一作为梯度下降策略。

    参考书籍《视觉SLAM十四讲 从理论到实践》


    如果您认可我的文章,希望能够关注我的微信公众号,我会不定期更新工作中学到的东西和一些技术比较前沿的东西。

    在这里插入图片描述

    在这里插入图片描述

    展开全文
  • 控制系统仿真课程设计 题 目基于 学生姓名 学 号 专 业 班 级 指导教师 NCD优化的非线性优化PID控制 内蒙古科技大学控制系统仿真课程设计 目录 基于NCD优化的非线性优化PID控制 . 4 摘 要 . 4 第一章 绪论 . 6 1.1 ...
  • 基于C/C++的非线性优化库,最优化方法库
  • 非线性优化一维搜索的研究与改进
  • poblano_toolbox:MATLAB的非线性优化
  • nimnlopt:非线性优化库Nlopt的包装
  • 结合工作经验和MATLAB帮助文档,对MATLAB的非线性优化函数fmincon做了详细整理
  • ceres非线性优化

    2020-05-25 17:18:00
    使用Ceres求解非线性优化问题,一共分为三个部分: 1、 第一部分:构建cost fuction,即代价函数,也就是寻优的目标式。这个部分需要使用仿函数(functor)这一技巧来实现,做法是定义一个cost function的结构体,在...
  • matlab开发-使用gmarguardt方法进行多变量非线性优化。基于马尔夸特方法的多元非线性优化
  • 本书详细介绍了深度和法向量的非线性优化具体方法及公式推导。
  • matlab机器学习 无约束非线性优化工具包 亲测有效 强大实用 提高效率缩短开发周期 非常好用 强烈推荐
  • 用matlab非线性优化函数,解决矩形材料上截取若干小圆形铁片问题,solve_simple.m是主程序,有一定实际意义。
  • 非线性优化库NLopt简介

    千次阅读 2018-04-03 15:58:43
    非线性优化库NLopt NLopt 是一个轻量级开源非线性优化库, 为多种优化算法提供了统一的接口。 主页:https://nlopt.readthedocs.io/en/latest/ git:https://github.com/stevengj/nlopt 目录 非线性优化库...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,904
精华内容 2,761
关键字:

非线性优化