American Institute of Mathematical Sciences

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

A smoothing-type algorithm for absolute value equations

Xiaoqin Jiang 1, and  Ying Zhang 2,

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.
Keywords: uniquely solvable, smoothing-type algorithm, global convergence, Absolute value equations, local quadratic convergence..
Mathematics Subject Classification: Primary: 90C05, 90C33; Secondary: 15A0.
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-58. 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, New York, 1992.  Google Scholar

[3]

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

[4]

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

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

[10]

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

[11]

O. L. Mangasarian, Absolute value equation solution via concave minmization, Optimization Letters, 1 (2007), 3-8. 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-108. 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-367. 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-372. 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-121. 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-244. 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-35.  Google Scholar

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

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

[20]

J. Rohn, An algorithm for solving the absolute value equation, Eletronic Journal of Linear Algebra, 18 (2009), 589-599.  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-403. 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-58. 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, New York, 1992.  Google Scholar

[3]

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

[4]

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

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

[10]

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

[11]

O. L. Mangasarian, Absolute value equation solution via concave minmization, Optimization Letters, 1 (2007), 3-8. 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-108. 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-367. 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-372. 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-121. 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-244. 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-35.  Google Scholar

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

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

[20]

J. Rohn, An algorithm for solving the absolute value equation, Eletronic Journal of Linear Algebra, 18 (2009), 589-599.  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-403. doi: 10.1007/s10957-009-9557-9.  Google Scholar

[1]

Zheng-Hai Huang, Nan Lu. Global and global linear convergence of smoothing algorithm for the Cartesian $P_*(\kappa)$-SCLCP. Journal of Industrial & Management Optimization, 2012, 8 (1) : 67-86. doi: 10.3934/jimo.2012.8.67
[2]

Zheng-Hai Huang, Shang-Wen Xu. Convergence properties of a non-interior-point smoothing algorithm for the P*NCP. Journal of Industrial & Management Optimization, 2007, 3 (3) : 569-584. doi: 10.3934/jimo.2007.3.569
[3]

Fakhrodin Hashemi, Saeed Ketabchi. Numerical comparisons of smoothing functions for optimal correction of an infeasible system of absolute value equations. Numerical Algebra, Control & Optimization, 2020, 10 (1) : 13-21. doi: 10.3934/naco.2019029
[4]

Chunlin Hao, Xinwei Liu. Global convergence of an SQP algorithm for nonlinear optimization with overdetermined constraints. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 19-29. doi: 10.3934/naco.2012.2.19
[5]

Liping Zhang, Soon-Yi Wu, Shu-Cherng Fang. Convergence and error bound of a D-gap function based Newton-type algorithm for equilibrium problems. Journal of Industrial & Management Optimization, 2010, 6 (2) : 333-346. doi: 10.3934/jimo.2010.6.333
[6]

Zhong Tan, Qiuju Xu, Huaqiao Wang. Global existence and convergence rates for the compressible magnetohydrodynamic equations without heat conductivity. Discrete & Continuous Dynamical Systems, 2015, 35 (10) : 5083-5105. doi: 10.3934/dcds.2015.35.5083
[7]

Ruiying Wei, Yin Li, Zheng-an Yao. Global existence and convergence rates of solutions for the compressible Euler equations with damping. Discrete & Continuous Dynamical Systems - B, 2020, 25 (8) : 2949-2967. doi: 10.3934/dcdsb.2020047
[8]

Shuhua Wang, Zhenlong Chen, Baohuai Sheng. Convergence of online pairwise regression learning with quadratic loss. Communications on Pure & Applied Analysis, 2020, 19 (8) : 4023-4054. doi: 10.3934/cpaa.2020178
[9]

Yi Zhang, Liwei Zhang, Jia Wu. On the convergence properties of a smoothing approach for mathematical programs with symmetric cone complementarity constraints. Journal of Industrial & Management Optimization, 2018, 14 (3) : 981-1005. doi: 10.3934/jimo.2017086
[10]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008
[11]

Olivier Bokanowski, Maurizio Falcone, Roberto Ferretti, Lars Grüne, Dante Kalise, Hasnaa Zidani. Value iteration convergence of $\epsilon$-monotone schemes for stationary Hamilton-Jacobi equations. Discrete & Continuous Dynamical Systems, 2015, 35 (9) : 4041-4070. doi: 10.3934/dcds.2015.35.4041
[12]

Qiyu Jin, Ion Grama, Quansheng Liu. Convergence theorems for the Non-Local Means filter. Inverse Problems & Imaging, 2018, 12 (4) : 853-881. doi: 10.3934/ipi.2018036
[13]

Aibin Zang. Kato's type theorems for the convergence of Euler-Voigt equations to Euler equations with Drichlet boundary conditions. Discrete & Continuous Dynamical Systems, 2019, 39 (9) : 4945-4953. doi: 10.3934/dcds.2019202
[14]

Stefan Kindermann, Antonio Leitão. Convergence rates for Kaczmarz-type regularization methods. Inverse Problems & Imaging, 2014, 8 (1) : 149-172. doi: 10.3934/ipi.2014.8.149
[15]

Stefano Scrobogna. Global existence and convergence of nondimensionalized incompressible Navier-Stokes equations in low Froude number regime. Discrete & Continuous Dynamical Systems, 2020, 40 (9) : 5471-5511. doi: 10.3934/dcds.2020235
[16]

Chun-Hsiung Hsia, Chang-Yeol Jung, Bongsuk Kwon. On the global convergence of frequency synchronization for Kuramoto and Winfree oscillators. Discrete & Continuous Dynamical Systems - B, 2019, 24 (7) : 3319-3334. doi: 10.3934/dcdsb.2018322
[17]

X. X. Huang, D. Li, Xiaoqi Yang. Convergence of optimal values of quadratic penalty problems for mathematical programs with complementarity constraints. Journal of Industrial & Management Optimization, 2006, 2 (3) : 287-296. doi: 10.3934/jimo.2006.2.287
[18]

Stefano Galatolo, Hugo Marsan. Quadratic response and speed of convergence of invariant measures in the zero-noise limit. Discrete & Continuous Dynamical Systems, 2021, 41 (11) : 5303-5327. doi: 10.3934/dcds.2021078
[19]

Lorenza D'Elia. $ \Gamma $-convergence of quadratic functionals with non uniformly elliptic conductivity matrices. Networks & Heterogeneous Media, 2021  doi: 10.3934/nhm.2021022
[20]

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

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (160)
  • HTML views (0)
  • Cited by (8)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy