A smoothing-type algorithm for absolute value equations

Previous Article
Optimal capacity reservation policy on innovative product
JIMO Home
This Issue
Next Article
Pricing and replenishment strategy for a multi-market deteriorating product with time-varying and price-sensitive demand

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

Abstract
Related Papers

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 and 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.
[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.

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

[1]	Zheng-Hai Huang, Nan Lu. Global and global linear convergence of smoothing algorithm for the Cartesian $P_(\kappa)$-SCLCP. Journal of Industrial and 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 PNCP. Journal of Industrial and 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 and 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 and 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 and 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 and 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 and Continuous Dynamical Systems - B, 2020, 25 (8) : 2949-2967. doi: 10.3934/dcdsb.2020047
[8]	Dongmei Yu, Cairong Chen, Yinong Yang, Deren Han. An inertial inverse-free dynamical system for solving absolute value equations. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022055
[9]	Shuhua Wang, Zhenlong Chen, Baohuai Sheng. Convergence of online pairwise regression learning with quadratic loss. Communications on Pure and Applied Analysis, 2020, 19 (8) : 4023-4054. doi: 10.3934/cpaa.2020178
[10]	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 and Management Optimization, 2018, 14 (3) : 981-1005. doi: 10.3934/jimo.2017086
[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 and Continuous Dynamical Systems, 2015, 35 (9) : 4041-4070. doi: 10.3934/dcds.2015.35.4041
[12]	J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control and Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008
[13]	Qiyu Jin, Ion Grama, Quansheng Liu. Convergence theorems for the Non-Local Means filter. Inverse Problems and Imaging, 2018, 12 (4) : 853-881. doi: 10.3934/ipi.2018036
[14]	Aibin Zang. Kato's type theorems for the convergence of Euler-Voigt equations to Euler equations with Drichlet boundary conditions. Discrete and Continuous Dynamical Systems, 2019, 39 (9) : 4945-4953. doi: 10.3934/dcds.2019202
[15]	Stefan Kindermann, Antonio Leitão. Convergence rates for Kaczmarz-type regularization methods. Inverse Problems and Imaging, 2014, 8 (1) : 149-172. doi: 10.3934/ipi.2014.8.149
[16]	Stefano Scrobogna. Global existence and convergence of nondimensionalized incompressible Navier-Stokes equations in low Froude number regime. Discrete and Continuous Dynamical Systems, 2020, 40 (9) : 5471-5511. doi: 10.3934/dcds.2020235
[17]	Chun-Hsiung Hsia, Chang-Yeol Jung, Bongsuk Kwon. On the global convergence of frequency synchronization for Kuramoto and Winfree oscillators. Discrete and Continuous Dynamical Systems - B, 2019, 24 (7) : 3319-3334. doi: 10.3934/dcdsb.2018322
[18]	X. X. Huang, D. Li, Xiaoqi Yang. Convergence of optimal values of quadratic penalty problems for mathematical programs with complementarity constraints. Journal of Industrial and Management Optimization, 2006, 2 (3) : 287-296. doi: 10.3934/jimo.2006.2.287
[19]	Stefano Galatolo, Hugo Marsan. Quadratic response and speed of convergence of invariant measures in the zero-noise limit. Discrete and Continuous Dynamical Systems, 2021, 41 (11) : 5303-5327. doi: 10.3934/dcds.2021078
[20]	Lorenza D'Elia. $ \Gamma $-convergence of quadratic functionals with non uniformly elliptic conductivity matrices. Networks and Heterogeneous Media, 2022, 17 (1) : 15-45. doi: 10.3934/nhm.2021022

2021 Impact Factor: 1.411

Tools

Metrics

Other articles
by authors

on AIMS
Xiaoqin Jiang Ying Zhang
on Google Scholar
Xiaoqin Jiang Ying Zhang

[Back to Top]