精华内容
下载资源
问答
  • 信赖域算法

    千次阅读 2018-10-02 16:28:51
    如果你关心最优化(Optimization),你一定听说过一类叫作“信赖域(Trust Region)”的算法。在本文中,我将讲述一下信赖域算法与一维搜索的区别、联系,以及信赖域算法的数学思想,实现过程。 【1】信赖域算法与一...

    如果你关心最优化(Optimization),你一定听说过一类叫作“信赖域(Trust Region)”的算法。在本文中,我将讲述一下信赖域算法与一维搜索的区别、联系,以及信赖域算法的数学思想,实现过程。

    【1】信赖域算法与一维搜索算法的区别、联系
    最优化的目标是找到极小值点,在这个过程中,我们需要从一个初始点开始,先确定一个搜索方向 d,在这个方向上作一维搜索(line search),找到此方向上的可接受点(例如,按两个准则的判定)之后,通过一定的策略调整搜索方向,然后继续在新的方向上进行一维搜索,依此类推,直到我们认为目标函数已经收敛到了极小值点。
    这种通过不断调整搜索方向,再在搜索方向上进行一维搜索的技术被很多很多算法采用,也取得了很实际的工程意义,但是,我们非要这样做不可吗?有没有另外一种途径,可以不通过“调整搜索方向→进行一维搜索”的步骤,也能求得极小值点?当然有,这就是信赖域算法干的好事。

    为了说明这两种途径所实现的算法的区别和联系,请允许我做一个可能不太恰当,但是比较形象的比喻:

    上图表述的是:如果把求最优解的过程比喻为“造一个零件”的过程的话,那么,使用一维搜索的那些算法和信赖域算法就像是两种不同的工艺,它们分别使用不同的技术(一维搜索&信赖域方法)——即两种不同的材料作为达成最终目标的基础。
    作为一个了解最优化理论并不多的人,我从我看到过的书得到的感受就是:相比使用一维搜索的那一类算法,貌似信赖域算法们的应用还不够那么多。当然这仅仅是个人感觉,勿扔砖...

    【2】信赖域算法的基本思想
    信赖域和line search同为最优化算法的基础算法,但是,从“Trust Region”这个名字你就可以看出,它是没有line search过程的,它是直接在一个region中“search”。
    在一维搜索中,从 xk 点移动到下一个点的过程,可以描述为: xk+αkdk 
    此处 αkdk 就是在 dk 方向上的位移,可以记为 sk 
    而信赖域算法是根据一定的原则,直接确定位移 sk ,同时,与一维搜索不同的是,它并没有先确定搜索方向 dk 。如果根据“某种原则”确定的位移能使目标函数值充分下降,则扩大信赖域;若不能使目标函数值充分下降,则缩小信赖域。如此迭代下去,直到收敛。

    关于这种寻优的方法,我这里又有一个比喻,希望能帮助你理解:

    要从上海火车站去人民广场,有两种方法:
    ①可以先定一个方向,比如先向西走,走着走着发现方向有点不对(人民广场应该是时尚地标啊,怎么越走感觉越郊区了呢),就调整一下方向,变成向东南方向走,诸如此类。

    ②用信赖域算法,就比如,我先划一个圈,然后在这个圈里面找离人民广场可能最接近的点,如果我的圈划得太大了,一下子就划到了莘庄(不熟悉上海的同学可以查一下地图),我一步就走到了上海南站,那还得了,马上给我回来,把圈缩小到两个地铁站的距离之内,然后再在里面找离人民广场最近的点。

    【3】信赖域算法的数学模型
    前面说了,根据一定的原则,可以直接确定位移,那么,这个原则是什么呢?
    答:利用二次模型模拟目标函数 f(x) ,再用二次模型计算出位移 s 。根据位移 s 可以确定下一点 x+s ,从而可以计算出目标函数的下降量(下降是最优化的目标),再根据下降量来决定扩大信赖域或缩小信赖域。
    那么,我该如何判定要扩大还是缩小信赖域呢?为了说明这个问题,必须先描述信赖域算法的数学模型:


    第一个式子就是我们用于模拟目标函数的二次模型,其自变量为 s ,也就是我们要求的位移。 gk 为梯度, Gk 为Hesse矩阵,袁亚湘的书上说,如果Hesse矩阵不好计算,可以利用“有限差分”来近似 Gk (不好意思我不懂),或者用拟牛顿方法来构造Hesse矩阵的近似矩阵。
    第二个式子中的 hk 是第 k 次迭代的信赖域上界(或称为信赖域半径),因此第二个式子表示的就是位移要在信赖域上界范围内。此外,第二个式子中的范数是没有指定是什么范数的,例如,是2-范数还是∞-范数之类的(在实际中都有算法用这些范数)。

    现在又回到了上面的问题:我该如何判定要扩大还是缩小信赖域呢?通过衡量二次模型与目标函数的近似程度,可以作出判定:
    第 k 次迭代的实际下降量为: Δfk=fk−f(xk+sk) 
    第 k 次迭代的预测下降量为: Δmk=fk−m(sk) 
    定义比值: rk=ΔfkΔmk 
    这个比值可以用于衡量二次模型与目标函数的近似程度,显然 r 值越接近1越好。

     

    由此,我们就可以给出一个简单的信赖域算法了。

    【4】信赖域算法的步骤
    一个考虑周全的信赖域算法可能非常麻烦,为了说明其步骤,这里只说明基本的迭代步骤:

    • 从初始点 x0 ,初始信赖域半径 h0=∥g0∥ 开始迭代
    • 到第 k 步时,计算 gk 和 Gk
    • 解信赖域模型,求出位移 sk ,计算 rk
    • 若 rk≤0.25 ,说明步子迈得太大了,应缩小信赖域半径,令 hk+1=∥sk∥4
    • 若 rk≥0.75 且 ∥sk∥=hk ,说明这一步已经迈到了信赖域半径的边缘,并且步子有点小,可以尝试扩大信赖域半径,令 hk+1=2hk
    • 若 0.25<rk<0.75 ,说明这一步迈出去之后,处于“可信赖”和“不可信赖”之间,可以维持当前的信赖域半径,令 hk+1=hk
    • 若 rk≤0 ,说明函数值是向着上升而非下降的趋势变化了(与最优化的目标相反),这说明这一步迈得错得“离谱”了,这时不应该走到下一点,而应“原地踏步”,即 xk+1=xk ,并且和上面 rk≤0.25 的情况一样缩小信赖域。反之,在 rk>0 的情况下,都可以走到下一点,即 xk+1=xk+sk


    【5】最重要的一种信赖域算法:Levenberg-Marquardt算法
    当信赖域模型中的范数 ∥s∥≤hk 取2-范数时(即 ∥s∥2≤hk ),就得到了Levenberg-Marquardt算法(简称LM算法)的数学模型:

    具体请看这里

    【6】信赖域算法的收敛性
    信赖域算法具有整体收敛性。这个证明我没看(太长了),此处略。

    转载自:https://www.codelast.com/%E5%8E%9F%E5%88%9B%E4%BF%A1%E8%B5%96%E5%9F%9Ftrust-region%E7%AE%97%E6%B3%95%E6%98%AF%E6%80%8E%E4%B9%88%E4%B8%80%E5%9B%9E%E4%BA%8B/

    展开全文
  • 信赖域方法

    2019-06-11 21:31:42
    参考: 1: https://www.codelast.com/原创信赖域trust-region算法是怎么一回事/

    理解信赖域最好的途径是与线(一维)搜索对比,理解其区别.在ceres中,就提供了两种求解器,一种是基于信赖域的,一种是基于线搜索.
    信赖域与线(一维)搜索之间的区别,可以用以下例子来理解;故事是这样的,永强头一天和王大拿约定第二天晚上一起喝酒,王大拿在山庄北边找一个店等永强,但是当时并没有说具体在哪家店.第二天永强从象牙山庄西边出发,去找王大拿.他有两种策略:一种是一维搜索,一种是信赖域.如果采用一维搜索的方案,永强已经确定了王大拿的方向(西北边),那他只要往那个方向走即可.一边走一边喊王大拿的名字,就可以确定走的距离,最终即可找到王大拿.如果采用信赖域的方案,永强首先划定一个10米的圆圈,在这个圈中找到里王大拿最近的地方(可以通过观察周边情况确定,如是否能看到周围有酒馆,是否是王大拿经常出没的地方等),然后不断画圈,最终把王大拿所在的酒馆找出来.

    一,线搜索方法

    在线搜索方法中,δx=akpk\delta x = a_kp_k 其中,aka_k是一个数值,表示步长,pkp_k表示与状态量相同维度的向量.一般来说,首先要确定方向pk=(Bk)1fkp_k=-(B_k)^{-1}\triangledown f_k. 根据BkB_k的不同, 线搜索分为如下三类

    1. Bk=IB_k = I 时,即为原始最陡梯度下降法
    2. Bk=2fkB_k = \triangledown^2 f_k, 即为牛顿法(若二阶导求不出来,用fkTfk\triangledown f_k^T\triangledown f_k来近似,则为高斯牛顿法)
    3. BkB_k为对称正定矩阵,为拟牛顿法.

    在确定完方向之后,如即采用最陡梯度下降法,pk=fkp_k = -\triangledown f_k. 下一步就是确定求步长aka_k. 当然我们希望目标函数:
    Minf(x+δx)=Minf(xakfk)Min f(x+\delta x) =Min f(x - a_k\triangledown f_k)
    当目标函数f为二阶时,上式是一个一元二次方程,可以求得其精确解;如f(x)=1/2x2f(x) = 1/2x^2, 有:pk=x,ak=1p_k = - x, a_k = 1.
    当然,我们会遇到目标函数不是二阶的时候,那我们很有可能求不出步长的精确解,不过没关系,优秀的革命前辈总结了四个经验性条件:Armijo条件,Curvature条件,Wolfe条件,Goldstein条件.符合这四个条件的步长,会是一个区间.在该区间中进行逐步二分,最终收敛.

    二,信赖域方法

    信赖域方法与线搜索方法的出发点不同,信赖域方法的得名即反应了其初衷:在一个可信赖的步长范围内,用另外一个函数去代替原始目标函数,求得在该范围内的一个极小值.我们首先以摄影测量中应用及其广泛的列文伯格马夸尔特(LM)算法给出样例,然后再给出标准信赖域方法的步骤.
    在LM中,目标函数是f(x)f(x), 在信赖域δx&lt;Δk|\delta x|&lt;\Delta _k内,可以以其二阶泰勒展开作为其近似:m(δx)=f(x)+fδx+1/2δxTfδxm(\delta x) = f(x) + f&#x27;\delta x + 1/2\delta x^Tf&#x27;&#x27;\delta x. 那么问题变为:
    Minm(δx)=f(x)+fδx+1/2δxTfδx=f(x)+gTδx+1/2δxTBδxMin m(\delta x) = f(x) + f&#x27;\delta x + 1/2\delta x^Tf&#x27;&#x27;\delta x = f(x) + g^T \delta x + 1/2\delta x^TB\delta x
    s.t.δx&lt;Δks.t. |\delta x|&lt;\Delta _k
    可以看出,不管目标函数是几次,其二阶泰勒展开均为二次,根据KKT条件,m(δx)m(\delta x)有最优解,存在一个λ\lambda, 满足:

    1. B+λI=gB + \lambda I = -g
    2. λ(Δδx)=0\lambda (\Delta - ||\delta x||) = 0
    3. B+λIB + \lambda I正定.

    B=JTJB = J^TJ, 则有:δx=(JTJ+λI)1JTb\delta x = -(J^TJ + \lambda I)^{-1}J^Tb

    参考:
    1:https://www.codelast.com/原创信赖域trust-region算法是怎么一回事/
    2:https://blog.csdn.net/fangqingan_java/article/details/46405669
    3:https://www.processon.com/view/link/5cffa80ce4b0f1ac03704d14 线搜索方法
    4:https://blog.csdn.net/fangqingan_java/article/details/46405669
    5: https://blog.csdn.net/frozenspring/article/details/78898308

    展开全文
  • 一类非光滑优化问题的信赖域方法,李曼玉,刘金魁,本文的目的在于将经典的信赖域方法推广到求解非凸非光滑优化问题。首先利用拟割向量构建信赖域子问题,接着将线搜索和信赖域方法
  • 无约束优化的Broyden族信赖域算法,耿玲玲,贺祖国,本文给出了一种信赖域方法与线搜索方法的结合,信赖域方法是近二十年发展起来的一类重要的数值计算方法,它与传统的线搜索方法并
  • 域Newton 算法的新型ELM网络(TRON-ELM), 并采用信赖域Newton 算法求解ELM网络的输出权值. 该算法首先 构造一个ELM网络代价函数的Newton 方程, 并将其作为一个无约束优化问题, 采用共轭梯度法求解, 避免了求代价...
  • 信赖域方法记录

    2020-01-04 11:56:44
    这里有一个东北大学的关于"信赖域方法"的教学链接,比较基础和人性化.

    这里有一个东北大学的关于"信赖域方法"的教学链接,比较基础和人性化.

    展开全文
  • 信赖域方法研究

    2012-12-10 16:50:55
    信赖域方法与线搜索技术一样,是优化算法中的一种保证全局收敛的重要方法
  • 求解非线性规划的修正滤子信赖域方法
  • 非光滑优化的信赖域算法的改进,雷蕾,,信赖域方法是处理非线性优化的一种相对较新的方法。良好的可靠性、稳定性和收敛性使得它在数值优化算法领域中占有重要地位。本文
  • 一种求解锥模型信赖域子问题的算法,黄梓馨,艾文宝,本文主要探讨的是带锥模型的信赖域子问题的求解。我们通过对具有良好定义域的锥模型信赖域子问题的研究,提出了一个能有效地解决
  • 改进的固定步长的自适应信赖域算法,杭丹,王晓燕,对于无约束优化问题,在HEILONG文章的启示下构造了一个新的R-函数,并提出了一种新的不重解子问题的非单调自适应信赖域算法。与其文
  • 信赖域算法matlab实现

    热门讨论 2011-09-15 17:13:18
    使用matlab实现的信赖域算法,中文注释
  • Trust Region Methods 信赖域方法 Problem Description 问题描述 Optimality Conditions 最优化条件 Line Search Methods 线搜索方法 Trust Region Methods 信赖域方法 Direct Search Methods 直接搜索法 Nonlinear...

    Trust Region Methods 信赖域方法

    • Problem Description 问题描述
    • Optimality Conditions 最优化条件
    • Line Search Methods 线搜索方法
    • Trust Region Methods 信赖域方法
    • Direct Search Methods 直接搜索法
    • Nonlinear Least Squares(NLS) 非线性最小二乘法 – LMA

    信赖域算法介绍

    最优化的目标是找到极小值点,在这个过程中,我们需要从一个初始点开始,先确定一个搜索方向 p ,在这个方向上做线搜索(line search),找到此方向上的可接受点(例如,按两个准则的判定)之后,通过一定的策略调整搜索方向,然后继续在新的方向上进行一维搜索,依此类推,直到我们认为目标函数已经收敛到了极小值点。

    信赖域算法与一维搜索算法的区别、联系

    在Jorge Nocedal和Stephen J. Wright的《Numerical Optimization》一书的第2.2节介绍了解优化问题的两种策略-line search和trust region。本质上它们的作用都是在优化迭代过程中从当前点找寻下一点。它们的最大区别是先确定步长还是先确定方向

    • 信赖域方法与线搜索算法不同之处其一在于, 后者先产生搜索方向p(k)\underline p^{(k)}, 再求一合适的步长α(k)\alpha^{(k)}, 迭代依照的如下形式进行

    • θ(k+1)=θ(k)+α(k)p(k) \underline\theta^{(k+1)} =\underline\theta^{(k)}+\alpha^{(k)} \underline p^{(k)}

    • 而trust region方法则先把搜索范围缩小到一个小的范围,小到能够用另一个函数(Model function)去近似目标函数(Objective function),然后通过优化这个model function来得到参数更新的方向及步长。

      同时选取搜索方向与步长 (或者说, 先划定步长的范围, 再选取搜索方向) . 迭代的方式为 $\underline\theta^{(k+1)} =\underline\theta^{(k)}+ \underline p^{(k)} $ (可以认为此时步长融于p(k)\underline p^{(k)} 中)

    线搜索方法用得比信赖域方法广泛,是不是说明信赖域方法没有优点呢?
    举个简单的例子,求解:

    image-20200809111247564

    如果直接用线搜索,初始点在 0 处无法进行下一步的搜索,因为梯度为0. 而使用TR:,显然可以往最优方向进行搜索。

    https://blog.csdn.net/purgle/article/details/73800186

    信赖域算法的基本思想

    下面是线搜索算法与信赖域算法的一个图例.

    信赖域与线搜索的一个比较
    • 图中, 椭圆虚线为建立的模型(model function) m(k)m^{(k)} 的等高线, 而圆形虚线为信赖域的边界.
    • 从图中可以看到, 线搜索得到的函数值下降并不客观 (当然这可能与 m(k)m^{(k)} 对目标函数的近似程度有关) ,
    • 而信赖域方法得到的下一迭代点被牢牢地锁在信赖域中, 反而带来了较大的下降.

    trust region方法则先把搜索范围缩小到一个小的范围,小到能够用另一个函数(Model function)去近似目标函数(Objective function),然后通过优化这个model function来得到参数更新的方向及步长。

    由上面的表述我们可以得到信赖域方法的几个要素

    1. 近似模型函数 m(k)(p)m^{(k)}(\underline p)
    2. 可信赖域 region of trust TΔ\mathcal T_\Delta
    3. 迭代增量 p\underline p (包括步长和方向)
    • 近似目标函数的 model fuction 为:
      J(θ(k))m(k)(0) J(\underline\theta^{(k)}) \approx m^{(k)}(\underline 0)

    • 代替最小化目标函数,TR 方法最小化 model function
      minp(J(θ(k)+p))minp(m(k)(0+p)) \min_{\underline p}\left(J(\underline\theta^{(k)}+\underline p)\right) \approx \min_{\underline p}\left(m^{(k)}(\underline 0 + \underline p)\right)

    • 信任域(TR)方法还计算当前迭代 的 region of trust TΔ\mathcal T_\Delta 。 如果下一个迭代点 θ(k+1)=θ(k)+p\underline\theta ^{(k + 1)} = \underline\theta ^{(k)} + \underline p 还在这个信任域内,则该 model function 将很好地近似于原始目标函数。

    • 很可能,这个近似在信任域之外不成立

    • 近似模型的quality计算指标:(分子表示函数实际减小的值;分母表示近似模型减少的值)
      ρ(k)=J(θ(k))J(θ(k)+p)m(k)(0)m(k)(p) \rho^{(k)} = \frac{J(\underline\theta ^{(k)})-J(\underline\theta ^{(k)}+\underline p)}{m^{(k)}(\underline 0)-m^{(k)}(\underline p)}

      • ρ(k)<1\rho ^{(k)} < 1 表示模型函数下降速度快于原始函数
      • ρ(k)=1\rho ^{(k)} = 1 表示完美契合
      • ρ(k)>1\rho ^{(k)} > 1 表示原始函数的下降速度比模型函数的下降速度快

    因此,近似模型函数 m(k)(p)m^{(k)}(\underline p) 进行了优化 w.r.t 迭代增量 p\underline p ,且该解限制其在信赖域范围内
    minp{m(k)(p)}w.r.tpTΔ \min_{\underline p}\left\{m^{(k)}(\underline p)\right\}\quad w.r.t \quad\underline p\in\mathcal T_{\Delta}

    • 信赖域算法同时优化步长和搜索方向,而线搜索算法有一个顺序的方法

      Trust region methods optimize the step length and the search direction simultaneouslyLine search algorithms have a sequential approach

    数学模型

    基本形式

    • 信赖域算法:通常选取二次函数(quadratic model function)逼近真实模型的
      J(θ(k)+p)=J(θ(k))+[dJ(θ)dθθ(k)]Tp+12pTB(k)pm(k)(p) J(\underline \theta^{(k)} + \underline p) = \underbrace{J(\underline\theta^{(k)}) +\left[\frac{dJ(\underline\theta)}{d\underline\theta}\Bigg|_{\underline\theta^{(k)}} \right]^T\underline p + \frac12\underline p^T\underline B^{(k)}\underline p }_{m^{(k)}(\underline p)}

      和拟牛顿法法的近似“损失函数”一样

      如果B(k)\underline B^{(k)} 选择为Hessian,则为TR的牛顿方法。一般情况下会(比如 Hessian非正定的时候)用对称非奇异矩阵 B(k)\underline B^{(k)} 去近似Hessian矩阵;

    • 在每次迭代中半径为Δ(k)\Delta^{(k)} 的球用来定义信赖域的范围 TΔ\mathcal T_\Delta

      image-20200810114132418

    • 因此,我们必须解决下面的优化子问题:关于 $p $ 的带约束的最优化问题,
      minp{m(k)(p)}=minp{J(θ(k))+[dJ(θ)dθθ(k)]Tp+12pTB(k)p} \min_{\underline p}\left\{m^{(k)}(\underline p)\right\} =\min_{\underline p} \left\{ J(\underline\theta^{(k)}) +\left[\frac{dJ(\underline\theta)}{d\underline\theta}\Bigg|_{\underline\theta^{(k)}} \right]^T\underline p + \frac12\underline p^T\underline B^{(k)}\underline p \right\}
      要求:参数 pp 被限制在一个球形区域内
      p2Δ(k) \left|\left| \underline p\right| \right|_2 \le \Delta^{(k)}

    Δ(k)\Delta^{(k)} 的选择

    近似模型的quality计算指标:
    ρ(k)=J(θ(k))J(θ(k)+p)m(k)(0)m(k)(p) \rho^{(k)} = \frac{J(\underline\theta ^{(k)})-J(\underline\theta ^{(k)}+\underline p)}{m^{(k)}(\underline 0)-m^{(k)}(\underline p)}

    其中分子表示函数实际减小的值;分母表示近似模型减少的值。

    • 如果 ρ(k)<0\rho ^{(k)} < 0,一般情况下分母不可能小于0,因为目标函数求解的是最小值;此时说明分子小于0,即下一个目标点比上一步大,此时需要舍弃
    • 如果 0<ρ(k)00<\rho ^{(k)} \approx 0 大于0,但是接近0,说明模型(分母)变化范围比较大,但是实际(分子)改变比较小,此时应该减少信赖域范围Δk
    • 0<ρ(k)<10< \rho ^{(k)} < 1 大于0但是明显小于1,表示模型函数下降速度快于原始函数,此时可以不用调整
    • 0<ρ(k)10< \rho ^{(k)} \approx 1 大于0并且接近1,表明近似效果好,可以适当增加信赖域半径Δk
    • ρ(k)>1\rho ^{(k)} > 1 表示原始函数的下降速度比模型函数的下降速度快

    信赖域的大小对于每步的效果直观重要. 若信赖域过小, 则算法可能就会错过充分下降的机会; 若过大, 信赖域中模型m**k的极小点可能就与目标函数f的极小点相距甚远, 从而又得增大信赖域.

    而信赖域算法是根据一定的原则,直接确定位移 sk ,同时,与一维搜索不同的是,它并没有先确定搜索方向 dk 。如果根据“某种原则”确定的位移能使目标函数值充分下降,则扩大信赖域;若不能使目标函数值充分下降,则缩小信赖域。如此迭代下去,直到收敛

    信赖域算法流程

    由此我们得到信赖域算法的步骤

    1. 给出初始点 θ(0)\underline\theta^{(0)} 和初始信赖域半径 Δ(0)\Delta^{(0)},开始迭代 k

    2. 计算模型在第k步的近似 m(k)m^{{(k)}}:求解最优化子问题,得到试探步长 p\underline p

    3. 求解 model accurancy ρ\rho at p\underline p

    4. ρ(k)14\rho^{(k)}≤\frac14,缩小(shrink)信赖域半径,令
      Δ(k+1)=14Δ(k) \Delta^{(k+1)} = \frac14 \Delta^{(k)}
      k = k + 1 返回第一步

    5. else:

      • ρ(k)>0.75\rho^{(k)}>0.75,扩大信赖域半径,使得 Δk+1=2Δ\Delta_{k+1}=2\DeltaΔk+1=2Δ。
      • 若0.25<rk≤0.750.25<r_k\le 0.750.25<r**k≤0.75。维持当前信赖域半径。
      • 若rk<0r_k<0r**k<0,缩小信赖域重新计算当前试探步长。
    这里写图片描述

    image-20200810125755206

    image-20200818185635699

    [关于子问题的最优解]

    https://blog.csdn.net/fangqingan_java/article/details/46956643

    信赖域问题的子问题表示为:
    minp{m(k)(p)}=minp{J(θ(k))+[dJ(θ)dθθ(k)]Tp+12pTB(k)p} \min_{\underline p}\left\{m^{(k)}(\underline p)\right\} =\min_{\underline p} \left\{ J(\underline\theta^{(k)}) +\left[\frac{dJ(\underline\theta)}{d\underline\theta}\Bigg|_{\underline\theta^{(k)}} \right]^T\underline p + \frac12\underline p^T\underline B^{(k)}\underline p \right\}
    该问题为标准的带不等式约束的二次优化问题,可以根据KKT条件(后面会深入介绍)得到该问题的最优解
    定理 1
    向量 p\underline p^* 为信赖域子问题的最优解,仅当 p\underline p^* 是可行解,且存在标量 λ0\lambda \ge 0 使得下面的三个条件成立:

    image-20200810131321611

    其中第二个条件又称为互补条件. 此定理揭示了信赖域方法的优势: 就算B**k是不定的, 我们仍然有子问题达到全局极小的充要条件. 相比之下, 其他方法往往至多有充分条件.

    从下图中可以看出最优解 p\underline p^* 和参数λ\lambda 的关系

    这里写图片描述
    • 当半径参数 Δ=Δ1\Delta = \Delta _1 时,最优解为 p3p^3 此时相当于没有约束,此时 λ=0\lambda= 0

    • 当半径参数 Δ=Δ2\Delta = \Delta _2 时,最优解被球形约束限制,此时满足 Δ=pΔ=||p^∗||,根据上面条件(a)有
      λp=Bpg \lambda p^* = -Bp^*-g
      如果能够找到这样的p满足这些条件就能找到最优解。

    ⭕折线算法 Dog-Leg Method

    目的:找到最小化问题的近似解

    折线算法可用于B(k)\underline B^{(k)}为正定的情形

    定义完全步(Full Step)

    我们在线搜索牛顿法时有:

    image-20200810132449591

    对于TR子优化问题
    minp{m(k)(p)}=minp{J(θ(k))+[dJ(θ)dθθ(k)]Tp+12pTB(k)p} \min_{\underline p}\left\{m^{(k)}(\underline p)\right\} =\min_{\underline p} \left\{ J(\underline\theta^{(k)}) +\left[\frac{dJ(\underline\theta)}{d\underline\theta}\Bigg|_{\underline\theta^{(k)}} \right]^T\underline p + \frac12\underline p^T\underline B^{(k)}\underline p \right\}
    求TR中的位移 p\underline p

    折线算法

    折线算法可用于 B(k)\underline B^{(k)} 为正定的情形。寻找信赖域半径 Δ(k)\Delta^{(k)} 和最优解 p(k)(Δ)\underline p^{*(k)}(\Delta) 之间的关系。

    以下省去上标k, 并以 p(Δ)\underline p (\Delta) 表示解以强调其对 $\Delta $ 的依赖性.

    1. 使用高斯牛顿法得到迭代步长:当 p(k)Δ(k)\underline p^{(k)}\le \Delta^{(k)}时 (信赖域非常大), 显然应当有 p(k)(Δ)\underline p^{*(k)}(\Delta)

      image-20200823205856310

      若计算出pND<Δ\underline p_{ND}<\Delta 已经不用继续计算下去 – case 1

    2. pt\underline p_{t}】当 p(k)>>Δ(k)\underline p^{(k)} >> \Delta^{(k)} 时(信赖域非常小), 可认为 m(k)(p)m^{(k)}(\underline p) 问题中的中的二次项(梯度)对子问题的求解影响较小, 从而忽略二次项,即:
      m(k)(p)=J(θ(k))+[dJ(θ)dθθ(k)]TgTpt m^{(k)}(\underline p) =J(\underline\theta^{(k)}) +\underbrace{\left[\frac{dJ(\underline\theta)}{d\underline\theta}\Bigg|_{\underline\theta^{(k)}}\right]^T}_{g^T}\underline p_{t}
      calculate the exact minimum of quadratic function along the stepest descent function is equal to 求二次函数的精确最小值沿最小步下降函数等于

      image-20200823205911350

    3. ps【ps\underline p_s
      ps=pNDpt=[B(k)]1[dJ(θ)dθθ(k)]+[dJ(θ)dθθ(k)]=[I[B(k)]1][dJ(θ)dθθ(k)] \underline p_s =\underline p_{ND} -\underline p_t =- [\underline B^{(k)}]^{-1} \left[\frac{dJ(\underline\theta)}{d\underline\theta}\Bigg|_{\underline\theta^{(k)}} \right] + \left[\frac{dJ(\underline\theta)}{d\underline\theta}\Bigg|_{\underline\theta^{(k)}} \right]=\left[I-[\underline B^{(k)}]^{-1}\right]\left[\frac{dJ(\underline\theta)}{d\underline\theta}\Bigg|_{\underline\theta^{(k)}} \right]

    我们用 p(τ);τ[0,2]\underline p(\tau);\tau\in[0,2] 表示折线轨迹, 其严格的数学表达为
    KaTeX parse error: No such environment: equation at position 30: …\tau) = \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲}̲ \left\{ \begin…

    根据折线算法得到的就是折线轨迹与信赖域边界的交点

    对半径为 Δ\Delta 的信赖域使用DogLeg方法计算出来的步长为
    KaTeX parse error: No such environment: equation at position 30: …\tau) = \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲}̲ \left\{ \begin…

    可以看到,DogLeg方法实际上使用了如下策略:

    1. 如果高斯牛顿法的步长小于信赖域半径,则等同于高斯牛顿法

      image-20200818184927729
    2. 如果高斯牛顿法和梯度下降法步长都大于信赖域半径,则将梯度下降法的步长缩放到信赖域半径

      image-20200818185039879

      求$\tau $ 归一法

    3. 如果不满足以上条件,则以连接二条轨迹,与信赖域边界相交于某一点d,从原点指向d的向量即为本次迭代的步长。

      image-20200818185140495

      image-20200819171234507

    Direct Search Methods 直接搜索法

    • Box Search
    • Section 坐标搜索算法
    • Nelder Mead 单纯形

    有时候目标函数的梯度不可用

    image-20200810152755124

    介绍

    • 首先,直接搜索方法在实践中效果很好
    • 不需要梯度信息
    • 一些方法只使用目标函数JJ在特定搜索点的排名信息, 比当 JJ 不存在数值分析性

    缺点:

    • 有时直接搜索方法不收敛,不幸的是,收敛性很难证明。
    • 在许多情况下,它们在收敛速度方面表现不佳

    类型介绍:

    image-20200810153222770

    https://blog.csdn.net/m0_37854871/article/details/84969300

    1. Box Search

    • 将搜索空间分割成等距的box
    • 计算box边缘的所有目标函数值并取最小值
    • 缺点:存在维度灾难
    • 因此,有一些方法可以使用生物原理(遗传算法)来生成一个boxes子集。
    image-20200811103801498

    2. Section 坐标搜索算法 (属于线搜索算法)

    坐标搜索和模式搜索方法并不从函数值中显式地构建目标函数的模型, 而是从当前迭代点出发沿着特定的方向寻找具有更小函数值的点. 若找到了这样的点, 它们就步进并重复之前的过程, 当然此前可能会对之前的搜索方向做一些改动. 当没有满意的点存在时, 算法就可能会调整沿着当前搜索方向前进的步长, 或直接产生新的搜索方向.

    image-20200811103932386

    The process of finding a solution might be inefficient or will be even impossible if there are valleys or ridges

    坐标搜索方法(也称为坐标下降法交替变量法) 循环遍历 n 个坐标方向 e1,e2,,ene_1,e_2,\ldots,e_n, 在每个方向上均以线搜索获取新的迭代点.

    一定是先从 θ1\underline\theta_1 方向开始的

    具体说来, 第一次迭代中, 我们仅改变xxx的第一个分量x1x_1x1并寻找极小(或至少减小)目标函数的这一分量的新值. 下一步迭代中, 则对第二个分量 x2x_2x2进行同样的操作. 在nnn步迭代后, 我们又回到第一个变量重复遍历.

    尽管简单直观, 但此法在实际操作中却可能十分低效, 就比如下图中表示的, 我们将坐标搜索方法应用于带两个变量的二次函数上.图中显示, 经几步迭代后, x1,x2x_1,x_2x1,x2向解的行进都明显变慢.

    coordinate search method

    就算坐标搜索收敛于一解, 一般来说它也要比最速下降法慢得多, 并且这一差距随着变量数的增加而越变越大. 不过由于坐标搜索不需要计算梯度∇fk\nabla f_k∇f**k, 且它在变量耦合程度不高时的效果还不错, 因此它仍是优化目标函数的有效方法.

    a sectioning algorithm would never reach the real minimum at [ ] * 0 0 T θ = exactly. (Or it would need an infinite number of iterations).

    https://blog.csdn.net/m0_37854871/article/details/84969300#3__114

    3. ⭕Nelder Mead

    • 目的:使用更复杂的方法确定搜索方向

    • 记住:没有可用的梯度信息

    • 想法:评估几个点,对它们进行排名,试图通过把最坏的点向最好的点移动来改善结果

      Idea: Evaluate several points, rank them, try to improve the result by shifting the worst point in the direction of the best point(s)

    定义:Simplex 单纯形

    image-20200811104918480

    3 个越是 4个顶点

    Nelder-Mead单纯形反射方法自其1965年被发明以来一直是广受欢迎的DFO算法。其名称来源于在算法的任意阶段, 我们都保持对单纯形 SS 的空间 Rl\R^l 中的 l+1l+1 个顶点(vertices)追索,它们形成的凸腔构成单纯形. (这一方法与线性规划中的单纯形法没有任何关联)。 给定有顶点 的单纯 θ(0),...,θ(l)\underline\theta^{(0)},...,\underline\theta^{(l)} 的单纯形SS , 我们可定义关联矩阵

    算法

    Nelder-Mead算法中的单次迭代中, 我们移除具有最差函数值的顶点并代之以具更好值的点. 而新点则是通过沿着连接最差顶点与剩余顶点中心的线反射、扩张或收缩单纯形得到。若以这种方式我们无法找到更好的点, 我们就仅保持具最好函数值的点不动,,而令其他的顶点向该值移动以收缩单纯形.

    下面我们来详细描述算法的一次迭代过程.

    • 该方法生成初始工作单纯形。

    • 先定义一些符号: 当前单纯形的 l+1l+1 个顶点 θ(0),...,θ(l)Rl\underline\theta_{(0)},...,\underline\theta_{(l)}\in\R^l,计算每个点的目标函数值,并对他们进行排序,满足目标函数值从小到大:
      J(θ(1))J(θ(2))J(θ(l+1)) J(\underline\theta_{(1)})\le J(\underline\theta_{(2)})\le\cdots \le J(\underline\theta_{(l+1)})
      另外对这些点进行命名:

      • “best vertex”θ(1)=θ(b)\underline \theta{(1)} = \underline\theta^{(b)}
      • “second best vertex”θ(2)=θ(sb)\underline\theta_{(2)} = \underline\theta^{(sb)}
      • “second worst vertex”θ(l)=θ(sw)\underline\theta_{(l)} = \underline\theta^{(sw)}
      • “worst vertex”θ(l+1)=θ(w)\underline\theta_{(l+1)} = \underline\theta^{(w)}

      Remark

      in R2\R^2 we denote θ(sb)=θ(sw)=θ(m)\underline\theta^{(sb)} = \underline\theta^{(sw)} = \underline\theta^{(m)} as “middle vertex

    • 通过执行一系列由基本转换组成的转换(transformation),尝试沿着顶点的方向移动(shift)最坏的顶点

      • Reflection 反射
      • Expansion 扩张
      • (inner/outer) Contraction
      • Shrinking

    1. reflection

    每个转换的performance取决于目标函数的局部属性/形状。例如在如下区域进行reflection反射

    image-20200811112810345
    • the worst vertex θ(w)\underline\theta ^{(w)} 绕 centroid c\underline c reflect 转换:

      image-20200811113440940

    • 计算新点的坐标:
      θ(r)=c+α(cθ(w))αR \underline\theta^{(r)} = \underline c + \alpha\left(\underline c - \underline\theta^{(w)}\right)\quad \alpha\in \R
      记个点的目标函数值为:
      J(θ(r))=J(r) J(\underline\theta^{(r)}) = J^{(r)}

      中心点 c\underline c 怎么计算的?

    cc is the centroid of all vertices other than the worst, the centroid of n arbitrary points is given by
    c=1ni=1nθ(i) \underline c = \frac1n\sum_{i=1}^ n\underline\theta_{(i)}

    • 反射变换的结果:如果新的点的函数值小于倒数第二差的点,则将最差的点舍弃,将此新点加入

      image-20200811113842825

    2. Explansion

    例如在如下区域进行 explansion

    image-20200811113941221
    • 假设经过 reflection 得到的新点 θ(r)\underline\theta^{(r)} 的目标函数值比最优点还低:J(r)<J(b)J^{(r)}<J^{(b)},尝试进一步改进解决方案并扩展单纯形

      image-20200811114258743

    • 计算扩展的新点θ(e)\underline\theta^{(e)}的新坐标
      θ(e)=c+γ(cθ(w))γR \underline\theta^{(e)} = \underline c + \gamma(\underline c - \underline\theta^{(w)}) \quad \gamma \in\R

    • 扩张变换的结果:如果新的点的函数值小于被扩张的点,将此新点加入替换被扩张的点

      image-20200811114545688

    3. outer contraction

    例如在如下区域进行 outer contraction

    image-20200811114633357

    尝试对 reflect 后的点进行 outer contraction

    image-20200811114938403

    • θ(r)\underline\theta^{(r)} outer contraction 到点 θ(oc)\underline\theta^{(oc)}
      θ(oc)=c+β(θ(r)c)βR \underline\theta^{(oc)} = \underline c + \beta(\underline\theta^{(r)} - \underline c) \quad \beta \in \R

    • outer contraction 变换的结果:如果新的点的函数值小于 θ(r)\underline\theta^{(r)} 的目标函数值,将此新点加入替换原来的点

      image-20200811115405778

    4. inner contraction

    例如在如下区域进行 inner contraction

    image-20200811115457054

    尝试对 the original simplex 进行 inner contraction,即不将 最差的点先进行 反射操作,再 contraction,而直接对最差的点进行 contraction

    image-20200811115915458

    • θ(w)\underline\theta^{(w)} outer contraction 到点 θ(ic)\underline\theta^{(ic)}
      θ(ic)=c+β(θ(w)c)βR \underline\theta^{(ic)} = \underline c + \beta(\underline\theta^{(w)} - \underline c) \quad \beta \in \R

    • inner contraction 变换的结果:如果新的点的函数值小于 θ(w)\underline\theta^{(w)} 的目标函数值,将此新点加入替换原来的点

      image-20200811120030696

    5. shinking

    例如在如下区域进行 shinking

    image-20200811120135477

    保留最忧点不动,其它点按比例缩放

    image-20200811120232874

    shrinking的结果为:

    image-20200811120254263

    总结 Nelder Mead 算法流程:

    image-20200811120415464

    Final remarks:

    • 尽管在1998年已经推导出了一组目标函数和初始simplexe且具有可证明的收敛性,但对该算法的严格分析仍是困难的。然而,即使在简单的情况下,算法也可能失败。
    • 单纯形算法(Nelder Mead)与数值数学和以前的ODS术语中涉及的线性规划的数值单纯形算法无关。

    Nonlinear Least Squares(NLS) 非线性最小二乘法 – LMA

    image-20200811121249069

    二:问题定义

    【非线性最小二乘法】

    image-20200811165043744

    • 目的:找到适合给定输入(𝑢)和最佳输出数据(𝑦)的最佳曲线(二次)参数(parameterization)

    • 例子:找到下面曲线的参数 θ1,θ2,θ3,θ4\theta_1,\theta_2,\theta_3,\theta_4,使它能够最优拟合数据
      f(u)=θ1e(θ2u)+θ3e(θ4u) f(u) = \theta_1e^{(\theta_2 u)}+\theta_3e^{(-\theta_4 u)}


    • 假设我们有一组给定的(测量的)数据 y[1],y[2],...,y[N]\underline y^{[1]},\underline y^{[2]},...,\underline y^{[N]} , 以及对应的输入点 u[1],u[2],...,u[N]\underline u^{[1]},\underline u^{[2]},..., u^{[N]}

    • 定义一个模型函数(moderl function),以最优拟合这些测量值
      y=m(u,θ) \underline y = \underline m(\underline u,\underline \theta)

    • 定义一个目标函数(objectivefunction):使用测量曲线和参数化曲线的平方和

      Using the sum of squares between measurement and parameterized curve

      image-20200811165954231

    • 使用第2章的搜索技术来最小化目标函数 求解

    image-20200819221145135
    J(θ)=123θ1eθ22+12112θ2eθ32+12263θ3eθ42 J(\underline\theta)=\frac12||3-\theta_1e^{\theta_2}||^2+\frac12||11-2\theta_2e^{\theta_3}||^2 + \frac12||26-3\theta_3e^{\theta_4}||^2

    image-20200822112919032

    线性 model function为:
    y=ax+b y = ax+b
    则优化问题为:
    mina,bJ=i=010(yi(axi+b))2 \min_{a,b} J=\sum_{i=0}^{10} (y_i-(ax_i+b))^2

    三:问题的解

    NLS问题的有趣特性是目标函数的 梯度Hessian 矩阵的近似容易求得

    • Gradient of J(θ)J(\theta)

      image-20200811170623404

    • The approximation of the Hessian of J(θ)J(\underline\theta)

      image-20200811170725958

    由高斯牛顿法

    image-20200810132449591

    • 如果我们现在应用牛顿法得到高斯牛顿搜索方向 pGN\underline p_{GN} (参见Ch.2幻灯片47)

      image-20200811170953056

    • 改进的牛顿法中插入(∗)和(∗∗)会得到Levenberg Marquardt搜索方向

      image-20200811171058678

    非约束优化总结

    image-20200811171150159

    线搜索&信赖域

    image-20200811171312733

    基于梯度的方法

    需要目标函数的一次导数信息

    Steepest descent 最速梯度下降法

    • 梯度往往不是最优搜索方向
      • [代数] 由于收敛速度慢,通常在谷中失败

    基于Hessian的方法

    需要目标函数的梯度信息和二次 Hessian 信息

    牛顿法

    • 搜索方向根据Hessian 调整
      • better. perform. in valleys
    • 在最优值附近,可以一步达到最小值
    • Hessian has to be pos. def.
      • 如果非正定:Modified-Newton

    拟牛顿法

    • 目标函数不提供Hessian,但梯度是连续可微的
      • Secant approximation of the Hessian

    信赖域法

    • 目标函数用一个(通常是二次的)模型函数逼近
    • 模型函数在信赖域提供了一个很好的近似
      • Step size and search direction are optimized simultaneously

    直接搜索

    image-20200811171337888

    无梯度信息

    Box Search:维度灾难

    Sectioning

    • 沿着坐标轴方向使用线搜索技术确定最小值
    • 如果函数包含谷底(例如香蕉函数),则此算法会失效
    • 不是所有问题可以由独立优化参数解决

    Simplex Algorithm

    • 单纯形算法自动适应问题
      • 对含有 valleys的问题表现较好

    于收敛速度慢,通常在谷中失败

    基于Hessian的方法

    需要目标函数的梯度信息和二次 Hessian 信息

    牛顿法

    • 搜索方向根据Hessian 调整
      • better. perform. in valleys
    • 在最优值附近,可以一步达到最小值
    • Hessian has to be pos. def.
      • 如果非正定:Modified-Newton

    拟牛顿法

    • 目标函数不提供Hessian,但梯度是连续可微的
      • Secant approximation of the Hessian

    信赖域法

    • 目标函数用一个(通常是二次的)模型函数逼近
    • 模型函数在信赖域提供了一个很好的近似
      • Step size and search direction are optimized simultaneously

    直接搜索

    [外链图片转存中…(img-3UpmtI1z-1603197799950)]

    无梯度信息

    Box Search:维度灾难

    Sectioning

    • 沿着坐标轴方向使用线搜索技术确定最小值
    • 如果函数包含谷底(例如香蕉函数),则此算法会失效
    • 不是所有问题可以由独立优化参数解决

    Simplex Algorithm

    • 单纯形算法自动适应问题
      • 对含有 valleys的问题表现较好
    展开全文
  • 信赖域方法和线搜索类似都是迭代方法,与其不同的是,每次迭代时,在一个选定的可信赖区域内,选择当前迭代点的近似模型 mkm_k ,然后计算最优步长;如果步长不合适,可以对区域进行缩放。该小结主要介绍: 信赖域...
  • 提出并实现了用于广域阻尼控制器结合参数设计的新方法,结合非线性时域仿真技术与信赖域方法,解决了优化目标函数构造、控制参数初值获取和信赖域法子问题模型获取3个子问题,实现了多运行方式下、多个广域阻尼控制器的...
  • 提出了基于柔度的最小...采用信赖域方法求解该问题,使优化过程具有更强的鲁棒性和可靠性,同时解决了柔度灵敏度方法应用在复杂结构中的问题。最后,通过某导弹发射台的骨架损伤数值仿真,验证了该方法的可行性和有效性。
  • 信赖域狗腿(dogleg)方法

    万次阅读 2018-06-03 18:14:53
    信赖域狗腿方法 信赖域方法(Trust-region methods)又称为TR方法,它是一种最优化方法,能够保证最优化方法总体收敛。现今,信赖域算法广泛应用于应用数学、物理、化学、工程学、计算机科学、生物学与医学等学科...
  • 我们需要比较不同信赖域算法的作用以及信赖域算法和线搜索型方法的比较。我们的数值结果需要包括函数的最优值,如果条件允许的话还需要提供最优点,函数调用次数和迭代次数以及程序的运行结果,如果结果不满足条件,...
  • 基于改进的信赖域算法的双极性波形SHEPWM的多重解
  • 信赖域算法中Dogleg算法的demo,被优化的函数很简单,不过算法框架还是正确的
  • 提出利用信赖域狗腿法解决通用非球面光学元件抛光后置求解的强非线性问题。基于低序体表示和齐次变换方法建立适用于任意非球面面形和任意轨迹抛光的正向运动学模型;基于信赖域狗腿法建立强非线性正向运动学模型的...
  • 解等式约束的信赖域子问题,经典方法,文件很小
  • 对无约束最优化问题提出了一类新的带线搜索的非单调自适应信赖域算法.新算法采用自适应技术,当试验步不成功时,不重解信赖域子问题,而采用Wolfe线搜索,故相对于原有的算法减少了计算量.并在适当的条件下,证明了算法的...
  • 计算柯西点列,即最速下降方向dB=−gTggTBggd^B=-\frac{g^Tg}{g^TBg}gdB=−gTBggTg​g,如 果最速下降方向超出了信赖域,返回与信赖域的交点。 这时可以求得方向为信赖域半径除以dU的范数∗dU信赖域半径除以d^U 的...
  • 最小二乘优化整理(信赖域方法)

    千次阅读 2018-08-06 19:19:24
    信赖域方法和线搜索类似都是迭代方法,与其不同的是,每次迭代时,在一个选定的可信赖区域内,选择当前迭代点的近似模型 mkmk ,然后计算最优步长;如果步长不合适,可以对区域进行缩放。该小结主要介绍: 信赖域...
  • 针对无约束最优化问题,将BFGS公式与信赖域算法有机结合,给出了Bk的一个新的修正公式,在此公式中引入了一个可调整的参数θ,并且在一定条件下证明了该算法的全局收敛性.
  • 提出了非单调信赖域算法求解无约束非光滑优化问题,并和经典的信赖域方法作比较分析。同时,设定了一些条件,在这些假设条件下证明了该算法是整体收敛的。数值实验结果表明,非单调策略对无约束非光滑优化问题的求解...
  • 信赖域(Trust Region)算法

    千次阅读 2017-07-23 22:07:25
    在本文中,我将讲述一下信赖域算法与一维搜索的区别、联系,以及信赖域算法的数学思想,实现过程。【1】信赖域算法与一维搜索算法的区别、联系 最优化的目标是找到极小值点,在这个过程中,我们需要从一个初始点...
  • 给出了求解二维第一类Fredholm积分方程信赖域方法。通过引入正则化参数将离散后的Fredholm积分方程转化带参数的最优化问题,借助于KKT条件将二次信赖域子问题参数化,并进行分析求解,最后给出了数值模拟。

空空如也

空空如也

1 2 3 4 5 ... 12
收藏数 228
精华内容 91
关键字:

信赖域