Preconditioned conjugate gradient methods for absolute value equations
DOI:
https://doi.org/10.33993/jnaat491-1197Keywords:
Absolute value equations, linear systems, unconstrained quadratic optimization, linear complementarity problemsAbstract
We investigate the NP-hard absolute value equations (AVE), \(Ax-B|x| =b\), where \(A,B\) are given symmetric matrices in \(\mathbb{R}^{n\times n}, \ b\in \mathbb{R}^{n}\).
By reformulating the AVE as an equivalent unconstrained convex quadratic optimization, we prove that the unique solution of the AVE is the unique minimum of the corresponding quadratic optimization. Then across the latter, we adopt the preconditioned conjugate gradient methods to determining an approximate solution of the AVE.
The computational results show the efficiency of these approaches in dealing with the AVE.
Downloads
References
M. Achache and N. Hazzam. Solving absolute value equations via linear comple-mentarity and interior-point methods. Journal of Nonlinear Functional Analysis, 2018,pp. 1–10. https://doi.org/10.23952/jnfa.2018.39 DOI: https://doi.org/10.23952/jnfa.2018.39
M. A. Noor, J. Iqbal and E. Al-Said, Residual iterative method for solving absolutevalue equations. Article ID 406232. (2012), pp. 1–9. https://doi.org/10.1155/2012/406232 DOI: https://doi.org/10.1155/2012/406232
R. W. Cottle, J. S. Pang and R. E. Stone, The Linear Complementarity Problem. Academic Press. New-York (1992).
R. Fletcher, Practical Methods of Optimization. John Wiley and Sons. New-York(1987).
R. Fletcher and C.M. Reeves, Functions minimization by conjugate gradients. Computational journal.7, (1964), pp.149-154, https://doi.org/10.1093/comjnl/7.2.149 DOI: https://doi.org/10.1093/comjnl/7.2.149
M. Hladick, Bounds for the solution of absolute value equations. Computational Optimization and Applications. 69(1), (2018), pp. 243–266. https://doi.org/10.1007/s10589-017-9939-0 DOI: https://doi.org/10.1007/s10589-017-9939-0
J. Iqbal, M.A. Noor and K.I. Noor, On iterative method for solving absolute value equations. Optimization Letters. 6, (2012), pp. 1027–1033. https://doi.org/10.1007/s11590-011-0332-0 DOI: https://doi.org/10.1007/s11590-011-0332-0
S. Ketabchi and H. Moosaei, An efficient method for optimal correcting of absolute value equations by minimal changes in the right hand side. Computers and Mathematics with Applications.64, (2012), pp. 1882–1885. https://doi.org/10.1016/j.camwa.2012.03.015 DOI: https://doi.org/10.1016/j.camwa.2012.03.015
O.L. Mangasarian. A generalized Newton method for absolute value equations. Optimization Letters. 3, (2009), pp. 101–108. https://doi.org/10.1007/s11590-008-0094-5 DOI: https://doi.org/10.1007/s11590-008-0094-5
O.L. Mangasarian. A Newton method for linear programming. Journal of Optimization Theory and Applications. 121, (2004), pp. 1–18. https://doi.org/10.1023/b:jota.0000026128.34294.77 DOI: https://doi.org/10.1023/B:JOTA.0000026128.34294.77
O.L. Mangasarian. R.R. Meyer, Absolute value equations. Linear Algebra and Applications. 419, (2006), pp. 359–367. https://doi.org/10.1016/j.laa.2006.05.004 DOI: https://doi.org/10.1016/j.laa.2006.05.004
T. Migot, L. Abdellah and M. Haddou. Solving absolute value equation using complementarity and smoothing functions. Computational and Applied Mathematics. 327, (2018), pp. 196–207. https://doi.org/10.1016/j.cam.2017.06.019 DOI: https://doi.org/10.1016/j.cam.2017.06.019
L. Lehmann, M. Radons, M. Rump and CH. Strom, Sign controlled solvers for the absolute value equation with an application to support vector machines. (2010).
J. Rohn, On unique solvability of the absolute value equations. Optimization Letters 3, (2009), pp. 603–606. https://doi.org/10.1007/s11590-009-0129-6 DOI: https://doi.org/10.1007/s11590-009-0129-6
J. Rohn, An algorithm for computing al l solutions of an absolute value equation. Optimization Letters 6, (2012), pp. 851–856. https://doi.org/10.1007/s11590-011-0305-3 DOI: https://doi.org/10.1007/s11590-011-0305-3
Y. Shi, Modified Quasi-Newton Methods for Solving Systems of Linear Equations. Int. J. Contemp. Math. Shi. 2(15),(2007), pp. 737–744. https://doi.org/10.12988/ijcms.2007.07072 DOI: https://doi.org/10.12988/ijcms.2007.07072
G. Zoutendijk, Nonlinear Programming, Computational Methods, in Integer and Non-linear Programming, J. Abadie, edition, North- Holland, Amsterdam, (1970) pp. 37–86.
N. Ujevic. A new iterative method for solving linear systems. Appl. Math. Comput. 179, (2006), pp. 725–730. https://doi.org/10.1016/j.amc.2005.11.128 DOI: https://doi.org/10.1016/j.amc.2005.11.128
Published
How to Cite
Issue
Section
License
Copyright (c) 2020 Journal of Numerical Analysis and Approximation Theory
This work is licensed under a Creative Commons Attribution 4.0 International License.
Open Access. This article is distributed under the terms of the Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
