精华内容
下载资源
问答
  • 常用的约束优化方法
    2015-11-27 20:24:14

    机器学习理论问题中的三个方面,模型/策略/算法,优化指的是算法方面求解方法。

    min f(x)


    在无约束的条件下,主要的优化方法有:

    1.梯度下降(gradient descene)

    梯度下降分:

    1)批量梯度下降(batch gradient descene)

    2) 随机梯度下降(stochastic gradient descene)

    2.坐标下降(coordient descene)

    3.牛顿法

    4.拟牛顿法

    拟牛顿法主要有:

    1)DFP

    2)BFGS

    3)L-BFGS

    更多相关内容
  • 约束优化方法

    2019-05-12 19:10:13
    本篇文章将详解带有约束条件...拉格朗日求得的并不一定是最优解,只有在凸优化的情况下,才能保证得到的是最优解,所以本文称拉格朗日乘子法得到的为可行解,其实就是局部极小值,接下来从无约束优化开始一一讲解。 ...

    本篇文章将详解带有约束条件的最优化问题,约束条件分为等式约束与不等式约束,对于等式约束的优化问题,可以直接应用拉格朗日乘子法去求取最优值;对于含有不等式约束的优化问题,可以转化为在满足 KKT 约束条件下应用拉格朗日乘子法求解。拉格朗日求得的并不一定是最优解,只有在凸优化的情况下,才能保证得到的是最优解,所以本文称拉格朗日乘子法得到的为可行解,其实就是局部极小值,接下来从无约束优化开始一一讲解。

    无约束优化

    首先考虑一个不带任何约束的优化问题,对于变量 x∈RN 的函数 f(x) ,无约束优化问题如下:

    minxf(x)

    该问题很好解,根据 Fermat 定理,直接找到使目标函数得 0 的点即可 即 ∇xf(x)=0 ,如果没有解析解的话,可以使用梯度下降或牛顿方法等迭代的手段来使 x 沿负梯度方向逐步逼近极小值点。

    等式约束优化

    当目标函数加上约束条件之后,问题就变成如下形式:

    minx f(x)
    s.t. hi(x)=0,i=1,2,…,m

    约束条件会将解的范围限定在一个可行域,此时不一定能找到使得 ∇xf(x) 为 0 的点,只需找到在可行域内使得 f(x) 最小的值即可,常用的方法即为拉格朗日乘子法,该方法首先引入 Lagrange Multiplier α∈Rm ,构建 Lagrangian 如下:

    L(x,α)=f(x)+∑i=1mαihi(x)

    求解方法如下:首先对 Lagrangian 关于 α 与 x 求 :

    {
    ∇xL(x,α)=0
    ∇αL(x,α)=0

    令导数为 0 ,求得 x 、α 的值后,将 x 带入 f(x) 即为在约束条件 hi(x) 下的可行解。这样做的意义是什么呢? 接下来看一个直观的示例,对于二维情况下的目标函数是 f(x,y),在平面中画出 f(x,y) 的等高线,如下图的虚线所示, 并只给出一个约束等式 h(x,y)=0 ,如下图的绿线所示,目标函数 f(x,y) 与约束 g(x,y) 只有三种情况,相交、相切或者没有交集,没交集肯定不是解,只有相交或者相切可能是解,但相交得到的一定不是最优值,因为相交意味着肯定还存在其它的等高线在该条等高线的内部或者外部,使得新的等高线与目标函数的交点的值更大或者更小,这就意味着只有等高线与目标函数的曲线相切的时候,才可能得到可行解.
    在这里插入图片描述

    1

    因此给出结论:拉格朗日乘子法取得极值的必要条件是目标函数与约束函数相切,这时两者的法向量是平行的,即

    ∇xf(x)–α∇xh(x)=0

    所以只要满足上述等式,且满足之前的约束 hi(x)=0,i=1,2,…,m ,即可得到解,联立起来,正好得到就是拉格朗日乘子法。这里只是直观展示了一下拉格朗日乘子法的几何推导 ,并没有给出详细的证明。

    不等式约束优化

    当约束加上不等式之后,情况变得更加复杂,首先来看一个简单的情况,给定如下不等式约束问题:

    minx f(x) s.t. g(x)≤0

    对应的 Lagrangian 与图形分别如下所示:

    L(x,λ)=f(x)+λg(x)

    这时的可行解必须落在约束区域 g(x) 之内,下图给出了目标函数的等高线与约束:

    在这里插入图片描述

    由图可见可行解 x 只能在 g(x)<0 或者 g(x)=0 的区域里取得:

    当可行解 x 落在 g(x)<0 的区域内,此时直接极小化 f(x) 即可;
    当可行解 x 落在 g(x)=0 即边界上,此时等价于等式约束优化问题.
    当约束区域包含目标函数原有的的可行解时,此时加上约束可行解扔落在约束区域内部,对应 g(x)<0 的情况,这时约束条件不起作用;当约束区域不包含目标函数原有的可行解时,此时加上约束后可行解落在边界 g(x)=0 上。下图分别描述了两种情况,右图表示加上约束可行解会落在约束区域的边界上。
    在这里插入图片描述
    以上两种情况就是说,要么可行解落在约束边界上即得 g(x)=0 ,要么可行解落在约束区域内部,此时约束不起作用,另 λ=0 消去约束即可,所以无论哪种情况都会得到:
    λg(x)=0

    还有一个问题是 λ 的取值,在等式约束优化中,约束函数与目标函数的梯度只要满足平行即可,而在不等式约束中则不然,若 λ≠0,这便说明 可行解 x 是落在约束区域的边界上的,这时可行解应尽量靠近无约束时的解,所以在约束边界上,目标函数的负梯度方向应该远离约束区域朝向无约束时的解,此时正好可得约束函数的梯度方向与目标函数的负梯度方向应相同:

    −∇xf(x)=λ∇xg(x)

    上式需要满足的要求是拉格朗日乘子 λ>0 ,这个问题可以举一个形象的例子,假设你去爬山,目标是山顶,但有一个障碍挡住了通向山顶的路,所以只能沿着障碍爬到尽可能靠近山顶的位置,然后望着山顶叹叹气,这里山顶便是目标函数的可行解,障碍便是约束函数的边界,此时的梯度方向一定是指向山顶的,与障碍的梯度同向,下图描述了这种情况 :

    2

    可见对于不等式约束,只要满足一定的条件,依然可以使用拉格朗日乘子法解决,这里的条件便是 KKT 条件。接下来给出形式化的 KKT 条件 首先给出形式化的不等式约束优化问题:

    minx f(x)
    s.t. hi(x)=0, i=1,2,…,m
    gj(x)≤0, j=1,2,…,n

    列出 Lagrangian 得到无约束优化问题:

    L(x,α,β)=f(x)+∑i=1mαihi(x)+∑j=1nβigi(x)

    经过之前的分析,便得知加上不等式约束后可行解 x 需要满足的就是以下的 KKT 条件:

    ∇xL(x,α,β)=0,
    βjgj(x)=0,
    hi(x)=0,
    gj(x)<=0
    βj>0,
    j=1,2,…,n=0, i=1,2,…,m≤0, j=1,2,…,n≥0, j=1,2,…,n(1)(2)(3)(4)(5)

    满足 KKT 条件后极小化 Lagrangian 即可得到在不等式约束条件下的可行解。 KKT 条件看起来很多,其实很好理解:

    (1) :拉格朗日取得可行解的必要条件;

    (2) :这就是以上分析的一个比较有意思的约束,称作松弛互补条件;

    (3) ∼ (4) :初始的约束条件;

    (5) :不等式约束的 Lagrange Multiplier 需满足的条件。

    主要的KKT条件便是 (3) 和 (5) ,只要满足这俩个条件便可直接用拉格朗日乘子法, SVM 中的支持向量便是来自于此,需要注意的是 KKT 条件与对偶问题也有很大的联系.
    原文参考:http://www.cnblogs.com/ooon/p/5721119.html

    展开全文
  • 最优化方法:第五章 常用约束优化方法.ppt
  • 找到约束优化问题的最佳点(最大值或最小值)的 MATLAB 代码 职能 constrv.m :返回给定点的约束违规。 func.m :要优化的函数。 它可以返回函数值和惩罚函数值。 main.m :主要功能。 实现基于约束的优化过程。 执行...
  • 常用约束优化方法 单纯形.ppt
  • 用遗传算法求解无约束优化问题已经取得了成功,但如何处理有约束优化问题是其面临的问题之一.目前处理这一问题没有一致适用的方法,最常用的处理约束方法是惩罚函数法,也有一些其它方法.本文对近几年出现的几种...
  • 优化方法:六、约束优化方法

    万次阅读 2018-07-25 10:55:56
    前面我们已经讨论无约束问题的最优化方法,但实际碰到的问题常常是存在约束的。一般的约束最优化问题的数学模型为: minf(X)s.t.{gi(X)≥0,&nbsp;&nbsp;i=1,2,⋯,l,hj(X)=0,&nbsp;&nbsp;j=1,2,⋯,m...

    主要参考书目:

    • 最优化方法及其应用/郭科,陈聆,魏友华.-北京:高等教育出版社,2007.7(2013.7重印)

    前面我们已经讨论无约束问题的最优化方法,但实际碰到的问题常常是存在约束的。一般的约束最优化问题的数学模型为:

    minf(X)s.t.{gi(X)0,  i=1,2,,l,hj(X)=0,  j=1,2,,m. m i n f ( X ) s . t . { g i ( X ) ≥ 0 ,     i = 1 , 2 , ⋯ , l , h j ( X ) = 0 ,     j = 1 , 2 , ⋯ , m .

    解决约束问题一般有两种思路,一是通过“罚函数”把约束问题转化为无约束问题解决;二则是构造某种迭代过程使之不能越出可行域。

    1、外点罚函数法

    • 基本思路
      构造一函数为
      F(X,Mk)=f(X)+Mkα(X), F ( X , M k ) = f ( X ) + M k α ( X ) ,

      1
      该方法之所以叫做外点法,是因为在很多情况下(不是所有情况),当惩罚因子比较小的时候,最优解会落在可行域之外,随着惩罚因子的增加,向可行域内部移动,也就是说迭代过程中最优解一直在可行域之外。
    • 特点
      该方法实现了有约束问题向无约束问题的转化,但存在着一些问题:
      (1)惩罚因子选的小会使最优解更容易落在可行域外,而惩罚因子选的大又会使函数的Hesse矩阵性质变坏。
      (2)迭代过程中得到的解常常在可行域之外,难以观察到内点的变化情况也无法求得近似最优解。

    2、内点罚函数法

    • 基本思路
      对于纯不等式约束问题,为使得迭代过程中解一直在可行域内。我们通过罚函数在可行域边界处构造一个“壁垒”使得迭代过程中解不能离开可行域。
      1
    • 特点
      该方法保证了迭代过程中得到的解一直处于可行域内,但仍然面临过三个问题:
      (1)需要找到一个可行的初始点。
      (2)如果搜索步长过大,有可能一步跨过壁垒,所以在搜索过程中应适当控制步长,防止该情况发生。
      (3)无法解决等式约束的问题。

    3、混合罚函数法

    • 基本思路
      为解决内点法不能应对等式约束的问题,采用以下混合罚函数:
      F(X,rk)=f(X)+rki=1l1gi(X)+1rkj=1m[hj(X)]2 F ( X , r k ) = f ( X ) + r k ∑ i = 1 l 1 g i ( X ) + 1 r k ∑ j = 1 m [ h j ( X ) ] 2
    • 外插技术
      F(X,r) F ( X , r ) 的最优解 X X ∗ 可以看做 r r 的函数,当我们得到了前几点的X(r)后,可以通过外插法估计下一个最优值,并把该点当做下一次迭代的初始点,以加快收敛速度。
      通常使用两点外插或者三点外插。

    4、约束坐标轮换法

    • 基本思路
      与无约束优化问题的坐标轮换法类似,但是搜索时不再使用一般的以为搜索方法,而采用以下规则:
      1
      该方法可以引入一个步长缩放因子,当在t步长下的搜索已满足该步长下的终止限,而步长并不足够下,则缩短步长进行下一轮搜索。
    • 特点
      该方法算法简单明了,但存在以下问题:
      (1)收敛较慢;
      (2)可能出现“死点”,导致输出伪最优点;
      (3)可能出现在某几个点之间循环的现象。

    5、复合型法

    • 基本思路
      与单纯形法类似,但该方法使用的是顶点更多的复合型。(顶点可以使降维的可能性减小,而且由于约束边界的限制,使用单纯形容易“卡死”在某个地方,而复合型则提供了更多可能的搜索方向)
    • 具体细节
      (1)生成初始复合型
      1
      (2)跑出可行域的点一律认为是最坏的点。
      (3)如果无法利用最坏点搜索(即步长t降的很小仍不符合要求)则改用次坏点替代最坏点,并以此类推。
      (4)关于复合型的顶点数,当 n5 n ≤ 5 时,一般取 k=2n k = 2 n n>5 n > 5 时一般取 k=(1.251.5)n k = ( 1.25 ∼ 1.5 ) n
    • 特点
      属于直接法,对目标函数要求少。
      但其收敛速度较慢,而且不能应对等式约束。
    展开全文
  • 约束优化方法

    千次阅读 2018-09-15 20:50:17
    1.1问题定义 1.1.1优化问题定义 最优化问题数学上定义,最优化问题的一般形式为  (1) 其中的是自变量,f(x)是目标函数,为约束集或者说可行域。 ...可行域这个东西,有等式约束,也...1.1.2最优化方法定义 优化...

    1.1问题定义

    1.1.1优化问题定义

    最优化问题数学上定义,最优化问题的一般形式为

                                       (1)

    其中的是自变量,f(x)是目标函数,为约束集或者说可行域。

    可行域这个东西,有等式约束,也有不等式约束,或者没有约束,这次的精力主要还是集中在无约束的优化问题上,如果有精力,再讨论有约束的。

    1.1.2最优化方法定义

    优化问题的解法叫最优化方法。
    最优化方法通常采用迭代的方法求它的最优解,其基本思想是:给定一个初始点。按照某一迭代规则产生一个点列,使得当是有穷点列时,其最后一个点是最优化模型问题的最优解,当是无穷点列时,它有极限点,且其极限点是最优化模型问题的最优解。一个好的算法应具备的典型特征为:迭代点能稳定地接近局部极小值点的邻域,然后迅速收敛于。当给定的某个收敛准则满足时,迭代即终止。

    好吧,上面是一堆描述,来点定义,设为第k次迭代点,第k次搜索方向,为第k次步长因子,则第k次迭代为

                    (2)

    然后后面的工作几乎都在调整这个项了,不同的步长和不同的搜索方向分别构成了不同的方法。

    当然步长和搜索方向是得满足一些条件,毕竟是求最小值,不能越迭代越大了,下面是一些条件

                               (3)

                 (4)

    式子(3)的意义是搜索方向必须跟梯度方向(梯度也就是)夹角大于90度,也就是基本保证是向梯度方向的另外一边搜索,至于为什么要向梯度方向的另外一边搜索,就是那样才能保证是向目标函数值更小的方向搜索的,因为梯度方向一般是使目标函数增大的(不增大的情况是目标函数已经到达极值)。

    式子(4)的意义就很明显了,迭代的下一步的目标函数比上一步小。

    最优化方法的基本结构为:

    给定初始点

    (a)      确定搜索方向,即按照一定规则,构造目标函数f在点处的下降方向作为搜索方向。

    (b)      确定步长因子,使目标函数值有某种意义的下降。

    (c)      令

    满足某种终止条件,则停止迭代,得到近似最优解,否则,重复以上步骤。

    能不能收敛到最优解是衡量最优化算法的有效性的一个重要方面。

     

    1.1.3收敛速度简介

    收敛速度也是衡量最优化方法有效性的一个重要方面。

    设算法产生的迭代点列在某种范数意义下收敛,即

           (5)

    若存在实数(这个不是步长)以及一个与迭代次数k无关的常数,使得

       (6)

    则称算法产生的迭代点列具有阶收敛速度。特别地,常用的说法有以下几种。

    (a)      当时,迭代点列叫做具有Q-线性收敛速度;

    (b)      当,q>0时或,q=0时,迭代点列叫做具有Q-超线性收敛速度;

    (c)      当时,迭代点列叫做具有Q-二阶收敛速度;

    还有一种叫做R-收敛速度,不讨论了,有兴趣可以查阅相关资料。

    一般认为,具有超线性收敛速度和二阶收敛速度的方法是比较快速的。但是对于一个算法,收敛性和收敛速度的理论结果并不保证算法在实际执行时一定有好的实际计算特性。一方面是由于这些结果本身并不能保证方法一定有好的特性,另一方面是由于算法忽略了计算过程中十分重要的舍入误差的影响。

     

    1.2步长确定

    1.2.1一维搜索

    如前面的讨论,优化方法的关键是构造搜索方向和步长因子,这一节就讨论如何确定步长。

    这样,从x_k出发,沿搜索方向,确定步长因子,使得

    的问题就是关于α的一维搜索问题。注意这里是假设其他的都确定了的情况下做的搜索,要搜索的变量只有α。
    如果求得的,使得目标函数沿搜索方向达到最小,即达到下面的情况

    或者说

    如果能求导这个最优的,那么这个就称为最优步长因子,这样的搜索方法就称为最优一维搜索,或者精确一维搜索。
    但是现实情况往往不是这样,实际计算中精确的最优步长因子一般比较难求,工作量也大,所以往往会折中用不精确的一维搜索。
    不精确的一维搜索,也叫近似一维搜索。方法是选择,使得目标函数f得到可接受的下降量,即使得下降量是用户可接受的。也就是,只要找到一个步长,使得目标函数下降了一个比较满意的量就可以了。
    为啥要选步长?看下图,步长选不好,方向哪怕是对的,也是跑来跑去,不往下走,二维的情况简单点,高维的可能会弄出一直原地不动的情况来。
     

    一维搜索的主要结构如下:1)首先确定包含问题最优解的搜索区间,再采用某种分割技术或插值方法缩小这个区间,进行搜索求解。

    当然这个搜索方法主要是适应单峰区间的,就是类似上面的那种,只有一个谷底的。

    1.2.1.1确定搜索区间

    确定搜索区间一般用进退法,思想是从某一点出发,按某步长,确定函数值呈现“高-低-高”的三个点,一个方向不成功,就退回来,沿相反方向寻找。

    下面是步骤。

    1.2.1.2搜索求解

    搜索求解的话,0.618法简单实用。虽然Fibonacci法,插值法等等虽然好,复杂,就不多说了。下面是0.618法的步骤。

    普通的0.618法要求一维搜索的函数是单峰函数,实际上遇到的函数不一定是单峰函数,这时,可能产生搜索得到的函数值反而大于初始区间端点出函数值的情况。有人建议每次缩小区间是,不要只比较两个内点处的函数值,而是比较两内点和两端点处的函数值。当左边第一个或第二个点是这四个点中函数值最小的点是,丢弃右端点,构成新的搜索区间;否则,丢弃左端点,构成新的搜索区间,经过这样的修改,算法会变得可靠些。步骤就不列了。

    1.2.2不精确一维搜索方法

    一维搜索过程是最优化方法的基本组成部分,精确的一维搜索方法往往需要花费很大的工作量。特别是迭代点远离问题的解时,精确地求解一个一维子问题通常不是十分有效的。另外,在实际上,很多最优化方法,例如牛顿法和拟牛顿法,其收敛速度并不依赖于精确一维搜索过程。因此,只要保证目标函数f(x)在每一步都有满意的下降,这样就可以大大节省工作量。

    有几位科学家Armijo(1966)和Goldstein(1965)分别提出了不精确一维搜索过程。设

            (2.5.1)

    是一个区间。看下图

    在图中,区间J=(0,a)。为了保证目标函数单调下降,同时要求f的下降不是太小(如果f的下降太小,可能导致序列的极限值不是极小值),必须避免所选择的α太靠近区间j的短短。一个合理的要求是

                            (2.5.2)

                  (2.5.3)

    其中0<ρ<1/2,。满足(2.5.2)要求的α_k构成区间J_1=(0,c],这就扔掉了区间J右端附件的点。但是为了避免α太小的情况,又加上了另一个要求(2.5.3),这个要求扔掉了区间J的左端点附件的点。看图中两条虚线夹出来的区间J_2=[b,c]就是满足条件(2.5.2)和(2.5.3)的搜索区间,称为可接受区间。条件(2.5.2)和(2.5.3)称为Armijo-Goldstein准则。无论用什么办法得到步长因子α,只要满足条件(2.5.2)和(2.5.3),就可以称它为可接受步长因子。

    其中这个要求是必须的,因为不用这个条件,可能会影响牛顿法和拟牛顿法的超线性收敛。

    在图中可以看到一种情况,极小值e也被扔掉了,为了解决这种情况,Wolfe-Powell准则给出了一个更简单的条件代替

                                   (2.5.4)

    其几何解释是在可接受点处切线的斜率大于或等于初始斜率的σ倍。准则(2.5.2)和(2.5.4)称为Wolfe-Powell准则,其可接受区间为J_3=[e,c]。

    要求ρ<σ<1是必要的,它保证了满足不精确线性搜索准则的步长因子的存在,不这么弄,可能这个虚线会往下压,没有交点,就搞不出一个区间来了。

    一般地,σ值越小,线性搜索越精确。取σ=0.1,就得到一个相当精确的线性搜索,而取σ=0.9,则得到一个相当弱的线性搜索。不过σ值越小,工作量越大。所以不精确线性搜索不要求过小的σ,通常可取ρ=0.1,σ=0.4。

    下面就给出Armijo-Goldstein准则和Wolfe-Powell准则的框图。

    从算法框图中可以看出,两种方法是类似的,只是在准则不成立,需要计算新的时,一个利用了简单的求区间中点的方法,另一个采用了二次插值方法。

    算法步骤只给出Armijo-Goldstein不精确一维搜索方法的,下面就是

    好了,说到这,确定步长的方法也说完了,其实方法不少,实际用到的肯定是最简单的几种,就把简单的几种提了一下,至于为什么这样,收敛如何,证明的东西大家可以去书中慢慢看。

     

    1.3方向确定

    1.3.1最速下降法

    最速下降法以负梯度方向作为最优化方法的下降方向,又称为梯度下降法,是最简单实用的方法。

    1.3.1.1算法步骤

    下面是步骤。

    看个例子。

    这个选步长的方法是对二次函数下的特殊情况,是比较快而且好的显式形式,说明步长选得好,收敛很快。

    1.3.1.2缺点

    数值实验表明,当目标函数的等值线接近一个圆(球)时,最速下降法下降较快,当目标函数的等值线是一个扁长的椭球是,最速下降法开始几步下降较快,后来就出现锯齿线性,下降就十分缓慢。原因是一维搜索满足,即,这表明在相邻两个迭代点上函数f(x)的两个梯度繁星是互相直交(正交)的。即,两个搜索方向互相直交,就产生了锯齿性质。当接近极小点时,步长越小,前进越慢。
    下图是锯齿的一个图。

    1.3.2牛顿法

    1.3.2.1算法思想和步骤

    牛顿法的基本思想是利用目标函数的二次Taylor展开,并将其极小化。
    设f(x)是二次可微实函数,,Hesse矩阵正定。在附件用二次Taylor展开近似f,

    其中,为f(x)的二次近似。将上式右边极小化,便得

    这就是牛顿迭代公式。在这个公式中,步长因子。令,,则上面的迭代式也可以写成

    其中的Hesse矩阵的形式如下。

    一个例子如下。

    对于正定二次函数,牛顿法一步就可以得到最优解。
    对于非二次函数,牛顿法并不能保证经过有限次迭代求得最优解,但由于目标函数在极小点附近近似于二次函数,所以当初始点靠近极小点时,牛顿法的收敛速度一般是快的。
    当初始点远离最优解,不一定正定,牛顿方向不一定是下降方向,其收敛性不能保证,这说明步长一直是1是不合适的,应该在牛顿法中采用某种一维搜索来确定步长因子。但是要强调一下,仅当步长因子收敛到1时,牛顿法才是二阶收敛的。
    这时的牛顿法称为阻尼牛顿法,步骤如下。

    下面看个例子。

    这样的牛顿法是总体收敛的。

    1.3.2.2缺点

    牛顿法面临的主要困难是Hesse矩阵不正定。这时候二次模型不一定有极小点,甚至没有平稳点。当不正定时,二次模型函数是无界的。
    为了克服这种困难,有多种方法,常用的方法是使牛顿方向偏向最速下降方向。具体做法是将Hesse矩阵改变成,其中,使得正定。一般希望是比较小,最好是刚刚好能使正定。

    1.3.3拟牛顿法

    牛顿法在实际应用中需要存储二阶导数信息和计算一个矩阵的逆,这对计算机的时间和空间要求都比较高,也容易遇到不正定的Hesse矩阵和病态的Hesse矩阵,导致求出来的逆很古怪,从而算法会沿一个不理想的方向去迭代。

    有人提出了介于最速下降法与牛顿法之间的方法。一类是共轭方向法,典型的是共轭梯度法,还有拟牛顿法。

    其中拟牛顿法简单实用,这里就特地介绍,其他方法感兴趣的读者可以去看相关资料。

    1.3.3.1算法思想和步骤

    牛顿法的成功的关键是利用了Hesse矩阵提供的曲率信息。但是计算Hesse矩阵工作量大,并且有些目标函数的Hesse矩阵很难计算,甚至不好求出,这就使得仅利用目标函数的一阶导数的方法更受欢迎。拟牛顿法就是利用目标函数值f和一阶导数g(梯度)的信息,构造出目标函数的曲率近似,而不需要明显形成Hesse矩阵,同时具有收敛速度快的特点。
    在开集上二次可微,f在附近的二次近似为

    两边求导,得


    ,得

    其中,是梯度。那么,只要构造出Hesse矩阵的逆近似满足这种上式就可以,即满足关系

    这个关系就是拟牛顿条件或拟牛顿方程。
    拟牛顿法的思想就是——用一个矩阵去近似Hesse矩阵的逆矩阵,这样就避免了计算矩阵的逆。
    当然需要满足一些条件:

    (a)    是一个正定的矩阵

    (b)    如果存在,则

    (c)    初始正定矩阵取定后,应该由递推给出,即;其中是修正矩阵,是修正公式。

    常用而且有效的修正公式是BFGS公式,如下

    下面给出BFGS公式下的拟牛顿法

    在上述步骤中,初始正定矩阵通常取为单位矩阵,即。这样,拟牛顿法的第一次迭代相当于一个最速下降迭代。

    1.3.3.2优缺点

    与牛顿法相比,有两个优点:

    (a)    仅需一阶导数

    (b)    校正保持正定性,因而下降性质成立

    (c)    无需计算逆矩阵,但具有超线性收敛速度

    (d)    每次迭代仅需要次乘法计算

    缺点是初始点距离最优解远时速度还是慢。

    解决方法是,迭代前期用最速下降法进行迭代,得到一定解以后用拟牛顿法迭代。

     

     

    致谢

    Deep Learning高质量交流群里的多位同学@ ParadiseLost,@一路走来 等等,那个MathType太好用了。

     

    参考文献

    【1】最优化理论与方法。袁亚湘,孙文瑜

    展开全文
  • 包括了一维最优化算法 如:0....其次,约束优化部分,提供了混合罚函数法(DFP),混合罚函数法(POWELL),综合约束函数双下降法、可变容差法、复合形法、网格法、随机实验法、解线性规划的单纯型法等等方法的源代码。
  • ABC带约束优化算法

    2019-04-12 19:25:58
    人工蜂群算法是模仿蜜蜂行为提出的一种优化方法,是集群智能思想的一个具体应用,它的主要特点是不需要了解问题的特殊信息,只需要对问题进行优劣的比较,通过各人工蜂个体的局部寻优行为,最终在群体中使全局最优值...
  • 机器学习中的最优化方法(一) 无约束优化方法* 掌握常用的优化方法对机器学习算法而言是必不可少的,本文只介绍无约束问题的优化,后续会介绍有约束的情况。 主要介绍以下几个内容: 1 优化概述 2 无约束问题的优化...
  • 惩罚函数也叫乘子法,求解带约束的非线性规划问题时,常用KKT条件列出满足条件的方程组,解方程组后即可得到最值点,但是满足KKT条件的方程组是一个非线性方程组,利用计算机求解很难给出通用算法,本篇介绍的惩罚...
  • 这个是我见过关于线性规划与非线性规划较为详细的课件,里面举例使用MATLAB编程来解决问题并简单的介绍了MATLAB中常用的几个函数。
  • - 最优化方法及其应用/郭科,陈聆,魏友华.-北京:高等教育出版社,2007.7(2013.7重印) 在第四章中,我们解决了确定搜索步长的问题,现在解决确定搜索方向的问题。 1、最速下降法 基本思路 搜索方向总沿着f(X)f...
  • 每一个实际问题,如果不是显式地至少也是...惩函数法是最常用的求解约束优化问题的方法。 我们可以用两种方式设计惩函数法。首先,在可行个体移近约束边界时就惩罚它;这种方法被称为内点法或闸方法。它不容许种群中
  • 这项工作在理论上将Pareto优化与惩罚方法进行了比较,后者是将约束优化转换为无约束优化常用方法。 我们证明,在两类约束布尔优化问题上,最小拟阵优化(P可求解)和最小成本覆盖(NP难),帕累托优化比惩罚函数...
  • 螺栓联接是煤矿机械中常用的一种联接方式,通过带螺栓多约束组件建立参数化模型,针对组件模型特性引入同步变化理论,构建了基于组件的改进型多约束优化数学模型。在实例分析和优化设计中,结合相关设计理论进行对比,...
  • 方法通过分析程序代码自动提取3类输入约束,随后使用这些约束引导符号执行更关注于核心功能代码。在KLEE中实现了上述优化框架,并对coreutils、binutils、grep、patch、diff这5个程序套件中的7个常用程序做了检测...
  • 1.程序适用于任意维解析函数的无约束优化问题,求解最小值及最小值点; 2.可实现的梯度法:最陡下降法、共轭梯度法、牛顿法、拟牛顿法等; 3.可选择的一维线搜索法:黄金分割法、Armijo准则、强Wolfe条件等; 4.动态...
  • 约束优化方法

    2017-10-01 21:17:25
    本文介绍了无约束优化的两种常用方法,梯度法和牛顿法,拟牛顿法和BFGS,Broyden类算法
  • 常用优化方法

    千次阅读 2018-05-18 14:14:15
    熟悉机器学习的童鞋都知道,优化方法是其中一个非常重要的话题,最常见的情形就是利用目标函数的导数通过多次迭代来求解无约束最优化问题。实现简单,coding方便,是训练模型的必备利器之一。 2. 几个数学概念 1)...
  • 约束优化方法之拉格朗日乘子法与KKT条件 文章目录一、无约束优化二、等式约束优化三、不等式约束优化四、参考文献 在约束最优化问题中,约束条件分为等式约束与不等式约束,对于等式约束的优化问题,可以直接应用...
  • 拓扑优化常用优化算法,移动渐进线方法,内含详细的程序说明,指出使用改算法的具体操作
  • 优化问题综述(四)有约束优化算法

    万次阅读 2018-09-04 14:27:42
    等式约束条件:解决方法是消元法或者拉格朗日法。 不等式约束条件:一般用KKT(Karush Kuhn Tucker)条件对偶求解 等式约束条件下的优化算法 问题的数学描述:minxf(x),s.t.,hi(x)=0,i=1,2,..,Iminxf(x),s.t.,hi...
  • 【机器学习】常用优化方法原理

    千次阅读 2018-01-02 21:39:20
    在ML/DL中,有许多优化方法可以选择,只有清楚了它们的原理才能更好地选择。 1、SGD 随机梯度下降是最经典的方法,其思想如下图所示: 首先求出m个样本的Loss的和,求这个和对于神经网络参数theta的梯度,并将...
  • 软件质量检测常用方法是软件测试,符号执行作为主流的测试技术已被广泛应用于学术界与工业界中。但是随着程序规模的增大和函数调用的增加,因某些路径约束条件的特殊性,而难以生成正确的测试用例,从而导致符号...
  • 优化方法常用数学符号的含义

    万次阅读 多人点赞 2019-02-27 18:22:06
    优化方法常用符号 min⁡x∈Ωf(x)f(x)在Ω上的最小值\min \limits_{x \in \Omega} f(x) \qquad f(x) 在 \Omega 上的最小值x∈Ωmin​f(x)f(x)在Ω上的最小值 max⁡x∈Ωf(x)f(x)在Ω上的最大值\max \limits_{x \in...
  • 粒子群算法求解带约束优化问题 源码实现

    千次阅读 多人点赞 2021-03-29 14:30:32
    粒子群算法求解带约束优化问题 源码实现 python实现。带你体验下粒子群算法是如何求解带等式约束、不等式约束、上下限约束的问题。
  • 常用的凸优化方法

    万次阅读 2017-10-24 21:45:17
    为什么凸优化这么重要?见知乎,写的很好 https://www.zhihu.com/question/24641575 http://blog.csdn.net/zkq_1986/article/details/52317258 1 梯度下降法 2 坐标下降法

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 84,869
精华内容 33,947
热门标签
关键字:

常用的约束优化方法