对称锥权互补问题的正则化非单调非精确光滑牛顿法

数学物理学报 ›› 2021, Vol. 41 ›› Issue (2): 507-522.

对称锥权互补问题的正则化非单调非精确光滑牛顿法

迟晓妮^1,^2,*(),曾荣^1,³,刘三阳⁴,朱志斌¹

¹ 桂林电子科技大学数学与计算科学学院广西桂林 541004
² 广西密码学与信息安全重点实验室广西桂林 541004
³ 广西自动检测技术与仪器重点实验室广西桂林 541004
⁴ 西安电子科技大学数学与统计学院西安 710071

收稿日期:2019-03-15 出版日期:2021-04-26 发布日期:2021-04-29
通讯作者: 迟晓妮 E-mail:chixiaoni@126.com
基金资助:
国家自然科学基金(11861026);国家自然科学基金(61877046);国家自然科学基金(61967004);广西自然科学基金(2016GXNSFBA380102);广西密码学与信息安全重点实验室研究课题(GCIS201819);广西自动检测技术与仪器重点实验室基金(YQ18112)

A Regularized Nonmonotone Inexact Smoothing Newton Algorithm for Weighted Symmetric Cone Complementarity Problems

Xiaoni Chi^1,^2,*(),Rong Zeng^1,³,Sanyang Liu⁴,Zhibin Zhu¹

¹ School of Mathematics and Computing Science, Guilin University of Electronic Technology, Guangxi Guilin 541004
² Guangxi Key Laboratory of Cryptography and Information Security, Guangxi Guilin 541004
³ Guangxi Key Laboratory of Automatic Detecting Technology and Instruments, Guangxi Guilin 541004
⁴ School of Mathematics and Statistics, Xidian University, Xi'an 710071

Received:2019-03-15 Online:2021-04-26 Published:2021-04-29
Contact: Xiaoni Chi E-mail:chixiaoni@126.com
Supported by:
the NSFC(11861026);the NSFC(61877046);the NSFC(61967004);the NSF of Guangxi(2016GXNSFBA380102);the Guangxi Key Laboratory of Cryptography and Information Security(GCIS201819);the Guangxi Key Laboratory of Automatic Detection Technology and Instrument(YQ18112)

摘要/Abstract

摘要：

该文提出正则化非单调非精确光滑牛顿法求解对称锥权互补问题（wSCCP）.算法将正则化参数视为一个独立变量，因此它与许多现有的算法相比，更简单易实现.在每次迭代中，算法只需求得方程组的近似解.另外，算法中的非单调线搜索包含了两种常用的非单调形式.在单调假设下，证明算法全局收敛且局部二阶收敛.最后，一些数值结果表明了算法的有效性.

关键词: 正则化非精确牛顿法, 对称锥权互补问题, 非单调线搜索, 全局收敛, 局部二阶收敛

Abstract:

In this paper, we propose a regularized nonmonotone inexact smoothing Newton algorithm for solving the weighted symmetric cone complementarity problem(wSCCP). In the algorithm, we consider the regularized parameter as an independent variable. Therefore, it is simpler and easier to implement than many available algorithms. At each iteration, we only need to obtain an inexact solution of a system of equations. Moreover, the nonmonotone line search technique adopted in our algorithm includes two popular nonmonotone search schemes. We prove that the algorithm is globally and locally quadratically convergent under suitable assumptions. Finally, some preliminary numerical results indicate the effectiveness of our algorithm.

Key words: Regularized inexact smoothing Newton algorithm, Weighted symmetric cone complementarity problem, Nonmonotone line search, Global convergence, Locally quadratic convergence

中图分类号:

O221

迟晓妮,曾荣,刘三阳,朱志斌. 对称锥权互补问题的正则化非单调非精确光滑牛顿法[J]. 数学物理学报, 2021, 41(2): 507-522.

Xiaoni Chi,Rong Zeng,Sanyang Liu,Zhibin Zhu. A Regularized Nonmonotone Inexact Smoothing Newton Algorithm for Weighted Symmetric Cone Complementarity Problems[J]. Acta mathematica scientia,Series A, 2021, 41(2): 507-522.

图/表 5

表 1

表 2

表 3

表 4

表 5

参考文献 31

1	Potra F A . Weighted complementarity problems-a new paradigm for computing equilibria. SIAM J Optim, 2012, 22 (4): 1634- 1654 doi: 10.1137/110837310
2	Anstreicher K M . Interior-point algorithms for a generalization of linear programming and weighted centring. Optim Methods Softw, 2012, 27 (4/5): 605- 612
3	Potra F A . Sufficient weighted complementarity problems. Comput Optim Appl, 2016, 64 (2): 467- 488 doi: 10.1007/s10589-015-9811-z
4	Jian Z . A smoothing Newton algorithm for weighted linear complementarity problem. Optim Lett, 2016, 10 (3): 499- 509 doi: 10.1007/s11590-015-0877-4
5	Chi X N , Gowda M S , Tao J Y . The weighted horizontal linear complementarity problem on a Euclidean Jordan algebra. J Global Optim, 2019, 73 (1): 153- 169 doi: 10.1007/s10898-018-0689-z
6	Chen X J , Qi L Q , Sun D F . Global and superlinear convergence of the smooothing Newton method and its application to general box constrained variational inequalities. Math Comput, 1998, 67 (222): 519- 540 doi: 10.1090/S0025-5718-98-00932-6
7	Chi X N , Liu S Y . A one-step smoothing Newton method for second-order cone programming. J Comput Appl Math, 2009, 223 (1): 114- 123 doi: 10.1016/j.cam.2007.12.023
8	Hayashi S , Yamashita N , Fukushima M . A combined smoothing and regularization method for monotone second-order cone complementarity problems. SIAM J Optim, 2005, 15 (8): 593- 615
9	Huang Z H , Ni T . Smoothing algorithms for complementarity problems over symmetric cones. Comput Optim Appl, 2010, 45 (3): 557- 579 doi: 10.1007/s10589-008-9180-y
10	Kong L C , Sun J , Xiu N H . A regularized smoothing Newton method for symmetric cone complementarity problems. SIAM J Optim, 2008, 19 (3): 1028- 1047 doi: 10.1137/060676775
11	Fang L , He G P . Some modifications of Newton's method with higher-order convergence for solving nonlinear equations. J Comput Appl Math, 2009, 228 (1): 296- 303 doi: 10.1016/j.cam.2008.09.023
12	Liu Y J , Zhang L W , Wang Y H . Analysis of a smoothing method for symmetric conic linear programming. J Appl Math Comput, 2006, 22 (1/2): 133- 148 doi: 10.1007/BF02896466
13	Pan S H , Chen J S . A regularization method for the second-order cone complementarity problem with the Cartesian P0-property. Nonlinear Anal, 2009, 70 (4): 1475- 1491 doi: 10.1016/j.na.2008.02.028
14	Qi L Q , Sun D F , Zhou G L . A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities. Math Program, 2000, 87 (1): 1- 35 doi: 10.1007/s101079900127
15	Tang J Y , Dong L , Zhou J C , et al. A smoothing-type algorithm for the second-order cone complementarity problem with a new nonmonotone line search. Optim, 2015, 64 (9): 1935- 1955 doi: 10.1080/02331934.2014.906595
16	Wu J , Zhang L W , Zhang Y . A smoothing Newton method for mathematical programs governed by second-order cone constrained generalized equations. J Glob Optim, 2013, 55 (2): 359- 385 doi: 10.1007/s10898-012-9880-9
17	Yu G L , Liu S Y . Optimality conditions of globally proper efficient solutions for set-valued optimization problems. Acta Math Appl Sin, 2010, 33 (1): 150- 160
18	Zhang Y S , Gao L F . A smoothing inexact Newton method for symmetric cone complementarity problems. Acta Math Sci, 2015, 35A (4): 824- 832
19	Chi X N , Liu S Y . An infeasible-interior-point predictor-corrector algorithm for the second-order cone program. Acta Math Sci, 2008, 28B (3): 551- 559
20	Yoshise A . Interior point trajectories and a homogeneous model for nonlinear complementarity problems over symmetric cones. SIAM J Optim, 2006, 17 (4): 1129- 1153
21	Wan Z P , Wang X J , He J L , et al. Asymptotic approximation method and its convegence on semi-infinite programming. Acta Math Sci, 2006, 26B (1): 17- 24
22	Xu Y H , Liu S Y . The (h, φ)-Lipschitz function, its generalized directional derivative and generalized gradient. Acta Math Sci, 2006, 26A (2): 212- 222
23	Ahookhosh M , Ghaderi S . On efficiency of nonmonotone Armijo-type line searches. Appl Math Model, 2017, 43, 170- 190 doi: 10.1016/j.apm.2016.10.055
24	Grippo L , Lampariello F , Lucidi S . A nonmonotone line search technique for Newton's Method. SIAM J Numer Anal, 1986, 23 (4): 707- 716 doi: 10.1137/0723046
25	Zhang H , Hager W W . A nonmonotone line search technique and its application to unconstrained optimization. SIAM J Optim, 2004, 14 (4): 1043- 1056 doi: 10.1137/S1052623403428208
26	Faraut J , Korányi A . Analysis on Symmetric Cones. New York: Oxford University Press, 1994
27	Mifflin R . Semismooth and semiconvex functions in constrained optimization. SIAM J Control Optim, 1977, 15 (6): 957- 972
28	Qi L , Sun J . A nonsmooth version of Newton's method. Math Program, 1993, 58 (1/3): 353- 367
29	Clarke F H . Optimization and Nonsmooth Analysis. New York: Wiley, 1983
30	Gowda M S , Sznajder R , Tao J . Some P-properties for linear transformations on Euclidean algebras. Linear Algebra Appl, 2004, 393 (1): 203- 232
31	Sun D , Sun J . Strong semismoothness of the Fischer-Burmeister SDC and SOC complementarity functions. Math Program, 2005, 103 (3): 575- 581 doi: 10.1007/s10107-005-0577-4

	Algorithm 4.1		Grippo's method		Zhang-Hager's method
n	ACPU	AIter	ACPU	AIter	ACPU	AIter
100	0.0077	4.86	0.0097	4.96	0.0080	4.94
200	0.0327	5.08	0.0340	5.16	0.0353	5.26
300	0.0967	6.00	0.0997	6.00	0.0995	6.00
400	0.2683	6.00	0.2763	6.00	0.2835	6.00
500	0.4576	6.00	0.4810	6.02	0.4757	6.02
600	0.7771	6.50	0.7824	6.58	0.9503	6.66
700	1.2112	7.00	1.2178	7.00	1.5006	7.00
800	1.6096	7.00	1.6162	7.00	1.7667	7.00

	SOCCP(w =0)		wSOCCP(w = e)		wSOCCP(w = (1, 1, 0, …, 0)^T)
n	ACPU	AIter	ACPU	AIter	ACPU	AIter
100	0.0092	5.54	0.0077	4.86	0.0081	5.00
200	0.0404	6.00	0.0327	5.08	0.0403	6.00
300	0.1084	6.52	0.0967	6.00	0.0999	6.00
400	0.3224	7.00	0.2683	6.00	0.2885	6.10
500	0.6037	7.00	0.4576	6.00	0.5476	7.00
600	0.8666	7.12	0.7771	6.50	0.8525	7.00
700	1.3798	7.82	1.2112	7.00	1.2700	7.00
800	1.9243	8.00	1.6096	7.00	1.6915	7.00

	SOCCP(w =0)		wSOCCP(w = e)		wSOCCP(w = (1, 1, 0, …, 0)^T)
n	ACPU	AIter	ACPU	AIter	ACPU	AIter
100	0.0180	6.24	0.0145	5.02	0.0179	6.00
200	0.0617	7.08	0.0512	6.00	0.0621	7.00
300	0.1395	7.76	0.1145	6.54	0.1294	7.28
400	0.3378	8.22	0.2916	7.00	0.3434	8.00
500	0.6096	8.92	0.4744	7.00	0.5601	8.02
600	0.9576	9.28	0.8505	7.24	0.9394	8.96
700	1.4090	9.50	1.3711	8.00	1.3584	9.00
800	2.2010	9.76	1.6803	8.00	1.7638	9.00

n	(x₀, s₀)	ACPU	AIter
100	(e, 0)	0.0078	5.00
100	(0, e)	0.0069	4.38
100	(1, 1)	0.0092	5.46
100	-(1, 1)	0.0094	5.66
100	10×(1, 1)	0.0101	5.92
100	-10×(1, 1)	0.0098	5.88

	SOCCP(w = 0)		wSOCCP(w = (1, 0, 0, 1, 0)^T)
(x₀, s₀)	ACPU	AIter	ACPU	AIter
(1, 1)	0.0149	8.00	0.0085	7.00
-(1, 1)	0.0144	8.00	0.0150	9.00
10×(1, 1)	0.0255	13.00	0.0174	12.00
-10×(1, 1)	0.0231	13.00	0.0194	13.00