二阶锥线性互补问题的低阶罚函数算法

赵雯宇,郝自军,余国林

(北方民族大学数学与信息科学学院,宁夏 银川 750021)

二阶锥线性互补问题的低阶罚函数算法

赵雯宇,郝自军,余国林

(北方民族大学数学与信息科学学院,宁夏 银川 750021)

本文研究了二阶锥线性互补问题的低阶罚函数算法.利用低阶罚函数算法将二阶锥线性互补问题转化为低阶罚函数方程组,获得了低阶罚函数方程组的解序列在特定条件下以指数速度收敛于二阶锥线性互补问题解的结果,推广了二阶锥线性互补问题的幂罚函数算法.数值实验结果验证了算法的有效性.

二阶锥;线性互补问题;低阶罚函数算法;指数收敛速度

1引言

考虑二阶锥线性互补问题:求向量 x ∈ Rn,使得

其中 Rn是 n 维欧式空间,A ∈ Rn×n是 n×n 阶实矩阵,b∈ Rn是 n 维实向量,K 是二阶锥的笛卡尔乘积.也就是说

其中 m,n1,···,nm≥ 1,n1+ ···+nm=n,且 Kni⊂ Rni是 ni维二阶锥.即

其中 ‖ ·‖ 表示欧几里得范数. 为了方便用 (x1,x2) 表示 (x1,xT2)T, 用 u ≿Kniv(或 v ≾Kniu)表示 u − v ∈ Kni. 显然 K ⊂ Rn是一个 闭凸且自 对 偶锥. 若 ni=1,K1为非负实 数 集 R+.若 n1= ···=nm=1, 则 Kn退化为 Rn+, 此时问题 (1.1) 退化为一般的线性互补问题.

二阶锥互补问题是近十多年来研究的新问题,它是二阶锥规划的推广,在工程设计、金融、管理科学等领域都有广泛应用[1,2,3]. 在过去的十多年中, 对二阶锥规划和二阶锥线性互补问题已有广泛研究, 并提出了各种算法, 例如光滑牛顿算法[4,5,6,7]、半光滑牛顿算法[8,9]、内点算法[10]、价值函数算法[11]、矩阵分裂算法[12]等, 其中有些算法需要 O(n3) 浮点运算次数,这在问题维数n变得很大时可能不是有效的.

众所周知,罚函数方法是求解约束优化问题的重要方法,其主要思路是将约束优化问题转化为一系列无约束优化问题来求解. 文献 [13] 提出了具有良好性质的 l1罚函数. 之后, 许多学者致力于精确罚函数算法的研究[14,15,16,17], 相比经典的 l1精确罚函数, 这些方法只需较弱的条件即可保证精确性.2008 年,Wang 和 Yang[18]提出一种幂罚函数算法求解线性互补问题. 之后,Huang 和 Wang[19,20]将幂罚函数算法推广到求解非线性互补问题和混合互补问题.2015 年,Hao 和 Wan[21]等将幂罚函数算法推广到求解二阶锥线性互补问题. 实际上, 幂罚函数算法 就是一类低阶罚函数算法. 文献 [18,21] 中罚函数的幂参数仅是形如1/k(k ∈ Z+) 的特殊数. 基于此, 本文将文献 [21]中幂参数范围推广到 (0,1]中任意实数, 提出一般低阶罚函数算法.同时证明在矩阵A 正定时,低阶罚函数方程组的解序列在罚参数趋于无穷时以指数速度收敛到二阶锥线性互补问题的解,并将低阶罚函数算法的数值结果与著名的光滑 Fischer-Burmeister(F-B) 函数算法进行比较, 结果表明提出的算法是有效的.

本文共分 5 节,第 2 节给出一些预备知识;第 3 节探讨二阶锥线性互补问题的低阶罚函数算法,并证明算法的收敛性;第 4 节给出一些数值实验结果;第 5 节进行总结.在本文中,对任意 p ＞ 1,‖ ·‖p表示 lp范数. 特别地,当 p=2 时,它代表欧几里得范数 ‖ ·‖.

2预备知识

本 节 给 出 单 块 二 阶 锥 Kn的 一 些 基 础 知 识. 对 任 意 的 x=(x1,x2) ∈ R × Rn−1, y=(y1,y2) ∈ R × Rn−1,它们的约当积 (Jordan product)[1]定义为

本文用 x2表示 x ◦ x, 用 x+y 表示普通向量加法, 这样 “ ◦ ”, “ + ” 以及 e=(1,0,···,0) ∈R×Rn−1构成了 Kn的约当代数. 易知约当积满足交换律,但一般不满足结合律,即 (x◦y)◦z与 x ◦ (y ◦ z) 并不总相等,这是研究和分析二阶锥优化算法的主要困难之一.但约当积在幂意义下结合律成立,即 (x ◦ x)◦ x=x ◦ (x ◦ x) 对任意 x ∈ Rn成立. 因此对任意正整数 p,xp有意义,且对任意正整数 m 和 n,有 xm+n=xm◦ xn. 关于与二阶锥相关的欧几里得约当代数的其他概念,如迹、行列式、可逆向量、平方根、绝对值向量等,详细内容可参考文献 [1,4, 22,23].

与矩阵的谱分解类似,以 Kn为基础,Rn中的任意向量都可以在二阶锥意义下进行谱分解[4,22]. 对任意 x=(x1,x2) ∈ R × Rn−1,x 的谱分解为

其中 λ1,λ2和 u(1),u(2)分别表示 x 的特征值和相应的特征向量,ω 是 Rn−1中满足 ‖ω‖ =1的任意向量. 易知 e=u(1)+u(2), λ1≤ λ2, 且 x2/=0 时分解式 (2.2) 唯一.

下面给出谱分解的一些基本性质.

命题2.1[4,22]对任意的 x=(x1,x2) ∈ R × Rn−1, λ1,λ2和 u(1),u(2)是 按 (2.2) 和 (2.3)式给出的x的特征值和相应的特征向量,则

(4) λ1是非负的 (正的) 当且仅当 x ∈ Kn(x ∈ int Kn),其中 int Kn表示 Kn内部;

(5)tr(x)= λ1+ λ2=2x1,det(x)= λ1λ2=x21− ‖x2‖2,2‖x‖ = λ21+ λ22.

由命题 2.1, 对任意的 x,y ∈ Rn且 x ∈ Kn,y ∈ Kn, 〈x,y〉=0 当且仅当 x ◦ y=0. 因此互补条件可以由约当积等价描述. 根据 x 的谱分解 (2.2) 和 (2.3), 一个标量函数 ˆf:R → R可以被扩展为与 Kn(n ≥ 1) 相关的二阶锥向量值函数[4,24]

其中 λ1,λ2是 x 的特征值,u(1),u(2)是相应的特征向量.

式 (2.4) 给出了 定 义二阶锥函 数 的一种形式, 但其含 义 还需进一步分 析. 对任 意 x ∈ Rn, x 到 Kn的投影定义为在 Kn上离 x 最近的点,记作 [x]+,即 [x]+∈ Kn且

显然,当n=1 时,上述投影退化为

下述命题指出,|x|和 [x]+具有 (2.4) 式的形式 (参见文献 [4] 命题 3.3).

命题2.2对任意 x=(x1,x2) ∈ R × Rn−1, λ1,λ2和 u(1),u(2)是按式 (2.2) 和 (2.3) 给出的x的特征值和相应的特征向量,则

类似于在 Kn上投影的概念, 定义[6]

显然 [x]−是 x 在 −Kn上投影的相反向量,且 x=[x]+−[x]−,[x]+,[x]−∈ Kn,[x]+◦[x]−=0.

3低阶罚函数算法及其收敛性分析

本节提出二阶锥线性互补问题 (1.1) 的低阶罚函数算法, 并给出相应的收敛性分析.不失一般性,假设向量由一个二阶锥块组成,即 K=Kn,因为收敛性分析很容易推广到二阶锥的一般形式 (1.2).

下面考虑低阶罚函数方程组: 求 xη∈ Rn,使得

其中 0 ＜ r ≤ 1 是幂参数, η ≥ 1 是罚参数. 当 −xη的谱分解为 −xη= γ1v(1)+ γ2v(2)时, 定义

当 x ≿K0 不成立时, 方程组 (3.1) 中的罚项 η [−xη]r+惩罚 xη的 “ 负” 项. 由于 η[−xη]r+∈ K,故 Axη− b ≿K0 总成立. 当 η → +∞ 时,我们希望低阶罚函数方程组 (3.1) 的解序列收敛于二阶锥线性互补问题 (1.1) 的解. 因此二阶锥线性互补问题 (1.1) 被转化为低阶罚函数方程组序列.基于此,给出如下低阶罚函数算法.

算法3.1步骤1取任意向量 b ∈ Rn, 矩阵 A ∈ Rn×n, 令 ~x=0 ∈ Rn.

步骤2若 b≾K0,停止,转步骤 7;否则,转步骤 3.

步骤3若 A−1b ≿K0, 令 ~x=A−1b, 停止, 转步骤 7; 否则, 转步骤 4.

步骤4设置幂参数 0 ＜ r ≤ 1,罚参数 η ≥ 1,误差限为 eps,倍数参数 c ＞ 1,选择一个初始点 (x01,x02) ∈ R × Rn−1, 且当 x01＜ 0 时,x02/=0.

步骤5对罚参数 η 和初始点 x0,解非线性方程组

假设 xη是 (3.3) 式的解, 令 Tol=|xTη(Axη− b)|.

步骤6如果 Tol≤ eps,令 ~x=xη,停止,转步骤 7;否则,令 x0=xη,η =cη,转步骤 5.

步骤7向量 ~x 是二阶锥线性互补问题 (1.1) 的近似最优解.

下面讨论算法 3.1 的收敛性分析,为此给出如下假设.

假设3.1矩阵 A 正定,但不一定对称,即存在正常数 ω,使得

众所周知, 二阶锥线性互补问题 (1.1) 与下述变分不等式等价: 求 x∗≿K0, 使得

由假设 3.1 及文献 [3] 中定理 2.3.3 知变分不等式 (3.5) 有唯一解, 因而二阶锥线性互补问题(1.1) 亦有唯一解.同时,由于方程组可看作无约束变分不等式, 故 (3.1) 式也有唯一解.

下述命题 3.1 给出低阶罚函数方程组 (3.1) 解的有界性,命题 3.2 给出 ‖[−xη]+‖ 的一个上界,其证明只需将文献 [21]命题 3.1 和 3.2 中的幂参数 1/k(k ∈ Z+) 换为式 (3.1) 中的实数r ∈ (0,1]即可,这里不再赘述.

命题3.1对任意的 η ≥ 1,0 ＜ r ≤ 1, 低阶罚函数方程组 (3.1) 的解有界,即存在正常数W,独立于 xη,η 和 r,使得 ‖xη‖ ≤ W.

命题3.2对任意 η≥ 1,0 ＜ r ≤ 1,存在正常数 M,独立于 xη和 η,使得

利用命题 3.1 和命题 3.2,可以得到如下重要结果, 它给出了算法 3.1 求解二阶锥线性互补问题 (1.1) 的收敛性分析.

定理3.1对任意 η ≥ 1,0 ＜ r ≤ 1,令 xη是低阶罚方程组 (3.1) 的解, 且 x∗是二阶锥线性互补问题 (1.1) 的解. 则存在独立于 x∗,xη和 η 的正常数 M,使得

证利用 −xη=[−xη]+− [−xη]−,向量 x∗− xη可以分解为

其中 [−xη]−如 (2.6) 式的形式所定义,且

下面考虑 rη的估计值. 如果 rη=0, 由 (3.6) 和 (3.8) 式可知不等式 (3.7) 显然成立, 故下面 只讨 论 rη/=0 的情 形. 显 然 [−xη]−≿K0, 由二 阶锥 线性 互补 问题 与变 分不 等 式 (3.5)的等价性及 (3.9) 式,在 (3.5) 式中用 [−xη]−代替 y 可得

在 (3.1) 式两端同时左乘 rη, 可得

将 (3.10) 和 (3.11) 式相加得

由 (3.2) 式知 [−xη]r+≿K0, 又由于 x∗≿K0, 根据 (3.9) 式可得

将不等式 (3.13) 应用于 (3.12) 式得 rTηA(xη− x∗) ≥ 0, 即

由 (3.8) 式知 rη=x∗− xη− [−xη]+,代入 (3.14) 式得

由假设 3.1,式 (3.15),Cauchy-Schwarz 不等式及范数相容性知,存在常数 b0＞ 0,使得

其中 ‖A‖ 表示矩阵 A 的 2- 范数. 用 ‖x∗− xη‖ 同除 (3.16) 式两端得最后由 (3.6) 及 (3.17) 式知结论 (3.7) 成立. 证毕.

根据定理 3.1,在假设 3.1 下, 当 η → +∞ 时,低阶罚函数方程组 (3.1) 的解序列 {xη} 以指数速度收敛到二阶锥线性互补问题 (1.1) 的解. 但若假设 3.1 不成立, 又会有怎样的收敛性结果呢? 下述定理 3.2 证明了此种情形下低阶罚函数方程组 (3.1) 解序列的任意极限点都是二阶锥线性互补问题 (1.1) 的解.

定理3.2对任意 ηi,假设低阶罚函数方程组 (3.1) 有解 xηi,对任意幂参数 0 ＜ r ≤ 1,令{ηi} 是一列满足 ηi≥ 1 的正数序列, 且, 则序列 {xηi} 的任意极限点都是二阶锥线性互补问题 (1.1) 的解.

证对任意 ηi≥ 1, 因为 xηi是低阶罚函数方程组 (3.1) 关于 ηi的解, 故

注意到

从式 (3.18) 得 Axηi− b= ηi[−xηi]r+∈ K, 在此式中令 i → ∞, 由 K 的闭性知

下面证明

反 设x∈/ K, 此 时 令 ε:=‖ [−x]r+‖, 则 ε＞ 0. 故 由 (3.20) 式知 当 i 充 分 大时,xηi∈/ K 且‖ [xηi]r+‖≥12ε ＞ 0. 同时, 由 (3.18) 式得当 i → ∞ 时,

这与式 (3.19) 矛盾, 故式 (3.22) 成立.

下面再证明

情形1如果显然

情形2如果则由 (3.20) 式知当 i 充分大时,由 (3.18) 式知

在此式中令 i→ ∞,则Ax − b=0,所以xT(Ax − b)=0.

情形3如果x ∈ bd K{0},其 中 bd K 表 示 K 的边界,此时令则根据向量的谱分解 (2.2)–(2.3),x可以分解为这里和 v(1),v(2)分别表示x的特征值和相应的特征向量.因此

即x= µ2v(2). 假设 xηi的谱分解为

由于对任意 y=(y1,y2)∈ R × Rn−1,当 ‖y2‖ ＞ 0 时,

都连续,故由 (3.20) 式知当 i→ ∞ 时,

特别地,当 i 充分大时有 µ2(i) ≥12µ2＞ 0, 此时由 (3.18) 式得

由以上 3 种情形知式 (3.23) 成立.

最后, 由 (3.21)–(3.23) 式可得x 是二阶锥线性互补问题 (1.1) 的解. 由极限点x的任意性,可知结论成立.证毕.

4数值实验

本节用一些数值算例来检验算法 3.1 的有效性,所有例子均采用离散牛顿法求解其对应于 (3.1) 式 的非线性方 程组, 所有的数 值 实验运行 环境为 Intel(R)Core(TM)i5-3570K CPU 3.40GHz,4G of RAM,and windows7 with MATLAB R2009a.

例4.1考虑在 K2上的二阶锥线性互补问题 (1.1),其数据如下

例 4.1 的精确解为 x∗=(1,1)T. 下面考虑用算法 3.1 求解,首先取幂参数 r=1, 初始点x0=(−1,1)T,取罚参数 η =10 × 2i,i=2,···,7,其数值实验结果如表 4.1 所示,其中 NS 代表数值解,Err 代表数值解 NS 与 x∗的距离. 事实上,本例对应的低阶罚函数方程组 (3.1) 可以利用分析方法求解,且 xη=((η − 2)/(1+ η),(η +2)/(1+ η)),容易得到

因此当 η → +∞ 时,xη以指数速度 O(η−1) 收敛到 x∗,这与式 (3.7) 的结论一致.由表 4.1 可以看出数值实验结果和分析结果是一致的.

下面考虑 Chen 和 Ma[25,26]已经测试过的两个例子. 在测试中令 且初始

η =1000. 例 4.2 和例 4.3 的终止准则分别设为 eps=10−8和 eps=10−7.

例4.2考虑在 K5上的二阶锥线性互补问题 (1.1),其数据如下

本例的解 x∗≈ (0.049185,−0.0030997,0.0096024,0.0031883,0.048033)T[25], 且矩阵 A 满足假设 3.1. 选取不同的初始点,测试结果如表 4.3 所示.

例4.3考虑在 K3上的二阶锥线性互补问题 (1.1),其数据如下

本例的解 x∗≈ (0.183606,−0.154346,−0.099440)T[25],A 是对称半正定矩阵. 选取不同初始点,测试结果如表 4.4 所示.

众所周知, 当 K=Kn时,F-B 函数定义为 满足

二阶锥互补问题的光滑 F-B 函数 φ(µ,x,y):R × Rn× Rn→ Rn为[4]

上述平方和平方根都是指约当积意义下的平方和平方根. 将 y=Ax − b 代入 (4.1) 式, 则二阶锥线性互补问题转化为光滑 F-B 方程,即求 x ∈ Rn,使得

其中µ＞0是光滑参数.

众所周知, 当 µ ↓ 0 时,方程组 (4.2) 的解序列趋向于二阶锥线性互补问题 (1.1) 的解[4].下面给出相应的光滑 F-B 算法.

光滑F-B算法

步骤1取任意向量 b ∈ Rn, 矩阵 A ∈ Rn×n, 令 ~x=0 且 ~x ∈ Rn.

步骤2如果 b≾K0,停止,转步骤 7;否则,转步骤 3.

步骤3如果 A−1b ≿K0, 令 ~x=A−1b, 停止, 转步骤 7; 否则, 转步骤 4.

步骤4取光滑参数 µ ＞ 0,误差限为 eps,倍数参数 0 ＜ d ＜ 1,初始点 x0.

步骤5对光滑参数 µ 和初始点 x0, 解非线性方程组 (4.2), 假设 xµ是 (4.2) 式的解, 令Tol=|xTµ(Axµ− b)|.

步骤6如果 Tol≤ eps,令 ~x=xµ,停止,转步骤 7;否则,令 x0=xµ,µ =dµ,转步骤 5.

步骤7向量 ~x 是二阶锥线性互补问题 (1.1) 的近似最优解.

例 4.4 用随机产生的二阶锥线性互补问题来比较算法 3.1 和光滑 F-B 算法的数值效果,为了方便,例 4.4 中随机产生的矩阵取对称正定矩阵.

例4.4考虑 K 为 100 个块的二阶锥线性互补问 题, 即 K=Kn1× Kn2× ···× Kn100,且 A=diag(A1,···,A100),b=(b1,···,b100). 每一个块矩阵 Ai(i=1,···,100) 是随机产生的对称 正定矩阵. 每 一个向量 块 bi(i=1,···,100) 满 足 qiT(Aqi− bi)=0, 其 中 qi∈ Kni是随机产生的.

表 4.5: 例 4.4 中不同规模情形的数值结果

算法 3.1光滑 F-B 算法问题 m-Val a-Val m-Err a-Err CPU M-Val a-Val m-Err a-Err CPU 200 维 5.56e-8 9.33e-9 9.89e-8 1.48e-8 23.46 1.00e-6 4.06e-7 8.08e-6 4.96e-7 20.54 300 维 2.80e-7 2.33e-8 5.67e-7 5.12e-8 122.91 1.00e-6 4.16e-7 2.15e-6 4.24e-7 53.26 400 维 7.68e-8 2.13e-8 2.86e-7 5.11e-8 130.19 1.00e-6 3.76e-7 1.22e-6 3.40e-7 163.40 500 维 8.72e-8 1.90e-8 2.70e-6 4.44e-8 195.75 1.00e-6 4.16e-7 1.73e-6 4.03e-7 552.13

3

其次固定 ni=8,且, 在算法 3.1 中令 c=10, 初始 η =10, 而光滑 F-B方法中令 d=0.1,初始 µ =0.001. 取共同的终止准则为 eps=10−6, 则数值结果如表 4.6 所示,其中 m-Iter 和 a-Iter 分别代表最大迭代次数和平均迭代次数.

由表 4.5 可知两种算法对例 4.4 都是可行的, 但算法 3.1 的精度明显优于光滑 F-B 算法;而表 4.6 说明,算法 3.1 与光滑 F-B 算法的结果相当,但算法 3.1 所需时间明显少于光滑 F-B算法. 由表 4.6 还可看出, 算法 3.1 对不同参数 r 所得结果也不同, 但一般来说, 参数较小时数值结果更优, 这与结论 (3.7) 一致.

5结论

本文将文献 [21]中二阶锥线性互补问题的幂罚函数算法推广到一般的低阶罚函数算法.当矩阵A 正定时,低阶罚函数方程组的解序列以指数速度收敛到二阶锥线性互补问题的解.当矩阵 A 非正定时,低阶罚函数方程组解序列的任意极限点是二阶锥线性互补问题的解,但收敛速度未知.数值实验结果表明,在矩阵正定条件下,低阶罚函数算法的数值精度和计算时间优于光滑 F-B 算法,而且在低阶罚函数算法中,选取较小的幂参数 r,数值结果更优.

参考文献

[1]Alizadeh F,Goldfarb D.Second-order cone programming[J].Math.Prog.,2003,95(1):3–51.

[2]Lobo MS,Vandenberghe L,Boyd S,et al.Applications of second-order cone programming[J].Linear Alg.Appl.,1998,284(1):193–228.

[3]Facchinei F,Pang J S.Finite-dimensionalvariationalinequalities and complementarity problems[M]. New York:Springer-Verlag,2003.

[4]Fukushima M,Luo Z Q,Tseng P.Smoothing functions for second-order-cone complementarity problems[J].SIAM J.Optim.,2002,12(2):436–460.

[5]Huang Z H,Ni T.Smoothing algorithms for complementarity problems over symmetric cones[J]. Comput.Optim.Appl.,2010,45(3):557–579.

[6]Chen XD,Sun D,Sun J.Complementarity functions and numericalexperiments on some smoothing Newton methods for second-order-cone complementarity problems[J].Comput.Optim.Appl.,2003, 25(1-3):39–56.

[7] 董丽, 王洪芹, 潘虹. 一个求解二阶锥规划的光滑牛顿算法 [J]. 数学杂志,2015,35(6):1453–1460.

[8]Kanzow C,Ferenczi I,Fukushima M.On the local convergence of semismooth Newton methods for linear and nonlinear second-order cone programs without strict complementarity[J].SIAM J. Optim.,2009,20(1):297–320.

[9]Pan S,Chen J S.A damped Gauss-Newton method for the second-order cone complementarity problem[J].Appl.Math.Optim.,2009,59(3):293–318.

[10]Monteiro R DC,Tsuchiya T.Polynomialconvergence of primal-dualalgorithms for the second-order cone program based on the MZ-family of directions[J].Math.Prog.,2000,88(1):61–83.

[11]Chen J S.Two classes of merit functions for the second-order cone complementarity problem[J]. Math.Meth.Oper.Res.,2006,64(3):495–519.

[12]Hayashi S,Yamaguchi T,Yamashita N,et al.A matrix-splitting method for symmetric affi ne secondorder cone complementarity problems[J].J.Comput.Appl.Math.,2005,175(2):335–353.

[13]Zangwill W I.Non-linear programming via penalty functions[J].Manag.Sci.,1967,13(5):344–358. [14]Luo Z Q,Pang J S,Ralph D.Mathematical programs with equilibrium constraints[M].Cambridge: Cambridge Univ.Press,1996.

[15]Han S P,Mangasarian O L.Exact penalty functions in nonlinear programming[J].Math.Prog., 1979,17(1):251–269.

[16]Di Pillo G,Grippo L.An exact penalty function method with global convergence properties for nonlinear programming problems[J].Math.Prog.,1986,36(1):1–18.

[17]Bertsekas DP,Nedi´c A,Ozdaglar AE.Convex analysis and optimization[M].Massachusetts:Athena Sci.Belmont,2003.

[18]Wang S,Yang X.A power penalty method for linear complementarity problems[J].Oper.Res.Lett., 2008,36(2):211–214.

[19]Huang C,Wang S.A power penalty approach to a nonlinear complementarity problem[J].Oper. Res.Lett.,2010,38(1):72–76.

[20]Huang C,Wang S.A penalty method for a mixed nonlinear complementarity problem[J].Nonl. Anal.:The.Meth.Appl.,2012,75(2):588–597.

[21]Hao Z,Wan Z,Chi X.A power penalty method for second-order cone linear complementarity problems[J].Oper.Res.Lett.,2015,43(2),137–142.

[22]Chen J S.The convex and monotone functions associated with second-order cone[J].Optim.,2006, 55(4):363–385.

[23]Faraut J,Kor´anyi A.Analysis on symmetric cones[M].Oxford:Oxford Univ.Press,1994.

[24]Chen J S,Chen X,Tseng P.Analysis of nonsmooth vector-valued functions associated with secondorder cones[J].Math.Prog.,2004,101(1):95–117.

[25]Ma C.A regularized smoothing Newton method for solving the symmetric cone complementarity problem[J].Math.Comp.Model.,2011,54(9):2515–2527.

[26]Chen L,Ma C.A modifi ed smoothing and regularized Newton method for monotone second-order cone complementarity problems[J].Comp.Math.Appl.,2011,61(5):1407–1418.

A LOWER ORDER PENALTY METHOD FOR SECOND-ORDER CONE LINEAR COMPLEMENTARITY PROBLEMS

ZHAO Wen-yu,HAO Zi-jun,YU Guo-lin
(School of Mathematics and Information Science,Beifang University of Nationalities, Yinchuan 750021,China)

In this paper,a lower order penalty method for solving the second-order cone linear complementarity problems is proposed. By this method,the second-order cone linear complementarity problem is transformed into lower order penalty equations.We prove that the solution sequence of the lower order penalty equations converges to the solution of the second-order cone linear complementarity problems at an exponential rate under a mild assumption,which extend the power penalty method for solving this problem.Numerical results demonstrate that our method is effi cient.

second-order cone;linear complementarity problem;low order penalty method; exponential convergence rate

tion:90C25;90C30

0C25;90C30

O224;O221.2

A

0255-7797(2017)02-0427-12

2016-01-27 接收日期:2016-05-23

国家自然科学基金 (11361001;11661002); 宁夏自然科学基金 (NZ16093); 宁夏高等学校科研项目 (NGY2016136).

赵雯宇 (1991–), 女, 山西吕梁,硕士, 主要研究方向: 最优化理论与方法.