文摘

新的收敛性能的近端增广拉格朗日方法建立了连续等式和不等式约束的凸优化问题。特别是,乘数序列不需要是有界的。讨论不同的收敛结果依赖于迭代序列生成的算法收敛或发散。此外,在某些凸性假设,我们显示的每一聚点是简并点或马的原始问题。数值实验给出了最后。

1。介绍

在本文中,我们考虑下面的非线性规划问题: 在哪里为每一个和为每一个都是连续可微的函数,是一个非空的和闭集。用可行域解集。

增广拉格朗日算法是非常受欢迎的工具,用于解决非线性规划问题。在每个外层迭代的方法,一个简单的优化问题已经解决了,可以使用的高效算法,特别是大的问题。最著名的增广拉格朗日算法基于Powell-Hestenes-Rockafellar [1- - - - - -3]公式已成功用于定义实际的非线性规划算法(4- - - - - -7]。在每个迭代中,具有简单约束的最小化问题大约是解决而拉格朗日乘数法和惩罚参数更新主程序。增广拉格朗日方法比其他方法的优势在于,子问题可以解决使用算法,可以处理大量的变量没有利用任何形式的矩阵的分解。

不可或缺的假设在大多数现有的增广拉格朗日方法的全局收敛性分析是乘数序列生成的算法是有界的。这种限制性假设范围增广拉格朗日方法在许多实际的应用情况。重要的工作在这个方向包括(8),全局收敛性改性增广拉格朗日方法建立了具有等式约束的非凸优化;和Andreani et al。4)和Birgin et al。9]研究了增广拉格朗日方法使用非凸约束问题的维护策略。最近,对于不等式约束全局优化,罗et al。10)建立了基于四种类型非方法的收敛性质的增广拉格朗日函数的有界性假设乘数序列。可以找到更多的信息在5,11,12]。

本文的优化问题( 等式和不等式约束),同时,我们进一步研究近端拉格朗日方法的收敛性质,无需乘法器序列的有界性。本文的主要贡献在于以下三个方面。首先,被认为是更一般的约束,没有限制只有不等式约束(10,13),需要的有界性在[9]。第二,一个重要的假设的全局收敛特性(4- - - - - -7,9,10是迭代序列必须提前收敛;在这里,我们进一步讨论时的情况是不同的,发展的必要和充分条件收敛于原始问题的最优值。第三,的定义变性在[9,10]扩展从不等式约束不等式和等式约束。

本文组织如下。节2,我们建议乘法器算法和研究其全局收敛特性。初步计算结果报告部分3。结论是在一节4。

2。乘法器算法

原始的增广拉格朗日函数( )是 在哪里,表示一切积极的标量,。

鉴于,增广拉格朗日松弛的问题与增广拉格朗日被定义为 鉴于,那么最优解集( ),用,被定义为

如果关闭和有界,那么全球的最优解( )存在。然而,如果是无限的,那么( )也许不能解决的。为了克服这个困难,我们在本文假设是有界的从下面, 这种假设是相当温和优化编程,否则目标函数可以更换的。它确保了最优解集和总是存在的,因为从下面有界(2.1)和(2.3)。

回想一下,一个向量据说是马的角度( )如果存在为每一个和为每一个这样 在哪里表示正常锥在。所有的收藏集和令人满意的(2.4)是用。

基于原始的增广拉格朗日乘数算法提出了如下。它的一个主要特点是,等式和不等式约束的拉格朗日因子不限于是有限的,这使得该算法适用于在实践中许多问题。

算法2.1(基于乘法器算法)。步骤1。选择一个初始点,,,,。集。步骤2。计算 步骤3。找到;步骤4。如果和,然后停止;否则,让回到步骤2。

迭代公式在(2。7)只是用来保证其收敛为零。事实上,在实际的数值实验,我们可以选择改进算法的收敛性。下面的引理给出了惩罚参数之间的关系和乘数和。

引理2.2。让得到的算法2.1,那么以下条款 所有方法为零。

证明。在此之前立即从(2。8)。

建立算法的收敛性质2.1,我们首先考虑的摄动分析( )。鉴于,定义可行域的扰动 和水平集的扰动 很明显,恰逢可行的( )。给出相应的扰动函数

下面的结果表明,扰动值函数是上半为零。

引理2.3。摄动函数在零从右上半。

证明。自对于任何,然后通过定义(2.12)。这意味着。

引理2.4。让得到的算法2.1。对于任何,一个 每当是足够大的。

证明。对于任何给定的,它遵循从(2。7)和引理2.4,当足够大,我们有吗 因此,对于,

引理2.5。让得到的算法2.1。对于任何,一个 每当是足够大的。

证明。我们证明这个结果的矛盾的方法。假设我们可以找到一个和一个无限的子序列这样 但 它遵循从(2.17),
自,它需要考虑以下两种情况。
案例1。存在一个索引和一个无限的子序列这样。然后,遵循从(2.19),
利用引理2.2事实上,给了我们 每当是足够大的。加之(2.20),收益率通过接近,,导致矛盾。例2。存在一个索引和一个无限的子序列这样。它遵循从(2.19), 最后一步是由于引理在哪里2.2,因为和。在上面的不平等限制产量,这是一个矛盾。这就完成了证明。

引理2.6。让得到的算法2.1。对于任何,一个

证明。对于一个任意,我们有 证明已经完成。

与这些准备,算法的全局收敛性属性2.1可以,这表明,如果该算法在有限步终止,然后我们获得马的角度( );否则,每极限值将最优解( )。

定理2.7。让是由算法生成的迭代序列2.1。如果终止在有限的步骤,然后得到马的角度( );否则,每极限值属于。

证明。根据算法的建设2.1,第一部分是显而易见的。第二部分还有待证明。让被给予。它遵循的前题2.4- - - - - -2.6,当足够大,我们有吗 因此, 请注意,和由于连续性,关闭吗,对所有和对所有和亲密感。把限制在(2.26)的收益率,进一步说明,因为是任意的,。证明已经完成。

上述结果适用于时的情况至少有一个聚点。然而,一个自然的问题是:如何算法执行是不同的?下面的定理给出了一个答案。

定理2.8。让是算法生成的迭代序列2.1。然后, 当且仅当低半连续在从右。

证明。我们第一次显示出充分性。根据定理的证明2。7(回忆2.26)),我们知道 每当是足够大的。自低半连续在(从右,以较低的限制2.28)的收益率 也就是说, 我们现在展示的必要性。相反的假设下半连续零从右不是,那么存在吗和这样 对于任何给定的,因为我们可以选择一个子序列令人满意的 此外,让与,这也进一步说明由(2.31)。因此, 最后一步是由于在哪里和自。在双方采取限制(2.33)和使用(2。7),(2.27),引理2.2,我们得到 导致矛盾。证明已经完成。

注意,在许多实际情况下,集通常代表一个更简单的约束,例如,一个盒子或有界多胞形(7]。因此,我们得出本文所考虑的情况是一个有界,关闭,凸子集的。在这种情况下,全球增广拉格朗日松弛问题的最优解总是存在。因此,我们选择在步骤1的算法2.1,进而暗示对所有由(2。7)。不过,首先,我们需要扩展的定义从不等式约束的简并10不等式和等式约束。

定义2.9。一个点如果存在据说退化和这样 在哪里表示的投影到和。

定理2.10。假设是一个有界,关闭,凸集的。让和是由算法生成的迭代序列2.1。然后,每一个聚点说,,要么是退化或马的角度( )。

证明。注意的是,对所有通过和(2。7),然后是一个全局最优的解决方案一步3在算法2.1。应用著名的优化问题的最优性条件增广拉格朗日松弛问题( )的收益率 在哪里的正常锥吗在。这在一起(2.5)和(2.6)意味着 在我们使用正常锥凸集的基本性质。让吗是一个无限的子序列这样。现在考虑以下两种情况。案例1。要么或是无限的。在这种情况下,我们必须有 自和是有限的,我们可以假设通过后继如有必要吗 很明显,和并非都是零。另一方面,锥,它遵循从(2.36), 和使用的正常锥凸集的基本性质,我们进一步 自和作为我们从(2.39)和(2.41) 我们使用投影算子的连续性。
如果,然后。自,我们有作为。使用(2.5)和引理2.2,我们获得 一起,(2.39),意味着对所有。因此,我们获得的(2.42), 所以是简并的。例2。这两个和是有界的。在这种情况下,我们可以假设不失一般性 限制在(2.37)产生 相当于
我们声称是一个可行的点。事实上,如果对于一些,然后作为。从(2.5),我们必须有有界性的矛盾。请注意,(2.6)可以写成 在双方的有界性和使用限制,我们获得对所有。因此,是一个可行的解决方案( )。
如果,也就是说,后,然后几乎相同的论点1,我们可以证明(cf。2.43))。因此, 这在一起(2.47)意味着马的角度( ),,是对应的拉格朗日因子。

3所示。数字报告

给一些洞察我们的算法的行为呈现在这篇文章中,我们解决以下nonlinar编程问题。奔腾4的测试是在PC与2.8 GHz CPU和1.99 GB内存和计算机代码编写的MATLAB 7.0。数值结果被发表在表1- - - - - -4,在那里是迭代的数量,是惩罚参数,是迭代点发现算法,然后呢是客观价值。

示例3.1(见[14])。它认为,

示例3.2(见[14])。考虑

例3.3。它认为,

例3.4。考虑

4所示。结论

增广拉格朗日方法是解决许多实际的非凸优化问题的有效工具。本文建立了新的近端增广拉格朗日算法的收敛性质,而无需乘法器序列的有界性。证明,如果该算法在有限步终止,然后获得一个马的原始问题;否则,迭代序列广义的算法收敛于最优解。即使是不同的,我们也提出了一个收敛的充分必要条件最优值。此外,在适当的假设下,我们表明,每一个聚点算法产生的迭代序列的退化或者是一个原始的马点的问题。为我们未来的工作,有趣和重要的主题之一是这些不错的属性是否可以扩展到更一般的锥编程,例如,非线性半定规划或二阶锥规划。

确认

作者要感谢裁判对他们有价值的评论,这大大提高了纸的表示。研究的第一作者部分是由中国国家自然科学基金(11101248,11101248)和山东省自然科学基金(ZR2010AQ026)。研究的第二部分是作者支持由中国国家自然科学基金(11171247)。第四部分是作者研究支持由中国国家自然科学基金(10971118)。