A Robust Iterative Solver for LCPs with Singularity Detection and Performance Guarantees

Abstract

In this study, we present a novel algorithm for solving Linear Complementarity Problems (LCPs), a class of optimization problems encountered across numerous application domains. Our approach distinguishes itself by its ability to intelligently adapt to the challenges posed by singular and ill-conditioned matrices, which often hinder the performance of traditional LCP solvers.

At the core of our algorithm is a singularity detection mechanism, analyzing matrix properties to determine the most appropriate solution method. For well-conditioned matrices, we leverage the precision of direct methods, while for singular matrices, we employ robust techniques such as the pseudo-inverse or Singular Value Decomposition (SVD).

Furthermore, we introduce an optimized preconditioning strategy, accelerating the convergence of iterative methods, particularly for large-scale LCPs. This adaptive approach, combined with intelligent handling of cases with no solution, ensures increased robustness and efficiency.

Experimental results demonstrate the superiority of our algorithm compared to conventional LCP solvers, particularly for ill-conditioned or singular problems. This advancement opens new perspectives for solving complex LCP problems in diverse application domains, including engineering, finance, and machine learning.