\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

The proximal methods for solving absolute value equation

  • * Corresponding author: Saeed Ketabchi

    * Corresponding author: Saeed Ketabchi
Abstract Full Text(HTML) Figure(0) / Table(3) Related Papers Cited by
  • 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.

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

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • 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
  • [1] J. Y. Bello CruzO. 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. DalesBanach Algebras and Automatic Continuity, London Mathematical Society Monographs, Clarendon Press, Oxford, 2000. 
    [4] V. EdalatpourD. 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. GotohA. 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. MoosaeiS. KetabchiM. A. NoorJ. 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. SaheyaC. 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. SartakhtiH. 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. WenX. 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.
  • 加载中

Tables(3)

SHARE

Article Metrics

HTML views(570) PDF downloads(405) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return