  A Discrete-Time Linear Complementarity System (DLCS) is a dynamical system in
discrete time whose state evolution is governed by linear dynamics in states
and algebraic variables that solve a Linear Complementarity Problem (LCP). The
DLCS is the hybrid dynamical system that is the discrete-time counterpart of
the well-known Linear Complementarity System (LCS). We derive sufficient
conditions for Lyapunov stability of a DLCS when using a quadratic Lyapunov
function that depends only on the state variables and a quadratic Lyapunov
function that depends both on the state and the algebraic variables. The
sufficient conditions require checking the feasibility of a copositive program
over nonconvex cones. Our results only assume that the LCP is solvable and do
not require the solutions to be unique. We devise a novel, exact cutting plane
algorithm for the verification of stability and the computation of the Lyapunov
functions. To the best of our knowledge, our algorithm is the first exact
approach for stability verification of DLCS. A number of numerical examples are
presented to illustrate the approach. Though our main object of study in this
paper is the DLCS, the proposed algorithm can be readily applied to the
stability verification of LCS. In this context, we show the equivalence between
the stability of a LCS and the DLCS, resulting from a time-stepping procedure
applied to the LCS for all sufficiently small time steps.
