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

Abstract

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

CLC Number:

O221

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.

Trendmd

Figures/Tables 5

References 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

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

RichHTML

PDF (PC)

Abstract

Cite this article

share this article

Figures/Tables 5

References 31

Related Articles 8

Metrics

Comments

Recommended 10

[1]	Guodong Ma. A Strongly Convergent Generalized Gradient Projection Method for Minimax Optimization with General Constraints [J]. Acta mathematica scientia,Series A, 2020, 40(3): 641-649.
[2]	HU Chao-Ming, WAN Zhong, WANG Xu. A New Nonmonotone Spectral Conjugate Gradient Algorithm [J]. Acta mathematica scientia,Series A, 2013, 33(1): 78-88.
[3]	TANG Jing-Yong, HE Guo-Ping. A One-step Smoothing Newton Method for Second-order Cone Programming [J]. Acta mathematica scientia,Series A, 2012, 32(4): 768-778.
[4]	Zhang Li; Zhou Weijun. On the Global Convergence of the Hager-Zhang Conjugate Gradient Method with Armijo Line Search [J]. Acta mathematica scientia,Series A, 2008, 28(5): 840-845.
[5]	Tong Xiaojiao ;He Wei. Lagrangian Globalization Projection Methods for Nonlinear Constrained Equations [J]. Acta mathematica scientia,Series A, 2008, 28(1): 96-108.
[6]	Zhou Changyin; He Guoping; Wang Yongli. An Active Constraints Identification Technique-based SSLE Algorithm and Its Convergence Analysis [J]. Acta mathematica scientia,Series A, 2007, 27(3): 535-540.
[7]	GAO Zi-You, Ren Hua-Ling, HE Guo-Ping. A New Sequential Systems of Linear Equations Algorithm Without Strict Complementary Slackness [J]. Acta mathematica scientia,Series A, 2004, 24(3): 275-284.
[8]	Shi Baochang, Chen Ting, Zhu Shijing. A Unified Approach to Method of Centers for Multiobjective Decision Making [J]. Acta mathematica scientia,Series A, 1997, 17(S1): 15-22.