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

一种等式约束优化问题的增广Lagrange信赖域方法

王晓，袁亚湘

1. 中国科学院大学 数学科学学院，北京; 2.中国科学院 国家重点科学与工程计算实验室，北京)

摘 要：本文提出了一种针对等式约束优化问题的增广拉格朗日信赖域方法。不同于传统拉格朗日方法在每一步迭代中固定拉格朗日乘子与罚因子，并极小化增广拉格朗日函数，新提出的这种方法将尝试最小化拉格朗日函数的二阶近似函数。我们提出了一种新的罚参数调整策略。利用拉格朗日乘子的可适应性更新，我们证明了该方法的全局收敛性。本文还公布了CUTEr测试问题集的数值结果。

关 键 词:等式约束;增广拉格朗日函数;信赖域;拉格朗日乘子;惩罚参数;收敛

AMS分类号:90C30;65k05

1 引言

在本文中，我们考虑如下等式约束优化:

其中为Lipschitz连续可微，与，i=1，hellip;，m，Lipschitz是连续可微的。在过去的几十年里，人们研究了大量有效的方法来求解(1)。其中最著名的方法是序列二次规划(SQP)方法，它可以追溯到Wilson^[31]，并由后来由Han^[20]、Powell^[27]等人进一步发展。它的基本思想是通过变换将原问题转化为一系列二次规划(QP)子问题。在每一次迭代，试运行步骤解决以下QP子问题:

其中k为迭代次数，为约束的雅可比矩阵，为拉格朗日函数的正定海赛矩阵或其在当前迭代点的近似估计。在这里，乘数是一个矢量。在实际计算中，需要特定的策略应用于SQP法的全局化。第一种策略是采用线搜索技术。然而，为了避免无界解，线搜索方法通常需要在的零空间中为正定，当设为精确的拉格朗日函数的黑森函数时，该条件往往不成立。另一个策略是应用信赖域技术。它通过添加信任区域约束来限制试探步的步长，这种方法允许不确定，这样就可以选择Bk作为拉格朗日函数的精确黑森函数。然而，可能会出现复杂度提升的情况，因为包含信任区域界限可能会导致不可行的线性约束的存在。因此，有必要放松约束(如[6，28])然而，这使得算法更加复杂。此外，选择一个有效的评价函数以确保全局收敛是非常重要。本文研究了几种类型的评价函数，例如罚函数，罚函数和增广拉格朗日函数。然而，所有这些评价函数都需要依赖于参数，甚至对某些参数非常敏感，因此需要谨慎的处理。

为了避免前面提到的不可行子问题所带来的麻烦，基于罚函数方法的处理策略引起了广泛的重视。两个合成方法有序列二次规划()方法和序列^[15]方法分别用二次规划()方法求解^[32]。它们的共同点是将(2)中的线性化约束作为罚项移到目标中，并且融入了信赖域技巧。对应的或的惩罚函数作为评价函数。然而，与这两种方法相关的一个主要问题是非光滑性。由于评价函数的非光滑性，可能会产生Maratos效应。导致超线性收敛步因为评价函数值的增加而被拒绝。使用非光滑精确罚函数的另一个困难是对应的子问题是一个非光滑问题，可能不容易解决。在这些问题的启发下，我们考虑建立一类光滑可行的子问题。

近年来，非线性规划的罚函数法得到了很大的发展。这类方法的关键思想是将原始约束移动到目标(1)中，在每个迭代中都有一个更简单的优化问题，例如，待解决的问题是无约束优化或简单有界优化问题。最著名的罚函数法之一是增广拉格朗日方法。该方法首先由Hestenes^[21]，Powell^[26]和Rockfellar^[30]进行研究，然后由Conn等人对其[8]进行调整。从那时起，它就吸引了很多人许多关注，许多基于增广拉格朗日函数的变种已经涌现出来(2、3、13、14)，并在各个领域中得到广泛的应用，如压缩感知^[5]、半定规划^[34]、矩阵补全^[16]等。让我们以(1)为例。在每一次迭代，增广拉格朗日函数和固定的拉格朗日乘数及惩罚参数最小化:

通过引入显式拉格朗日乘子，该方法降低了简单的罚函数法产生病态条件作用的可能性，如Courant罚函数法或log-barrier方法(参考[25])。此外，不同于和方法，它不引入任何非光滑性(如[25])。因此，可以实现无约束优化的标准方法和软件。Conn等人^[8]完成了一本关于实用增广拉格朗日方法的很有影响力的著作，在此基础上，他们提出了一种著名的拉格朗日方法计算软件包Lancelot^[9]。在下面的实验中，我们将在数值上把我们的方法与它作比较。在[8]中，子问题(3)只需要解到预先给定的精度下，其中序列是一列收敛到0的正数。然而，这种做法也是值得商榷的。首先，当很小时，如果的非线性程度很高，求解(3)来达到所需的精度对算力的损耗是巨大的。第二，当拉格朗日乘数与解处乘子差别很大时，也没有必要把子问题（3）求解得过于精确。因此，本文希望构造易于求解的子问题，以降低每一个迭代的计算成本。

Niu和Yuan^[24]给出了一个有用的方法。他们提出了一种滤波器式的方法，子问题是最小化在信赖域内的增广拉格朗日的二次逼近函数，因此不同于标准的增广拉格朗日方法(3)。Niu和Yuan方法的一个优点是：信任域子问题是一个相对简单的问题，可以通过多种算法有效地求解。一些满意的数值结果被发表在^[24]中。但是，这份研究并没有在论文中给出收敛性正名。近年来，Curtis等人将类似的信任域子问题应用于研究中[11]，并提出了一种新的信任域子问题大规模约束优化的自适应方法。给出了较好的数值结果。但是，如果一阶临界性罚参数更新次数趋向无穷，约束违反收敛为零，则不能得到迭代的累积点的基于信赖域子问题良好的数值性质。在受到上述两篇论文的启发下，我们采用了相同的子问题设计算法。

我们在这篇论文中所作的贡献有几个方面。首先，我们提出了一个新的策略更新惩罚参数，这不仅取决于约束，而且依赖于模型的改进。这种新策略通常会防止迭代收敛在在带有乘法器和惩罚参数的增广拉格朗日函数的局部极小化附近。其次，我们给出了在有界条件或无界条件下该方法的全局收敛性。此外，松弛常数应用正线性相关(RCPLD)约束条件(稍后定义)分析全局收敛性。这种RCPLD条件最近由Andreani等人提出。并已被证明比许多其他传统约束条件弱。

符号：在本文中，我们使用来表示维实数向量空间，作为非负实数的集合。表示所有非负的集合整数。上标(i)表示向量的第个元素，下标表示向量的第个元素算法中的迭代数。没有指定，表示欧几里德范数中的。我们将表示为的梯度，表示为在处的雅可比矩阵，即，

我们把表示为的零空间，把算子表示为的欧氏投影闭凸集。为了方便起见，我们将缩写为，以及类似的缩写，和也被使用。本文的其余部分组织如下。在第二节中，我们提出了一个增广等式约束优化的拉格朗日信赖域(ALTR)方法(1)第三部分研究了该方法的全局收敛性。在第4节，初步对大多数等式约束优化问题进行了数值计算。最后，我们在第五部分得出了一些结论。

2 算法描述

在本章中，本文针对等式约束优化问题提出一种ALTR方法。首先，本文给出两种常用的最优性条件。

定义2.1：称为Fritz-John点， 如果在该点处Fritz-John 条件成立：存在常数和向量 使得以及

特别地，当且可行性条件成立时，我们得到下面的KKT点的定义：

定义2.2：称为KKT点， 如果在该点处KKT 条件成立：存在向量使得：

约束条件通常用于描述梯度之间的关系限制。非线性规划中最广泛使用的约束条件之一是所谓的线性独立约束条件（LICQ）（参见，例如^[25]）。关于（1），我们给出如下定义：

定义2.3：给定（1）的可行点，我们说LICQ条件保持在，如果所有等式约束的梯度，是线性独立的。

最近，另一种约束条件引起了人们的广泛关注^[1-3，29]，这被称为恒定正线性依赖（CPLD）条件。已经证明了这一点CPLD条件弱于LICQ条件。后来Andreani等人^[4]提出RCPLD约束条件，证明严格弱于CPLD。正如本文所述的问题（1）只有平等约束，我们在平等方面陈述了RCPLD的定义约束优化。

定义2.4：给定（1）的可行点，我们说RCPLD条件保持在，如果存在的邻域，使得对于任何x具有相同的等级邻域。接下来我们将详细讨论我们的算法，包括与信任区域相关的问题子问题，拉格朗日乘子和惩罚参数的更新策略。

2.1 信赖域子问题

首先，让我们回顾一下经典的增广拉格朗日方法。 增广拉格朗日函数关于定义为：

其中isin;Rm指乘数的矢量，表示惩罚参数。引入增广拉格朗日函数（5）的原因基于以下理论结果。如果是（1）的局部解，并且*是与相关的拉格朗日乘数，在一些规律性假设下，存在阈值，使得对于所有gt;，是的严格局部最小值。有兴趣的读者可参考[25，定理17.5]了解更多详情。基于这个结果，即使在实践中，确切的*和值未知的话，当不特别大并且接近*时，仍然可以通过最小化来获得x *的良好估计。因此，给定当前迭代，即可通过解决以下子问题获得：

好消息是，我们没有必要完全解决（6）。考虑到公差，Conn^[8]建议应用算法求解（8）找到，直到满足这样的条件：

然后通过强制→0以及和的自适应更新，算法将找到KKT点或Fritz-John点。然而，在实践中，由于可能是高度非线性的，因此这个过程可能太复杂，特别是当很小，而不是最小化非线性函数，Niu和Yuan[24]考虑其二次近似。对的这种近似可以定义为:

其中是拉格朗日函数的Hessian函数，或其近似。在惩罚项中，它们的线性化近似。为了确保为足够逼近的近似值，我们用信任域技术把搜索区域限制在当前迭代范围内，并给出了以下信任域子问题：

在（8）中，可以选择近似的Hessian Bk阵。 例如，可以通过更新策略生成，例如阻尼BFGS更新（参见，例如^[25]），这仅取决于f和c的一阶导数。

子问题（8）最小化l2范数信任区域内的二次函数。这种问题具有强大的优势，即有非常有效的方法来解决它，例如gqtpar子例程^[23]，顺序子空间方法^[18]等。 实际上，它只需要大多数是多项式（n）次操作（参见例如^[10]）。 而且，没有必要完全解决问题（8）。 找到一个令人满意的非精确解决方案就足够了。

对于某些正常数。例如，对于= 0.5，截断的CG方法总是满足（9），如果qk（d）的Hessian是正定的（参见，例如^[33]）。我们认为（9）允许存在多种不精确的（8）的解决方案。在下面的分析中，我们假设（9）适用于所有k。在获得试用步骤sk之后，我们应该决定是否接受它。类似于信任区域方法中的经典策略，实际减小量与预测减小量之间的比率如下：

如果比率远离1，则意味着在当前信任区域中的近似值是不够的。 然后我们减少。我们期望当足够小时，比率接近于1。

但是，可能会出现微妙的情况。对于某些和，可能是的局部最小值，因此等式= 0成立。然后，尽管在 = 处达到的最小值，并且在d = 0时qk（d）的梯度是零，由于负曲率，qk（d）可以在d = 0附近取负值，因为可能是单位矩阵的充分大负数倍。分别对于每个正信任区域半径，给出lt;0，Aredk和Predk分别是负和正的，这可能导致无限循环。事实上，在这种情况下，有两种情况是可能的。一种情形中，还是可行的。那则有下面的关系式：

此时，是KKT点，因为。在这种情况下，算法经过有限步终止。另一种情况发生在不可行时，给出

您可能感兴趣的文章

• 在线办公系统的设计与实现外文翻译资料
• 正则表达式模式匹配外文翻译资料
• 层适应网格一致收敛的充分条件外文翻译资料
• 深度残差网络中的恒等映射外文翻译资料
• 固定和灵活汇率下国际调整的货币动态外文翻译资料
• 政策选择的本质外文翻译资料
• 大数据在海洋观测中的应用：机遇与挑战外文翻译资料
• 基于遗传算法的贝叶斯多核学习方法相关向量机外文翻译资料
• 数据库管理系统外文翻译资料
• 数据仓库外文翻译资料