Uniqueness of the Minimal l1-Norm Solution to the Monotone Linear Complementarity Problem

Abstract EN

The linear complementarity problem (LCP) has wide applications in economic equilibrium, operations research, and so on, which attracted a lot of interest of experts.

Finding the sparsest solution to the LCP has real applications in the field of portfolio selection and bimatrix game.

Motivated by the approach developed in compressive sensing, we may try to solve an l1-minimization problem to obtain the sparsest solution to the LCP, where an important theoretical problem is to investigate uniqueness of the solution to the concerned l1-minimization problem.

In this paper, we investigate the problem of finding the minimal l1-norm solution to the monotone LCP and propose a sufficient and necessary condition for the uniqueness of the minimal l1-norm solution to the monotone LCP, which provides an important theoretical basis for finding the sparsest solution to the monotone LCP via solving the corresponding l1-minimization problem.

Furthermore, several examples are given to confirm our theoretical finding.