英语原文共 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