A smoothing-type algorithm for       absolute value equations

Xiaoqin Jiang; Ying Zhang

doi:10.3934/jimo.2013.9.789

Article Contents

2013, Volume 9, Issue 4: 789-798. Doi: 10.3934/jimo.2013.9.789

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

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
2.
Department of Mathematics, School of Science, Tianjin University, Tianjin 300072

Received: January 31, 2012

Revised: June 30, 2013

Published: September 2013

Abstract Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 90C05, 90C33; Secondary: 15A06.

Citation:

Related Papers

Cited by

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.