Abstract
Presented is an algorithm which in a finite (but exponential) number of steps computes all solutions of an absolute value equation Ax + B|x| = b (A, B square), or fails. Failure has never been observed for randomly generated data. The algorithm can also be used for computation of all solutions of a linear complementarity problem.
Similar content being viewed by others
References
Fiedler M., Nedoma J., Ramík J., Rohn J., Zimmermann K.: Linear optimization problems with inexact data. Springer-Verlag, New York (2006)
Mangasarian O.: Absolute value equation solution via concave minimization. Optim. Lett. 1(1), 3–8 (2007). doi:10.1007/s11590-006-0005-6
Mangasarian O.: Absolute value programming. Comput. Optim. Appl. 36(1), 43–53 (2007)
Mangasarian O.L.: A generalized Newton method for absolute value equations. Optim. Lett. 3(1), 101–108 (2009). doi:10.1007/s11590-008-0094-5
Mangasarian O.L., Meyer R.R.: Absolute value equations. Linear Algebra Appl. 419(2–3), 359–367 (2006). doi:10.1016/j.laa.2006.05.004
Murty K.G.: Linear complementarity, linear and nonlinear programming. Heldermann, Berlin (1988)
Pardalos P.: Linear complementarity problems solvable by integer programming. Optimization 19(4), 467–474 (1988). doi:10.1080/02331938808843365
Pardalos, P.M.: The linear complementarity problem. In: Gomez, S. et al. (eds) Advances in optimization and numerical analysis. Proceedings of the 6th workshop on optimization and numerical analysis, Oaxaca, Mexico, January 1992. Dordrecht: Kluwer Academic Publishers. Math. Appl. Dordr. 275, 39–49 (1994)
Prokopyev O.: On equivalent reformulations for absolute value equations. Comput. Optim. Appl 44(3), 363–372 (2009). doi:10.1007/s10589-007-9158-1
Rohn J.: Systems of linear interval equations. Linear Algebra Appl. 126, 39–78 (1989). doi:10.1016/0024-3795(89)90004-9
Rohn, J.: An algorithm for solving the absolute value equation. Electron. J. Linear Algebra 18, 589–599 (2009). http://www.math.technion.ac.il/iic/ela/ela-articles/articles/vol18_pp589-599.pdf
Rohn, J.: An algorithm for solving the absolute value equation: An improvement. Technical Report 1063, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague (2010). http://uivtx.cs.cas.cz/~rohn/publist/absvaleqnreport.pdf
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Rohn, J. An algorithm for computing all solutions of an absolute value equation. Optim Lett 6, 851–856 (2012). https://doi.org/10.1007/s11590-011-0305-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-011-0305-3