The proximal methods for solving absolute value equation

Samira Shahsavari; Saeed Ketabchi

doi:10.3934/naco.2020037

Article Contents

2021, Volume 11, Issue 3: 449-460. Doi: 10.3934/naco.2020037

This issue Previous Article Application of survival theory in Mining industry Next Article Approximate controllability of a non-autonomous evolution equation in Banach spaces

The proximal methods for solving absolute value equation

Samira Shahsavari and
Saeed Ketabchi^,

Department of Applied Mathematics, Faculty of Mathematical Sciences, University of Guilan, Rasht, Iran

^* Corresponding author: Saeed Ketabchi
^* Corresponding author: Saeed Ketabchi

Received: May 2020

Revised: July 2020

Early access: August 2020

Published: September 2021

Abstract / Introduction Full Text(HTML) Figure(0) / Table(3) Related Papers Cited by

Abstract

In this paper, by considering that the objective function of the least squares NP-hard absolute value equations (AVE) $ Ax-\vert x\vert = b $, is non-convex and non-smooth, two types of proximal algorithms are proposed to solve it. One of them is the proximal difference-of-convex algorithm with extrapolation and another is the proximal subgradient method. The convergence results of the proposed methods are proved under certain assumptions. Moreover, a numerical comparison is presented to demonstrate the effectiveness of the suggested methods.

Keywords:

Absolute value equation,
The proximal difference-of-convex algorithm,
The proximal subgradient method,
Non-convex and non-smooth.

Mathematics Subject Classification: Primary: 90C26; Secondary: 90C25, 65D10.

Citation:

FullText(HTML)

Table 1. Numerical results

$ n $	$ PSM $			$ PDCA_e(\phi_1) $			$ PDCA_e(\phi_2) $			$ NMA $
	$ k $	$ f^* $	Time(s)	$ k $	$ f^* $	Time(s)	$ k $	$ f^* $	Time(s)	$ k $	$ f^* $	Time(s)
100	3	1.3014e-13	0.00	6	3.1549e-09	0.01	6	6.7541e-09	0.01	3	3.3234e-14	0.00
200	4	4.8438e-13	0.00	15	6.1291e-09	0.14	15	4.2898e-08	0.14	3	5.5826e-13	0.02
300	4	5.7916e-13	0.01	11	3.1076e-09	0.33	11	4.9451e-08	0.35	3	1.5016e-13	0.07
400	4	2.1847e-12	0.03	15	5.3480e-09	1.06	15	4.9031e-08	1.13	3	8.9333e-14	0.15
500	3	1.4051e-12	0.05	21	4.1335e-09	2.99	22	4.9321e-08	3.13	3	4.7710e-14	0.31
600	4	2.5018e-12	0.09	28	5.1572e-09	6.97	34	2.7704e-07	8.64	4	7.6831e-14	0.65
700	4	4.9005e-12	0.12	48	2.5569e-08	17.97	49	5.0799e-07	18.40	4	1.6743e-13	0.88
800	3	1.8771e-12	0.18	9	1.7880e-08	5.43	10	4.9939e-07	6.57	3	7.4302e-13	1.22
900	3	2.3440e-12	0.25	10	4.8424e-09	8.49	12	5.0099e-07	10.44	3	4.8301e-13	1.80
1000	4	2.2558e-11	0.35	187	1.2343e-08	211.21	235	5.4557e-07	265.12	4	7.5471e-13	2.87
1200	3	8.5001e-12	0.50	60	5.7357e-09	113.34	64	5.0522e-07	123.40	3	1.4848e-12	4.46
1400	4	6.2183e-12	0.75	22	1.7305e-08	65.07	27	5.0418e-07	82.38	3	4.7878e-13	6.92
1600	4	1.2471e-11	1.15	56	2.3000e-08	244.24	71	5.2194e-07	313.12	3	1.3944e-12	9.93
1800	4	2.6274e-11	1.64	77	1.8945e-08	470.20	98	5.0848e-07	598.70	3	3.8787e-12	14.34
2000	4	7.3268e-11	2.11	29	2.0366e-06	250.21	28	6.7804e-06	254.94	3	3.2740e-11	20.24
2500	4	1.5833e-11	3.70	21	3.5403e-06	360.32	21	7.2616e-06	363.47	3	6.4072e-13	37.47
3000	4	1.9845e-11	6.18	-	-	-	-	-	-	3	1.2198e-12	64.59
3500	4	1.1487e-10	9.72	-	-	-	-	-	-	4	1.4824e-12	114.05
4000	4	4.8631e-11	13.99	-	-	-	-	-	-	4	1.7890e-08	165.84
4500	4	1.8675e-10	19.14	-	-	-	-	-	-	3	3.4833e-09	223.21
5000	4	7.5360e-11	25.71	-	-	-	-	-	-	3	3.0396e-12	296.17
5500	4	5.9422e-11	35.54	-	-	-	-	-	-	4	2.7493e-8	416.63
6000	4	8.8736e-11	41.20	-	-	-	-	-	-	3	3.8974e-12	531.20
6500	3	8.3807e-11	52.38	-	-	-	-	-	-	-	-	-
7000	4	1.0264e-10	71.85	-	-	-	-	-	-	-	-	-
7500	4	3.8926e-10	82.25	-	-	-	-	-	-	-	-	-
8000	4	5.8126e-11	163.77	-	-	-	-	-	-	-	-	-

| Show Table

DownLoad: CSV

Table 2. Rank and time of four algorithms

n(d)	$ PSM $		$ PDCA_e(\phi_1) $		$ PDCA_e(\phi_2) $		$ NMA $
	Time(s)	Rank	Time(s)	Rank	Time(s)	Rank	Time(s)	Rank
100	0.00	1.5	0.01	3.5	0.01	3.5	0.00	1.5
200	0.00	1	0.14	3.5	0.14	3.5	0.02	2
300	0.01	1	0.33	3	0.35	4	0.07	2
400	0.03	1	1.06	3	1.13	4	0.15	2
500	0.05	1	2.99	3	3.13	4	0.31	2
600	0.09	1	6.97	3	8.64	4	0.65	2
700	0.12	1	17.97	3	18.40	4	0.88	2
800	0.18	1	5.43	3	6.57	4	1.22	2
900	0.25	1	8.49	3	10.44	4	1.80	2
1000	0.35	1	211.21	3	265.12	4	2.87	2
1200	0.50	1	113.34	3	123.40	4	4.46	2
1400	0.75	1	65.07	3	82.38	4	6.92	2
1600	1.15	1	244.24	3	313.12	4	9.93	2
1800	1.64	1	470.20	3	598.70	4	14.34	2
2000	2.11	1	250.21	3	254.94	4	20.24	2
2500	3.70	1	360.32	3	363.47	4	37.47	2
3000	6.18	1	-	3.5	-	3.5	64.59	2
3500	9.72	1	-	3.5	-	3.5	114.05	2
4000	13.99	1	-	3.5	-	3.5	165.84	2
4500	19.14	1	-	3.5	-	3.5	223.21	2
5000	25.71	1	-	3.5	-	3.5	296.17	2
5500	35.54	1	-	3.5	-	3.5	416.63	2
6000	41.20	1	-	3.5	-	3.5	531.20	2
6500	52.38	1	-	3	-	3	-	3
7000	71.85	1	-	3	-	3	-	3
7500	82.25	1	-	3	-	3	-	3
8000	163.77	1	-	3	-	3	-	3

| Show Table

DownLoad: CSV

Table 3. Rank and accuracy of four algorithms

n	$ PSM $		$ PDCA_e(\phi_1) $		$ PDCA_e(\phi_2) $		$ NMA $
	$ f^* $	Rank	$ f^* $	Rank	$ f^* $	Rank	$ f^* $	Rank
100	1.3014e-13	2	3.1549e-09	3.5	6.7541e-09	3.5	3.3234e-14	1
200	4.8438e-13	1.5	6.1291e-09	3	4.2898e-08	4	5.5826e-13	1.5
300	5.7916e-13	1.5	3.1076e-09	3	4.9451e-08	4	1.5016e-13	1.5
400	2.1847e-12	2	5.3480e-09	3	4.9031e-08	4	8.9333e-14	1
500	1.4051e-12	2	4.1335e-09	3	4.9321e-08	4	4.7710e-14	1
600	2.5018e-12	2	5.1572e-09	3	2.7704e-07	4	7.6831e-14	1
700	4.9005e-12	2	2.5569e-08	3	5.0799e-07	4	1.6743e-13	1
800	1.8771e-12	2	1.7880e-08	3	4.9939e-07	4	7.4302e-13	1
900	2.3440e-12	2	4.8424e-09	3	5.0099e-07	4	4.8301e-13	1
1000	2.2558e-11	2	1.2343e-08	3	5.4557e-07	4	7.5471e-13	1
1200	8.5001e-12	1.5	5.7357e-09	3	5.0522e-07	4	1.4848e-12	1.5
1400	6.2183e-12	2	1.7305e-08	3	5.0418e-07	4	4.7878e-13	1
1600	1.2471e-11	2	2.3000e-08	3	5.2194e-07	4	1.3944e-12	1
1800	2.6274e-11	2	1.8945e-08	3	5.0848e-07	4	3.8787e-12	1
2000	7.3268e-11	1.5	2.0366e-06	3.5	6.7804e-06	3.5	3.2740e-11	1.5
2500	1.5833e-11	2	3.5403e-06	3.5	7.2616e-06	3.5	6.4072e-13	1
3000	1.9845e-11	2	-	3.5	-	3.5	1.2198e-12	1
3500	1.1487e-10	2	-	3.5	-	3.5	1.4824e-12	1
4000	4.8631e-11	1	-	3.5	-	3.5	1.7890e-08	2
4500	1.8675e-10	1	-	3.5	-	3.5	3.4833e-09	2
5000	7.5360e-11	2	-	3.5	-	3.5	3.0396e-12	1
5500	5.9422e-11	1	-	3.5	-	3.5	2.7493e-8	2
6000	8.8736e-11	2	-	3.5	-	3.5	3.8974e-12	1
6500	8.3807e-11	1	-	3	-	3	-	3
7000	1.0264e-10	1	-	3	-	3	-	3
7500	3.8926e-10	1	-	3	-	3	-	3
8000	5.8126e-11	1	-	3	-	3	-	3

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	J. Y. Bello Cruz, O. P. Ferreira and L. F. Prudente, On the global convergence of the inexact semi-smooth Newton method for absolute value equation, Computational Optimization and Applications, 65 (2016), 93-108. doi: 10.1007/s10589-016-9837-x.
[2]	X. Chen, Smoothing methods for nonsmooth, nonconvex minimization, Mathematical Programming, 134 (2012), 71–99. doi: 10.1007/s10107-012-0569-0.
[3]	H. G. Dales, Banach Algebras and Automatic Continuity, London Mathematical Society Monographs, Clarendon Press, Oxford, 2000.
[4]	V. Edalatpour, D. Hezari and D. K. Salkuyeh, A generalization of the Gauss Seidel iteration method for solving absolute value equations, Applied Mathematics and Computation, 293 (2017), 156-167. doi: 10.1016/j.amc.2016.08.020.
[5]	J. Gotoh, A. Takeda and K. Tono, DC formulations and algorithms for sparse optimization problems, Mathematical Programming, 169 (2018), 141-176. doi: 10.1007/s10107-017-1181-0.
[6]	F. Hashemi and S. Ketabchi, Numerical comparisons of smoothing functions for optimal correction of an infeasible system of absolute value equations, Numerical Algebra, Control and Optimization, 10 (2020), 13-21.
[7]	S. Ketabch and H. Moosaei, An efficient method for optimal correcting of absolute value equations by minimal changes in the right hand side, Computers and Mathematics with Applications, 64 (2012), 1882-1885. doi: 10.1016/j.camwa.2012.03.015.
[8]	S. Ketabchi and H. Moosaei, Minimum norm solution to the absolute value equation in the convex case, Journal of Optimization Theory and Applications, 154 (2012), 1080-1087. doi: 10.1007/s10957-012-0044-3.
[9]	C.-X. Li, A modified generalized newton method for absolute value equations, Journal of Optimization Theory and Applications, 170 (2016), 1055-1059. doi: 10.1007/s10957-016-0956-4.
[10]	P. L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM Journal on Numerical Analysis, 16 (1979), 964-979. doi: 10.1137/0716071.
[11]	O. L. Mangasarian, A generalized Newton method for absolute value equations, Optimization Letters, 3 (2009), 101-108. doi: 10.1007/s11590-008-0094-5.
[12]	O. L. Mangasarian, Absolute value equation solution via concave minimization, Optimization Letters, 1 (2007), 3-8. doi: 10.1007/s11590-006-0005-6.
[13]	O. L. Mangasarian, Primal-dual bilinear programming solution of the absolute value equation, Optimization Letters, 6 (2012), 1527-1533. doi: 10.1007/s11590-011-0347-6.
[14]	R. D. Millan and M. P. Machado, Inexact proximal $\epsilon$-subgradient methods for composite convex optimization problems, Journal of Global Optimization, 75 (2019), 1029-1060. doi: 10.1007/s10898-019-00808-8.
[15]	H. Moosaei, S. Ketabchi, M. A. Noor, J. Iqbal and V. Hooshyarbakhsh, Some techniques for solving absolute value equations, Applied Mathematics and Computation, 268 (2015), 696-705. doi: 10.1016/j.amc.2015.06.072.
[16]	G. Ning and Y. Zhou, An improved differential evolution algorithm for solving absolute value equations, High Performance Computing and Applications, (2016), 38–47. doi: 10.1007/978-3-319-32557-6_4.
[17]	G. B. Passty, Ergodic convergence to a zero of the sum of monotone operators in Hilbert space, Journal of Mathematical Analysis and Applications, 72 (1979), 383-390. doi: 10.1016/0022-247X(79)90234-8.
[18]	D. T. Pham and H. A. Le Thi, Convex analysis approach to D.C. programming: theory, algorithms and applications, Acta Mathematica Vietnamica, 22 (1997), 289-355.
[19]	T. J. Ransford, A short proof of Johnson's uniqueness-of-norm theorem, Bulletin of the London Mathematical Society, 21 (1989), 487-488. doi: 10.1112/blms/21.5.487.
[20]	B. Saheya, C. H. Yu and J. S. Chen, Numerical comparisons based on four smoothing functions for absolute value equation, Journal of Applied Mathematics and Computing, 56 (2018), 131-149. doi: 10.1007/s12190-016-1065-0.
[21]	J. S. Sartakhti, H. Afrabandpey and M. Saraee, Simulated annealing least squares twin support vector machine (SA-LSTSVM) for pattern classification, Soft Computing, 21 (2017), 4361-4373.
[22]	D. K. Salkuyeh, The Picard-HSS iteration method for absolute value equations, Optimization Letters, 8 (2014), 2191-2202. doi: 10.1007/s11590-014-0727-9.
[23]	B. Wen, X. Chen and T. K. Pong, A proximal difference-of-convex algorithm with extrapolation, Computational Optimization and Applications, 69 (2018), 297-324. doi: 10.1007/s10589-017-9954-1.
[24]	C. Zhang and Q. J. Wei, Global and finite convergence of a generalized newton method for absolute value equations, Journal of Optimization Theory and Applications, 143 (2009), 391-403. doi: 10.1007/s10957-009-9557-9.