登录

  • 登录
  • 忘记密码?点击找回

注册

  • 获取手机验证码 60
  • 注册

找回密码

  • 获取手机验证码60
  • 找回
毕业论文网 > 外文翻译 > 理工学类 > 数学与应用数学 > 正文

信赖域与线搜索技术的结合外文翻译资料

 2022-08-06 09:08  

英语原文共 25 页,剩余内容已隐藏,支付完成后下载完整资料


信赖域与线搜索技术的结合

摘要

我们提出了一种使用信赖域技术和线搜索的非线性优化算法,与传统的信赖域方法不同,如果试验步导致目标函数增加,我们的算法不会解决子问题,而是执行回溯线搜索,从失效点回溯可以沿着直线或曲线完成。我们证明了该新算法保留了信赖域方法的强收敛性,并给出了数值结果。

关键词:信赖域,回溯,无约束最优化,非线性优化

一、引言

在本文中,我们研究了一种新型的信赖域方法来解决无约束优化问题。

(1.1)

我们的目标是设计一种算法,该算法可以保留信赖域方法的收敛性,但是在变量很大时,计算更加简便。信赖域方法通过解决子问题来计算试验步骤

(1.2)

s.t. (1.3)

当是当前近似解中目标函数的梯度,是一个近似于f的Hessian的n x n的对称矩阵。是信赖域半径,与行搜索相比,信赖域方法的优点之一是允许不确定。

在获得(1.1)-(1.2)的精确或近似解的试验步骤dk后,信赖域算法计算函数实际缩减量比率,,和预计的减少,。信赖域半径是根据来确定的。现在如果步骤dk不成功,则,终止算法,减小信赖域半径,并重新计算(1.1)-(1.2)。这个算法对于计算计算量小的已经足够了。

但是,如果变量数量很大,则解决信赖域问题可能会很复杂,因为这需要求解一个或多个线性系统

(1.4)

(参考Dennis 和 Schnabel(1983))

相比之下,线搜索方法只需很少的计算即可确定新的试验点。因此,我们要想如何将回溯线搜索合并到信赖域方法中,从而避免在步骤不成功时解决子问题。

但是,引入线搜索可能会削弱算法的收敛性。因此,我们先讨论实际中可能出现的两种情况以及对应的解决方法。

第一种是当线搜索算法中的搜索方向与最陡的下降方向gk正交时,通常需要减小步长才能接受。在某些情况下,舍入误差可能会导致线搜索失败。 信赖域算法将缩小信赖域,并且新的试验步骤将朝更陡的方向激素按。这个属性使该方法在涉及噪声和舍入误差(Carter(1991))方面更加有效,应当保留。

第二种困难情况是,行搜索算法中的搜索方向或信赖域方法中的尝试步骤过大时,这可能是由一个较小的矩阵Bk引起的。在这种情况下,减小信赖域得到的判断步骤几乎与第一个失败的判断步骤相一致。在这种情况下,信任区域方法的行为与回溯线搜索方法类似,不同之处在于它的计算成本会更高。 此时进行回溯线搜索是有利的。

我们得出结论,如果搜索方向均为下坡,就应该执行回溯。在本文中,我们证明了可以安全地沿直线或曲线路径进行,因为我们找到了一种方法解决(1.1)-(1.2)

因此,试验步骤dk始终是目标函数下降的方向。根据这个,如果gk远离0,那么dk与-gk之间的夹角将远离。这证明了该方法具有很好的收敛性。

Toint(1982)也将线搜索合并到了信赖域方法中,但是在他的算法中,线搜索是在每次迭代时执行的。在我们的算法中,仅当试验点xk dk不能给出最低点时才执行回溯线搜索。

信赖域方法的理论与实现受到了广泛关注,(参考Fletche(1987),Gay(1981),More(1983),More and Sorensen(1983),Powell(1975),Sorensen(1982a,1982b),Powell(1984) and Eisenstat and Walker(1991))。本文参考了以上文献。

文中的符号表示欧几里得向量范数或其诱导矩阵范数,表示矩阵A的广义逆,lt;v1,v2gt;表示向量v1与v2之间的角度。对称矩阵的特征值表示为,我们用A0表示矩阵是半正定的。

二、子问题

在本节中,我们给出关于求解(1.1)-(1.2)的一些子问题,并考虑一些计算它的近似解的技术。我们先看一下已经被证明的结果(参考More and Sorensen(1983) and Gay(1981))。

引理2.1 令向量是下面问题的解,

(2.1)

s.t. , (2.2)

其中是一个对称矩阵,并且Delta;gt;0,当且仅当且存在使得

(2.3)

(2.4)

(2.5)

为了用封闭形式表示信赖域问题的解,可以方便地利用广义逆的一些性质。假设A是一个对称半正定的n x n矩阵,其特征分解

, (2.6)

其中,,Q=[q1,hellip;hellip;,qn]为正交矩阵。我们定义A的广义逆

(2.7)

其中,通过改写A的形式A=,这很容易证明, 对一些向量,如果d是

Ad=-g, (2.8)

的解, 那么

, (2.9)

其中,v在A的零空间中,. 通过这些我们得到

. (2.10)

将这些结果应用于(2.3),对于一些在的零空间中的v,我们得到

, (2.11)

我们也得出.

考虑二次模型在最速下降方向-g的最大下降量, 可以得到在信赖域内的最大下降量的下限

引理2.2(powell,1975)如果为(2.1)-(2.2)的解,则

. (2.12)

信赖域算法的全局收敛理论仅要求计算出的试验步骤dk满足对于任意k,

(2.13)

其中beta;为常数。如果dk为(1.2)-(1.3)的明确解,那么不等式(2.13)显然是符合的。步长dk的其他选择,例如powell提出的折线步,在信赖域内的二维子空间上的最小值(Dennis and Mei (1979);Shultz ,Schnabel and Byrd(1985))也符合(2.13)。对我们算法的主要要求之一是要满足(2.13)。

由于我们的算法将在试验步骤dk增加目标函数时执行回溯线搜索,因此我们将要求dk充分下降。因此,考虑信赖域约束情况下,我们现在研究由信赖域方法形成的搜索方向的下降特性。

引理2.3 如果为(2.1)-(2.2)的解,如果,且满足(2.3)-(2.4)则有

, (2.14)

, (2.15)

其中和为B的最大和最小特征值.

证明 由(2.3)我们得到

, (2.16)

则. (2.17)

因为,通过不等式以及非负得出(2.14).

由方程(2.11)和不等式(2.10),(2.17)得出

(2.18)

. 证毕

当时,根据(2.5)易得。通过等式(2.11)和(2.18),根据(2.10)我们得到

(2.19)

结合(2.15)和(2.19)我们得到以下结论。

引理2.4 如果为(2.1)-(2.2)的解

(2.20)

证明 如果,我们可以看到不等式2.20遵循关系(2.19)和等式.

如果,通过(2.15)以及 得到

. 证毕

此引理表明最优解满足

. (2.21)

现在我们证明了和-g之间的夹角是Delta;的单调函数。为了确定这个结果,我们假设在困难的情况下,我们总是在信赖域的边界处选择一个解。这将在以下结果的证明中说明。

引理2.5 假设gne;0,令Delta;2gt;Delta;1gt;0,并且规定当Delta;=Delta;1并且Delta;=Delta;2时,和为(2.1)-(2.2)的解。则

(2.22)

证明 根据引理2.1,我们知道存在,使得

, (2.23)

(2.24)

为了证明,用反证法,假设. 条件推出,根据这点以及(2.23)-(2.24)

我们能够得出

, (2.25)

显然矛盾,因此。

对于其余的证明,我们考虑三种情况

  1. 如果(B lambda;2I)正定,引理是正确的,因为可以证明函数

, (2.26)

给出 和-g之间夹角的余弦,该方程对于所有在单调增长。

  1. 如果B lambda;1I是单数则,必须满足,且

,并且。在这种情况下,通常被称为困难情况,可能会有很多解决方案来解决两个信赖域问题,如More和Soresen(1983)所提那样,我们将在信赖域的边界处选择一个解决方案。因此我们有

. (2.27)

3) 为了完成证明,我们假设B lambda;1I是正定的,并且. 我们发现,根据(2.11),我们可以得到。根据这个式子,结合theta;(lambda;)为单调递增,我们得到

. (2.28)

这也证明了引理的正确,证毕.

所有这些结果都与信任区域问题的精确解有关,我们现在考虑一个(2.1)-(2.2)的近似解,

(2.29)

其中,参数 使得是正定的。让我们假设满足不等式

(2.30)

对于连续gamma;gt;1,引理2.1证明了是(2.1)的解s.t. ,所以(2.12)和(2.20)给出

(2.31)

(2.32)

这两个属性((2.31)在模型中下降,(2.32)足够的下降条件)将确保该算法具有良好的收敛性。但是基于(2.30)步长的大小不可能总是合适的,例如牛顿法步长可以比更小,因此,我们现在得出一个替代条件,在不限制步长的下限,该条件将确保(2.31)和(2.32)均满足。

不等式(2.14)对lambda;建议以下上限

, (2.33)

是一个很小的数,确保是正定的。考虑任意,对于是正定的,并且支持(2.33)以及

。 (2.34)

对于任意lambda;,根据(2.29)我们能够得出

。 (2.35)

利用(2.29)和(2.35) 我们得到

剩余内容已隐藏,支付完成后下载完整资料


资料编号:[255167],资料为PDF文档或Word文档,PDF文档可免费转换为Word

您需要先支付 30元 才能查看全部内容!立即支付

企业微信

Copyright © 2010-2022 毕业论文网 站点地图