精华内容
下载资源
问答
  • Ceres Solver 非线性优化
    千次阅读
    2022-03-02 11:01:18


    1. Ceres Solver

    Ceres solver 是谷歌开发的一款用于非线性优化的库
    谷歌的开源激光雷达SLAM项目Cartographer 中被大量使用

    使用Ceres求解非线性优化问题,一共分为四个部分:

    1. 构建 代价函数cost fuction,也就是寻优的目标式
    2. 通过代价函数构建 待求解的优化问题
    3. 配置求解器参数
    4. 求解问题

    Ceres主要用于求解无约束或者有界约束的最小二乘问题
    这个概念可以用以下表达式表示:
    在这里插入图片描述
    任务就是找到一组满足约束 l l lj ≤ x ≤x xj ≤ u ≤u uj x x x1,⋯, x x xk, 使得优化目标函数取值最小

    • x x x1,⋯, x x xk 优化参数,被称为参数块,它们的取值就是寻找的解
    • l l lj u u uj j j j个优化参数 x x xj的下界和上界
    • ρ ρ ρi ( ∥ f (∥f (fi ( x (x (x1,⋯, x x xk ) ∥ )∥ )2 ) ) ) 残差项,其中 f f fi ( ⋅ ) (⋅) ()是代价函数, ρ ρ ρi ( ⋅ ) (⋅) ()则是关于代价函数平方的核函数
      核函数存在的意义主要是为了降低野点对于解的影响

    2. 下载安装

    使用以下命令安装依赖

    sudo apt-get install cmake libgoogle-glog-dev libgflags-dev libatlas-base-dev libeigen3-dev libsuitesparse-dev
    

    下载源码,推荐用国内源

    git clone https://gitcode.net/mirrors/ceres-solver/ceres-solver.git
    

    开始编译

    mkdir ceres-bin
    cd ceres-bin/
    cmake ../ceres-solver
    make -j3
    sudo make install
    

    测试一下

    bin/simple_bundle_adjuster ../ceres-solver-2.0.0/data/problem-16-22106-pre.txt
    

    在这里插入图片描述


    3. 简易例程

    Ceres官网教程给出的例程中,求解的问题是求 x x x使得 1 2 \frac{1}{2} 21 ∗ ( 10 − x ) * (10−x) (10x)2 取到最小值

    代码如下:

    #include <iostream>
    #include <ceres/ceres.h>
    
    using namespace std;
    using namespace ceres;
    
    /* 第一步:构建代价函数,利用仿函数对()进行重载 */
    struct CostFunctor
    {
      template <typename T>
      bool operator()(const T *const x, T *residual) const
      {
        residual[0] = T(10.0) - x[0];
        return true;
      }
    };
    
    /* 主函数 */
    int main(int argc, char **argv)
    {
      google::InitGoogleLogging(argv[0]);
    
      /* 寻优参数x的初始值,为5.0 */
      double initial_x = 5.0;
      double x = initial_x;
    
      /* 第二步:构建寻优问题 */
      Problem problem;
    
      /* 使用自动求导,将之前的代价函数结构体传入,第一个1是输出维度,即残差的维度,第二个1是输入维度,即待寻优参数x的维度。 */
      CostFunction *cost_function = new AutoDiffCostFunction<CostFunctor, 1, 1>(new CostFunctor);
    
      /* 向问题中添加误差项,本问题比较简单,添加一个就行。 */
      problem.AddResidualBlock(cost_function, NULL, &x);
    
      /* 第三步:配置求解器 */
      Solver::Options options;
      options.linear_solver_type = ceres::DENSE_QR; /* 配置增量方程的解法 */
      options.minimizer_progress_to_stdout = true;  /* 配置输出到cout */
      Solver::Summary summary;                      /* 定义优化信息 */
    
      /* 第四步:运行求解器 */
      Solve(options, &problem, &summary);
    
      /* 输出优化的简要信息 */
      std::cout << summary.BriefReport() << "\n";
    
      /* 输出最终的结果信息 */
      std::cout << "x : " << initial_x << " -> " << x << "\n";
    
      return 0;
    }
    
    

    4. 环境运行

    在与源码和编译文件夹同级路径再新增测试文件夹ceres-examples

    $ mkdir ceres-examples
    $ ls
    # ceres-bin  ceres-examples  ceres-solver
    $ cd ceres-examples
    

    文件以example.cpp为例,新建文件复制上述代码

    再新建CMakeLists.txt文件

    cmake_minimum_required(VERSION 2.8)
    project(ceres-examples)
    
    find_package(Ceres REQUIRED)
    include_directories(${CERES_INCLUDE_DIRS})
    
    add_executable(example example.cpp)
    target_link_libraries(example ${CERES_LIBRARIES})
    

    然后编译并执行文件

    $ cmake ../ceres-examples/
    $ make
    $ ./example 
    

    在这里插入图片描述
    最终解为10使得 1 2 \frac{1}{2} 21 ∗ ( 10 − x ) * (10−x) (10x)2 取到最小值


    5. 非线性拟合

    拟合非线性函数的曲线: y = e y=e y=e3x2+2x+1

    #include <iostream>
    #include <ceres/ceres.h>
    #include <time.h> 
    
    using namespace std;
    using namespace ceres;
    
    /* 构建代价函数结构体,abc为待优化参数,residual为残差。*/
    struct CostFunctor
    {
      CostFunctor(double x, double y) : _x(x), _y(y) {}
      template <typename T>
      bool operator()(const T *const abc, T *residual) const
      {
        residual[0] = _y - exp(abc[0] * _x * _x + abc[1] * _x + abc[2]);
        return true;
      }
      const double _x, _y;
    };
    
    /* 主函数 */
    int main()
    {
      /* 参数初始化设置,abc初始化为0,噪声 */
      double a = 3, b = 2, c = 1;
      double abc[3] = {0, 0, 0};
    
      /* 设置rand()产生随机数时的随机数种子 */
      srand((int)time(0));
    
      /* 生成待拟合曲线的数据散点 */
      vector<double> x_data, y_data;
      for (int i = 0; i < 1000; i++)
      {
        double x = i / 1000.0;
        x_data.push_back(x);
        y_data.push_back(exp(a * x * x + b * x + c) + (rand() % 11 - 5) / 10.0);
      }
    
      /* 第二步:构建寻优问题 */
      Problem problem;
    
      /* 遍历所有数据点,添加AddResidualBlock */
      for (int i = 0; i < 1000; i++)
      {
        problem.AddResidualBlock(
            new AutoDiffCostFunction<CostFunctor, 1, 3>(new CostFunctor(x_data[i], y_data[i])),
            nullptr, /* 不使用核函数 */
            abc);    /* 待优化参数 */
      }
    
      /* 第三步:配置求解器 */
      Solver::Options options;
      options.linear_solver_type = DENSE_QR;
      options.minimizer_progress_to_stdout = true;
      Solver::Summary summary;
    
      /* 第四步:运行求解器 */
      Solve(options, &problem, &summary);
    
      /* 输出最终的结果信息 */
      cout << "a= " << abc[0] << endl;
      cout << "b= " << abc[1] << endl;
      cout << "c= " << abc[2] << endl;
    
      return 0;
    }
    

    参考上节编辑文件和编译,执行效果如下:

    在这里插入图片描述
    求出来和原始参数很接近


    谢谢!

    更多相关内容
  • 使用Python语言实现四种非线性优化算法,并探究学习率对其优化效果的影响。
  • 它可用于解决非线性最小二乘优化问题。 该函数提供了一种使用无迹卡尔曼滤波器解决非线性最小二乘优化问题的方法。 包括三个示例:一般优化问题、求解由神经网络模型表示的一组非线性方程的问题和神经网络训练问题...
  • ( 2)SCE-UA算法求解具有区间约束的非线性约束优化问题较有效,但对于一般的不等式约束非线性优化问题其求解效率有待于进一步提高.提出了群体复合形进化算法,能充分利用目标函数值的信息,优化搜索过程具有较强的方向性...
  • 包括非线性优化中的梯度法、信赖域法、基本牛顿法、拟牛顿法BFGS、DFP、共轭梯度法以及内点法的实现,包括针对一个实例的多种算法迭代次数与精度的对比,内容充分详实。
  • BNB20 解决混合整数非线性优化问题。 它是一种分支定界算法。
  • [迁移到GIT-HUB的项目] OptLib是一个非线性优化例程库,其重点是使用随机方法,包括模拟退火,遗传算法和蒙特卡洛。 例程使用MPI并行化。
  • 非线性优化算法及实现.pdf
  • Matlab遗传算法工具箱在非线性优化中的应用
  • 这种方法可以应用于一般的非线性优化。 该函数展示了一种使用扩展卡尔曼滤波器解决一些无约束非线性优化问题的方法。 包括两个示例:一般优化问题和求解由神经网络模型表示的一组非线性方程的问题。 该函数需要...
  • Matlab遗传算法工具箱在非线性优化中的应用-Matlab遗传算法工具箱在非线性优化中的应用.pdf 摘 要:投影寻踪是一种降维处理技术,通过它可以将多维分析问题通过投影方向转化为一维问题分析。应用该法的关 键在于...
  • 实验四 用 MATLAB 求解非线性优化问题 一实验目的 了解 Matlab 的优化工具箱利用 Matlab 求解非线性优化问题 二相关知识 非线性优化包括相当丰富的内容 们这里就 Matlab 提供的一些函数来介 绍相关函数的用法及其所...
  • NLOP是用于非线性优化的开源C ++模板库。 NLOP-非线性优化简介NLOP是一个用于非线性优化的开源C ++模板库。 动机我之所以开发此项目,主要是因为我对凸优化感兴趣。 我希望这对其他凸优化研究人员的学与教很有用。 ...
  • * 相同的界面,但比 'fminunc' / 'lsqnonlin' 更好。 * 用于一般非线性最小化的 BFGS 算法。 * 非线性最小二乘法的 Levenberg-Marquardt 算法。 * 支持有界约束。 * 支持使用有限差分计算梯度和雅可比矩阵。
  • MINOTAUR是用于开发用于混合整数非线性优化问题的算法的框架。 它包括一些求解器。 它是免费和开源的。 有关使用和分发许可证的详细信息,请参阅LICENSE文件。 重要连结 下载每晚版本(即将推出)
  • matlab优化工具箱 非线性优化 约束优化 线性规划、二次规划

    非线性优化汇总——Matlab优化工具箱(持续更新中)

    室内定位/导航/优化技术探讨:WX: ZB823618313

    原创不易,路过的各位大佬请点个赞


    主要汇总非线性优化类型、应用

    每个优化问题及求解器都对应的链接,如果没有未来会更新

    对应Matlab优化工具包

    目录性 博客

    尽管题目为非线性优化,实际还包含了:Optimization Toolbox 快速入门、线性规划、最小二乘、二次规划、(二阶)锥规划,可能还专门会会讲解一下 优化问题的构建和设置

    Optimization Toolbox™ 提供了多个函数,这些函数可在满足约束的同时求出可最小化或最大化目标的参数。该工具箱包含适用于下列各项的求解器:线性规划 (LP)、混合整数线性规划 (MILP)、二次规划 (QP)、二阶锥规划 (SOCP)、非线性规划 (NLP)、约束线性最小二乘、非线性最小二乘和非线性方程。

    1、优化算法汇总——优化工具包

    1. 非线性优化:查找单变量函数在定区间上的最小值 (求解器:fminbnd

    2. 非线性优化:无约束非线性优化(Unconstrained nonlinear minimization)(求解器:fminsearch和fminunc
    无约束非线性优化:fminunc(https://blog.csdn.net/weixin_44044161/article/details/116032924?spm=1001.2014.3001.5501)
    无约束非线性优化:fminsearch(https://blog.csdn.net/weixin_44044161/article/details/123826153)

    3. 非线性优化:有约束非线性优化(Constrained nonlinear minimization)(求解器:fmincon

    4. 非线性优化:求解半无限约束多变量非线性函数的最小值(求解器:fseminf

    5. 最小二乘: 线性最小二乘(Linear least squares) (==求解器:lsqlinlsqnonneg ==)
    6. 最小二乘:非线性最小二乘(Nonlinear least squares)(求解器:lsqnonlin和lsqcurvefit
    7. 最小二乘:约束最小二乘(Constrained least squares)(求解器:lsqlin

    8. 线性规划 (Linear Programming, LP)(求解器:linprog
    9. 半正定规划(semidefinite programming, SDP)(求解器:CVX:sdp
    10. 二次规划/二次约束二次规划(Quadraitic Constraint Quadraitic Programming, QCQP)(求解器:quadprog
    11. (二阶)锥规划 (Second-Order Cone Programming, SOCP) (求解器:coneprog和secondordercone)

    12. 未完待续(可留言推荐)

    2、优化问题及对应求解器

    2.1、非线性优化

    类型优化模型求解器

    在这里插入图片描述
    在这里插入图片描述

    2.2、最小二乘

    类型优化模型求解器

    在这里插入图片描述
    在这里插入图片描述

    2.3、线性规划

    类型优化模型求解器

    在这里插入图片描述

    2.4、(二阶)锥规划 (Second-Order Cone Programming, SOCP)

    类型优化模型求解器
    锥规划见下面coneprog(锥规划)secondordercone(二阶锥约束)(也可以用CVX工具包求解)

    |
    second-order cone constraint(所谓二阶是指锥里面用到的是二范数,下面的表达式表示一个二阶锥。):
    在这里插入图片描述
    在这里插入图片描述
    根据仿射变换的性质,变换后凹凸性不变,因此二阶锥仍然是一个凸锥。
    注:对向量 x xx 仿射变换(相当于将一个图形平移,或变大变小,或旋转,或倒影): y = A x + b y = A x + b y=Ax+b,其中 A x A x Ax 表示对 x x x变大或变小或旋转倒影,而 + b + b +b 表示平移。

    二阶锥规划(标准形式):

    在这里插入图片描述

    2.5、二次规划/二次约束二次规划(Quadraitic Constraint Quadraitic Programming, QCQP)

    类型优化模型求解器
    在这里插入图片描述
    由于二次约束可以转换为二阶锥约束,因此QCQP问题可以转化为二阶锥规划问题,并用 coneprog 或者 CVX 求解

    二次约束二次规划:
    在这里插入图片描述
    由于二次约束可以转换为二阶锥约束,因此QCQP问题可以转化为二阶锥规划问题,并用 coneprog 或者 CVX 求解

    2.6、半正定规划(semidefinite programming, SDP)

    类型优化模型求解器
    锥规划见下面CVX工具包(也可以用coneprog),实际上都用的内点法

    注意:半正定规划问题可以转化为二阶锥规划问题,并用 coneprog 或者 CVX 求解,同理,SOCP也可以转换为SDP问题

    对SDP理解:可以简单理解为:半正定规划是线性规划的矩阵形式
    在这里插入图片描述

    原创不易,路过的各位大佬请点个赞

    展开全文
  • 到底什么是非线性优化

    千次阅读 2019-10-11 10:21:17
    1.非线性优化真的那么难?​ 其实,在上高中的时候我们就已经对非线性优化的求解方法了然于心了。可见,非线性优化并不是我们想的那么困难,只不过在后来由于学习了大量的新知识,而迷失其中。你可能不相信,那么让...

    转自:http://blog.sina.com.cn/s/blog_7445c2940102x3x4.html
    侵删

    1.非线性优化真的那么难?​

    其实,在上高中的时候我们就已经对非线性优化的求解方法了然于心了。可见,非线性优化并不是我们想的那么困难,只不过在后来由于学习了大量的新知识,而迷失其中。你可能不相信,那么让我们一同回到高中的数学课上。数学老师给了如下的问题:​​
    在这里插入图片描述
    ​如何找到上面这个函数的最小值?相信你很快的就能想起上面这个问题的解法,并且求出上面这个函数的极值。而至此,我们已经解决了一个非线性优化的问题。​为什么这么说呢?请看下面的公式:​

    在这里插入图片描述

    当这个公式中的f(x)是一个非线性函数的时候,上面的问题就是一个非线性优化的问题。​也就是说,非线性优化问题是针对一个非线性函数求最值的问题。那么,再让我们回过头看一看数学老师出的问题,这不就是一个非线性优化问题吗?​而且,求解方法也很简单,就是对函数求导,再令导数为零,我们就找到了极值点。可见,非线性优化并不是一个高不可攀的山峰。​

    那么,我们是否可以对所有的非线性优化问题,都可以用上面的解法呢?很遗憾,对于很多情况,通过导数为零求解析的求出极值点,是做不到的,如下式:​​

    在这里插入图片描述

    我们对x,y分别求偏导,得到:​​

    在这里插入图片描述

    我们很难直接的从上面的式子中,求出导数为0的点。一方面,是因为该函数已经不是初等函数。另一方面,是因为增加了未知数(变量)的个数。我们重新写一下公式(1),如下:​

    在这里插入图片描述

    可见,这个函数是一个单变量的非线性函数,而且极值点只有一个。即使,增加x的幂次方,不过是增加了几个极值点,我们还是可以通过之前的办法,只不过将每个极值点的值都带回方程,就可以找到整个函数上的最小值。无论,这个一维函数如何复杂,都可以画在一个二维坐标中,如下:​

    在这里插入图片描述

    上图中,极值点1和点3是最小值点,点2是最大值点,而点4既不是最大值点,也不是最小值点。通过比较我们知道,点3是全局最小值点,而点1是局部最小值点。

    但是,如果再增加函数的变量个数会发生什么呢?比如,只再增加一个变量y,此时函数变为f(x,y),而这个函数在x和y的方向上都有多个极值点。这时,我们还能将这个函数表示在三维坐标系下,如下:​

    在这里插入图片描述

    此时,极值点的分布就比一维的情况复杂了许多。当变量个数继续增加的时候,极值点的个数会成几何倍增加,显然也就无法通过求解出所有极值点再比较大小的方法,实现对问题的求解。​

    2.如何求解复杂的非线性优化问题?

    上面的方法是一种比较贪心的解决方法,希望直接找到问题的解。俗话说,饭得一口一口吃,不能一口吃个胖子。这里要注意的一点就是,虽然我们不能直接找到函数值为零的点。但是,非线性函数的导数是存在的,也就可以计算出每一点的导数。也就是说,既然不能直接找到极值点,我们就应该一步一步的逐渐逼近函数的极值点。​

    我们将原问题找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是一样不可求的。那么怎么办呢?​

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

    因为,我们求的f(x+Δx)处于f(x)的邻域中,所以就可以用泰勒级数在点x处展开,如下:​

    在这里插入图片描述

    将上式对Δx求导,并令其等于0,得到:​​

    在这里插入图片描述

    因为上式存在Δx的高阶项,所以还是很难得到上式的解。不过,由于是在点x的邻域内,因此我们可以忽略Δx的高阶项。

    (1)当我们只保留一阶项的时候,得到如下式子:​

    在这里插入图片描述

    上式中的J(x)在多维情况下,被称为雅可比矩阵,其实就是对f(x)求偏导。接着,一般书就会直接给出增量Δx的大小,如下:​

    在这里插入图片描述

    这个过程其实不太好理解。因为,如果从一维的角度理解,那么此处的f’(x)只是一个斜率,按理说斜率的多少跟Δx的值是无关的,只要Δx值不要太大保证在邻域内就可以。所以,直接得出上面的式子就感觉很诡异。​

    其实,换一个角度解释上面的式子就很容易理解。这里让Δx等于负梯度,重点并不在于Δx的大小,而是规定了Δx的方向。其实,即使在1维里,我们也可以这么理解,Δx=-k,此处的k只用于提供方向,也就是正负号,而不代表走多远。​对于多维情况更是如此,因为我们需要知道增量的方向,而方向是由Δx各维度大小决定的。其实,一个更清晰的表示应该是将梯度归一化,然后再乘以一个步长系数,如下所示:​

    在这里插入图片描述

    这个方法也就是我们经常听到的——最速下降法

    (2)如果我们保留到二阶项的时候,得到如下式子:​

    在这里插入图片描述

    上式中的H(x)被称为Hessian矩阵,而且J(x)和H(x)在点x的值是已知的,所以上式是一个线性方程组。写成矩阵形式如下:​

    在这里插入图片描述

    Δx的值可以通过解这个方程得到,求解方法由很多,在此就不再赘述。这个方法,就叫做——牛顿法

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

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

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

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

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

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

    展开全文
  • 非线性优化经典著作——《methods for nonlinear least square problems》
  • 国交大非线性优化课程讲义,讲解了常用非线性规划问题的求解过程
  • 非线性优化与g2o

    2017-07-13 19:36:23
    非线性优化
  • 非线性优化算法总结

    千次阅读 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十四讲 从理论到实践》


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

    在这里插入图片描述

    在这里插入图片描述

    展开全文
  • 非线性优化主要算法的Matlab程序,有精确线搜索的0.618法和抛物线法, 非精确线搜索的Armijo准则, 最速下降法, 牛顿法, 共轭梯度法, BFGS 算法, DFP 算法, Broyden 族方法, 信赖域方法, 求解非线性最小二乘问题的L-M...
  • 遗传算法非线性优化算法很实用含附件-遗传算法模型优化应用.rar
  • SLAM14讲学习笔记(三)非线性优化基础

    千次阅读 多人点赞 2019-04-01 21:43:29
    如果前面的内容已经熟知了,但仍然不太理解这个非线性优化,希望打开我最后的总结链接看看,融会贯通。 主要有两个方程: 状态方程: 其中,w,v都是噪声。非线性优化的主要目的就是在有噪声的情况下,...
  • matlab加速迭代法代码非线性预处理项目:非线性优化的收敛加速 项目目标: 该项目通过使用定点方法作为非线性预处理器(内部迭代)来开发简单的定点优化方法(例如,用于规范张量分解的交替最小二乘(ALS))的收敛...
  • matlab求解非线性优化问题
  • 用MATLAB求解非线性优化问题

    千次阅读 2021-05-03 01:56:18
    实验十五用MATLAB求解非线性优化问题一、实验目的:了解Matlab的优化工具箱,利用Matlab求解非线性优化问题。二、相关知识非线性优化包括相当丰富的内容,我们这里就Matlab提供的一些函数来介绍相关函数的用法及其所...
  • BF共轭梯度法优化无约束非线性问题,求函数极小值,理论和例子参考《最优化方法》(北京理工大学出版社)(程序为自编!!!请不要下架!!!)。压缩包内含matlab程序文件(直接运行BFCG.m),Word文档算例说明....
  • 针对目前常用的解线性约束的非线性优化问题的方法在实际应用中还存在不收敛、收敛较慢,或“基变量大量达界后,找不到新的入基变量”等问题,该文提出了求解该问题的新方法夹逼可行方向法,已证明算法的最优性与收敛性。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 176,656
精华内容 70,662
关键字:

非线性优化

友情链接: csevent.rar