Milan Hladík. Properties of the solution set of absolute value equations and the related matrix classes. SIAM J. Matrix Anal. Appl., 44(1):175–195, March 2023.
[PDF] [gzipped postscript] [postscript] [HTML]
The absolute value equations (AVE) problem is an algebraic problem of solving Ax+|x|=b. So far, most of the research focused on methods for solving AVE, but we address the problem itself by analysing properties of AVE and the corresponding solution set. In particular, we investigate topological properties of the solution set, such as convexity, boundedness, connectedness, or whether it consists of finitely many solutions. Further, we address problems related to nonnegativity of solutions such as solvability or unique solvability. AVE can be formulated by means of different optimization problems, and in this regard we are interested in how the solutions of AVE are related with optima, Karush-Kuhn-Tucker points and feasible solutions of these optimization problems. We characterize the matrix classes associated with the above mentioned properties and inspect the computational complexity of the recognition problem; some of the classes are polynomially recognizable, but some others are proved to be NP-hard. For the intractable cases, we propose various sufficient conditions. We also post new challenging problems that raised during the investigation of the problem.
Prop. 3.5: should be rho(AD_s)<1 instead of rho(A)<1. Thanks to Cairong Chen for pointing out the typo.
@article{Hla2023a,
author = "Milan Hlad\'{\i}k",
title = "Properties of the solution set of absolute value equations and the related matrix classes",
journal = "SIAM J. Matrix Anal. Appl.",
fjournal = "SIAM Journal on Matrix Analysis and Applications",
volume = "44",
number = "1",
month = "March",
pages = "175-195",
year = "2023",
doi = "10.1137/22M1497018",
issn = "0895-4798",
issnweb = "1095-7162",
url = "https://epubs.siam.org/doi/10.1137/22M1497018",
bib2html_dl_html = "https://doi.org/10.1137/22M1497018",
bib2html_errata = "Prop. 3.5: should be rho(AD_s)<1 instead of rho(A)<1. Thanks to Cairong Chen for pointing out the typo.",
bib2html_dl_pdf = "https://epubs.siam.org/doi/epdf/10.1137/22M1497018",
abstract = "The absolute value equations (AVE) problem is an algebraic problem of solving Ax+|x|=b. So far, most of the research focused on methods for solving AVE, but we address the problem itself by analysing properties of AVE and the corresponding solution set. In particular, we investigate topological properties of the solution set, such as convexity, boundedness, connectedness, or whether it consists of finitely many solutions. Further, we address problems related to nonnegativity of solutions such as solvability or unique solvability. AVE can be formulated by means of different optimization problems, and in this regard we are interested in how the solutions of AVE are related with optima, Karush-Kuhn-Tucker points and feasible solutions of these optimization problems. We characterize the matrix classes associated with the above mentioned properties and inspect the computational complexity of the recognition problem; some of the classes are polynomially recognizable, but some others are proved to be NP-hard. For the intractable cases, we propose various sufficient conditions. We also post new challenging problems that raised during the investigation of the problem.",
keywords = "Absolute value equations; Linear complementarity problem; Special matrices; Interval analysis; NP-hardness",
}
Generated by bib2html.pl (written by Patrick Riley ) on Mon Apr 15, 2024 08:26:42