The study of new fixed-point iteration schemes for solving absolute value equations

Rashid Ali, Zhao Zhang, Fuad A. AwwadHeliyon 2024 · DOI

TL;DR

This paper introduces two novel fixed-point iteration schemes for solving Absolute Value Equations (AVEs), a class of problems with broad applications in various scientific and engineering fields. The authors demonstrate the theoretical convergence of these new methods and validate their effectiveness through numerical experiments, showing they outperform existing approaches in terms of speed and efficiency.

What Problem Does This Paper Address?

Absolute Value Equations (AVEs) are a significant class of nonlinear equations that appear in diverse areas such as bimatrix games, contact problems, and optimization. The general form of an AVE is $Ax - |x| = b$, where $A$ is a matrix and $|x|$ denotes the element-wise absolute value of the vector $x$. Solving these equations can be challenging due to their non-differentiable nature. While various numerical methods exist, there's a continuous need for more efficient and robust algorithms. This paper aims to address this by developing and analyzing new fixed-point iteration schemes specifically designed for AVEs, particularly when the coefficient matrix $A$ is an M-matrix or strictly diagonally dominant.

Methods

The core of this paper lies in the development of two new fixed-point iteration schemes. The authors achieve this by reformulating the AVE into a fixed-point equation. A key technique involves decomposing the matrix $A$ into its diagonal, strictly lower-triangular, and strictly upper-triangular components, along with a diagonal matrix $Q$.

  • Scheme I: This scheme is derived by splitting the matrix $A$ into $A = \Omega - N$, where $\Omega$ and $N$ are derived from the diagonal and triangular parts of $A$. This leads to an iterative formula of the form $s^{i+1} = (I_d - \mu D^{-1}N)^{-1}\{s^i - D^{-1}[\Omega s^i - |s^i| - b]\}$, where $D$ is the diagonal of $A$, $\mu$ is a positive constant, and $I_d$ is the identity matrix. The convergence of this scheme is analyzed using matrix norms and spectral radii.
  • Scheme II: This scheme is developed by further splitting the matrix $A$ and introducing an auxiliary matrix $\Gamma$. The iterative formula for Scheme II is $s^{i+1} = (I_d - \mu D^{-1}(N + \Gamma))^{-1}\{\mu\{s^i - D^{-1}[(\Omega + \Gamma)s^i - |s^i| - b]\} + (1-\mu)s^i\}$. Similar to Scheme I, its convergence is rigorously analyzed.

The theoretical convergence of both schemes is established by proving inequalities that bound the error between successive iterates and the true solution, under specific conditions related to the spectral radius of certain matrix products.

Datasets

Not discussed in the paper. The paper focuses on generating synthetic data for numerical experiments based on specific matrix structures and problem sizes.

Key Insights and Ideas

  • Matrix Decomposition for Fixed-Point Formulation: The novel approach of decomposing the coefficient matrix $A$ into its diagonal and triangular components, combined with a carefully chosen diagonal matrix $Q$, is central to deriving the new fixed-point iteration schemes. This decomposition allows for a structured transformation of the AVE into a form amenable to iterative solutions.
  • Convergence Guarantees: The paper provides rigorous theoretical proofs for the convergence of the proposed schemes. This is crucial for establishing their reliability and understanding the conditions under which they are guaranteed to find a solution. The use of spectral radius conditions ($p(|W^{-1}|P) < 1$ and $p(|J^{-1}|F) < 1$) is a standard yet powerful tool in analyzing the convergence of iterative methods.
  • Superior Performance in Numerical Tests: The most significant insight comes from the numerical results, which consistently show that the proposed schemes (Scheme I and Scheme II) outperform several existing methods (AOR, SOR, MSA, MM, SAOM, NM, MT, MSD) in terms of both the number of iterations (IT) and computational time (CPU). This suggests that the new schemes are not only theoretically sound but also practically efficient.

Key Results

The paper presents numerical results from three examples, demonstrating the effectiveness of the proposed schemes.

  • Convergence Criteria: Table 1 shows that the convergence requirements for both theorems are met for various problem sizes, indicating the theoretical validity of the schemes.
  • Efficiency Comparison (Example 3.1): For a problem with $n=4900$, Scheme II required only 43 iterations and a CPU time of 0.1429, significantly outperforming existing methods like AOR (97 iterations, 0.6729 CPU), SOR (91 iterations, 0.4217 CPU), and MSA (88 iterations, 0.3321 CPU). Scheme I also showed substantial improvements over these methods. Figure 1 visually confirms this superior performance.
  • Efficiency Comparison (Example 3.2): For a problem with $m=256$, Scheme I achieved the solution in 8 iterations with a CPU time of 0.2378, while Scheme II took 11 iterations with a CPU time of 0.2569. Both were notably faster than MM (21 iterations), SAOM (17 iterations), and NM (13 iterations). Figure 2 illustrates this advantage.
  • Efficiency Comparison (Example 3.3): For a large problem with $n=7000$, Scheme II required only 9 iterations and a CPU time of 2.8510, while Scheme I also achieved the solution in 11 iterations with a CPU time of 2.5418. These were significantly better than MT (27 iterations), SAOM (22 iterations), and MSD (15 iterations). Figure 3 further highlights the efficiency of the proposed schemes.

Limitations and Future Work

  • Limitations: The current study focuses on AVEs where the coefficient matrix $A$ is an M-matrix or a strictly diagonally dominant matrix. The authors acknowledge that the applicability of their schemes to broader classes of coefficient matrices has not been explored.
  • Future Work: The authors explicitly state their intention to focus future studies on AVEs with various broader classes of coefficient matrices. This suggests that extending the current methodology to more general cases is a primary direction for future research.

Summary updated

Abstract

Absolute value equations (AVEs) play a crucial role in solving various complexities across scientific computing, engineering, management science, and operations research. This article presents two fixed-point iteration schemes designed for such AVEs. Furthermore, we show some convergence conditions under specific circumstances. Lastly, the theoretical findings are validated using numerical examples, which emphasize the distinct advantages offered by the newly developed schemes. These results are highly promising and may stimulate future research in this domain.
BibTeX
@inproceedings{ali2024study,
  author = {Rashid Ali and Zhao Zhang and Fuad A. Awwad},
  title = {{The study of new fixed-point iteration schemes for solving absolute value equations}},
  booktitle = {Heliyon},
  year = {2024},
  doi = {10.1016/j.heliyon.2024.e34505},
}
Figure