October  2013, 9(4): 789-798. doi: 10.3934/jimo.2013.9.789

A smoothing-type algorithm for absolute value equations

1. 

Department of Public Basic, Wuhan Yangtze Business University, Wuhan 430065, China

2. 

Department of Mathematics, School of Science, Tianjin University, Tianjin 300072, China

Received  February 2012 Revised  July 2013 Published  August 2013

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.
Citation: Xiaoqin Jiang, Ying Zhang. A smoothing-type algorithm for absolute value equations. Journal of Industrial & Management Optimization, 2013, 9 (4) : 789-798. doi: 10.3934/jimo.2013.9.789
References:
[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.  doi: 10.1007/s10589-009-9242-9.  Google Scholar

[2]

R. W. Cottle, J. S. Pang and R. E. Stone, "The Linear Complementarity Problem,", Academic Press, (1992).   Google Scholar

[3]

N. J. Higham, Estimating the matrix $p$-norm,, Numerische Mathematik, 62 (1992), 539.  doi: 10.1007/BF01396242.  Google Scholar

[4]

R. A. Horn and C. R. Johnson, "Matrix Analysis,", Cambridge University Press, (1985).   Google Scholar

[5]

S. L. Hu and Z. H. Huang, A note on absolute value equations,, Optimization Letters, 4 (2010), 417.  doi: 10.1007/s11590-009-0169-y.  Google Scholar

[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.  doi: 10.1016/j.cam.2008.10.056.  Google Scholar

[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.  doi: 10.1016/j.cam.2010.08.036.  Google Scholar

[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.  doi: 10.1007/s001860400384.  Google Scholar

[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.  doi: 10.1016/j.cam.2007.08.024.  Google Scholar

[10]

O. L. Mangasarian, Absolute value programming,, Computational Optimization and Applications, 36 (2007), 43.   Google Scholar

[11]

O. L. Mangasarian, Absolute value equation solution via concave minmization,, Optimization Letters, 1 (2007), 3.  doi: 10.1007/s11590-006-0005-6.  Google Scholar

[12]

O. L. Mangasarian, A generalized Newton method for absolute value equations,, Optimization Letters, 3 (2009), 101.  doi: 10.1007/s11590-008-0094-5.  Google Scholar

[13]

O. L. Mangasarian and R. R. Meyer, Absolute value equations,, Linear Algebra and Its Applications, 419 (2006), 359.  doi: 10.1016/j.laa.2006.05.004.  Google Scholar

[14]

O. A. Prokopyev, On equivalent reformulations for absolute value equations,, Computational Optimization and Applications, 44 (2009), 363.  doi: 10.1007/s10589-007-9158-1.  Google Scholar

[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.  doi: 10.1016/j.ejor.2008.11.008.  Google Scholar

[16]

L. Qi, Convergence analysis of some algorithms for solving nonsmooth equations,, Mathematics of Operations Research, 18 (1993), 227.  doi: 10.1287/moor.18.1.227.  Google Scholar

[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.   Google Scholar

[18]

J. Rohn, A theorem of the alternatives for the equation $Ax+B|x|=b$,, Linear and Multilinear Algebra, 52 (2004), 421.  doi: 10.1080/0308108042000220686.  Google Scholar

[19]

J. Rohn, Solvability of systems of interval linear equations and inequalities,, in, (2006), 35.  doi: 10.1007/0-387-32698-7_2.  Google Scholar

[20]

J. Rohn, An algorithm for solving the absolute value equation,, Eletronic Journal of Linear Algebra, 18 (2009), 589.   Google Scholar

[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.  doi: 10.1007/s10957-009-9557-9.  Google Scholar

show all references

References:
[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.  doi: 10.1007/s10589-009-9242-9.  Google Scholar

[2]

R. W. Cottle, J. S. Pang and R. E. Stone, "The Linear Complementarity Problem,", Academic Press, (1992).   Google Scholar

[3]

N. J. Higham, Estimating the matrix $p$-norm,, Numerische Mathematik, 62 (1992), 539.  doi: 10.1007/BF01396242.  Google Scholar

[4]

R. A. Horn and C. R. Johnson, "Matrix Analysis,", Cambridge University Press, (1985).   Google Scholar

[5]

S. L. Hu and Z. H. Huang, A note on absolute value equations,, Optimization Letters, 4 (2010), 417.  doi: 10.1007/s11590-009-0169-y.  Google Scholar

[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.  doi: 10.1016/j.cam.2008.10.056.  Google Scholar

[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.  doi: 10.1016/j.cam.2010.08.036.  Google Scholar

[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.  doi: 10.1007/s001860400384.  Google Scholar

[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.  doi: 10.1016/j.cam.2007.08.024.  Google Scholar

[10]

O. L. Mangasarian, Absolute value programming,, Computational Optimization and Applications, 36 (2007), 43.   Google Scholar

[11]

O. L. Mangasarian, Absolute value equation solution via concave minmization,, Optimization Letters, 1 (2007), 3.  doi: 10.1007/s11590-006-0005-6.  Google Scholar

[12]

O. L. Mangasarian, A generalized Newton method for absolute value equations,, Optimization Letters, 3 (2009), 101.  doi: 10.1007/s11590-008-0094-5.  Google Scholar

[13]

O. L. Mangasarian and R. R. Meyer, Absolute value equations,, Linear Algebra and Its Applications, 419 (2006), 359.  doi: 10.1016/j.laa.2006.05.004.  Google Scholar

[14]

O. A. Prokopyev, On equivalent reformulations for absolute value equations,, Computational Optimization and Applications, 44 (2009), 363.  doi: 10.1007/s10589-007-9158-1.  Google Scholar

[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.  doi: 10.1016/j.ejor.2008.11.008.  Google Scholar

[16]

L. Qi, Convergence analysis of some algorithms for solving nonsmooth equations,, Mathematics of Operations Research, 18 (1993), 227.  doi: 10.1287/moor.18.1.227.  Google Scholar

[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.   Google Scholar

[18]

J. Rohn, A theorem of the alternatives for the equation $Ax+B|x|=b$,, Linear and Multilinear Algebra, 52 (2004), 421.  doi: 10.1080/0308108042000220686.  Google Scholar

[19]

J. Rohn, Solvability of systems of interval linear equations and inequalities,, in, (2006), 35.  doi: 10.1007/0-387-32698-7_2.  Google Scholar

[20]

J. Rohn, An algorithm for solving the absolute value equation,, Eletronic Journal of Linear Algebra, 18 (2009), 589.   Google Scholar

[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.  doi: 10.1007/s10957-009-9557-9.  Google Scholar

[1]

Qiao Liu. Local rigidity of certain solvable group actions on tori. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 553-567. doi: 10.3934/dcds.2020269

[2]

Nguyen Huy Tuan. On an initial and final value problem for fractional nonclassical diffusion equations of Kirchhoff type. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020354

[3]

George W. Patrick. The geometry of convergence in numerical analysis. Journal of Computational Dynamics, 2021, 8 (1) : 33-58. doi: 10.3934/jcd.2021003

[4]

Matania Ben–Artzi, Joseph Falcovitz, Jiequan Li. The convergence of the GRP scheme. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 1-27. doi: 10.3934/dcds.2009.23.1

[5]

Xavier Carvajal, Liliana Esquivel, Raphael Santos. On local well-posedness and ill-posedness results for a coupled system of mkdv type equations. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020382

[6]

Ziang Long, Penghang Yin, Jack Xin. Global convergence and geometric characterization of slow to fast weight evolution in neural network training for classifying linearly non-separable data. Inverse Problems & Imaging, 2021, 15 (1) : 41-62. doi: 10.3934/ipi.2020077

[7]

Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465

[8]

Philipp Harms. Strong convergence rates for markovian representations of fractional processes. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020367

[9]

Alberto Bressan, Carlotta Donadello. On the convergence of viscous approximations after shock interactions. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 29-48. doi: 10.3934/dcds.2009.23.29

[10]

Mengni Li. Global regularity for a class of Monge-Ampère type equations with nonzero boundary conditions. Communications on Pure & Applied Analysis, 2021, 20 (1) : 301-317. doi: 10.3934/cpaa.2020267

[11]

Liam Burrows, Weihong Guo, Ke Chen, Francesco Torella. Reproducible kernel Hilbert space based global and local image segmentation. Inverse Problems & Imaging, 2021, 15 (1) : 1-25. doi: 10.3934/ipi.2020048

[12]

Claudio Bonanno, Marco Lenci. Pomeau-Manneville maps are global-local mixing. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1051-1069. doi: 10.3934/dcds.2020309

[13]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018

[14]

Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115

[15]

Toshiko Ogiwara, Danielle Hilhorst, Hiroshi Matano. Convergence and structure theorems for order-preserving dynamical systems with mass conservation. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3883-3907. doi: 10.3934/dcds.2020129

[16]

Xiuli Xu, Xueke Pu. Optimal convergence rates of the magnetohydrodynamic model for quantum plasmas with potential force. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 987-1010. doi: 10.3934/dcdsb.2020150

[17]

Takiko Sasaki. Convergence of a blow-up curve for a semilinear wave equation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1133-1143. doi: 10.3934/dcdss.2020388

[18]

Matúš Tibenský, Angela Handlovičová. Convergence analysis of the discrete duality finite volume scheme for the regularised Heston model. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1181-1195. doi: 10.3934/dcdss.2020226

[19]

Roland Schnaubelt, Martin Spitz. Local wellposedness of quasilinear Maxwell equations with absorbing boundary conditions. Evolution Equations & Control Theory, 2021, 10 (1) : 155-198. doi: 10.3934/eect.2020061

[20]

Norman Noguera, Ademir Pastor. Scattering of radial solutions for quadratic-type Schrödinger systems in dimension five. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021018

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (80)
  • HTML views (0)
  • Cited by (9)

Other articles
by authors

[Back to Top]