Article Contents
Article Contents

# A smoothing-type algorithm for absolute value equations

• The system of absolute value equations $Ax+B|x|=b$, denoted by AVEs, is proved to be NP-hard, where $A, B$ are arbitrary given $n\times n$ real matrices and $b$ is arbitrary given $n$-dimensional vector. In this paper, we reformulate AVEs as a family of parameterized smooth equations and propose a smoothing-type algorithm to solve AVEs. Under the assumption that the minimal singular value of the matrix $A$ is strictly greater than the maximal singular value of the matrix $B$, we prove that the algorithm is well-defined. In particular, we show that the algorithm is globally convergent and the convergence rate is quadratic without any additional assumption. The preliminary numerical results are reported, which show the effectiveness of the algorithm.
Mathematics Subject Classification: Primary: 90C05, 90C33; Secondary: 15A06.

 Citation:

•  [1] L. Caccetta, B. Qu and G. L. Zhou, A globally and quadratically convergent method for absolute value equations, Computational Optimization and Applications, 48 (2011), 45-58.doi: 10.1007/s10589-009-9242-9. [2] R. W. Cottle, J. S. Pang and R. E. Stone, "The Linear Complementarity Problem," Academic Press, New York, 1992. [3] N. J. Higham, Estimating the matrix $p$-norm, Numerische Mathematik, 62 (1992), 539-555.doi: 10.1007/BF01396242. [4] R. A. Horn and C. R. Johnson, "Matrix Analysis," Cambridge University Press, Cambridge, 1985. [5] S. L. Hu and Z. H. Huang, A note on absolute value equations, Optimization Letters, 4 (2010), 417-424.doi: 10.1007/s11590-009-0169-y. [6] S. L. Hu, Z. H. Huang and J. S. Chen, Properties of a family of generalized NCP-functions and a derivative free algorithm for complementarity problems, Journal of Computational and Applied Mathematics, 230 (2009), 69-82.doi: 10.1016/j.cam.2008.10.056. [7] S. L. Hu, Z. H. Huang and Q. Zhang, A generalized Newton method for absolute value equations associated with second order cones, Journal of Computational and Applied Mathematics, 235 (2011), 1490-1501.doi: 10.1016/j.cam.2010.08.036. [8] Z. H. Huang, Locating a maximally complementary solution of the monotone NCP by using non-interior-point smoothing algorithms, Mathematical Methods of Operations Research, 61 (2005), 41-55.doi: 10.1007/s001860400384. [9] Z. H. Huang, Y. Zhang and W. Wu, A smoothing-type algorithm for solving system of inequalities, Journal of Computational and Applied Mathematics, 220 (2008), 355-363.doi: 10.1016/j.cam.2007.08.024. [10] O. L. Mangasarian, Absolute value programming, Computational Optimization and Applications, 36 (2007), 43-53. [11] O. L. Mangasarian, Absolute value equation solution via concave minmization, Optimization Letters, 1 (2007), 3-8.doi: 10.1007/s11590-006-0005-6. [12] O. L. Mangasarian, A generalized Newton method for absolute value equations, Optimization Letters, 3 (2009), 101-108.doi: 10.1007/s11590-008-0094-5. [13] O. L. Mangasarian and R. R. Meyer, Absolute value equations, Linear Algebra and Its Applications, 419 (2006), 359-367.doi: 10.1016/j.laa.2006.05.004. [14] O. A. Prokopyev, On equivalent reformulations for absolute value equations, Computational Optimization and Applications, 44 (2009), 363-372.doi: 10.1007/s10589-007-9158-1. [15] O. A. Prokopyev, S. Butenko and A. Trapp, Checking solvability of systems of interval linear equations and inequalities via mixed integer programming, European Journal of Operational Research, 199 (2009), 117-121.doi: 10.1016/j.ejor.2008.11.008. [16] L. Qi, Convergence analysis of some algorithms for solving nonsmooth equations, Mathematics of Operations Research, 18 (1993), 227-244.doi: 10.1287/moor.18.1.227. [17] L. Qi, D. Sun and G. L. Zhou, A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequality problems, Mathematical Programming, 87 (2000), 1-35. [18] J. Rohn, A theorem of the alternatives for the equation $Ax+B|x|=b$, Linear and Multilinear Algebra, 52 (2004), 421-426.doi: 10.1080/0308108042000220686. [19] J. Rohn, Solvability of systems of interval linear equations and inequalities, in "Linear Optimization Problems with Inexact Data" (eds. M. Fiedler, J. Nedoma, J. Ramik, J. Rohn and K. Zimmermann), Springer, (2006), 35-77.doi: 10.1007/0-387-32698-7_2. [20] J. Rohn, An algorithm for solving the absolute value equation, Eletronic Journal of Linear Algebra, 18 (2009), 589-599. [21] 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.