A Class of Smoothing Modulus-Based Iterative Method for Solving Implicit Complementarity Problems

Cong Guo, Chenliang Li, Tao Luo

TL;DR

This paper introduces a new family of smoothing modulus-based iterative methods to solve Implicit Complementarity Problems (ICP). By transforming the non-differentiable ICP into a smooth, equivalent fixed-point equation, the authors developed a multi-step algorithm that achieves high-order convergence ($m+2$), significantly outperforming traditional matrix-splitting methods in both speed and precision.

What Problem Does This Paper Address?

Complementarity problems are a cornerstone of mathematical optimization, appearing in everything from elastic contact mechanics and fluid dynamics to economic equilibrium and convex quadratic programming.

The Implicit Complementarity Problem (ICP) is a complex generalization of the standard Linear Complementarity Problem (LCP). While an LCP looks for a vector that satisfies certain positivity and orthogonality constraints relative to a linear mapping, the ICP adds a mapping function $m(z)$ into the mix. This addition makes the problem "implicit" and significantly harder to solve using standard linear solvers because it introduces non-linearity and non-differentiability.

Methods

The authors tackle the ICP through a three-stage strategy:

  1. Fixed-Point Transformation: They first transform the ICP into an equivalent fixed-point equation involving absolute value terms ($|x|$). This is known as a modulus-based transformation.
  2. Smoothing: Because the absolute value function is non-differentiable at zero, standard Newton-type methods (which require derivatives) can't be used directly. The authors introduce a smoothing vector function to approximate the absolute value, controlled by a large positive integer $c$.
  3. Multi-Step Iteration: The core innovation is the Smoothing Modulus-Based $m+1$-step Iterative Method (Algorithm 4). Instead of a simple iteration, they use a sequence of $m$ internal steps to refine the solution.

By combining these, they move from a "jagged" non-differentiable problem to a "smooth" one that can be crushed using high-order iterative techniques.

Datasets

As a theoretical and computational mathematics paper, the authors did not use external "big data" sets. Instead, they evaluated their algorithms using four distinct numerical test cases (Examples 4.1–4.4) featuring different matrix structures:

  • Symmetric and Asymmetric Tridiagonal Block Matrices: These represent common structures found in discretized differential equations.
  • Varied Mapping Functions: They tested different $m(z)$ mappings, including square roots, arctangent functions, and cubic functions, to ensure the algorithm's robustness across different types of non-linearity.
  • Scaling: Problems were scaled from $n=400$ up to $n=42,025$ variables to test computational efficiency.

Key Insights and Ideas

  • The Power of $m+2$: The most significant theoretical finding is Theorem 3, which proves that their $m+1$-step algorithm achieves a convergence order of $m+2$. In practical terms, this means the error drops much faster per iteration than standard methods.
  • Smoothing vs. Splitting: Traditional methods often rely on "matrix splitting" (like the AMSOR method). The authors show that by treating the problem as a smooth nonlinear system instead, they can leverage the efficiency of Newton-like iterations.
  • Initial Value Sensitivity: The authors smartly use a basic modulus-based method (Algorithm 1) just to find a good starting point for their more powerful smoothing algorithms, ensuring the high-order method doesn't diverge early on.

Key Results

The numerical experiments compared the new methods (SMN, MSMN, and SM($m+1$)) against the Accelerated Modulus-based Matrix Splitting (AMSOR) method:

  • Efficiency: For a problem size of $n=6400$, the $m+1$-step method reached a solution in just 2 iterations, while AMSOR required 4.
  • Speed: In large-scale tests ($n=42,025$), the Modified Smoothing Newton method (MSMN) was nearly 3 times faster than the standard Smoothing Newton method (SMN).
  • Accuracy: The proposed methods consistently achieved much lower residual norms (errors as low as $10^{-16}$) compared to traditional methods, which often hovered around $10^{-7}$.

Limitations and Future Work

While the paper demonstrates strong numerical results, a few areas remain open for exploration:

  • Parameter Selection: The method relies on several parameters ($\alpha, \beta, \xi, c$). While the authors provide values that worked for their tests, a universal strategy for choosing optimal parameters for any given ICP isn't fully detailed.
  • Mapping Complexity: The test cases used relatively "well-behaved" mappings $m(z)$. It remains to be seen how the algorithm performs with highly oscillatory or discontinuous mappings.
  • Global Convergence: The convergence analysis is local (it works when you are "close enough" to the solution). Future work could focus on proving global convergence criteria for a wider class of matrices.

Summary updated

Abstract

In this paper, a class of smoothing modulus-based iterative method was presented for solving implicit complementarity problems. The main idea was to transform the implicit complementarity problem into an equivalent implicit fixed-point equation, then introduces a smoothing function to obtain its approximation solutions. The convergence analysis of the algorithm was given, and the efficiency of the algorithms was verified by numerical experiments.
BibTeX
@inproceedings{guo2022class,
  author = {Cong Guo and Chenliang Li and Tao Luo},
  title = {{A Class of Smoothing Modulus-Based Iterative Method for Solving Implicit Complementarity Problems}},
  booktitle = {American},
  year = {2022},
  doi = {10.4236/ajcm.2022.122011},
}
Figure