张思雨，刘陶文

(湖南大学数学与计量经济学院，湖南 长沙 410082)

0 引言

二阶锥规划是在一个仿射空间和有限个二阶锥的笛卡尔积的交上极小化或极大化一个线性函数的问题, 其约束是非光滑的,并且是凸的,因此它属于非光滑凸规划。在近几十年里,随着线性规划和半定规划等优化问题的理论、算法和应用的不断发展,二阶锥规划逐渐受到人们的关注,在设施选址、工程设计等领域得到了广泛的应用[1]。二阶锥规划包含线性规划,同时又是半定规划的特例,因此在求解二阶锥规划问题时,可以将线性规划的原始对偶方法推广到二阶锥规划上,也可以将其转化为半定规划问题,用半定规划的相关算法来求解,但这样做,会使问题的维数大大升高,从而给求解带来困难。因此,对二阶锥规划问题的算法研究是非常必要的,目前求解二阶锥规划问题的算法主要有内点法[2,11]、光滑化算法[3,12]、序列二次规划法、增广拉格朗日函数法等,其中增广拉格朗日函数法是最有效的方法之一。

1969 年,Hestenes 和Powell 在求解带等式约束的非线性规划问题时,提出了增广拉格朗日函数法[4],随后Rockafellar 将这一方法推广到了带有不等式约束的非线性规划问题上[5],尽管已经过去了将近50 年,增广拉格朗日方法及其衍生的方法仍然是求解约束优化问题的核心工具。2004 年,Shapiro 和Sun 在文献[6]中给出了锥约束条件下增广拉格朗日函数的一些性质,2007 年,Sun 等人在文献[7]中利用两个基本假设条件,给出了增广拉格朗日函数法求解一般约束优化问题的局部收敛性结果,并将其应用于非凸的非线性半定规划问题,特别地,这些结果的获得并不需要满足严格互补条件和罚参数趋于无穷,从而避免了数值不稳定性和因罚参数过大而导致病态问题.考虑如下的非线性二阶锥规划问题(NSOCP)[8]：

1 解NSOCP 的增广拉格朗日方法

问题(1)的拉格朗日函数定义为：

求解问题（1）的增广拉格朗日方法可以描述如下：

算法1（增广拉格朗日方法）

步3：更新乘子

则称在x*处二阶充分条件成立。其中且

定义2[9]若在x*处满足：

则称在x*处约束非退化条件成立。

定义3 若在x*处满足：

则称在x*处严格互补条件成立。

2006 年,Liu 和Zhang 在文献[10]中,利用二阶充分条件、约束非退化条件和严格互补条件证明了求解非线性二阶锥规划问题的增广拉格朗日方法具有局部收敛性且收敛速度与1/ρ成正比,但严格互补条件通常不容易成立,例如,考虑下面的非线性二阶锥规划问题[3]：

由于x*是最优解,故存在使得在处满足KKT 条件,计算可得：

经验证在x*处强二阶充分条件和约束非退化条件均成立,因此,本文我们仅在强二阶充分条件和约束非退化条件下分析增广拉格朗日方法求解非线性二阶锥规划问题的局部收敛性。

2 局部收敛性

首先给出一些在收敛性分析中用到的预备知识。

设X和Y是两个有限维的实Hilbert空间,B是X的一个开子集,在B上是局部Lipschitz连续函数,由Rademacher's 定理可知,ψ在B上是几乎处处F可微的,用表示ψ在B中所有F可微点的集合,则可定义ψ在x∈B处的B次微分：

设x*是稳定点,是x*处的拉格朗日乘子,对任意的映射,定义：

若严格互补条件在x*处不成立,则存在1,2, ,…J的一个划分(C,T)使得：

定义C的三个指标集：

定义T的三个指标集：

下面我们将仅在约束非退化条件和强二阶充分条件下,证明求解非线性二阶锥规划问题的增广拉格朗日方法是局部收敛的,且收敛速度与1/ρ成正比,为此,我们需要下面的引理。

引理1[7]令,若约束非退化条件和强二阶充分条件在x*处成立,则存在,使得对任意的,有：

和

其中：

引理2[10]设是连续函数,满足：

基于上述预备知识及引理2,我们给出下面一个重要的结论,它对本文的收敛性分析是至关重要的.

定理1设x*是非线性二阶锥规划问题（1）的稳定点,且约束非退化条件和强二阶充分条件均在x*处成立,,则有以下结论成立：

证明：由约束非退化条件在x*处成立,及文献[4],可知是单点集,故存在是x*处唯一的拉格朗日乘子,即；

令

因此

由强二阶充分条件在x*处成立,可知存在使得：

即：

文献[7]将引理1 和定理1 作为两个基本假设条件,并在此条件下证明了增广拉格朗日方法求解一般锥约束规划问题具有局部收敛性,且收敛速度与1/ρ成正比,因此本文只需证明引理1 和定理1 的结论对非线性二阶锥规划问题成立,便可以得到增广拉格朗日方法求解非线性二阶锥规划问题的局部收敛结果,引理1 的详细证明可参考文献[7].

其中τ是一个常数,且

由强二阶充分条件在x*处成立及式(23)可知,中的每个元素都是正定的,从而是非奇异的,因此,由文献[7]可得：存在和局部Lipschitz 连续函数,使得对任意的,有

3 结论

因严格互补条件通常不容易满足,所以本文在没有严格互补条件下研究了增广拉格朗日函数法求解非 线性二阶锥规划问题的局部收敛性,利用约束非退化条件和强二阶充分条件,得到增广拉格朗日函数法求解非线性二阶锥规划问题是局部收敛的,且收敛速度1/ρ成正比,并通过一个具体的例子表明这样做是有意义的,从而使得增广拉格朗日方法的应用范围更广。