M Kanat Camlibel

Jong-Shi Pang
email: pangj@rpi.edu

Jinglai Shen
email: shenj2@rpi.edu

LYAPUNOV STABILITY OF COMPLEMENTARITY AND EXTENDED SYSTEMS

Keywords: complementarity systems, Lyapunov stability, LaSalle's invariance principle, asymptotic and exponential stability

A linear complementarity system (LCS) is a piecewise linear dynamical system consisting of a linear time-invariant ordinary differential equation (ODE) parameterized by an algebraic variable that is required to be a solution to a finite-dimensional linear complementarity problem (LCP), whose constant vector is a linear function of the differential variable. Continuing the authors' recent investigation of the LCS from the combined point of view of system theory and mathematical programming, this paper addresses the important system-theoretic properties of exponential and asymptotic stability for an LCS with a C 1 state trajectory. The novelty of our approach lies in our employment of a quadratic Lyapunov function that involves the auxiliary algebraic variable of the LCS; when expressed in the state variable alone, the Lyapunov function is piecewise quadratic, and thus nonsmooth. The nonsmoothness feature invalidates standard stability analysis that is based on smooth Lyapunov functions. In addition to providing sufficient conditions for exponential stability, we establish a generalization of the well-known LaSalle invariance theorem for the asymptotic stability of a smooth dynamical system to the LCS, which is intrinsically a nonsmooth system. Sufficient matrix-theoretic copositivity conditions are introduced to facilitate the verification of the stability properties. Properly specialized, the latter conditions are satisfied by a passive-like LCS and certain hybrid linear systems having common quadratic Lyapunov functions. We provide numerical examples to illustrate the stability results. We also develop an extended local exponential stability theory for nonlinear complementarity systems and differential variational inequalities, based on a new converse theorem for ODEs with B-differentiable right-hand sides. The latter theorem asserts that the existence of a "B-differentiable Lyapunov function" is a necessary and sufficient condition for the exponential stability of an equilibrium of such a differential system.

1. Introduction. Fundamentally linked to a linear hybrid system, a linear complementarity system (LCS) is a piecewise linear dynamical system defined by a linear time-invariant ordinary differential equation (ODE) parameterized by solutions of a finite-dimensional linear complementarity problem (LCP) linearly coupled with the state of the differential equation. LCSs, and also nonlinear complementarity systems (NCSs), belong to the more general class of differential variational inequalities (DVIs) [START_REF] Pang | Differential variational inequalities[END_REF]. In the last few years there has been a rapidly growing interest in complementarity systems and DVIs from the mathematical programming community and the systems and control community, due to their applications in many areas such as robotics, nonsmooth mechanics, economics, and finance and traffic systems; see the recent review papers [START_REF] Brogliato | Some perspectives on analysis and control of complementarity systems[END_REF][START_REF] Schumacher | Complementarity systems in optimization[END_REF] and [START_REF] ¸amlibel | Complementarity Methods in the Analysis of Piecewise Linear Dynamical Systems[END_REF][START_REF] ¸amlibel | Switched networks and complementarity[END_REF][START_REF] ¸amlibel | Well-posedness of a class of linear network with ideal diodes[END_REF][START_REF] ¸amlibel | On linear passive complementarity systems[END_REF][START_REF] ¸amlibel | Stability and controllability of planar bimodal linear complementarity systems[END_REF][START_REF] ¸amlıbel | On the controllability of bimodal piecewise linear systems[END_REF][START_REF] Schumacher | On the Zeno behavior of linear complementarity systems[END_REF][START_REF] Heemels | Linear Complementarity Systems: A Study in Hybrid Dynamics[END_REF][START_REF] Heemels | Well-posedness of linear complementarity systems[END_REF][START_REF] Heemels | The rational linear complementarity systems[END_REF][START_REF] Heemels | Linear complementarity systems[END_REF][START_REF] Pang | Strongly regular differential variational systems[END_REF][START_REF] Shen | Linear complementarity systems: Zeno states[END_REF][START_REF] Van Der Schaft | Complementarity modeling of hybrid systems[END_REF][START_REF] Van Der Schaft | An Introduction to Hybrid Dynamical Systems[END_REF] for studies on specific issues pertaining to the LCS.

Stability is a classical issue in dynamical system theory. One of the most widely adopted stability concepts is Lyapunov stability, which plays important roles in system and control theory and in the analysis of engineering systems. In the classical Lyapunov stability theory, we assume that the ODE in consideration has a smooth (at least C 1 ) right-hand side and the origin is an equilibrium. Furthermore, we assume that there exists a continuously differentiable, positive definite, and coercive function of the system states, which is called a Lyapunov function. If the Lie derivative of such a function along the vector field of the system is nonpositive at all states (in a small neighborhood of the origin), then one can establish stability of the origin in the sense of Lyapunov. On the other hand, if the Lie derivative of such a Lyapunov function along the vector field of the system is negative at all nonzero states (in a small neighborhood of the origin), then the system is asymptotically stable at the origin. In the setting of linear systems, this leads to the well-known Lyapunov equation.

An important extension of the above results is LaSalle's invariance principle [START_REF] Khalil | Nonlinear Systems[END_REF], which plays a fundamental role in the stability analysis of smooth systems. This theorem says that if the largest invariant set of the zero level of the Lie derivative of the Lyapunov function along the system vector field is a singleton and contains the origin only, then the system is asymptotically stable at the origin. It is known that the singleton condition can be further expressed in terms of certain observability conditions. Thus checking the singleton condition is closely related to the observability analysis of the system. Extending classical smooth system theory to stability analysis of hybrid and switched systems has received growing attention in recent years. Among the extensive literature on the stability of linear switched systems, we mention a few relevant papers. A multiple-Lyapunov-function approach was proposed in [START_REF] Branicky | Multiple Lyapunov functions and other analysis tools for switched and hybrid systems[END_REF]; see also [START_REF] Ye | Stability theory of hybrid dynamical systems[END_REF] for related discussion. Uniform (asymptotic) stability of switched linear systems is studied in [START_REF] Hespanha | Uniform stability of switched linear systems: Extension of LaSalle's invariance principle[END_REF] where an extension of LaSalle's invariance principle to certain classes of switched linear systems is addressed. The latter result is further generalized to the stability analysis of switched nonlinear systems [START_REF] Hespanha | Nonlinear norm-observability notions and stability of switched systems[END_REF], where several nonlinear normobservability notions generalizing classical observability concepts are introduced to obtain sufficient conditions for asymptotic stability using arguments of the LaSalle type. For surveys of recent results, including extensive references, on stability and stabilization of switched linear systems, see [START_REF] Decarlo | Perspectives and results on the stability and stabilization of hybrid systems[END_REF][START_REF] Lin | Stability and stabilizability of switched linear systems: A short survey of recent results[END_REF]. Typically, the mentioned results assume that a Lyapunov-like function exists for each mode's vector field and holds for the entire state space. In many hybrid and switched systems, however, each mode holds only over a subset of the state space, especially for those systems whose switchings are triggered by state evolution, such as the LCS. Hence, the above results are rather restrictive, even for linear switched systems. Due to this concern, the paper [START_REF] Schumacher | Copositive Lyapunov functions,O p e nP r o b l e m s in Mathematical Systems and Control Theory[END_REF] had proposed copositive Lyapunov functions for "conewise linear systems" for which the feasible region of each mode is a polyhedral cone. This proposal leads to an interesting study of copositive matrices that satisfy the Lyapunov equation. Similar ideas and relevant results for piecewise linear systems can also be found in [START_REF] Johansson | Piecewise linear control systems[END_REF]. Also employing a copositivity theory, the authors of several recent papers [START_REF] Adly | A stability theory for second-order nonsmooth dynamical systems with application to friction problems[END_REF][START_REF] Goeleven | Stability and instability matrices for linear evolution variational inequalities[END_REF][START_REF] Goeleven | Necessary conditions of asymptotic stability for unilateral dynamical systems[END_REF][START_REF] Goeleven | On the stability of stationary solutions of evolution variational inequalities[END_REF] have developed an extensive stability theory for evolutionary variational inequalities (EVIs), including an extension of LaSalle's invariance principle to such systems, nec-essary conditions for asymptotic stability, application to mechanical systems under frictional contact, and matrix conditions for stability and instability for linear EVIs (LEVIs). The EVIs belong to the class of differential inclusions and are dynamic generalizations of a finite-dimensional variational inequality [START_REF] Facchinei | Finite-Dimensional Variational Inequalities and Complementarity Problems[END_REF]. In this paper, as an example of a DVI, we briefly discuss the "functional evolutionary variational inequality" (FEVI) as another dynamic generalization of a static finite-dimensional variational inequality (VI); see the system (5.8). In contrast to the EVI, the FEVI always has continuously differentiable solution trajectories, whose stability properties can be established without resorting to the framework of differential inclusions (DIs). Last, we mention [52, section 8.2], which studies the stability of "linear selectionable" DIs. While an LCS is related to such a DI, the two are quite different; consequently, the results from this reference are not applicable to the LCS. See the discussion at the end of subsection 3.3 for details.

It should be emphasized that while complementarity systems, and more generally, differential variational systems via their Karush-Kuhn-Tucker formulations, could be considered as special switched systems, LCSs, NCSs, and DVIs occupy a significant niche in many practical applications and have several distinguished features: inequality constraints on states, state-triggered mode switchings, and an endogenous control variable. These features invalidate much of the known theory of hybrid systems, which often allow arbitrary switchings, and necessitate the employment of the copositivity theory pioneered by such authors as Brogliato, Goeleven, and Schumacher. Another noteworthy point about the switched system theory is that it takes for granted a fundamental "non-Zenoness assumption" (i.e., finite number of switches in finite time) whose satisfaction is the starting point for stability analysis; for complementarity systems, this issue of finite switches is nontrivial and has been rigorously analyzed only very recently [START_REF] Pang | Strongly regular differential variational systems[END_REF][START_REF] Shen | Linear complementarity systems: Zeno states[END_REF]; see also [START_REF] ¸amlibel | Conewise Linear Systems: NonZenoness and Observability[END_REF].

Complementing the aforementioned works, this paper aims at analyzing the asymptotic and exponential stability of classes of nonsmooth differential systems, focusing in particular on the LCSs, NCSs, and DVIs. For an early work on the asymptotic behavior of solutions to the evolutionary nonlinear complementarity problem, see Chapter 3 in the Ph.D. thesis [START_REF] Hipfel | The Nonlinear Differential Complementarity Problem[END_REF]. A key assumption for the class of LCSs treated in our work is that they have C 1 state trajectories for all initial states. Since the right-hand side of such an LCS is a Lipschitz function of state, the results for the LEVIs are not applicable to this class of LCSs; see [START_REF] Goeleven | Stability and instability matrices for linear evolution variational inequalities[END_REF]Remark 10]. Nevertheless, there are LCSs that fall within the framework of the LEVI, and which are therefore amenable to the treatment in the cited reference (see, e.g., Corollary 2 therein) but which cannot be handled by our approach. In contrast to a set-valued approach, our analysis is based to a large extent on the theory of "B-differentiable" functions (see section 2 for a formal definition of such a nonsmooth function). Specifically, unlike many stability results in the literature where the candidate Lyapunov functions are chosen to be continuously differentiable in the state, the nontraditional Lyapunov-like function in our consideration is, in the case of the LCS, quadratic in both the state and the associated algebraic variable; thus it is piecewise quadratic when expressed in the system state only. The nonsmoothness of the resulting Lyapunov function is the novelty of our work, as a result of which mathematical tools that go beyond the scope of the classical Lyapunov stability theory are needed. In this regard, our analysis is in the spirit of [START_REF] Smirnov | Introduction to the Theory of Differential Inclusions[END_REF]Chapter 8]; yet the differential systems considered in our work are of a particular type, whose structure is fully exploited in designing the class of Lyapunov functions. Consequently, we are able to obtain much sharper results than those derived from the general theory of differential inclusions. In particular, combining LCP theory and stability methods, we obtain asymptotic stability results via an extension of LaSalle's invariance principle; moreover, our stability results for the LCS are expressed in terms of matrix copositivity conditions. Several special cases are highlighted and numerical examples are given. We further extend these results to inhomogeneous LCSs, NCSs, and DVIs, with the latter two classes of systems satisfying the strong regularity condition [START_REF] Robinson | Strongly regular generalized equations[END_REF][START_REF] Facchinei | Finite-Dimensional Variational Inequalities and Complementarity Problems[END_REF]. The noteworthy point of the latter extension is that it is based on a "converse theorem" of the exponential stability of an equilibrium of an ODE with a "B-differentiable" right-hand side. The latter theorem asserts that the existence of a "B-differentiable Lyapunov function" is a necessary and sufficient condition for the exponential stability of an equilibrium to such a differential system. Incidentally, there is an extensive literature on converse theorems for switched systems, some of which even involve discontinuous Lyapunov functions; see, e.g., [START_REF] Lin | A converse Lyapunov theorem for switched systems[END_REF][START_REF] Michel | Recent trends in stability of hybrid dynamical systems[END_REF][START_REF] Michel | Towards a stability theory of general hybrid dynamical systems[END_REF][START_REF] Pettersson | An LMI approach for stability analysis of nonlinear systems[END_REF]. Our main result, Theorem 5.2, differs from the common treatment in switched systems in a major way; namely, our theorem is established for a general ODE with a B-differentiable right-hand side and thus potentially has broader applicability than those restricted to switched systems.

The organization of the rest of the paper is as follows. In the next section, we formally define the LCS, review the notions of stability, asymptotic stability, and exponential stability, and briefly examine some matrix classes related to the LCP [START_REF] Cottle | The Linear Complementarity Problem[END_REF]. The stability results for the equilibrium x e = 0 of the LCS are presented in section 3, first for the "P-case" which is then extended to a non-P system. Numerical examples illustrating these results and the special case of a single-input-single-output (SISO) system are also given. Sections 4 and 5 address the stability issues of the extended systems; the former section treats the inhomogeneous LCS and the latter the NCS and the DVI, via the above-mentioned converse theorem for a B-differentiable ODE.

2. Linear complementarity systems. An LCS is defined by a tuple of four constant matrices A ∈ℜ n×n , B ∈ℜ n×m , C ∈ℜ m×n ,a n dD ∈ℜ m×m ; it seeks two time-dependent trajectories x(t) ∈ℜ n and u(t) ∈ℜ m for t ∈ [0,T]f o rs o m e 0 <T ≤∞such that

ẋ = Ax + Bu, 0 ≤ u ⊥ Cx + Du ≥ 0, x(0) = x 0 , (2.1)
where ẋ ≡ dx/dt denotes the time derivative of the trajectory x(t), x 0 is the initial condition, and a ⊥ b means that the two vectors a and b are orthogonal, i.e., a T b =0. We denote the above LCS by the tuple (A, B, C, D). Obviously, the LCP of finding a vector u ∈ℜ m satisfying 0 ≤ u ⊥ q + Du ≥ 0, w h i c hw ed e n o t eb yt h ep a i r( q, D) and whose solution set we denote SOL(q, D), has al o tt od ow i t hv a r i o u sp r o p e r t i e so ft h ea b o v eL C S .W er e f e rt h er e a d e rt o[ 1 3 ]f o r a comprehensive study of the LCP and also to the two-volume monograph [START_REF] Facchinei | Finite-Dimensional Variational Inequalities and Complementarity Problems[END_REF] for many advanced solution properties of the LCP that we will freely use throughout this paper. In particular, under the blanket assumption that BSOL(Cx,D)i sas i n g l e t o n for all x ∈ℜ n , an assumption which was introduced in [START_REF] Shen | Linear complementarity systems: Zeno states[END_REF] and used subsequently in [START_REF] Pang | Solution dependence on initial conditions in differential variational inequalities[END_REF], it follows that the LCS (2.1) is equivalent to the ODE

ẋ = Ax + BSOL(Cx,D),x (0) = x 0 , (2.2)
whose right-hand side Ax + BSOL(Cx,D) is a (single-valued) piecewise linear, and hence Lipschitz continuous and directionally differentiable (i.e., B(ouligand)-differentiable [START_REF] Pang | Newton's method for B-differentiable equations[END_REF]) function of x ∈ℜ n . (A word about notation: we identify the single vector in BSOL(Cx,D) with the set itself; thus we talk about the piecewise linear function x → BSOL(Cx,D) directly without referring to the element in BSOL(Cx,D). The same usage applies to other similar contexts.) The class of B-differentiable functions will play a central role throughout this work. Formally, a function Φ : D⊆ℜ n →ℜ m is B-differentiable at a point x in the open set D if Φ is Lipschitz continuous in a neighborhood of x contained in D and directionally differentiable at x;Φi sBdifferentiable in D if it is B-differentiable at every point therein. We refer the reader to [START_REF] Facchinei | Finite-Dimensional Variational Inequalities and Complementarity Problems[END_REF]Chapter 3] for basic properties of B-differentiable functions.

It follows from the ODE formulation (2.2) that the LCS (2.1) has a unique solution, which we denote x(t, x 0 ), for all initial conditions x 0 ∈ℜ n . If the initial condition x 0 is clear from the context, we will simply write x(t) to de-emphasize the dependence of the solution trajectory on the initial condition. Even in this case where the x-trajectory is unique, there is no guarantee that there is a unique u-trajectory, unless D is a P-matrix [START_REF] Cottle | The Linear Complementarity Problem[END_REF], which implies that SOL(q, D) is a singleton for all q ∈ℜ m , or unless the quadruple (A, B, C, D) satisfies the passifiability by pole shifting property and a rank condition [START_REF] ¸amlibel | On linear passive complementarity systems[END_REF]. See Proposition 2.2 for a unification of these uniqueness conditions. For our purpose, we are interested in the LCS (2.1) where the x-trajectory is unique and C 1 in time. It turns out that this condition is equivalent to the singlevaluedness of BSOL(Cx,D) as made precise in the following result.

Proposition 2.1. Let (A, B, C, D) be given. The following two statements are equivalent.

(a) For every x 0 ∈ℜ n ,t h eL C S(2.1) has a unique C 1 trajectory x(t, x 0 ) defined for all t ≥ 0. (b) For every x 0 ∈ℜ n ,t h es e tBSOL(Cx 0 ,D) is a singleton. Proof. It remains to show (a) ⇒ (b). This is clear because for any u 0 ∈ SOL(Cx 0 ,D), we have Bu 0 =ẋ(0,x 0 ) -Ax 0 ,w h e r e ẋ(0,x 0 ) is the time derivative of the unique trajectory x(t, x 0 ) evaluated at the initial time t =0.

Throughout the discussion of the LCS (2.1), we assume that condition (b) holds. There are simple instances where this condition holds easily. Statement (a) of the following result identifies one such instance; see [START_REF] Shen | Linear complementarity systems: Zeno states[END_REF]. The notation a • b denotes the Hadamard product of two vectors; i.e., the ith component of a • b is equal to a i b i .

Proposition 2.2. Suppose that SOL(Cx,D) = ∅ for all x ∈ℜ n . The following two statements hold.

(a ,D) is a singleton for all x ∈ℜ n if and only if for every x 0 ∈ℜ n , there exists a unique pair of trajectories (x(t, x 0 ),u(t, x 0 )) defined for all t ≥ 0 satisfying (2.1) such that x(•,x 0 ) is C 1 . Proof. For statement (a), it suffices to show that Bu 1 = Bu 2 for any two solutions u 1 and u 2 in SOL(Cx,D). This is easy because any two such solutions must satisfy u • Du ≤ 0f o ru ≡ u 1u 2 . For statement (b), it suffices to show the "only if" assertion; in turn it suffices to show the uniqueness of the u(t, x 0 ) trajectory. But this is also clear in view of the uniqueness of the C 1 trajectory x(t, x 0 ), which follows from Proposition 2.1.

) If u • Du ≤ 0 ⇒ Bu =0,t h e nBSOL(Cx,D) is a singleton for all x ∈ℜ n . (b) If [u • Du ≤ 0,B u=0 ]⇒ u =0 ,t h e nBSOL(Cx
Remark 2.1.

If D is positive semidefinite, then u•Du ≤ 0 implies (D +D T )u =0. Thus, if the matrix [ D + D T B ] has full column rank, then the implication [u • Du ≤ 0,
Bu =0 ]⇒ u = 0 holds. The former rank condition is used in [START_REF] ¸amlibel | On linear passive complementarity systems[END_REF] along with the passifiability condition, which implies the positive semidefiniteness of D, to yield the uniqueness of the u-trajectory.

There are many matrix classes in LCP theory; among these, the following are most relevant to this work. A matrix D ∈ℜ m×m is a P-matrix if u • Du ≤ 0 ⇒ u =0; the matrix D is an R 0 -matrix if SOL(0,D)={0};them a trixD is (strictly) copositive on a cone C⊆ℜ m if u T Du ≥ 0 for all u ∈C(u T Du > 0 for all nonzero u ∈C ); a copositive matrix D is copositive plus on

C if [u T Du =0 ,u ∈C] ⇒ (D + D T )u =0 .
Properties of these matrices will be used freely in the paper; see [START_REF] Cottle | The Linear Complementarity Problem[END_REF]. In particular, it is known that a matrix D is P if and only if SOL(q, D) is a singleton for all q ∈ℜ m ; moreover a constant c D > 0 exists such that u ≤c D q for all q ∈ℜ m ,w h e r eu is the unique solution of the LCP (q, D). It is further known that D is an R 0 -matrix if andonlyifSOL(q, D) is bounded (possibly empty) for all q ∈ℜ m . Clearly a P-matrix must be R

0 . Last, note that if D is copositive on a convex cone C,t h e n [ u T Du =0,u∈C] ⇒ (D + D T )u ∈C * , where C * denotes the dual cone of C. Consequently, if D is a symmetric matrix copositive on a convex cone C,t h e n [ u T Du =0,u∈C] ⇒ [ C∋u ⊥ Du ∈C * ]. (2.3)
We say that (D, C)i sa nR 0 -pair if the unique vector satisfying the right-hand complementarity conditions in the above implication is u =0.

The condition that BSOL(Cx,D) is a singleton is not as restrictive as it seems. Indeed, consider a homogeneous differential affine variational inequality (DAVI) ẋ = Ax + Bu, u ∈ SOL(K, Cx, D), (2.4) where u ∈ SOL(K, Cx, D)m e a n st h a tu ∈ K and

(u ′ -u) T (Cx + Du) ≥ 0 ∀ u ′ ∈ K,
with K being the polyhedral cone {u ∈ℜ m : Eu ≤ 0} for some matrix E of appropriate dimension. Introducing a multiplier λ for the constraint in K, we deduce that u ∈ SOL(K, Cx, D) if and only if

0=Cx + Du + E T λ, 0 ≤-Eu ⊥ λ ≥ 0.
If D is positive definite, we can solve for u from the first equation, obtaining u = -D -1 [Cx + E T λ], which we can substitute into Eu and Bu. T h i sr e s u l t si nt h eL C S

ẋ =[A -BD -1 C ]x -BD -1 E T λ, 0 ≤ λ ⊥-ED -1 Cx + ED -1 E T λ ≥ 0.
It is easy to see that the triple of matrices (B ′ ,C ′ ,D ′ ) ≡ (-BD -1 E T , -ED -1 C, ED -1 E T ) satisfies the property that B ′ SOL(C ′ x, D ′ ) is a singleton for all x, due to the positive definiteness of D. More generally, if D is only positive semidefinite (but not necessarily symmetric), it is still possible to convert (2.4) into an LCS (2.1) satisfying the desired singleton property, under suitable conditions; we refer the reader to [15,

= Ax + Bw, 0 ≤ w ⊥ Cx + Dw ≥ 0,
where

A ≡ A -B 0 DE T -E 0 -1 C 0 , B ≡ B 0 DE T -E 0 -1 0 I , C ≡-0 I DE T -E 0 -1 C 0 , D ≡ 0 I DE T -E 0 -1 0 I .
It is not difficult to show that if SOL(K, Cx, D) = ∅ for all x ∈ℜ n andif(D +D T )u = 0 ⇒ Bu = 0, then the triple ( B, C, D) is such that BSOL( Cx, D)i sas i n g l e t o nf o r all x ∈ℜ n .

2.1. Stability concepts. An important goal of this paper is to derive sufficient conditions for the "equilibrium solution" x = 0 of the LCS (2.1) to be "exponentially stable" and "asymptotically stable." While these are well-known concepts in systems theory [START_REF] Khalil | Nonlinear Systems[END_REF], we offer their formal definitions below for completeness. The setting is a time-invariant system on ℜ n , ẋ = f (x),x (0) = x 0 , (2.5) where f : ℜ n →ℜ n is Lipschitz continuous. Let x e ∈ℜ n be an equilibrium of the system (2.5), i.e., f (x e ) = 0, and let x(t, x 0 ) denote the unique trajectory of (2.5).

Definition 2.3. The equilibrium x e of (2.5) is (a) stable in the sense of Lyapunov if, for each ε>0,t h e r ei sδ ε > 0 such that

x 0 -x e <δ ε ⇒ x(t, x 0 ) -x e <ε ∀ t ≥ 0;
unstable otherwise; (b) asymptotically stable if it is stable and δ>0 exists such that x 0x e <δ⇒ lim t→∞ x(t, x 0 )=x e ;

(c) exponentially stable if there exist scalars δ>0, c>0,a n dμ>0 such that x 0x e <δ⇒ x(t, x 0 )x e ≤c x 0x e e -μt ∀ t ≥ 0.

Clearly, exponential stability implies asymptotic stability, which further implies stability, but not vice versa. For a Lipschitz function f (x) that is positively homogeneous in x, i.e., f (τx)=τf(x) for all τ ≥ 0, we will be interested in the particular equilibrium x e = 0. For the system (2.5) with such an f ,w eha v ex(t, τ x 0 )=τx(t, x 0 ) for all τ ≥ 0 and all pairs (t, x 0 ) ∈ [0, ∞) ×ℜ n . For such a function f , stability of x e = 0 is equivalent to linearly bounded stability, which means the existence of a constant η>0 such that x(t, x 0 ) ≤η x 0 for all (t, x 0 ) ∈ [0, ∞) ×ℜ n ; asymptotic stability is equivalent to global asymptotic stability, which means lim t→∞ x(t, x 0 )=0 for all x 0 ∈ℜ n ; and exponential stability is equivalent to global exponential stability, which means the existence of scalars c>0andμ>0 such that x(t, x 0 ) ≤c x 0 e -μt for all (t, x 0 ) ∈ [0, ∞)×ℜ n . Throughout the paper, we will omit the adjective "global" when we deal with the equilibrium x e = 0 for an ODE with a positively homogenous right-hand side.

Returning to the LCS (2.1), we note that, under our blanket assumption, the above definition is applicable to the equivalent system (2.2). Furthermore, since BSOL(0,D)={0}, x e = 0 is indeed an equilibrium of (2.2). Due to its piecewise linearity, the right-hand function f (x) ≡ Ax + BSOL(Cx,D) is in general not Fréchet differentiable (but is indeed positively homogeneous). Although f (x) is (globally) Lipschitz continuous, the nonsmoothness of f (x) invalidates much of the standard analysis of well-known stability results for smooth dynamical systems; see, e.g., the book [START_REF] Khalil | Nonlinear Systems[END_REF]. Our goal is to undertake a generalized stability analysis of the system (2.2), taking advantage of the special piecewise linear structure of the function f (x). The resulting theory is a significant advance from the classical linear systems theory and involves matrix-theoretic properties that are based on LCP theory.

Before proceeding to derive sufficient conditions for the asymptotic stability of the equilibrium x = 0, we state and prove a necessary condition for the said stability.

Proposition 2.4. Suppose that BSOL(Cx,D) is a singleton for all x ∈ℜ n .A necessary condition for x e =0to be an asymptotically stable equilibrium for the LCS (2.1) is that for all scalars λ ≥ 0, the following implication holds:

λx = Ax + Bu 0 ≤ u ⊥ Cx + Du ≥ 0 ⇒ x =0. (2.6)
If D is an R 0 -matrix, then (2.6) holds if and only if

λx = Ax + Bu 0 ≤ u ⊥ Cx + Du ≥ 0 ⇒ ( x, u )=0. (2.7)
Proof. Indeed, if (x * ,u * ) is a solution of the system at the left-hand side of (2.6) for some λ * ≥ 0, then defining the trajectory (x(t, x * ),u(t, x * )) = (e λ * t x * ,e λ * t u * )f o r all t ≥ 0, we deduce that, lim t→∞ x(t, x * )=0 only if x * = 0. This establishes the implication (2.6). Clearly (2.7) implies (2.6). The converse is also clear, provided that D is an R 0 -matrix.

Remark 2.2. By the implication (2.6), which holds for all λ ≥ 0, and by the homotopy invariance of the degree of a continuous mapping [START_REF] Lloyd | Degree Theory[END_REF], it follows that the index of the map x →-Ax-BSOL(Cx,D) at the origin is well defined and equal to 1. (The index of a continuous map at an isolated zero is a well-known topological concept; see the reference.) The latter degree-theoretic necessary condition for asymptotic stability is a special case of a more general result due to Mawhin [START_REF] Mawhin | Continuation theorems and periodic solutions of ordinary differential equations,i n Topological Methods in Differential Equations and Inclusions[END_REF]. The implication (2.7) defines the "mixed R 0 "-property of the matrix

A -λI B CD .
If A -λI is nonsingular, then this property is equivalent to the R 0 -property of the Schur complement D -C(A -λI) -1 B. In this regard, the left-hand system of (2.6) is an instance of a homogeneous "mixed LCP," where there is a mixture of linear equations and standard linear complementarity conditions.

3. Stability results for x e =0 .As in the classical analysis, our approach to the stability analysis of the system (2.1) is based on the existence of a Lyapunov function of a special kind. The novelty of our approach lies in the choice of the Lyapunov function: it is a quadratic function in the pair (x, u), which when expressed in the state variable x alone, is piecewise quadratic, and thus not smooth. At this point, we refer to the habilitation thesis of Scholtes [START_REF] Scholtes | Introduction to piecewise differentiable equations[END_REF] for the precise definition and an extensive study of piecewise differentiable functions; see also [START_REF] Facchinei | Finite-Dimensional Variational Inequalities and Complementarity Problems[END_REF]Chapter 4]. Results from these references will be used freely in our discussion.

We first consider the case where D is a P-matrix. It follows that SOL(Cx,D)i s a singleton for all x ∈ℜ n , whose unique element we denote u(x). A constant c ′ D > 0 exists such that

u(x) ≤c ′ D x ∀ x ∈ℜ m . (3.1)
Define three fundamental index sets:

α(x) ≡{i : u i (x) > 0=(Cx + Du(x)) i }, β(x) ≡{i : u i (x)=0=(Cx + Du(x)) i }, γ(x) ≡{i : u i (x)=0< ( Cx + Du(x)) i }.
In terms of these index sets, we have

u α (x)=-( D αα ) -1 C α• x, u ᾱ(x)=0 ,
where α = α(x)and ᾱ = β(x) ∪ γ(x). Let Gr SOL CD denote the graph of the solution function u(x); i.e., Gr SOL CD , which is a closed (albeit not necessarily convex) cone, consists of all pairs (x, u(x)) for all x ∈ℜ n . This graph can be described as follows.

For each subset α of {1,... ,m} with complement ᾱ, define

C α ≡ x ∈ℜ n : -( D αα ) -1 C α• C ᾱ• -D ᾱα ( D αα ) -1 C α•
x ≥ 0 and the matrix

E α ≡ ⎡ ⎢ ⎣ I -( D αα ) -1 C α• 0 ⎤ ⎥ ⎦ ∈ℜ (n+m)×n .
We then have

ℜ n = α C α and Gr SOL CD = α { E α x : x ∈C α } . (3.2)
The solution function u(x) is piecewise linear in x and thus has directional derivatives given as follows: with

u ′ (x; d) ≡ lim τ ↓0 u(x + τd) -u(x) τ (3.3)
denoting the directional derivative of u at x along the direction d, u ′ (x; d)i st h e unique vector v such that

free v i (Cd + Dv) i =0,i ∈ α(x), 0 ≤ v i ⊥ (Cd + Dv) i ≥ 0,i ∈ β(x), 0=v i ,i ∈ γ(x).
Thus there exists a subset β d ⊆ β(x) such that the directional derivative u ′ (x; d)i s given by

u ′ α d (x; d)=-(D α d α d ) -1 C α d • d, u ′ ᾱd (x; d)=0,
where α d = α(x) ∪ β d and ᾱd = {1,... ,m}\α d . N o t et h a tw ea l s oh a v e

u α d (x)=-(D α d α d ) -1 C α d • x, u ᾱd (x)=0.
Since there are only finitely many subsets α d ,ac o n s t a n t c ′ > 0 exists such that

u ′ (x; d) ≤ c ′ d ∀ ( x, d ) ∈ℜ 2n . (3.4)
Based on the LCP functions, we define the LCS map SOL ′ LCS :

x ∈ℜ n →ℜ 2m by SOL ′ LCS (x) ≡ u(x) u ′ (x; dx)
, where dx ≡ Ax + Bu(x), and let Gr SOL ′ LCS denote its graph. Unlike Gr SOL CD , which has a fairly simple representation in terms of the index subsets of {1,... ,m} (cf. (3.2)), Gr SOL ′ LCS is somewhat more complicated to describe using index sets; for one thing, the latter graph is not closed because the function u ′ (x; d) is in general not continuous in x. We denote the closure of Gr SOL ′ LCS by cl Gr SOL ′ LCS . Like Gr SOL CD ,G rS O L ′ LCS is a cone, albeit not necessarily convex.

In terms of u(x), the LCS (2.1) becomes the ODE ẋ = Ax+Bu(x) with a piecewise linear right-hand side which vanishes at the origin. In order to analyze the stability properties of the latter equilibrium x e = 0, we postulate the existence of a symmetric matrix

M ≡ PQ Q T R ∈ℜ (n+m)×(n+m)
that is strictly copositive on the cone Gr SOL CD ; i.e., y T My > 0 for all nonzero y ∈ Gr SOL CD . Since the latter is a closed cone, the strict copositivity condition is equivalent to the existence of a scalar c M > 0 such that

y T My ≥ c M y T y ∀ y ∈ Gr SOL CD . (3.5)
In fact, one such choice is c M ≡ min{y T My : y ∈ Gr SOL CD , y =1}, which is well defined and positive. Let

V (x, u) ≡ x u T PQ Q T R x u
be the quadratic form associated with the matrix M . The composite function

V (x) ≡ V (x, u(x)) = x T Px+2x T Qu(x)+u(x) T Ru(x)
is locally Lipschitz continuous and directional differentiable with

V ′ (x; v)=2x T Pv +2v T Qu(x)+2x T Qu ′ (x; v)+2u(x) T Ru ′ (x; v).
Associated with the trajectories (x(t, x 0 ),u(t, x 0 )) of the LCS (2.1), where u(t, x 0 ) ≡ u(x(t, x 0 )), define

ϕ x 0 (t) ≡ V (x(t, x 0 )) ∀ t ≥ 0.
By the chain rule of directional differentiation, the one-sided derivative of ϕ x 0 (t)i s given by

ϕ ′ x 0 (t+) = lim τ ↓0 ϕ x 0 (t + τ ) -ϕ x 0 (t) τ = V ′ (x(t, x 0 ); ẋ(t, x 0 )) =2x(t, x 0 ) T P ẋ(t, x 0 )+2ẋ(t, x 0 ) T Qu(t, x 0 )+2x T Qu ′ (x(t, x 0 ); ẋ(t, x 0 )) +2u(t, x 0 ) T Ru ′ (x(t, x 0 ); ẋ(t, x 0 )). Letting v(t, x 0 ) ≡ u ′ (x(t, x 0 ); ẋ(t, x 0 )) and substituting ẋ(t, x 0 )=Ax(t, x 0 )+Bu(t, x 0 ), we deduce ϕ ′ x 0 (t+) = v(t, x 0 ) T N (t, x 0 ), where N ≡ ⎡ ⎢ ⎣ A T P + PA PB + A T QQ B T P + Q T AQ T B + B T QR Q T R 0 ⎤ ⎥ ⎦ and z(t, x 0 ) ≡ ⎛ ⎜ ⎝ x(t, x 0 ) u(t, x 0 ) v(t, x 0 ) ⎞ ⎟ ⎠ ∈ Gr SOL ′ LCS . (3.6)
Note that, by (3.4),

v(t, x 0 ) ≤ c ′ ẋ(t, x 0 ) ≤c v ( x(t, x 0 ),u(t, x 0 )) (3.7) ∀ ( t, x 0 ) ∈ [0, ∞ ) ×ℜ n ,
for some constant c v > 0. Employing the notation introduced thus far, the following result provides sufficient conditions for the various kinds of stability to hold for the equilibrium x e = 0 of the LCS (2.1) with a P-matrix D. Theorem 3.1. Let D be a P-matrix. Suppose that matrices P , Q,a n dR,w i t h P and R symmetric, exist such that M is strictly copositive on Gr SOL CD .T h e following four statements hold for the equilibrium x e =0of (2.1).

(a) If -N is copositive on Gr SOL ′ LCS ,t h e nx e is linearly bounded stable.

(b) If -N is strictly copositive on cl Gr SOL ′ LCS ,t h e nx e is exponentially stable. (c) If -N is copositive on Gr SOL ′ LCS and [ z(t, ξ) T Nz(t, ξ)=0 ∀ t ≥ 0] ⇒ ξ =0, (3.8) then x e is asymptotically stable. (d) If -N is copositive-plus on Gr SOL ′ LCS and [ Nz(t, ξ)=0 ∀ t ≥ 0] ⇒ ξ =0, (3.9)
then x e is asymptotically stable.

Proof.L e tx 0 ∈ℜ n be arbitrary and let u 0 ≡ u(x 0 ). Since ϕ x 0 (t) ≡ V (x(t, x 0 )) is locally Lipschitz continuous for t ≥ 0, it is almost everywhere differentiable on [0, ∞), by Radamacher's theorem [START_REF] Rockafellar | Variational Analysis[END_REF]. Hence for almost all t ≥ 0, ϕ ′

x 0 (t) exists and is equal to ϕ ′

x 0 (t+), which is nonpositive, by the copositivity of -N on Gr SOL ′ LCS .O nt h e one hand, we have, for some constant ρ M > 0 independent of x 0 ,

ϕ x 0 (t)=ϕ x 0 (0) + t 0 ϕ ′ x 0 (s+) ds ≤ ϕ x 0 (0) = V (x 0 ,u 0 ) ≤ ρ M (x 0 ,u 0 ) 2 .
Hence by (3.1), we deduce that, for some constant ρ ′ M > 0 independent of x 0 ,

ϕ x 0 (t) ≤ ρ ′ M x 0 2 ∀ t ≥ 0. (3.10)
On the other hand, by (3.5),

ϕ x 0 (t)=V (x(t, x 0 ),u(t, x 0 )) ≥ c M ( x(t, x 0 ),u(t, x 0 )) 2 ≥ c M x(t, x 0 ) 2 .
Combining the two inequalities, we obtain x(t, x 0 ) ≤ ρ ′ M /c M x 0 , establishing the desired linearly bounded stability of x e =0.

The strictly copositivity of -N on cl Gr SOL ′ LCS implies the existence of a scalar

c N > 0 such that z T Nz ≤-c N z T z for all z ∈ GrSOL ′ LCS .
Hence, for all x 0 ∈ℜ n and for all t ≥ 0,

ϕ ′ x 0 (t+) ≤-c N (x(t, x 0 ),u(t, x 0 ),v(t, x 0 )) 2 . By (3.7), we deduce the existence of a constant c ′ M > 0 such that ϕ x 0 (t) ≥ c ′ M (x(t, x 0 ),u(t, x 0 ),v(t, x 0 )) 2 .
Therefore, we obtain, for some constant c>0,

z(t, x 0 ) 2 ≤ c ϕ x 0 (0) - t 0 z(s, x 0 ) 2 ds ∀ ( t, x 0 ) ∈ [0, ∞ ) ×ℜ n ,
where z(t, x 0 ) ≡ (x(t, x 0 ),u(t, x 0 ),v(t, x 0 )). By Gronwall's inequality, we therefore deduce

x(t, x 0 ) 2 ≤ z(t, x 0 ) 2 ≤ cϕ x 0 (0) e -ct ≤ cρ ′ M x 0 2 e -ct ,
where the last inequality is by (3.10). Consequently, x(t, x 0 ) ≤ cρ ′ M x 0 e -ct/2 . This establishes part (b) of the theorem. We will postpone the proof of part (c) because it requires an auxiliary result that is of independent interest; see Proposition 3.2 below. Since N is symmetric, it follows that if -N is copositive-plus on Gr SOL ′ LCS , then (3.8) and (3.9) are equivalent implications. Hence (d) follows from (c).

Part (c) of Theorem 3.1 is a generalized LaSalle's theorem for the LCS (2.1). The assumed implication (3.8) resembles a "generalized long-time observability condition" on the zero state of the LCS. Subsequently, we will discuss more about this condition; see subsection 3.1. For now, we note that if -N is copositive on Gr SOL ′ LCS and if (-N, C), where C is the closure of the convex hull of Gr SOL ′ LCS ,i sa nR 0 -pair, then (3.8) holds. Indeed, in this case, by (2.3), it follows that z(t, ξ) T Nz(t, ξ) = 0 implies z(t, ξ) = 0. In particular ξ = x(0,ξ) = 0; hence (3.8) holds.

To prove part (c) of Theorem 3.1, we define for each fixed x 0 ∈ℜ n the positive limit set

Ω(x 0 ) ≡ x ∞ ∈ℜ n : ∃{t k }↑∞such that x ∞ = lim k→∞ x(t k ,x 0 ) .
If M is strictly copositive on Gr SOL CD and -N is copositive on cl Gr SOL ′ LCS ,then Ω(x 0 ) is nonempty, by part (a) of Theorem 3.1. Additional properties of this set are summarized below.

Proposition 3.2. Let D be a P-matrix. If M is strictly copositive on cl Gr SOL LCS and -N is copositive on cl Gr SOL ′ LCS , then for every x 0 ∈ℜ n , the following three statements hold:

(a) for every

x ∞ ∈ Ω(x 0 ), the trajectory {x(t, x ∞ )} t≥0 ⊂ Ω(x 0 ); (b) a constant σ x 0 exists such that V (x ∞ , SOL(Cx ∞ ,D)) = σ x 0 for all x ∞ ∈ Ω(x 0 ); (c) ϕ ′ x ∞ (t)=0for all x ∞ ∈ Ω(x 0 ). Proof. Suppose x ∞ = lim k→∞ x(t k ,x 0 )
for some sequence {t k }↑∞ . For any t ≥ 0, we have x(t + t k ,x 0 )=x(t, x(t k ,x 0 )); hence taking limits as k ↑∞and using the continuity of x(t, •) in the second argument, we deduce

lim k→∞ x(t + t k ,x 0 )=x(t, x ∞ ),
which establishes part (a). To prove part (b), note that since ϕ ′

x 0 (t+) ≤ 0 for all t ≥ 0, it follows that ϕ x 0 (t) is nonincreasing. Since

ϕ x 0 (t)=V (x(t, x 0 ),u(t, x 0 )) = x(t, x 0 ) u(t, x 0 ) PQ Q T R x(t, x 0 ) u(t, x 0 ) ≥ 0, by the copositivity of M on Gr G CD (x(t, x 0 )), it follows that lim t→∞ ϕ x 0 (t)
exists. With σ x 0 denoting the above limit, it follows that V (x ∞ ,u(x ∞ )) = σ x 0 for all x ∞ ∈ Ω(x 0 ). Combining (a) and (b), we deduce that for all x ∞ ∈ Ω(x 0 ), we have

ϕ x ∞ (t)=V (x(t, x ∞ ),u(t, x ∞ )) = σ x 0 ∀ t ≥ 0. Thus, ϕ x ∞ (t) is a constant function on [0, ∞). Part (c) is therefore trivial. P r o o fo fT h e o r e m3.1(c). It suffices to show that Ω(x 0 )={0} for all x 0 ∈ℜ n . Let x ∞ ∈ Ω(x 0 ) be given. By part (c) of Proposition 3.2, we have 0 = ϕ ′ x ∞ (t)= z(t, x ∞ ) T Nz(t, x ∞ ) for all t ≥ 0. Hence (3.8) implies x ∞ = 0 as desired.
Admittedly, the conditions in Theorem 3.1 are in general not easy to verify. This is inevitable because most matrix properties in LCP theory are already so. Nevertheless, such difficulties have not prevented the fruitful development of the theory and applications of the LCP and its extensions. Thus we fully expect that Theorem 3.1 is of fundamental importance in the stability theory of the LCS. In what follows, we provide evidence for this optimism by deriving various special results and by giving examples to illustrate the broad applicability of this theorem. We begin by considering the case where both Q and R are taken to be zero. Proposition 3.3 below provides succinct matrix-theoretic conditions that ensure the existence of a "common Lyapunov function" for the LCS. (The study of copositivity has recently received renewed interest in the mathematical programming community; see, e.g., the Ph.D. thesis [START_REF] Parillo | Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization[END_REF] and the paper [START_REF] Sturm | On cones of nonnegative quadratic functions[END_REF]. It would be of interest to investigate how these works can be used to help check the conditions obtained herein.) Proposition 3.3. Let D be a P-matrix and P be a symmetric positive definite matrix.

(a) If, for every α ⊆{1,... ,m},

-( D αα ) -1 C α• C ᾱ• -D ᾱα ( D αα ) -1 C α• x ≥ 0 ⇒ x T [ A -B •α ( D αα ) -1 C α• ] T Px ≤ 0, (3.11)
then x e =0is a linearly bounded stable equilibrium of the LCS (2.1), (b) If, for every α ⊆{1,... ,m},

-(D αα ) -1 C α• C ᾱ• -D ᾱα (D αα ) -1 C α• x ≥ 0,x =0 ⇒ x T [ A -B •α (D αα ) -1 C α• ] T Px < 0, (3.12)
then x e =0is an exponentially stable equilibrium of the LCS (2.1). (c) If, for every α ⊆{1,... ,m}, (3.11) holds and

-( D αα ) -1 C α• C ᾱ• -D ᾱα ( D αα ) -1 C α• x ≥ 0 x T [ A -B •α ( D αα ) -1 C α• ] T Px =0 ⎫ ⎪ ⎪ ⎬ ⎪ ⎪ ⎭ ⇒ x =0, (3.13)
then x e =0is an asymptotically stable equilibrium of the LCS (2.1). Proof. With Q = 0 and R = 0, the matrices M and N become

M = P 0 00 and N = ⎡ ⎢ ⎣ A T P + PA PB 0 B T P 00 00 0 ⎤ ⎥ ⎦ .
By (3.1) and the positive definiteness of P , it follows that M is strictly copositive on Gr SOL CD . For any triple z

≡ (x, u(x),v) ∈ cl Gr SOL ′ LCS with x ∈C α ,w eh a v e z T Nz =2x T [ A -B •α (D αα ) -1 C α• ] T Px.
Hence, the proposition follows easily from Theorem 3.1. Remark 3.1. It should be noted that the resulting matrix M in the above proposition is not positive definite. This illustrates the fact that the strict copositivity of M on Gr SOL CD is not as restrictive as it seems.

A special case of Proposition 3.3 pertains to a "passive-like" LCS for which there exists a symmetric positive definite K such that

- A T K + KA KB -C T B T K -C -D -D T (3.14)
is positive semidefinite. This class of LCSs is closely related to the class of passive LCSs defined in [START_REF] ¸amlibel | Complementarity Methods in the Analysis of Piecewise Linear Dynamical Systems[END_REF][START_REF] ¸amlibel | On linear passive complementarity systems[END_REF] and to the class of positive real transfer functions via the well-known Kalman-Yakubovich-Popov lemma [START_REF] Khalil | Nonlinear Systems[END_REF]. In essence, we have bypassed the transfer functions and the "minimality" of the tuple (A, B, C, D)a n dw o r k e d directly with the positive semidefinite matrix (3.14). Note that if (3.14) is positive semidefinite, then the matrix D must be positive semidefinite albeit not necessarily symmetric. It is possible for such a D to be also P without being positive definite; a trivial example is

D ≡ 1 -2 01 .
The next result shows how Proposition 3.3 (b) can be applied to such an LCS. This result complements Theorem 11.2 [START_REF] ¸amlibel | On linear passive complementarity systems[END_REF] in providing a sufficient condition for a passivelike LCS to be asymptotically stable. Corollary 3.4. Suppose that D is a P-matrix and there exists a symmetric positive definite matrix K such that (3.14) is positive semidefinite. If for every α ⊆ {1,... ,m},

-( D αα ) -1 C α• C ᾱ• -D ᾱα ( D αα ) -1 C α• x ≥ 0 A T K + KA KB •α -( C α• ) T ( B •α ) T K -C α• -D αα -( D αα ) T I -( D αα ) -1 C α• x =0 ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ ⇒ x =0,
then x e is asymptotically stable. Proof. It suffices to verify the implication (3.13). Let x satisfy the left-hand condition in the latter implication. Proceeding as before, we deduce

0=

x u

T A T K + KA KB -C T B T K -C -D -D T x u = x T I -( D αα ) -1 C α• T A T K + PA KB •α -( C α• ) T ( B •α ) T K -C α• -D αα -( D αα ) T × I -( D αα ) -1 C α• x,
which implies, since (3.14) is symmetric positive semidefinite,

A T K + PA KB •α -( C α• ) T ( B •α ) T K -C α• -D αα -( D αα ) T I -( D αα ) -1 C α• x =0.
The desired implication (3.13) follows easily from the assumption of part (b) herein.

The assumption in Proposition 3.3(b) is significantly weaker than the passivity [START_REF] ¸amlibel | Complementarity Methods in the Analysis of Piecewise Linear Dynamical Systems[END_REF][START_REF] ¸amlibel | On linear passive complementarity systems[END_REF] of the LCS tuple (A, B, C, D). The next two examples illustrate this point. The first example has a matrix A that is not negatively stable and the matrix D is not positive semidefinite.

Example 3.1. Consider the tuple with n = 1 and m =2:

A =1,B =[ 2 -2 ],C = 1 -1
, and D = 13 01 .

By an easy calculation, we have

A -B •α ( D αα ) -1 C α• = ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ 1i f α = ∅, -1i f α = { 1 }, -1i f α = { 2 }, -9i f α = { 1, 2 },
and

C α = ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ { 0 } if α = ∅, ( -∞, 0] if α = { 1 }, [0, ∞ )i f α = { 2 }, { 0 } if α = { 1, 2 }.
Note that with P =1 ,t h em a t r i xA -B •∅ ( D ∅∅ ) -1 C ∅• is not negative definite;n e vertheless, the assumption in Proposition 3.3(b) is satisfied.

The next example has the same matrix D but has A = -1sothatA is negatively stable. Yet the LCS (A, B, C, D) is still not passive because D is not positive semidefinite. This example shows that passivity is not a necessary condition for exponential stability, even with a negatively stable matrix A.

Example 3.2. Consider the tuple with n = 1 and m =2:

A = -1,B =[ 01 ],C = 1 1
, and D = 13 01 .

By an easy calculation, we have

A -B •α (D αα ) -1 C α• = ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ -1i f α = ∅, -1i f α = {1}, -2i f α = {2}, -2i f α = {1, 2},
and

C α = ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ [0, ∞ )i f α = ∅, {0} if α = {1}, ( -∞, 0] if α = {2}, {0} if α = {1, 2}.
Again, the assumption in Proposition 3.3(b) is satisfied with P =1.

As noted in the proof of Theorem 3.1(b), the strict copositivity of -N on cl Gr SOL ′ LCS is equivalent to the existence of a constant

ρ N > 0 such that -z T Nz ≥ ρ N z 2 ∀ z ∈ Gr SOL ′ LCS .

Involving only Gr SOL ′

LCS , the latter inequality avoids the explicit description of the closure of this graph, which is a nontrivial task. We employ this equivalent condition for the strict copositivity of -N in the example below, for which we establish the asymptotic stability of the equilibrium with the choice of a nonzero pair (Q, R) satisfying part (b) of Theorem 3.1, and to which we cannot apply Proposition 3.3(b). This example combines Example 3.1 and the one in [27, section IV]. As such, the matrix A is not negatively stable.

Example

3.3. Consider the LCS ẋ = ⎡ ⎣ -5 -40 -1 -20 00 1 ⎤ ⎦ x + ⎡ ⎣ -30 0 -21 0 0 02-2 ⎤ ⎦ u, 0 ≤ u ⊥ ⎡ ⎣ 10 0 00 1 00-1 ⎤ ⎦ x + ⎡ ⎣ 100 013 001 ⎤ ⎦ u ≥ 0.
We claim that there exists no symmetric positive definite matrix P satisfying the assumptions of Proposition 3.3. Consider the two index sets α = ∅ and α = {1}.F o r these sets, we have

C ∅ = { x ∈ℜ 3 : x 1 ≥ 0=x 3 }, C {1} = { x ∈ℜ 3 : x 1 ≤ 0=x 3 } and A -B •∅ (D ∅∅ ) -1 C ∅• = ⎡ ⎣ -5 -40 -1 -20 00 1 ⎤ ⎦ and A -B •{1} (D {1}{1} ) -1 C {1}• = ⎡ ⎣ -2 -40 20 -20 00 1 ⎤ ⎦ .
By way of contradiction, suppose that there exists a symmetric and positive definite matrix P such that the assumption in Proposition 3.3(b) is satisfied. This would mean that there exists a symmetric positive definite matrix P such that xT ( ĀT

i P + P Āi )x<0 ∀ x ∈ Ci , (3.15) for i =1, 2, where C1 ≡{x ∈ℜ 2 | x1 ≥ 0}, C2 = {x ∈ℜ 2 | x1 ≤ 0},a n d Ā1 ≡ -5 -4 -1 -2 , Ā2 ≡ -2 -4 20 -2 .
Since Ci are both half-spaces, the relations (3.15) hold if and only if ĀT i P + P Āi are both negative definite for i =1, 2. As shown in [27, section IV], however, this cannot happen. Next, we claim that x e = 0 is an exponentially stable equilibrium of the LCS by verifying that with

P ≡ ⎡ ⎣ 100 030 001 ⎤ ⎦ ,Q ≡ 0, and R ≡ ⎡ ⎣ 900 000 000 ⎤ ⎦ ,
the assumptions in Theorem 3.1 are satisfied. The strict copositivity of M on Gr SOL CD , is not difficult to verify. We briefly sketch the proof of the strict copositivity of the matrix

-N = ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 10 7 0 | 30 0 | 000 71 2 0| 63 0 0 | 000 00 -2 | 0 -22| 000 -- -| - --|--- 36 3 0| 00 0 | 900 00 -2 | 00 0 | 000 00 2 | 00 0 | 000 -- -| - --|--- 00 0 | 90 0 | 000 00 0 | 00 0 | 000 00 0 | 00 0 | 000 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦
on the closure of Gr SOL ′ LCS .W eh a v eu 1 (x)=m a x ( 0 , -x 1 ), u 2 (x)=m a x ( 0 , -x 3 ), and u 3 (x)=m a x ( 0 ,x 3 ), With the last two rows and columns of N being identically equal to zero, we need not deal with the directional derivatives of u 2 and u 3 . Instead, we focus on

u ′ 1 (x 1 ; dx 1 )= ⎧ ⎪ ⎨ ⎪ ⎩ 0i f x 1 > 0, -dx 1 if x 1 < 0, max(0, -dx 1 )i f x 1 =0,
where

dx 1 = C 1• Ax + C 1• Bu(x)=-5x 1 -4x 2 -3max(0, -x 1 )
. It suffices to show the existence of a constant ρ N > 0 such that

• x 1 > 0 implies ⎛ ⎜ ⎜ ⎜ ⎜ ⎝ x 1 x 2 x 3 max(0, -x 3 ) max(0,x 3 ) ⎞ ⎟ ⎟ ⎟ ⎟ ⎠ T ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 10 7 0 | 00 71 2 0| 00 00 -2 |-22 -- -| -- 00 -2 | 00 00 2 | 00 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎛ ⎜ ⎜ ⎜ ⎜ ⎝ x 1 x 2 x 3 max(0, -x 3 ) max(0,x 3 ) ⎞ ⎟ ⎟ ⎟ ⎟ ⎠ ≥ ρ N x 2 , • x 1 < 0 implies ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ x 1 x 2 x 3 -x 1 max(0, -x 3 ) max(0,x 3 ) 2x 1 +4x 2 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ T ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 10 7 0 | 30 0 | 0 71 2 0| 63 0 0 | 0 00 -2 | 0 -22| 0 -- -| - --|- 36 3 0| 00 0 | 9 00 -2 | 00 0 | 0 00 2 | 00 0 | 0 -- -| - --|- 00 0 | 90 0 | 0 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ x 1 x 2 x 3 -x 1 max(0, -x 3 ) max(0,x 3 ) 2x 1 +4x 2 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ≥ ρ N x 2 , • and (x 1 = 0 implies) ⎛ ⎜ ⎜ ⎜ ⎜ ⎝ x 2 x 3 max(0, -x 3 ) max(0,x 3 ) max(0, 4x 2 ) ⎞ ⎟ ⎟ ⎟ ⎟ ⎠ T ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 12 0 | 00| 0 0 -2 |-22| 0 - -| --|- 0 -2 | 00| 0 02 | 00| 0 - -| --|- 00 | 00| 0 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎛ ⎜ ⎜ ⎜ ⎜ ⎝ x 2 x 3 max(0, -x 3 ) max(0,x 3 ) max(0, 4x 2 ) ⎞ ⎟ ⎟ ⎟ ⎟ ⎠ ≥ ρ N x 2 x 3 2 .
We will leave it to the reader to verify that the desired constant ρ N indeed exists in view of the positive definiteness of certain appropriate matrices.

3.1. Role of observability. The implication (3.8) can be refined by employing an explicit analytic expansion for the vector z(t, ξ)f o rt>0 sufficiently small. The expansion enables the application of the following known fact about an analytic function expressed in series form.

Lemma 3.5. Consider the univariate real-analytic function

ψ(t) ≡ ∞ j=0 a j t j ,t ≥ 0,
where {a j } j≥0 is a given sequence of scalars. The following three statements are valid: (a) in order for ψ(t) > 0 for all t>0 sufficiently small, it is necessary and sufficient that the sequence of coefficients {a j } j≥0 be lexicographically positive; i.e., these coefficients are not all zero and the first nonzero coefficient is positive;

(b) in order for ψ(t) ≥ 0 for all t>0 sufficiently small, it is necessary and sufficient that the sequence of coefficients {a j } j≥0 be lexicographically nonnegative; i.e., either all coefficients are zero or the sequence is lexicographically positive; (c) in order for ψ(t)=0for all t>0 sufficiently small, it is necessary and sufficient that a j =0for all j ≥ 0. If the coefficients a j are given by e T G j ξ for some n-vectors e and ξ and n × n matrix G, the above conditions on the infinite sequence {a j } j≥0 can be replaced by the finite sequence {a j } n-1 j=0 . For a given pair of matrices G ∈ℜ k×k and H ∈ℜ ℓ×k , the unobservable space of (H, G), denoted O(H, G), is the set of vectors ξ ∈ℜ k such that HG j ξ =0f o r all j =0 , 1,... ,k -1. In contrast to this linear subspace, the semiunobservable cone of (H, G), denoted SO(H, G), is the set of vectors ξ ∈ℜ n such that the family of scalars {H i• G j ξ} k-1 j=0 is lexicographically nonnegative for all i =1,... ,ℓ. The two sets O(H, G)a n dSO(H, G) have played an important role in the observability analysis of the LCS [START_REF] Pang | Strongly regular differential variational systems[END_REF]; they have an equally important role here in the asymptotic stability analysis of the LCS. We also define the open subset SO(H, G)ofSO(H, G) consisting of vectors ξ ∈ℜ n such that the family of scalars {H i• G j ξ} k-1 j=0 is lexicographically positive for all i =1,... ,ℓ. Note that 0 ∈ SO(H, G).

The one-sided directional derivative u ′ (x(t, x 0 ); CAx(t, x 0 )+CBu(t, x 0 )) is the unique vector v(t, x 0 ) satisfying

free v i (t, x 0 )( CAx(t, x 0 )+CBu(t, x 0 )+Dv(t, x 0 )) i =0,i ∈ α(x(t, x 0 )), 0 ≤ v i (t, x 0 ) ⊥ ( CAx(t, x 0 )+CBu(t, x 0 )+Dv(t, x 0 )) i ≥ 0,i ∈ β(x(t, x 0 )), 0=v i (t, x 0 ), ( CAx(t, x 0 )+CBu(t, x 0 )+Dv(t, x 0 )) i free, i ∈ γ(x(t, x 0 )). (3.16)
B yas t r o n gn o n -Z e n or e s u l tf o ra nL C Sw i t haP -m a t r i xD [START_REF] Pang | Strongly regular differential variational systems[END_REF], we deduce the existence of a time τ 0 > 0 and a triple of index sets (α n ,β n ,γ n ), both dependent on the initial condition x 0 , such that (α(x(t, x 0 )),β(x(t, x 0 )),γ(x(t, x 0 ))) = (α n ,β n ,γ n ) for all t ∈ (0,τ 0 ]. For all such times t, the system (3.16) becomes

( CAx(t, x 0 )+CBu(t, x 0 )+Dv(t, x 0 )) i =0,i ∈ α n , 0 ≤ v i (t, x 0 ) ⊥ ( CAx(t, x 0 )+CBu(t, x 0 )+Dv(t, x 0 )) i ≥ 0,i ∈ β n , 0=v i (t, x 0 ),i ∈ γ n .
The latter is a mixed LCP of the P-type. As explained in [START_REF] Pang | Strongly regular differential variational systems[END_REF], there exist a scalar τ ∈ (0,τ 0 ] and a subset β a ⊆ β n with complement βa ≡ β n \ β a such that for all t ∈ (0, τ ], the unique solution v(t, x 0 ) of the above mixed LCP satisfies (where

K≡α n ∪ β a ) v K (t, x 0 )=-( D KK ) -1 C K• AB x(t, x 0 ) u(t, x 0 ) .
Note that v β a (t, x 0 ) ≥ 0, v βa (t, x 0 ) = 0, and

C βa • -D βa K ( D KK ) -1 C K• AB x(t, x 0 ) u(t, x 0 ) ≥ 0.
Provided that τ 0 is sufficiently small, we have

supp(u(x 0 )) ⊆ α n ⊆K ⊆ α n ∪ β n ⊆{i :(Cx 0 + Du(x 0 )) i =0}.
In terms of the index set K,w eh a v e 0 < 0=

u α n (t, x 0 ) u β a (t, x 0 ) = - D α n α n D α n β a D β a α n D β a β a -1 C α n • C β a • x(t, x 0 ) and 0= 0 < ⎧ ⎨ ⎩ C βa • C γ n • - D βa α n D βa β t D γ n α n D γ n β t D α n α n D α n β a D β a α n D β a β a -1 C α n • C β a • ⎫ ⎬ ⎭ x(t, x 0 ).
Substituting the expression for u K (t, x 0 )i n t ot h eO D E ẋ = Ax + Bu and noting that u i (t, x 0 ) = 0 for all i ∈K, we deduce

x(t, x 0 )= ∞ j=0 t j j ! A(K) j x 0 , C(K)x(t, x 0 )= ∞ j=0 t j j ! C(K)A(K) j x 0 , AB x(t, x 0 ) u(t, x 0 ) = ∞ j=0 t j j ! AB •K I C K• (K) A(K) j x 0 , where A(K) ≡ A -B •K (D KK ) -1 C K• ,a n dw i t h K≡{1,... ,m}\K, C(K) ≡ -( D KK ) -1 C K• C K• -D KK ( D KK ) -1 C K• and D(K) ≡ C(K) AB •K I C K• (K) .
By Lemma 3.5, in order for v β a (t, x 0 ) ≥ 0=u β a (t, x 0 ) to hold for all t>0 sufficiently small, it is necessary and sufficient that

x 0 ∈ SO(D β a • (K),A(K)) ∩ O(C β a • (K),A(K)).
Moreover, if α n = ∅,t h e ns i n c eu α n (t, x 0 ) > 0 for all t>0 sufficiently small, we must have

x 0 ∈ SO(C α n • (K),A(K)). Similarly, if γ n = ∅,w ea l s oh a v ex 0 ∈ SO(C γ n • (K),A(K)).
Turning our attention to the implication (3.8), we note that Nz(t, x 0 )i se q u a lt o ⎡ ⎢ ⎣

A T P + PA PB •K + A T Q •K Q •K (B •K ) T P +(Q •K ) T A (B •K ) T Q •K +(Q •K ) T B •K R KK (Q •K ) T R KK 0 ⎤ ⎥ ⎦ ⎛ ⎜ ⎝ x(t, x 0 ) u K (t, x 0 ) v K (t, x 0 ) ⎞ ⎟ ⎠ = ∞ j=0 t j j ! ⎡ ⎢ ⎣ A T P + PA PB •K + A T Q •K Q •K (B •K ) T P +(Q •K ) T A (B •K ) T Q •K +(Q •K ) T B •K R KK (Q •K ) T R KK 0 ⎤ ⎥ ⎦ × ⎡ ⎢ ⎣ I C K• (K) D K• (K) ⎤ ⎥ ⎦ A(K) j x 0 . Define N (K) ≡ ⎡ ⎢ ⎣ A T P + PA PB •K + A T Q •K Q •K (B •K ) T P +(Q •K ) T A (B •K ) T Q •K +(Q •K ) T B •K R KK (Q •K ) T R KK 0 ⎤ ⎥ ⎦ ⎡ ⎢ ⎣ I C K• (K) D K• (K) ⎤ ⎥ ⎦ .
By Lemma 3.5, in order for Nz(t, x 0 ) = 0 for all t ≥ 0 sufficiently small, it is necessary and sufficient that x 0 ∈ O(N (K),A(K)). Based on the above discussion, we state and prove the following result which is derived from a refinement of the implication (3.8).

Proposition 3.6. Let D be a P-matrix. Suppose there exist symmetric matrices P and R and a matrix Q such that M is strictly copositive on Gr SOL CD and -N is copositive-plus on Gr SOL ′ LCS . Assume further that the following two conditions hold for all triples of index sets (α, β, γ) partitioning {1,... ,m} and for all subsets β a of β,w i t hK≡α ∪ β a :

(a) for α = γ = ∅,

SO(D K• (K),A(K)) ∩ O(C K• (K),A(K)) ∩ O(N (K),A(K)) = { 0 }, (3.17) (b) for α ∪ γ = ∅, SO(C α∪γ• (K),A(K)) ∩ SO(D β a • (K),A(K)) (3.18) ∩ O(C β a • (K),A(K)) ∩ O(N (K),A(K)) = ∅;
then x e =0is an asymptotically stable equilibrium of the LCS (2.1).

Proof. It suffices to show that the implication (3.8) holds. Let ξ satisfy the left-hand side of (3.8). Thus, in particular, Nz(t, ξ) = 0 for all t>0 sufficiently small. Following the above argument, we consider the pair of index sets (α n , K) associated with the trajectories u(x(t, ξ)) and u ′ (x(t, ξ); dx(t, ξ)), where dx(t, ξ) ≡ CAx(t, ξ)+CBu(x(t, ξ)). The empty intersection (3.18) implies that α n = γ n = ∅. Since ξ belongs to the intersection of the three sets in the left-hand side of (3.17), the latter condition then yields ξ = 0 as desired.

3.2. A SISO system. We illustrate Proposition 3.6 for a single-input-singleoutput (SISO) system, which has m = 1 and D = 1 (the latter is assumed without loss of generality). We write c T for C and b for B. Thus the SISO LCS is of the form

ẋ = Ax + b max(0, -c T x). (3.19)
In this case, we have u(x)=max(0, -c T x)a n d

SOL ′ LCS (x)= ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ 0 0 if c T x>0, 0 max( 0, -c T Ax ) if c T x =0, -c T x -c T ( A -bc T )x if c T x<0.
The reader can easily check that Gr SOL ′ LCS is not closed; nevertheless, one can verify that cl Gr SOL

′ LCS = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ 0 0 if c T x>0, 0 0 , 0 -c T Ax if c T x =0, -c T x -c T ( A -bc T )x if c T x<0.
The matrix M ≡ Pq q T r is strictly copositive on Gr SOL CD if and only if

[c T x ≥ 0,x =0]⇒ x T Px>0 and [c T x<0] ⇒ x T [P -qc T -cq T + rcc T ]x>0 .
In turn, this holds if and only if P and Pqc Tcq T + rcc T are both positive definite.

To see this, suppose that the above two implications hold. If c T x<0, then c T (-x) > 0; thus 0 < (-x) T P (-x)=x T Px. Hence P must be positive definite. This together with the second implication establishes the positive definiteness of P -qc T -cq T +rcc T . T h ec o n v e r s ei so b v i o u s . The matrix

-N ≡- ⎡ ⎢ ⎣ A T P + PA Pb+ A T qq b T P + q T Aq T b + b T qr q T r 0 ⎤ ⎥ ⎦ is copositive on Gr SOL ′ LCS if and only if c T x ≥ 0 ⇒ x T ( A T P + PA)x ≤ 0, c T x ≤ 0 ⇒ ⎛ ⎜ ⎝ x -c T x -c T (A -bc T )x ⎞ ⎟ ⎠ T ⎡ ⎢ ⎣ A T P + PA Pb+ A T qq b T P + q T Aq T b + b T qr q T r 0 ⎤ ⎥ ⎦ ⎛ ⎜ ⎝ x -c T x -c T (A -bc T )x ⎞ ⎟ ⎠ ≤ 0.

In turn the above implications hold if and only if -(A

T P + PA)a n d -I -c -( A T -cb T )c ⎡ ⎢ ⎣ A T P + PA Pb+ A T qq b T P + q T Aq T b + b T qr q T r 0 ⎤ ⎥ ⎦ ⎡ ⎢ ⎣ I -c T -c T ( A -bc T ) ⎤ ⎥ ⎦ (3.20)
are both positive semidefinite and thus copositive-plus. We examine the two conditions (3.17) and (3.18) in Proposition 3.6. For (3.17) where α = γ = ∅,t h e r ea r et w o cases:

K = ∅ or {1}.F o rK = ∅, (3.17) stipulates that O(A T P + PA,A)={0}.F o r K = {1},w eh a v e N (1) = N ⎡ ⎢ ⎣ I -c T -c T (A -bc T ) ⎤ ⎥ ⎦ ,
and the condition (3.17) stipulates that

{ 0 } = SO(-c T (A -bc T ),A-bc T ) ∩ O(-c T ,A-bc T ) ∩ O(N (1),A-bc T ) = O(c T ,A) ∩ O(N (1),A-bc T )=O(c T ,A) ∩ O(A T P + PA,A),
which is implied by the former case. For (3.18), there are 2 subcases: α = {1} or γ = {1}.F o r α = {1}, the condition (3.18) stipulates that SO(-c T ,Abc T ) ∩ O(N (1),A-bc T )=∅.F o rγ = {1}, the condition (3.18) stipulates that SO(c T ,Abc T ) ∩ O(A T P + PA,A)=∅, which is implied by O(A T P + PA,A)={0} because 0 ∈ SO(c T ,A-bc T ).

Summarizing the above analysis, we present a sufficient condition for x e =0t o be an asymptotically stable equilibrium of the SISO LCS (3.19).

Proposition 3.7. If there exist a symmetric positive definite matrix P , a vector q,a n das c a l a rr such that

Extension to non-P systems.

In this subsection, we extend Theorem 3.1 to the case where D is not a P-matrix; but we assume the blanket condition that BSOL(Cx,D) is a singleton for all x ∈ℜ n . The extension turns out to be technically nontrivial; for one thing, Gr SOL ′ LCS ceases to exist because SOL(Cx,D) is no longer a single-valued function, and thus we cannot employ its directional derivatives as defined by (3.3). In addition to the main result, Theorem 3.12, we also obtain a stability result for a passive LCS without assuming the P-property of D; see Corollary 3.13.

To carry out the extended analysis, we assume that the matrices Q and R are such that QSOL(Cx,D)andRSOL(Cx,D) are both singletons for all x ∈ℜ n .A m o n g other things, the single-valuedness of RSOL(Cx,D) yields the following important property of the quadratic term SOL(Cx,D) T RSOL(Cx,D).

Proposition 3.8. Let R be a symmetric matrix. Suppose that RSOL(Cx,D) is a singleton for all x ∈ℜ n . The function x → SOL(Cx,D) T RSOL(Cx,D) is a single-valued piecewise quadratic function on ℜ n . In other words, for any four vectors u i ∈ SOL(Cx,D), i =1 , 2, 3, 4, it holds that (u 1 ) T Ru 2 =( u 3 ) T Ru 4 ; moreover, this function is continuous in x and there exist finitely many matrices {E j } K j=1 ⊂ℜ n×n for some integer K>0 such that SOL(Cx,D) T RSOL(Cx,D) ∈{ x T E j x} K j=1 for every x ∈ℜ n . Proof. For any u i ∈ SOL(Cx,D), i =1, 2, 3, 4, we have Ru 1 = Ru 2 = Ru 3 = Ru 4 . Hence by the symmetry of R,w eh a v e (u 1 ) T Ru 2 =(u 3 ) T Ru 2 =(u 3 ) T Ru 4 .

Next, we show that the function x → SOL(Cx,D) T RSOL(Cx,D) is continuous. This follows easily from the single-valuedness of this map and the fact that the LCP solution map q → SOL(q, D)i spointwise upper Lipschitz continuous [START_REF] Cottle | The Linear Complementarity Problem[END_REF][START_REF] Facchinei | Finite-Dimensional Variational Inequalities and Complementarity Problems[END_REF][START_REF] Robinson | Some continuity properties of polyhedral multifunctions[END_REF] on ℜ m ; i.e., for every q ∈ℜ m , there exist positive scalars c and ε such that q ′q <ε⇒ SOL(q ′ ,D) ⊆ SOL(q, D)+c q ′q B, where B is the unit ball in ℜ m . Indeed, let {x k }⊂ℜ n be any sequence of vectors converging to some vector x ∞ ∈ℜ n .L e t {u k }⊂ℜ m be such that u k ∈ SOL(Cx k ,D) for every k. By the above continuity property of the LCP solution map, it follows that there exists a corresponding sequence { u k } such that u k ∈ SOL(Cx ∞ ,D) for every k and lim k→∞ u ku k = 0. By the single-valuedness of SOL(Cx ∞ ,D) T RSOL(Cx ∞ ,D)a n dRSOL(Cx ∞ ,D), we can write

(u k ) T Ru k =( u k ) T R u k +2(u k -u k ) T R u k +(u k -u k ) T R(u k -u k ) =SOL(Cx ∞ ,D) T RSOL(Cx ∞ ,D)+2(u k -u k ) T RSOL(Cx ∞ ,D) +(u k -u k ) T R(u k -u k ).
Passing to the limit k →∞easily establishes lim k→∞ (u

k ) T Ru k =S O L ( Cx ∞ ,D) T RSOL (Cx ∞ ,D)
. Finally, we postpone the identification of the matrices E j after our description of the structure of SOL(Cx,D) that immediately follows this proof.

It is well known that the graph of the set-valued LCP solution map S D : q → SOL(q, D) is the union of finitely many polyhedra in ℜ m ; this property is the basis for proving the upper Lipschitz continuity of this map used in the above proof. For the purpose of introducing a closed graph that plays the role of Gr SOL ′ LCS ,w h i c hi s not available in the non-P case, we first define certain subsets of the polyhedra that compose the graph Gr SOL CD . The derivation below is closely related to the development in [39, section 5.1] where we have identified a "linear Newton approximation" for the single-valued map BSOL(Cx,D).

For every vector x ∈ℜ n ,l e tL(x) be the (necessarily nonempty) family of pairs of index subsets α and J of {1,... ,m} such that (a) α ⊆J, (b) the columns of D J α are linearly independent, and (c) there exists u ∈ SOL(Cx,D) such that supp(u) ⊆ α and J⊆{ i :( Cx + Du) i =0 }, where supp(u) ≡{ i : u i > 0} is the support of the vector u. Here, we adopt the convention that an empty set of vectors is linearly independent; under this convention, if 0 ∈ SOL(Cx,D), then L(x) includes all pairs (∅, J ) for all subsets J⊆{ i :( Cx) i =0 }. For a given pair (α, J )i nL(x), by (b), the solution u in (c) is unique and given by

u α = -( D J α ) T D J α -1 ( D J α ) T C J• x, u ᾱ =0, (3.21)
where ᾱ is the complement of α in {1,... ,m}. Notice that the converse is not true; namely, for a given solution u ∈ SOL(Cx,D), it is possible for multiple pairs (α, J ) in L(x) to give rise to the same u, via (3.21). Define the set-valued map

G CD : x →G CD (x) ≡ -(D J α ) T D J α -1 (D J α ) T C J• x 0 :(α, J ) ∈L(x) .
Clearly, Gr G CD ⊆ Gr SOL CD . It is easily seen that Gr G CD is a cone in ℜ n+m ; subsequently, we will show that it is closed. Like the LCP solution graph, Gr G CD is not necessarily convex. In general, Gr G CD is a proper subset of Gr SOL CD ;f o r instance, if D is a singular matrix, then any positive vector that is a solution of the LCP (Cx,D) is not an element of the former graph. Moreover, due to the finite number of index sets, a positive constant ρ G > 0 exists such that

sup{ u : u ∈G CD (x) }≤ρ G x ∀ x ∈ℜ n . (3.22)
For any matrix W ∈ℜ p×m , define the family

T W (x) ≡ -W •α (D J α ) T D J α -1 (D J α ) T C J• :(α, J ) ∈L(x) ,
where, by convention, we define

W •α [(D J α ) T D J α ] -1 (D J α ) T C J• to be the zero ma- trix if α = ∅. In general, { Ex : E ∈T W (x) }⊆W SOL(Cx,D)
with equality holding if W SOL(Cx,D) is a singleton. Suppose that W SOL(Cx,D) is a singleton for all x ∈ℜ n . It then follows that the piecewise linear map h W (x) ≡ W SOL(Cx,D) is B-differentiable everywhere on ℜ n . Thus the directional derivative h ′ W (x; v)o fh W at x along the direction v is well defined and, according to standard theory [START_REF] Scholtes | Introduction to piecewise differentiable equations[END_REF], is an element of the set {Ev : E ∈A W (x)},w h e r eA W (x) ≡{ E : Ex = h W (x)} is the set of active pieces of h W at x. The following result sharpens this representation of h ′ W (x; v) by restricting to the pieces in T W (x), which is clearly a subfamily of A W (x).

Proposition 3.9. Let W ∈ℜ p×m be such that W SOL(Cx,D) is a singleton for all x ∈ℜ n . For the piecewise linear function h W (x) ≡ W SOL(Cx,D), it holds that h ′ W (x; v) ∈{Ev : E ∈T W (x)} for all x and v in ℜ n .

Proof.F o re a c hτ>0, h W (x + τv)=E τ (x + τv), where, for any pair of index sets

(α τ , J τ )inL(x+τv), E τ ≡-W •α τ [(D J τ α τ ) T D J τ α τ ] -1 (D J τ α τ ) T C J τ • .
Thuswehave (a) α τ ⊆J τ , (b) the columns of D J τ α τ are linearly independent, and (c) there exists u τ ∈ SOL(C(x + τv),D) such that supp(u τ ) ⊆ α τ and J τ ⊆{i :[C(x + τv)+Du τ ] i = 0}.I nf a c t ,u τ is given by (3.21),

u τ α τ = -(D J τ α τ ) T D J τ α τ -1 (D J τ α τ ) T C J τ • (x + τv),u τ ᾱτ =0,
where ᾱτ is the complement of α τ in {1,... ,m}.L e t{τ k } be an arbitrary sequence of positive scalars converging to zero for which there exists a pair (α ∞ , J ∞ ) such that (α τ k , J τ k )=( α ∞ , J ∞ ) for all k (there must be at least one such sequence for every pair (x, v) because there are only finitely many pairs of index sets). The corresponding sequence of solutions {u τ k } converges to a vector, say, u ∞ , which must be a solution of the LCP (Cx,D), by the continuity of the latter solution with respect to Cx.

Moreover, for all k sufficiently large, we have

supp(u ∞ ) ⊆ supp(u τ k ) ⊆ α ∞ ⊆J ∞ ⊆{i :(Cx + Du ∞ ) i =0}
by a simple limiting argument. Thus the pair (α ∞ , J ∞ ) belongs to L(x)a n dE τ k ∈ T W (x) for all k sufficiently large. Writing E ∞ ≡ E τ k for all such k,w eh a v e

h W (x + τ k v) -h W (x)=E τ k (x + τ k v) -E ∞ x = τ k E ∞ v, from which we obtain h ′ W (x; v)=E ∞ v,w h e r eE ∞ ∈T W (x)
, as desired. Dealing with a symmetric matrix, the next result completes the proof of Proposition 3.8. For a symmetric m × m matrix R, define the finite family of symmetric matrices T R (x) ⊂ℜ n×n :

-(C J• ) T D J α (D J α ) T D J α -1 R αα (D J α ) T D J α -1 (D J α ) T C J• :(α, J ) ∈L(x) .
Proposition 3.10. Let R ∈ℜ m×m be symmetric such that RSOL(Cx,D) is a singleton for all x ∈ℜ n . For the piecewise quadratic function h R (x) ≡ SOL(Cx,D) T RSOL(Cx,D), it holds that

(a) h R (x)=x T Ex for all E ∈ T R (x); (b) h ′ R (x; v) ∈{2x T Ev : E ∈ T R (x)} for all x and v in ℜ n .
Proof. It suffices to prove part (b). As a piecewise quadratic function, the directional derivative h ′ R (x; v) exists. For each τ>0, h R (x + τv)=(x + τv) T E τ (x + τv), where

E τ ≡ (C J τ • ) T D J τ α τ (D J τ α τ ) T D J τ α τ -1 R α τ α τ (D J τ α τ ) T D J τ α τ -1 (D J τ α τ ) T C J τ •
for any pair of index sets (α τ , J τ ) ∈L (x + τv). As in the proof of Proposition 3.9, we can take a sequence of positive scalars {τ k } converging to zero and a fixed pair

(α ∞ , J ∞ ) such that (α τ k , J τ k )=( α ∞ , J ∞ ) for all k.
It is now easy to complete the proof. We apply the above results to the singled-valued function:

V (x) ≡ V (x, SOL(Cx,D)) = x T Px+2x T QSOL(Cx,D)+SOL(Cx,D) T RSOL(Cx,D),
assuming that QSOL(Cx,D)a n dRSOL(Cx,D) are both singletons for all x ∈ℜ n . Under this assumption, V (x)=V (x, G CD (x)) is piecewise quadratic and

V ′ (x; v)=2x T Pv +2v T QSOL(Cx,D)+2x T E Q v +2x T E R v,
where

E Q ≡-Q •α (D J α ) T D J α -1 (D J α ) T C J• ∈T Q (x)a n d E R ≡ ( C J• ) T D J α ( D J α ) T D J α -1 R αα ( D J α ) T D J α -1 ( D J α ) T C J• ∈ T R (x)
for some pair (α, J ) ∈L (x); note that we can choose the same pair (α, J )f o r the directional derivatives of QSOL(Cx,D) and SOL(Cx,D) T RSOL(Cx,D) because (cf. the proofs of Propositions 3.9 and 3.10) both derivatives were derived from SOL(C(x+τv),D) corresponding to the same v.S i n c eQSOL(Cx,D

)=E Q x,wehave V ′ (x; v)=2x T [P + E Q +(E Q ) T + E R ]v. Note that the matrix P + E Q +(E Q ) T + E R is symmetric. With ϕ x 0 (t) ≡ V (x(t, x 0 )), we have ϕ ′ x 0 (t+) = V ′ (x(t, x 0 ); ẋ(t, x 0 )) =2x(t, x 0 ) T P + E Q t +(E Q t ) T + E R t Ax(t, x 0 )+BSOL(Cx(t, x 0 ),D) ,
where the equality in the second line is by a simple substitution, and for each t>0,

E Q t ≡-Q •α t (D α t J t D J t α t ) -1 D α t J t C J t • ∈T Q (x(t, x 0 ))
, and

E R t ≡ (C J t • ) T D J t α t (D J t α t ) T D J t α t -1 R α t α t (D J t α t ) T D J t α t -1 ×(D J t α t ) T C J t • ∈ T R (x(t, x 0 ))
for some pair (α t , J t ) ∈L (x(t, x 0 )). Corresponding to any such pair of index sets, letting z(t, x 0 ) ≡ (x(t, x 0 ),u(t, x 0 ),v(t, x 0 )),

u α t (t, x 0 ) u ᾱt (t, x 0 ) ≡ -(D J t α t ) T D J t α t -1 (D J t α t ) T C J t • x(t, x 0 ) 0 ∈ GrG CD (x(t, x 0 )), v α t (t, x 0 ) v ᾱt (t, x 0 ) ≡ -(D J t α t ) T D J t α t -1 (D J t α t ) T C J t • (Ax(t, x 0 )+BSOL(Cx(t, x 0 ),D)) 0 ,
where ᾱt is the complement of α t in {1,... ,m}, we obtain

Qu(t, x 0 )=E Q t x(t, x 0 ),B u (t, x 0 )=BSOL(Cx(t, x 0 ),D), x(t, x 0 ) T E R t (Ax(t, x 0 )+BSOL(Cx(t, x 0 ),D)) = u(t, x 0 ) T Rv(t, x 0 ), x(t, x 0 ) T E Q t (Ax(t, x 0 )+BSOL(Cx(t, x 0 ),D)) = x(t, x 0 ) T Qv(t, x 0 ),
and ϕ ′ x 0 (t+) = z(t, x 0 ) T Nz(t, x 0 ), where N is the same matrix defined by (3.6). Note that a constant ρ G > 0 exists satisfying

v(t, x 0 ) ≤ρ G (x(t, x 0 ),u(t, x 0 )) ∀ (t, x 0 ) ∈ [0, ∞ ) ×ℜ n . (3.23)
Augmenting the map G CD , define

G LCS : x → ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ -( D J α ) T D J α -1 ( D J α ) T C J• x 0 -(D J α ) T D J α -1 (D J α ) T C J• (Ax + BSOL(Cx,D)) 0 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ :(α, J ) ∈L(x) ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ .
Note that the pair (u(t, x 0 ),v(t, x 0 )) defined above belongs to

G LCS (x(t, x 0 )) ⊂ℜ 2m .
In what follows, we let z(t, x 0 ) denote any triple in Gr G LCS such that ϕ ′ x 0 (t+) = z(t, x 0 ) T Nz(t, x 0 ). We next show that the two graphs Gr G CD and Gr G LCS are closed.

Proposition 3.11. Both maps G CD and G LCS have closed graphs. Proof. We prove the claim only for G LCS .L e t{x k } be a sequence converging to x ∞ .F o re a c hk,l e t( α k , J k ) ∈L(x k ) be such that

lim k→∞ ⎛ ⎜ ⎜ ⎜ ⎜ ⎝ -(D J k α k ) T D J k α k -1 (D J k α k ) T C J k • x k 0 -(D J k α k ) T D J k α k -1 (D J k α k ) T C J k • (Ax k + BSOL(Cx k ,D)) 0 ⎞ ⎟ ⎟ ⎟ ⎟ ⎠ exists.
As in the proof of Proposition 3.9, there exist an infinite subset κ of {1, 2,...} and a pair (α

∞ , J ∞ ) ∈L (x ∞ ) such that (α k , J k )=( α ∞ , J ∞ ) for all k ∈ κ.S i n c e BSOL(Cx,D) is continuous in x, the displayed limit is therefore equal to ⎛ ⎜ ⎜ ⎜ ⎜ ⎝ -(D J ∞ α ∞ ) T D J ∞ α ∞ -1 (D J ∞ α ∞ ) T C J ∞ • x ∞ 0 -(D J ∞ α ∞ ) T D J ∞ α ∞ -1 (D J ∞ α ∞ ) T C J ∞ • (Ax ∞ + BSOL(Cx ∞ ,D)) 0 ⎞ ⎟ ⎟ ⎟ ⎟ ⎠
.

The closedness of the graph Gr G LCS follows.

The above discussion makes it clear that the LCS (2.1) is related to a "linear selectionable DI"; see Smirnov [52, section 8.2]. Nevertheless, there are significant differences between the two kinds of systems; such differences therefore dismiss the applicability of the stability results in the cited reference to the LCS. If x(t)i sa solution of (2.1), then ẋ(t) ∈A(x(t)), where the set-valued map A : ℜ n →ℜ n is given by

A(x) ≡{(A + E)x : E ∈T B (x)},
with the family T B (x) being finite and dependent on the state. In contrast, in order for the DI ẋ(t) ∈ A(x(t)) to be linear selectionable, there must exist a constant convex compact set M of real n×n matrices such that A(x) ≡{Mx : M ∈M}. Clearly, there are noticeable differences between the two sets A(x)and A(x); for instance, the latter is always convex, whereas the former consists of only finitely many vectors. In fact, linear selectionable DIs are like hybrid systems with "state independent switchings" [START_REF] Hespanha | Uniform stability of switched linear systems: Extension of LaSalle's invariance principle[END_REF], and the LCS is a hybrid system with state-triggered switchings.

The following result extends Theorem 3.1 to a non-P matrix D. The same proof applies.

Theorem 3.12. Suppose that BSOL(Cx,D) is a singleton for all x ∈ℜ n .A ssume further matrices P , Q,a n dR,w i t hP and R symmetric, exist such that (A1) QSOL(Cx,D) and RSOL(Cx,D) are singletons for all x ∈ℜ n ;

(A2) M is strictly copositive on Gr G CD . Let z(t, x 0 ) denote any triple in Gr G LCS such that ϕ ′

x 0 (t+) = z(t, x 0 ) T Nz(t, x 0 ).T h e following four statements hold for the equilibrium x e =0of (2.1).

(a) If -N is copositive on Gr G LCS ,t h e nx e is linearly bounded stable.

(b) If -N is strictly copositive on cl Gr G LCS ,t h e nx e is exponentially stable.

(c) If -N is copositive on Gr G LCS and (3.8) holds, then x e is asymptotically stable. (d) If -N is copositive-plus on Gr G LCS and (3.9) holds, then x e is asymptotically stable. Complementing Corollary 3.4, the next result is a specialization of the above theorem to a passive LCS.

Corollary 3.13. Assume that SOL(Cx,D) = ∅ for all x ∈ℜ n and that (D + D T )u =0⇒ Bu =0. If the quadruple (A, B, C, D) is passive with a passifying matrix K such that the only vector x for which

A T K + KA KB •α -( C α• ) T ( B •α ) T K -C α• -D αα -( D αα ) T I -(D J α ) T D J α -1 (D J α ) T C J• x =0
for some pair (α, J ) ∈L(x) is the zero vector, then x e =0is an asymptotically stable equilibrium of the LCS (2.1).

Proof.S i n c eD is positive semidefinite, the assumption (D + D T )u =0⇒ Bu =0 implies that BSOL(Cx,D) is a singleton for all x ∈ℜ n . The remaining proof is similar to that of part (b) of Corollary 3.4 and is not repeated.

4. An inhomogeneous extension. The stability results in the last section can be extended to a "generalized LCS" [START_REF] Pang | Differential variational inequalities[END_REF], which has exactly the same structure as the LCS except that the nonnegative orthant is replaced by an arbitrary polyhedral cone and its dual. Such an extension is significant because the generalized LCS is a much broader class of nonsmooth dynamical system than the LCS; for instance, it includes the case of a mixed LCP to be satisfied by the algebraic variable and also the case of more general linear constraints on the latter variable than nonnegativity. The generalized LCS also arises from the approximation of inhomogeneous (cf. Corollary 4.6) and nonlinear systems (see section 5). All the piecewise linearity properties that we have employed for the LCP have known extensions to the generalized LCP defined over a polyhedral cone. Based on these extended LCP results, we can easily generalize the Lyapunov stability theory to the generalized LCS without difficulty. The reason we have chosen to focus on the LCS is because this is a fundamental system in its own right with important applications in diverse fields.

Instead of presenting the details of the extended stability results, which will not involve significantly new ideas, we present below a Lyapunov stability theory for an inhomogeneous differential affine system, via a reduction to an equivalent homogeneous system. At the end of the section, we introduce a general reduction approach that paves the way to the treatment of differential nonlinear systems that is the topic of section 5.

Consider the following inhomogeneous LCS with D being a P-matrix:

ẋ = p + Ax + Bu, 0 ≤ u ⊥ q + Cx + Du ≥ 0, x(0) = x 0 , (4.1)
where p ∈ℜ n and q ∈ℜ m are constant vectors and the other matrices are defined in the same way as before. To avoid triviality, we assume throughout that (p, q) =0 . By the P-property of the matrix D, we deduce that the unique solution u(x)t ot h e LCP (q + Cx,D) is globally Lipschitz continuous in x; hence, for any x 0 ∈ℜ n ,t h e r e exists a unique continuously differentiable solution x(t, x 0 ) for all t ≥ 0 satisfying ẋ = p + Ax + Bu(x)andx(0) = x 0 . Since the right-hand side of the latter ODE is not positively homogeneous in x,t h es o l u t i o nx(t, •) is no longer positively homogeneous in the initial condition. Therefore, the local asymptotic/exponential stability of an equilibrium of (4.1) does not imply its global asymptotic/exponential stability. Such an equilibrium is a vector x e ∈ℜ n such that 0 = p + Ax e + Bu(x e ). In order to analyze the stability of such a vector x e ,l e t α e ≡{i : u e i > 0=(q + Cx e + Du e ) i }, β e ≡{i : u e i =0=(q + Cx e + Du e ) i }, γ e ≡{i : u e i =0< ( q + Cx e + Du e ) i } be the three fundamental index sets corresponding to the pair (x e ,u e ), where u e ≡ u(x e ) and define the matrices We say that x e is an isolated zero of the equation 0 = p+Ax+Bu(x) if a neighborhood of x e exists within which x e is the only zero of the equation. A similar definition applies to the "isolatedness" of the pair (x e ,u e ) in part (b) of the proposition below. Proposition 4.1. Let D be a P-matrix. The following three statements are equivalent.

A ≡ A -B •α e (D α e α e ) -1 C α e • , B •β e ≡ B •β e -B •
(a) x e is an isolated zero of the equation 0=p + Ax + Bu(x); (b) the pair (x e ,u e ) is an isolated solution of the mixed LCP in the variables (x, u) ∈ℜ n+m :

0=p + Ax + Bu, 0 ≤ u ⊥ q + Cx + Du ≥ 0;
(c) the following homogeneous mixed LCP has a unique solution (z, v)=(0, 0):

0= Az + B •β e v, 0 ≤ v ⊥ C β e • z + D β e β e v ≥ 0.
Any one of the above three conditions is necessary for x e to be an asymptotically stable equilibrium of (4.1).

Proof.( a )⇔ (b). Clearly (a) implies (b). The converse holds by the P-property of D.

(b) ⇔ (c). This follows from [15, Corollary 3.3.9] and the fact that D α e α e is nonsingular.

To see that any one of the three conditions (a)-(c) is necessary for x e to be an asymptotically stable equilibrium of (4.1), assume for the sake of contradiction that there exists a sequence {x k } of zeros of the equation 0 = p + Ax + Bu(x) such that x k = x e for all k and lim k→∞ x k = x e . E a c hs u c hz e r ox k ,f o rk sufficiently large, defines a stationary trajectory x k (t, x k )=x k for all t ≥ 0 that violates the asymptotic stability of x e .

Next we show that the stability (resp., asymptotic/exponential stability) of the equilibrium x e of the inhomogeneous LCS (4.1) is equivalent to the linearly bounded stability (resp., global asymptotic/exponential stability) of the equilibrium z =0o f the homogeneous LCS

ż = Az + B •β e v, 0 ≤ v ⊥ C β e • z + D β e β e v ≥ 0, (4.2)
which has a C 1 solution trajectory z(t, z 0 ) for every initial condition z 0 = z(0). Via this equivalence, the results in the previous sections can then be applied to yield sufficient conditions for the respective stability properties to hold for the inhomogeneous LCS (4.1).

Proposition 4.2. Let D be a P-matrix. The equilibrium x e of the LCS (4.1) is stable (resp., asymptotically/exponentially stable) if and only if z e =0is a linearly boundedly stable (resp., global asymptotically/exponentially stable) equilibrium of the homogeneous LCS (4.2).

Proof. Sufficiency. Suppose that z e = 0 is a linearly boundedly stable equilibrium of the homogeneous LCS (4.2). Hence there exists a constant η>0 such that for all solution trajectory z(t, z 0 ) of (4.2) satisfying z(0,z 0 )=z 0 , it holds that z(t, z 0 ) ≤ η z 0 for all (t, z 0 ) ∈ [0, ∞) ×ℜ n . We need to show that for every ε>0, a constant δ ε > 0 exists such that for all x 0x e <δ ε ⇒ lim sup t≥0 x(t, x 0 )x e <ε.T h e proof lies in showing that for x 0 sufficiently close to x e , the trajectory z(t, z 0 ) ≡ x(t, x 0 )x e , which has z(0,z 0 )=x 0x e ≡ z 0 , is a solution of the homogeneous LCS (4.2). Once the latter claim is established, the stability of x e f o l l o w s ;s od ot h e asymptotic and exponential stability. To prove the claim, let x 0 be given and let (z(t, z 0 ),v(t, z 0 )) be the unique solution trajectory of (4.2) satisfying z(0,z 0 )=z 0 ; it suffices to show that for all x 0 sufficiently close to x e , z(t, z 0 )=z(t, z 0 ) for all t ≥ 0. We do this by producing a suitable trajectory u(t, x 0 ) such that the pair (z(t, z 0 )+x e , u(t, x 0 )) satisfies (4.1); by the uniqueness of the solution to the latter LCS, we then deduce z(t, z 0 )=z(t, z 0 ) for all t ≥ 0 as desired. In turn, to produce the u(t, x 0 ) trajectory, let u β e (t, x 0 ) ≡ v(t, z 0 ), u γ e (t, x 0 ) ≡ 0, and u α e (t, x 0 ) ≡-(D α e α e ) -1 q α e + C α e • (z(t, z 0 )+x e )+D α e β e u β e (t, x 0 ) = u e α e -(D α e α e ) -1 C α e • z(t, z 0 )+D α e β e v(t, x 0 ) .

We have Note that both u e α e and q γ e + C γ e • x e + D γ e α e u e α e are positive. Being the Schur complement of a P-matrix, D β e β e is itself a P-matrix. Hence there exists a constant

q β e + C β e • (z(t, z 0 )+x e )+D β
L v > 0 such that v(t, z 0 ) ≤L v z(t, z 0 ) ≤L v η z 0 ∀ t ≥ 0,
where the second inequality is by the linearly bounded stability of the equilibrium z e = 0 for the homogeneous LCS (4.2). Consequently, provided that x 0 is sufficiently close to x e , or equivalently, that z 0 is sufficiently close to the origin, u α e (t, x 0 )a n d q γ e + C γ e • (z(t, z 0 )+x e )+D γ e α e u α e (t, x 0 )+D γ e β e u β e (t, x 0 ) remain positive for all t ≥ 0. Hence for all such x 0 , u(t, x 0 ) ∈ SOL(q + C(z(t, z 0 )+x e ),D) for all t ≥ 0. Since 0 = p + Ax e + Bu e = p + Ax e + B •α e u e α e = p + Ax e -B •α e (D α e α e ) -1 C α e • x e , we have

d(z(t, z 0 )+x e ) dt = Az(t, z 0 )+ Bv(t, z 0 ) =[A -B •α e ( D α e α e ) -1 C α e • ]z(t, z 0 ) +[B •β e -B •α e ( D α e α e ) -1 D α e β e ]v(t, z 0 ) = p + A( z(t, z 0 )+x e )+B u(t, x 0 ).
We have therefore verified all the required conditions for the pair (z(t, z 0 )+x e , u(t, x 0 )) to be a solution of (4.1). This establishes the sufficiency part of the proposition. Necessity. Suppose that x e is a stable equilibrium of the LCS (4.1). We may choose ε>0 sufficiently small such that for all x satisfying xx e <ε ,w eh a v e u α e (x) > 0a n d( q + Cx + Du(x)) γ e > 0. Corresponding to such an ε,l e tδ ε > 0b e such that x 0x e <δ ε ⇒ x(t, x 0 )x e <εfor all t ≥ 0. Consequently, for any such x 0 ,w eh a v e[ q + Cx(t, x 0 )+Du(x(t, x 0 ))] α e = 0 and u γ e (x(t, x 0 )) = 0. Since (q + Cx e + Du e ) α e = 0, we deduce C α e • ( x(t, x 0 )x e )+D α e α e ( u(x(t, x 0 ))u e ) α e + D α e β e u β e (t, x 0 )=0, which yields

(u(x(t, x 0 )) -u e ) α e = -(D α e α e ) -1 C α e • (x(t, x 0 ) -x e )+D α e β e u β e (t, x 0 ) . (4.3)
Notice that the directional derivative f ′ (x; •) is a piecewise linear function of the second argument; in particular, it is positively homogeneous. In general, a piecewise affine function is not differentiable. Thus the ODE ẋ = f (x) has a nonsmooth righthand side. The following result is the promised generalization of Proposition 4.2; the proof is essentially an abstraction of that of the cited proposition.

Proposition 4.5. Let f : ℜ n →ℜ n be a piecewise affine function with f (x e )=0. The equilibrium x e is stable (resp., asymptotically/exponentially stable) for the ODE ẋ = f (x) if and only if z e =0is a linearly boundedly stable (resp., asymptotically/exponentially stable) equilibrium of the ODE ż = f ′ (x e ; z).

Proof.S i n c ef is piecewise affine on ℜ n , it is globally Lipschitz continuous there. Hence the initial-value ODE ẋ = f (x),x (0) = x 0 (4.4) has a unique solution x(t, x 0 ) for all x 0 ∈ℜ n . The same is true of the ODE ż = f ′ (x e ; z),z (0) = z 0 (4.5) for all z 0 ∈ℜ n . Suppose that x e is a locally stable equilibrium of the ODE ẋ = f (x). Let ε>0 be such that f (x)=f ′ (x e ; xx e ) for all x satisfying xx e <ε . Corresponding to this ε,l e tδ ε > 0 be such that x 0x e <δ ε ⇒ x(t, x 0 )x e <ε for all t ≥ 0. It follows that z(t, z 0 ) ≡ x(t, x 0 )x e is the unique solution trajectory of (4.5) satisfying z(0,z 0 )=z 0 ≡ x 0x e . Hence z e = 0 is a linearly bounded stable equilibrium of (4.5), by the positive homogeneity of f ′ (x e ; •). The other assertions of the proposition can be proved similarly.

Instead of showing how Proposition 4.2 is a special instance of Proposition 4.5, we consider the more general inhomogeneous DAVI, ẋ = p + Ax + Bu, u ∈ SOL(K, q + Cx,D), (4.6) where K is a polyhedron in ℜ m . We assume that the pair (K, D)i s" c o h e r e n t l y oriented" [START_REF] Robinson | Normal maps induced by linear transformations[END_REF][START_REF] Facchinei | Finite-Dimensional Variational Inequalities and Complementarity Problems[END_REF]. This condition is necessary and sufficient for the AVI (K, q, D)t o have a unique solution for all vectors q ∈ℜ m ; moreover, under this condition, such a solution function is necessarily a piecewise affine function of q. Hence, letting u(x) be the unique element of SOL(K, q + Cx,D), the DAVI (4.6) is equivalent to the ODE with a piecewise affine right-hand side: ẋ = p + Ax + Bu(x). (Incidentally, this equivalence remains valid if the coherent orientation of the pair (K, D)i sw e a k e n e d to the condition that BSOL(K, q + Cx,D) is a singleton for all x ∈ℜ n ; nevertheless this weakening necessitates a modification of the following discussion about the directional derivatives, which becomes much more involved. For simplicity, we continue to assume the coherent orientation condition.) If (K, D) is coherently oriented, then the directional derivative u ′ (x; dx) of the solution function u(x) along a direction dx ∈ℜ n is the unique solution v to the generalized LCP

C(x) ∋ v ⊥ Cdx + Dv ∈C(x) * ,
where C(x) is the "critical cone" of the AVI (K, q + Cx,D)a tt h es o l u t i o nu(x), and C(x) * is the dual of C(x); specifically, C(x) ≡T(K; u(x)) ∩ (q + Cx+ Du(x)) ⊥ ,w h e r e T (K; u(x)) denotes the tangent cone of K at u(x) ∈ K (as in convex analysis [START_REF] Rockafellar | Convex Analysis[END_REF]) and the superscript denotes the orthogonal complement. It should be pointed out that both C(x) and its dual are polyhedral cones. For details of these results, we refer the reader to [15, Volume I, section 4.3].

Applying Proposition 4.5 to the DAVI (4.6), we obtain the following result, which requires no further proof.

Corollary 4.6. Let K be a polyhedron in ℜ m . Suppose that the pair (K, D) is coherently oriented. Let x e satisfy 0=p + Ax e + Bu(x e ). The equilibrium x e of (4.6) is stable (resp., asymptotically/exponentially stable) if and only if z e =0is a linearly boundedly stable (resp., asymptotically/exponentially stable) equilibrium of the differential complementarity system

ż = Az + Bv, C(x e ) ∋ v ⊥ Cz + Dv ∈C(x e ) * , (4.7)
where C(x e ) ≡T(K; u(x e )) ∩ (q + Cx e + u(x e )) ⊥ .

As mentioned in the beginning of this section, it is possible to extend the Lyapunov stability results for the LCS to the generalized LCS (4.7). Instead of repeating the derivation, we proceed to the other major topic of this paper, to be addressed in the next section. There, we establish a partial generalization of Proposition 4.2 and Corollary 4.6 that deals with the exponential stability of nonlinear systems; see Propositions 5.7 and 5.10.

Exponential stability of nonlinear systems via a converse theorem.

So far our development has been restricted to systems with linear structures. In this section, we extend our treatment to nonlinear systems via the so-called Lyapunov indirect method of "first-order approximation." The results in this section are of the exponential stability type. Due to the nonsmoothness of the solution function to the LCP/AVI, it seems difficult to develop an asymptotic stability theory for nonlinear systems without relying on exponential stability.

The cornerstone of the extended treatment of nonlinear systems is a converse theorem for the exponential stability of an equilibrium to an ODE with a B-differentiable right-hand side that is not F(réchet)-differentiable. In general, if the right-hand side of the ODE is not F-differentiable, the solution map of the ODE is not a differentiable function of the initial condition; nevertheless, the latter map remains B-differentiable, provided that the right-hand function of the ODE is so. This is formally stated in the following result whose proof can be found in the recent paper [START_REF] Pang | Solution dependence on initial conditions in differential variational inequalities[END_REF]Theorem 7].

Lemma 5.1. Suppose that for a given ξ ∈ℜ n , f is B-differentiable in a neighborhood of a solution trajectory x(t, ξ) of the ODE (4.4) for t ∈ [0,T].F o r e a c h t ∈ [0,T], the solution map x(t, •) of the ODE (4.4) is B-differentiable at ξ; the directional derivative

x ′ ξ (t, ξ; η) ≡ lim τ ↓0
x(t, ξ + τη)x(t, ξ) τ of x(t, •) at ξ along the direction η is the unique solution y(t) to the variational equation ẏ(t)=f ′ (x(t, ξ); y(t)), y(0) = η.

The following result gives a necessary and sufficient condition for an equilibrium of the ODE (4.4) to be exponentially stable in terms of the existence of a nonsmooth Lyapunov function satisfying certain conditions. Since the latter function is not necessarily differentiable, the result does not follow from standard system theory; see, e.g., [START_REF] Khalil | Nonlinear Systems[END_REF]Chapter 3]. Moreover, whereas the proof is inspired by that of Theorem 3.12 in the cited reference, some details are different as the Lyapunov function is not continuously differentiable. In particular, conditions (b) and (c) are normally stated in terms of the F-derivatives of V ; here they are expressed in terms of directional derivatives.

Theorem 5.2. Suppose that f is Lipschitz continuous in a neighborhood N 0 of the origin and that f (0) = 0. The following two statements hold.

(I) If there exist positive constants c 1 <c 2 ,a n dc 3 , a neighborhood N⊆N 0 of x e =0 , and a Lipschitz continuous and directionally differentiable function V in N such that (a) c 1 x 0 2 ≤ V (x 0 ) ≤ c 2 x 0 2 for all x 0 ∈N, (b) V ′ (x 0 ; f (x 0 )) ≤-c 3 x 0 2 for all t ≥ 0 and all x 0 ∈N, then x e =0is an exponentially stable equilibrium of the ODE (4.4). (II) Conversely, if x e =0is an exponentially stable equilibrium of the ODE (4.4) and if f is additionally directionally differentiable in N 0 , then there exist positive constants c 1 , c 2 , c 3 ,a n dc 4 , a neighborhood N⊆N 0 of x e =0 ,a n d a Lipschitz continuous and directionally differentiable function V in N such that (a), (b),a n d(c) hold, where (c) |V ′ (x 0 ; z) -V ′ (x 0 ; z ′ )|≤c 4 x 0 zz ′ for all x 0 ∈N and all z, z ′ in ℜ n . Proof. Without loss of generality, we take N to be an open ball centered at the origin and with radius r>0. We claim that under the assumption in (I), by defining the neighborhood

N ′ ≡{z ∈ℜ n : z ≤ c 1 /c 2 r/2 },
a unique solution trajectory x(t, x 0 ) exists satisfying the ODE (4.4) for all t ≥ 0 and all x 0 ∈N ′ ;m o r e o v e r , x(t, x 0 ) <r / 2 for all such pairs (t, x 0 ). Notice that the existence and uniqueness of such a trajectory do not follow directly from basic ODE theory because f is assumed to be Lipschitz continuous only in N 0 and not everywhere. Let x 0 ∈N ′ ; clearly x 0 <r/2 because c 1 <c 2 . Hence there is a time t 0 > 0 such that the trajectory x(t, x 0 ) exists and is unique for all t ∈ [0,t 0 ]. We claim that x(t, x 0 ) <r / 2 for all t in the domain of definition of the trajectory. Assume for the sake of contradiction that there exists t ∈ (0,t 0 ] such that x( t, x 0 ) = r/2 and that x(t, x 0 ) <r / 2 for all t ∈ [0, t ). For all ε>0 sufficiently small, we can write

V (x( t, x 0 )) -V (x 0 )= t-ε 0 V ′ (x(s, x 0 ); f (x(s, x 0 ))) ds + t t-ε V ′ (x(s, x 0 ); f (x(s, x 0 ))) ds < 0,
where the first summand in the right-hand side is nonpositive by (b) and the second summand is negative because x(s, x 0 ) is near r/2 > 0 for all s ∈ [ tε, t]. Hence,

c 1 x( t, x 0 ) 2 ≤ V (x( t, x 0 )) <V(x 0 ) ≤ c 2 x 0 2 ,
which implies x( t, x 0 ) 2 <r 2 /4, which is a contradiction. Thus, x(t, x 0 ) <r/2f o r all t ∈ [0,t 0 ]. Let t * ≡ sup{ t ≥ t 0 : the trajectory x(t, x 0 ) exists, is unique, and satisfies x(t, x 0 ) <r/2 for all t ∈ [0, t ] }.

It follows that there exists ε>0 such that for all t ∈ [0,t * ), the trajectory x(t, x 0 )can be continued beyond time t for at least ε duration. Since ε is independent of t,wemust have t * = ∞. Hence, the trajectory x(t, x 0 ) exists, is unique, and remains in N for all t ≥ 0. By condition (b), the trajectory x(t, x 0 )m ustsatisfyV ′ (x(t, x 0 ); f (x(t, x 0 ))) ≤ -c 3 x(t, x 0 ) 2 for all t ≥ 0 and all x 0 ∈N ′ . From this point on, we can follow the same line of proof as in Theorem 3.1(b) to complete the proof of the exponential stability of x e . This establishes part (I) of the theorem.

Conversely, to show (II), let N⊆N 0 be a subneighborhood of the equilibrium such that for some positive constants ν and κ, x(t, x 0 ) ≤κe -νt x 0 for all t ≥ 0 and all x 0 ∈N and that x(t, x 0 ) ∈N 0 for all such pairs (t, x 0 ). Define

V (z) ≡ T 0
x(τ, z) T x(τ, z) dτ, z ∈N, where the upper limit T>0 will be determined later. It is clear that V is Lipschitz continuous in N . To show that V is directionally differentiable, we need to show that the limit

lim τ ↓0 V (z + τh) -V (z) τ exists for all h ∈ℜ n .W eh a v e V (z + τh) -V (z)= T 0 ( x(s, z + τh) -x(s, z)) T ( x(s, z + τh)+x(s, z)) ds.
By the Lipschitz property of x(τ, •) and the exponential bound of x(τ, z), it follows by the Lebesgue convergence theorem that we can interchange the integral with the limit as τ ↓ 0a n do b t a i n lim

τ ↓0 V (z + τh) -V (z) τ =2 T 0 x ′ ξ (s, z; h) T x(s, z) ds,
where we have used Lemma 5.1 to justify the well-definedness of the directional derivative x ′ ξ (τ, z; h) (this is where the directional differentiability of f is needed). In particular, we have

V ′ (x 0 ; f (x 0 )) = 2 T 0 x ′ ξ (s, x 0 ; f (x 0 )) T x(s, x 0 ) ds.
By Lemma 5.1, x ′ ξ (s, x 0 ; f (x 0 )) is the unique function y(s) satisfying ẏ(s)=f ′ (x(s, x 0 ); y(s)) and y(0) = f (x 0 ). It is easy to verify that the function y(s) ≡ f (x(s, x 0 )) satisfies the latter initial-value ODE because ẋ(s, x 0 )=f (x(s, x 0 )). Hence x ′ ξ (s, x 0 ; f (x 0 )) = f (x(s, x 0 )); thus

V ′ (x 0 ; f (x 0 )) = 2 T 0 f (x(τ, x 0 )) T x(τ, x 0 ) dτ =2 T 0 ẋ(τ, x 0 ) T x(τ, x 0 ) dτ = x(T,x 0 ) 2 -x 0 2 ≤-(1 -κ 2 e -2νT ) x 0 2 .
Choosing T ≡ (ln(2κ 2 ))/(2ν), we deduce V ′ (x 0 ; f (x 0 )) ≤x 0 2 /2. Hence (b) holds with c 3 ≡ 1/2. To prove (a), note that

V (z) ≤ T 0 κ 2 e -2ντ z 2 dτ ≤ κ 2 2ν 1 -e -2νT z 2 .
Moreover, letting L>0 be a Lipschitz constant of f in N , and by shrinking N if necessary, we have x(t, x 0 ) ≥e -Lt x 0 for all (t, x 0 ) ∈ [0, ∞) ×N. Consequently, we can deduce

V (z) ≥ 1 -e -2LT 2L z 2 ∀ z ∈N.
Hence (a) holds with appropriate positive constants c 1 and c 2 . To prove (c), note that

V ′ (x; z) -V ′ (x; z ′ ) = lim τ ↓0 V (x + τz) -V (x + τz ′ ) τ .
Substituting the definition of the function V and taking absolute values, we deduce

| V ′ (x 0 ; z) -V ′ (x 0 ; z ′ ) | ≤ T 0 lim τ ↓0
x(s, x 0 + τz)x(s, x 0 + τz ′ ) x(s, x 0 + τz)+x(s, x 0 + τz ′ ) τ ds

≤ c 4 z -z ′ x 0
for some constant c 4 > 0 ,w h e r ew eh a v eu s e dt h eL i p s c h i t zc o n t i n u i t yo ft h es o l u t i o n map x(t, •) and the finiteness of the time T . We call a B-differentiable function V satisfying conditions (a), (b), and (c) in Theorem 5.2 a B-differentiable Lyapunov function for the nonsmooth ODE (4.4) at its equilibrium. An important consequence of Theorem 5.2 is the next perturbation result pertaining to the persistence of the exponential stability property. Notice that while the nominal function f is required to be B-(and thus directionally) differentiable, the perturbed function g is required to be only locally Lipschitz continuous. This observation is important as we see in the subsequent Corollary 5.5 that not requiring the perturbed function g to be directionally differentiable has its benefit.

Corollary 5.3. Let f be Lipschitz continuous and directionally differentiable in a neighborhood N 0 of an equilibrium x e of f . Suppose that x e is exponentially stable for the ODE (4.4). For every function g such that g(x e )=0, g is Lipschitz continuous in N 0 ,a n d

lim x→x e f (x) -g(x)
xx e =0; (5.1)

x e is an exponentially stable equilibrium of the ODE: ẋ = g(x).

Proof. Without loss of generality, we may take x e =0. LetV be a B-differentiable Lyapunov function for the ODE (4.4). According to part (I) of Theorem 5.2 applied to the function g, it suffices to show that a neighborhood N ′ ⊆N and a constant c ′ 3 > 0 exist such that V ′ (x 0 ; g(x 0 )) ≤c ′ 3 x 0 2 for all x 0 ∈N ′ . By properties (b) and (c) of V ,w eh a v e

V ′ (x 0 ; g(x 0 )) = V ′ (x 0 ; f (x 0 )) + [ V ′ (x 0 ; g(x 0 )) -V ′ (x 0 ; f (x 0 )) ] ≤-c 3 x 0 2 + c 4 x 0 f (x 0 ) -g(x 0 ) = -c 3 x 0 2 1 - c 4 c 3 f (x 0 ) -g(x 0 ) x 0 .
By (5.1), the existence of N ′ and c ′ 3 with the desired property is clear. Remark 5.1. The limit condition (5.1) postulates that f and g are "first-order approximations" of each other near x e . This condition, along with the directional differentiability of f at x e , implies that the perturbed function g is directionally differentiable at x e also, but not necessarily at other points.

We present a consequence of Corollary 5.3 that pertains to the ODE where the right-hand side is a "composite nonsmooth" function of a particular kind. Specifically, let f (x) ≡ Φ(x, u(x)), where Φ(x, y) is a B-differentiable function of two arguments (x, y) ∈ℜ n+m and u(x) is a B-differentiable function of x. We first state a lemma pertaining to the B-differentiability of such a function f . Lemma 5.4. Let Φ:ℜ n+m →ℜ ℓ be Lipschitz continuous in a neighborhood of (x 0 ,y 0 ) ∈ℜ n+m . Suppose that Φ(•,y 0 ) and Φ(x 0 , •) are directionally (and thus B-) differentiable at x 0 and y 0 , respectively. If

lim (x 0 ,y 0 ) =(x,y)→(x 0 ,y 0 ) Φ(x, y) -Φ(x 0 ,y) -(Φ(•,y 0 )) ′ (x 0 ; x -x 0 ) x -x 0 =0, (5.2)
then Φ is directionally (and thus B-) differentiable at (x 0 ,y 0 ) and Φ ′ ((x 0 ,y 0 ); (dx, dy)) = ( Φ(•,y 0 )) ′ (x 0 ; dx)+(Φ(x 0 , •)) ′ (y 0 ; dy). (5.3)

Thus, if u : ℜ n →ℜ m is B-differentiable at x 0 ,t h e ns oi sf (x) ≡ Φ(x, u(x)) and f ′ (x 0 ; z)=(Φ(•,u(x 0 )) ) ′ (x 0 ; z)+(Φ(x 0 , •)) ′ (u(x 0 ); u ′ (x 0 ; z)).
Proof. The B-differentiability of Φ at (x 0 ,y 0 ) and the directional derivative formula (5.3) follow from [START_REF] Robinson | An implicit-function theorem for a class of nonsmooth functions[END_REF]; see also [START_REF] Facchinei | Finite-Dimensional Variational Inequalities and Complementarity Problems[END_REF]Exercise 3.7.4]. The B-differentiability of the composite function f and the formula for its directional derivative f ′ (x 0 ; z) follow from the chain rule of B-differentiation; see [START_REF] Facchinei | Finite-Dimensional Variational Inequalities and Complementarity Problems[END_REF]Proposition 3.1.6].

Remark 5.2. The limit (5.2) is essential for (5.3) to hold; without the former, the latter need not hold. See [START_REF] Facchinei | Finite-Dimensional Variational Inequalities and Complementarity Problems[END_REF].

The next result formally establishes the above-mentioned consequence of Corollary 5.3.

Corollary 5.5. Let u : ℜ n →ℜ m be B-differentiable at x e ∈ℜ n and let Φ:ℜ n+m →ℜ n be Lipschitz continuous in a neighborhood of (x e ,u e ) ∈ℜ n+m ,w h e r e u e ≡ u(x e ) and (x e ,u e ) satisfies Φ(x e ,u e )=0. Suppose that Φ(•,u e ) and Φ(x e , •) are directionally differentiable at x e and u e , respectively, and that lim (x e ,u e ) =(x,u)→(x e ,u e ) Φ(x, u) -Φ(x e ,u) -(Φ(•,u e )) ′ (x e ; xx e )

xx e =0.

If the equilibrium x e is exponentially stable for the ODE (4.4),wher ef (x) ≡ Φ(x, u(x)), then z e =0is an exponentially stable equilibrium of the homogeneous ODE ż = (Φ( We further specialize Corollary 5.5 to the case where Φ is F-differentiable and u is piecewise smooth. Specifically, we say that a function Ψ : ℜ n →ℜ m is PC 1 (piecewise C 1 )n e a rap o i n tx 0 ∈ℜ n if there exist a neighborhood N of x 0 and finitely many C 1 functions {f 1 ,... ,f k } near x 0 for some positive integer k such that Ψ(x) ∈{ f 1 (x),... ,f k (x)} for all x ∈N . Basic properties of the family of PC 1 functions can be found in [START_REF] Scholtes | Introduction to piecewise differentiable equations[END_REF][START_REF] Facchinei | Finite-Dimensional Variational Inequalities and Complementarity Problems[END_REF]. In particular, it is known that a PC 1 function must be B-differentiable. Based on this remark, the result below does not require further proof.

Corollary 5.6. Let u : ℜ n →ℜ m be PC 1 near x e ∈ℜ n and let Φ:ℜ n+m →ℜ n be F-differentiable in a neighborhood of (x e ,u e ) ∈ℜ n+m ,w h e r eu e ≡ u(x e ) and (x e ,u e ) satisfies Φ(x e ,u e )=0 .L e tf (x) ≡ Φ(x, u(x)). The following statements are equivalent.

(a) x e is an exponentially stable equilibrium of the ODE (4. It is interesting to compare Corollary 5.6 with Proposition 4.5. The corollary pertains only to exponential stability, whereas the proposition deals with asymptotic stability as well. The difference between the two results is that the former proposition concerns a piecewise linear ODE, whereas the corollary concerns an ODE with a PC 1 right-hand side, for which there is no such exact approximation result as Lemma 4.4.

5.1. Strongly regular DVIs. We wish to apply Corollary 5.6 to the following differential variational inequality (DVI) [START_REF] Pang | Differential variational inequalities[END_REF]:

ẋ = F (x, u), u ∈ SOL(K, H(x, •)), (5.5)
where K is a closed convex set in ℜ m and F : ℜ n+m →ℜ n and H : ℜ n+m →ℜ m are continuously differentiable functions in a neighborhood of a given pair (x e ,u e ) ∈ℜ n+m that satisfies F (x e ,u e )=0a n du e ∈ SOL(K, H(x e , •)), with the latter notation meaning that u e is a solution of the variational inequality (VI) defined by the pair (K, H(x e , •)); i.e., u e ∈ K and ( uu e ) T H(x e ,u e ) ≥ 0 ∀ u ∈ K.

The key assumption to be made here is that u e is a "strongly regular" solution of the VI (K, H(x e , •)). The latter is a well-known property in the theory of finitedimensional VIs/CPs; it was introduced by Robinson [START_REF] Robinson | Strongly regular generalized equations[END_REF]; see also [START_REF] Facchinei | Finite-Dimensional Variational Inequalities and Complementarity Problems[END_REF]. We have employed this property in several recent studies of the DVI [START_REF] Pang | Solution dependence on initial conditions in differential variational inequalities[END_REF][START_REF] Pang | Strongly regular differential variational systems[END_REF] and will use it here as the main setting to facilitate the application of the previous results in the stability analysis of the given equilibrium pair (x e ,u e ). Noticethatweavoidassuming the strong monotonicity of the function H(x, •), which is unnecessarily restrictive in general; see nevertheless the discussion about the functional evolutionary variational inequality (5.8).

Under the strong regularity assumption, it follows that there exist neighborhoods U of u e and V of x e , and a Lipschitz continuous function u : V→Usuch that for every x ∈V , u(x) is the unique solution of the VI (K, H(x, •)) belonging to U and u(x e )=u e . Without further restricting the set K, the VI solution map u(x)i sn o t necessarily directionally differentiable; nevertheless, for a large class of closed convex sets K (such as a polyhedron), u(x)i saP C 1 [START_REF] Pang | Piecewise smoothness, local invertibility, and parametric analysis of normal maps[END_REF] (or a "semismooth" [START_REF] Pang | Semismooth homeomorphisms and strong stability of semidefinite and Lorentz complementarity problems[END_REF]) function near x e . For these special sets, the DVI (5.5) is therefore, locally near the pair (x e ,u e ), equivalent to an ODE with a composite nonsmooth right-hand side, ẋ = F (x, u(x)), to which Corollary 5.5 is applicable. Before detailing this application, we make an important remark regarding this approach. Namely, corresponding to a given x e ∈ℜ n , there may be multiple vectors u e satisfying the above-mentioned properties, each of which leads to a particular ODE that could be quite distinct from another. More interestingly, x e may be exponentially stable with respect to one resulting ODE but not to another. (This is illustrated in Example 5.1.) In other words, the "stability" of x e is linked to the particular solution of the VI (K, H(x e , •)). For future research, it may be of interest to extend this individual ODE-based stability theory for the nonlinear DVI (5.5) to a broader theory analogous to that for the LCS (2.1) or its affine generalization, the DAVI (4.6), where we have relied on the key assumption that BSOL(K, q + Cx,D) is a singleton for all x ∈ℜ n . In such affine cases, in spite of the possible multiplicity of solutions to the AVIs (K, q+Cx,D), the singleton assumption, or equivalently, the assumption of a unique C 1 trajectory x(t, x 0 ), leads to a unique ODE with a piecewise linear (thus Lipschitz) right-hand side to which Definition 2.3 applies. Incidentally, there are multiple C 1 x-trajectories in the example below.

Example 5.1. Consider the following nonlinear complementarity system (NCS):

ẋ = x( -1+2sinu ), 0 ≤ u ⊥ ( x +1)(1-sin u ) ≥ 0, (5.6)
where x ∈ℜand u ∈ℜ . It is clear that x e = 0 is an equilibrium. For any x>-1, the solutions of the associated nonlinear complementarity problem (NCP) 0 ≤ u ⊥ (x + 1)(1sin u) ≥ 0a r eu = 0 and u =( 2 k +1/2)π for k ≥ 0. Each of these solutions is strongly regular. The unique solution trajectory to (5.6) that is near the pair (x e ,u e )=( 0 , 0) initially is (x(t, x 0 ),u(t, x 0 )) = (x 0 e -t , 0) for all t ≥ 0. The equilibrium x e = 0 is clearly exponentially stable for the resulting ODE, which is ẋ = -x. In contrast, the unique solution trajectory to (5.6) that is near the pair (x e , u e )=(0,π/2) initially is (x(t, x 0 ),u(t, x 0 )) = (x 0 e t ,π/2) for all t ≥ 0. The same equilibrium x e = 0 is clearly unstable for the resulting ODE, which is ẋ = x.

Returning to the general discussion, we fix an implicit VI solution function u(x) as defined above. For simplicity, we focus on the case where K is a polyhedron. It follows that u(x)i saP C 1 function of x ∈V.L e tC(x e ) ≡T(K; u(x e )) ∩ H(x e ,u e ) ⊥ be the critical cone of the linearly constrained VI (K, H(x e , •)). It is known that the directional derivative u ′ (x e ; z) of the VI solution map u(x) along the direction z is the unique solution v of the generalized LCP: C(x e ) ∋ v ⊥ J x H(x e ,u e )z + J u H(x e ,u e )v ∈C(x e ) * .

Based on this characterization of the directional derivative, define the following gen-eralized LCS that extends (4.7) to the nonlinear case: ż = J x F (x e ,u e )z + J u F (x e ,u e )v, C(x e ) ∋ v ⊥ J x H(x e ,u e )z + J u H(x e ,u e )v ∈C(x e ) * .

(5.7) Proposition 5.7. Let K be polyhedral and let F and H be C 1 in a neighborhood of the pair (x e ,u e ),w h e r eF (x e ,u e )=0and u e is a strongly regular solution of the VI (K, H(x e , •)).L e tV×U and u : V→Ube, respectively, the neighborhood of (x e ,u e ) and the solution map associated with the strong regularity of u e . The two statements below are equivalent.

(a) x e is an exponentially stable equilibrium of the ODE: ẋ = F (x, u(x)).

(b) z e =0is an exponentially stable equilibrium of the generalized LCS (5.7).

Proof. This follows readily from Corollary 5.6. We illustrate Proposition 5.7 with a functional evolutionary variational inequality (FEVI) of the following kind: ẋ =Π K (x -Φ(x))x, (5.8) where Π K denotes the Euclidean projection onto the polyhedron K and Φ is a C 1 function defined on ℜ n . The equilibria of this DVI are precisely the solutions of the finite-dimensional VI (K, Φ). Incidentally, there are other dynamical systems whose equilibria are solutions of the VI. The above FEVI is different from the kind of evolutionary variational problems studied in the literature of differential inclusions which rely on a "generalized equation" formulation of the VI; see, e.g., [START_REF] Goeleven | Stability and instability matrices for linear evolution variational inequalities[END_REF]. A distinct advantage of the FEVI (5.8) over the latter kind is that the solution trajectories of (5.8) are all C 1 because the right-hand side is a Lipschitz function of x, whereas those based on the differential inclusion formulation need not be so. In addition, when started at a vector in K, a trajectory of (5.8) will remain in K. The last assertion is established in the result below.

Proposition 5.8. Let K b eaclose dc onvexsetandΦ be Lipschitz continuous on K.L e tx(t, x 0 ) denote the unique solution trajectory of (5.8) initiated at x(0) = x 0 . If x 0 ∈ K,t h e nx(t, x 0 ) ∈ K for all t ≥ 0.

Proof. Considering (5.8) as an ODE with an inhomogeneous right-hand side, we have x(t, x 0 )=e -t x 0 + t 0 e -(t-τ ) Π K x(τ, x 0 ) -Φ(x(τ, x 0 )) dτ = e -t x 0 +(1-e -t ) t 0 e τ Π K x(τ, x 0 ) -Φ(x(τ, x 0 )) dτ e t -1 = e -t x 0 +(1-e -t ) t 0 e τ Π K x(τ, x 0 ) -Φ(x(τ, x 0 )) dτ t 0 e τ dτ . (5.9) Since x(t, x 0 ) is well defined for all t,Π K x(τ, x 0 ) -Φ(x(τ, x 0 )) is continuous in τ . Hence, we can represent the integrals in (5.9) by Riemann sums: I ≡ t 0 e τ Π K x(τ, x 0 ) -Φ(x(τ, x 0 )) dτ t 0 e τ dτ = lim k→∞ k i=1 e s i Π K x(s i ,x 0 ) -Φ(x(s i ,x 0 ))

t k k i=1 e s i t k
, where s i is any point in the subinterval [ (i-1) k t, i k t]. Since K is a convex set, the vector k i=1 e s i t k

-1 k i=1 e s i Π K x(s i ,x 0 ) -Φ(x(s i ,x 0 )) t k , which is a convex combination of vectors in K, belongs to K for all positive integers k. By the closedness of K, it follows that the vector I, and thus x(t, x 0 ), also belongs to K.

The system (5.8) is a special DVI with F (x, u) ≡ u-x and H(x, u) ≡ u-x+Φ(x). Since H(x, •) is strongly monotone, the strong regularity condition holds trivially. Moreover, by the chain rule of B-differentiation, we have, letting u(x) ≡ Π K (x-Φ(x)), u ′ (x; z)=Π C (z -JΦ(x)z), where C≡T(K; u(x)) ∩ (u(x)x +Φ(x)) ⊥ is the critical cone of the polyhedron K at the projected vector u(x); see [START_REF] Facchinei | Finite-Dimensional Variational Inequalities and Complementarity Problems[END_REF]Chapter 4]. Consequently, the first-order LCS (5.7), which becomes ż =Π C (z -JΦ(x)z)z, is a functional evolutionary version of the finite-dimensional generalized LCP C∋z ⊥ JΦ(x)z ∈C * of the same kind as (5.8). Notice that if x ∈ SOL(K, Φ) so that u(x)=x,t h e nC = T (K, x) ∩ Φ(x) ⊥ coincides with the critical cone of the VI (K, Φ) at the solution x.

Summarizing the above discussion and invoking Proposition 5.7, we obtain the following result for the FEVI (5.8).

Corollary 5.9. Let K be a polyhedron and let Φ:ℜ n →ℜ n be C 1 .As o l u t i o n x e ∈ SOL(K, Φ) is exponentially stable for the FEVI (5.8) if and only if the origin is an exponentially stable equilibrium for the linearized FEVI: ż =Π C (z -JΦ(x e )z)z, where C≡T(K; x e ) ∩ Φ(x e ) ⊥ .

Next, we specialize Proposition 5.7 to the NCS ẋ(t)=F (x(t),u(t)), 0 ≤ u(t) ⊥ H(x(t),u(t)) ≥ 0, (5.10) which is a special case of (5.5) with K = ℜ m + .L e t( x e ,u e ) be as specified above. The strong regularity of u e can be characterized by introducing the three fundamental index sets (α e ,β e ,γ e ) associated with the pair (x e ,u e )( c f .t h eL C Sw i t haP -m a t r i x in section 3): α e = { i : u e i > 0=H i (x e ,u e ) }, β e = { i : u e i =0=H i (x e ,u e ) }, γ e = { i : u e i =0<H i (x e ,u e ) }. According to these sets, we can partition the (partial) Jacobian matrix J u H(x e ,u e ) as follows:

J u H(x e ,u e ) ≡ ⎡ ⎢ ⎣ J u α e H α e (x e ,u e ) J u β e H α e (x e ,u e ) J u γ e H α e (x e ,u e ) J u α e H β e (x e ,u e ) J u β e H β e (x e ,u e ) J u γ e H β e (x e ,u e ) J u α e H γ e (x e ,u e ) J u β e H γ e (x e ,u e ) J u γ e H γ e (x e ,u e ) ⎤ ⎥ ⎦ , where J u α H β denotes the matrix of partial derivatives [∂H j /∂u i ] (i,j)∈α×β .I ti sk n o w n that u e is a strongly regular solution of the NCP 0 ≤ u ⊥ H(x e ,u) ≥ 0 (5.11) if and only if (a) the principal submatrix J u α e H α e (x e ,u e ) is nonsingular, and (b) the Schur complement D β e β e ≡ J u β e H β e (x e ,u e ) -J u α e H β e (x e ,u e ) J u α e H α e (x e ,u e ) -1 J u β e H α e (x e ,u e ) (5.12) is a P-matrix. Moreover, for every z ∈ℜ n , the directional derivative u ′ (x e ; z)i st h e unique vector u satisfying u γ e = 0 and The results in section 3 can surely be applied to (5.13) to yield sufficient conditions for statement (b) of the following proposition to hold, whose proof follows readily from Proposition 5.7.

Proposition 5.10. Let F and H be C 1 in a neighborhood of the pair (x e ,u e ), where F (x e ,u e )=0and u e is a strongly regular solution of the NCP (5.11).L e t V×U and u : V→Ube, respectively, the neighborhood of (x e ,u e ) and the solution map associated with the strong regularity of u e . The following two statements are equivalent.

(a) x e is an exponentially stable equilibrium of the ODE ẋ = F (x, u(x)).

(b) z e =0is an exponentially stable equilibrium of the homogeneous LCS (5.13).

6. Concluding remarks. Based on the combined tools of contemporary finite dimensional LCPs and VIs/CPs and classical Lyapunov stability theory for smooth dynamical systems, we have obtained many stability results for the LCS and its nonlinear generalizations. Part of the novelty of our analysis is the employment of a nontraditional Lyapunov function in both the system state and the auxiliary algebraic variable, which leads to a nondifferentiable Lyapunov function of the state alone. We speculate that this approach might be useful in other contexts, such as in the convergence analysis of iterative algorithms for solving finite-dimensional variational and optimization problems.

The results in this paper have left open some questions that are worthy of further investigation. Foremost among these is the question of whether asymptotic stability would imply exponential stability for an LCS satisfying the P-property. In this vein, we recall [START_REF] Smirnov | Introduction to the Theory of Differential Inclusions[END_REF]Lemma 8.2] which establishes such an implication for a linear selectionable DI. Yet, as we have noted a few times, the DI result is not applicable to the LCS. Nevertheless, the same implication may be valid for the LCS. Another interesting question is the persistence of asymptotic stability of a B-differentiable differential system under small perturbations; related to the latter question is whether there are analogues of the results in subsection 5.1 for asymptotic stability. Finally, the authors in [START_REF] Goeleven | Stability and instability matrices for linear evolution variational inequalities[END_REF] have established a very interesting necessary degree-theoretic condition for the asymptotic stability of an evolutionary variational inequality. We feel that a further degree-theoretic exploration of the LCS and the DVI is warranted.

  (a) Pqc Tcq T + rcc T is positive definite, (b) -(A T P + PA) and (3.20) are both positive semidefinite, (c) O(A T P + PA,A)={0}, (d) SO(-c T ,A-bc T ) ∩ O(N (1),A-bc T )=∅, then x e =0is an asymptotically stable equilibrium of the SISO LCS (3.19).I ft h e two matrices in (b) are positive definite, then x e =0is exponentially stable.

  α e (D α e α e ) -1 D α e β e , C β e • ≡ C β e • -D β e α e (D α e α e ) -1 C α e • , D β e β e ≡ D β e β e -D β e α e (D α e α e ) -1 D α e β e .

  e α e u α e (t, x 0 )+D β e β e u β e (t, x 0 ) = C β e • z(t, z 0 )+ D β e β e v(t, z 0 ) and q γ e + C γ e • (z(t, z 0 )+x e )+D γ e α e u α e (t, x 0 )+D γ e β e u β e (t, x 0 ) = q γ e + C γ e • x e + D γ e α e u e α e + C γ e • z(t, z 0 )+ D γ e β e v(t, x 0 ), where C γ e • ≡ C γ e • -D γ e α e (D α e α e ) -1 C α e • and D γ e β e ≡ D γ e β e -(D α e α e ) -1 D α e β e .

  4). (b) The ODE (4.4) has a B-differentiable Lyapunov function at x e . (c) z e =0is an exponentially stable equilibrium of the ODE ż = J x Φ(x e ,u e )z + J y Φ(x e ,u e )u ′ (x e ; z). (5.4) (d) The ODE (5.4) has a B-differentiable Lyapunov function at the origin.

J

  x H α e (x e ,u e )z + J α e H α e (x e ,u e ) u α e + J α e H β e (x e ,u e ) u β e =0, 0 ≤ u β e ⊥ J x H β e (x e ,u e )z + J β e H α e (x e ,u e ) u α e + J β e H β e (x e ,u e ) u β e ≥ 0, which, by the nonsingularity of J α e H α e (x e ,u e ), is equivalent to the standard LCP0 ≤ u β e ⊥ C β e • z + D β e β e u β e ≥ 0,where C β e • ≡ J x H β e (x e ,u e )-J u α e H β e (x e ,u e )[ J u α e H α e (x e ,u e )] -1 J x H α e (x e ,u e ). Define the matrices A ≡ J x F (x e ,u e ) -J u α e F (x e ,u e )[ J u α e H α e (x e ,u e )] -1 J x H α e (x e ,u e ), B •β e ≡ J u β e F (x e ,u e ) -J u α e F (x e ,u e )[ J u α e H α e (x e ,u e )] -1 J u β e H α e (x e ,u e ); consider the homogeneous LCS where the algebraic variable involves only the β ecomponents: ż = Az + B •β e u β e , 0 ≤ u β e ⊥ C β e • z + D β e β e u β e ≥ 0. (5.13)

  Exercise 1.8.10] for a general conversion scheme. In what follows, we illustrate how this conversion can be carried out by assuming that the matrix

	DE T
	-E	0
	is nonsingular. Letting w = -Eu, we can show that (2.4) is equivalent to
	ẋ

  •,u e )) ′ (x e ; z)+(Φ(x e , •)) ′ (u e ; u ′ (x e ; z)). The converse is valid if additionally the right-hand side of the latter ODE is directionally differentiable in z. ′ (x e ; x)+(Φ(x e , •)) ′ (u e ; u ′ (x e ; x)) ]/ x =0, and since the function z → (Φ(•,u e )) ′ (x e ; z)+(Φ(x e , •)) ′ (u e ; u ′ (x e ; z)) is positively homogeneous and Lipschitz continuous, the first assertion of the corollary follows from Corollary 5.3. So does the second.

	Proof.W eh a v e

f (x)=f ′ (x e ; xx e )+e(x)=(Φ(•,u e )) ′ (x e ; xx e ) +(Φ(x e , •)) ′ (u e ; u ′ (x e ; xx e )) + e(x), where lim x→x e e(x)/ x-x e =0. Sincex e is locally exponentially stable for the ODE (4.4) if and only if x e ≡ 0 is locally exponentially stable for the ODE ˙ x = f ( x + x e ), and since f (x e )=Φ(x e ,u e )=0,w eha v e lim x→0 [ f ( x + x e ) -(Φ(•,u e ))

Acknowledgment. We are grateful to two referees who have offered many constructive comments that have significantly improved the presentation of the paper.

The work of this author is partially supported by the European Community through the Information Society Technologies thematic program under the project SICONOS (IST-2001-37172). The research of this author was partially supported by National Science Foundation Focused Research Group grant DMS 0353216. The research of this author was partially supported by the National Science Foundation under grant DMS 0508986.

Substituting this and using (q + Cx e + Du e ) β e = 0, we deduce [ q + Cx(t, x 0 )+Du(x(t, x 0 )) ] β e = C β e • ( x(t, x 0 )x e )+ D β e β e u β e (t, x 0 ). Hence u β e (t, x 0 ) satisfies 0 ≤ u β e (t, x 0 ) ⊥ C β e • ( x(t, x 0 )x e )+ D β e β e u β e (t, x 0 ) ≥ 0 for all t ≥ 0. Furthermore,

Therefore, by the uniqueness of the solution trajectory to (4.2), we deduce that z(t, z 0 ) ≡ x(t, x 0 )x e is the unique solution trajectory satisfying (4.2) and z(0,z 0 )= z 0 ≡ x 0x e , along with the auxiliary algebraic trajectory v(t, z 0 ) ≡ u β e (x(t, x 0 )). Consequently, the stability, and thus the linearly bounded stability, of the equilibrium z e = 0 for (4.2) follows readily; so do the global and global exponential stability, provided that the equilibrium x e is, respectively, asymptotically and exponentially stable for (4.1). An interesting special case occurs when x e is nondegenerate; i.e., when the index set β e is empty. In this case, for all x sufficiently close to x e ,t h eL C P( q + Cx,D)i s equivalent to a system of linear equations. As such, intuitively speaking, the stability of x e can be established via classical system-theoretic results. A formal statement of this assertion is presented below whose proof follows easily from Proposition 4.2.

Corollary 4.3. Let D be a P-matrix. Suppose that the equilibrium x e of the LCS (4.1) is nondegenerate. The following statements are equivalent.

(a) x e is asymptotically stable; (b) x e is exponentially stable;

(c) the matrix A is negatively stable, i.e., there exists a symmetric positive definite matrix K such that A T K + K A is negative definite. Proof.I fx e is nondegenerate, then the system (4.2) becomes the ODE: ż = Az, whose unique solution is given by z(t, z 0 )=e t A z 0 for all t ≥ 0. The conclusion of the corollary now follows from classical linear systems theory and Proposition 4.2.

The proof of Proposition 4.2 can be significantly simplified, and in fact, the proposition itself can be extended considerably, by exploiting an approximation property of a piecewise affine function. In spite of the generalization discussed below, the proof given above is of interest for several reasons: one, it helps us to understand the generalized result; two, it expresses the reduced homogeneous system (4.2) in a form that enables a direct application of the results in section 3, and three, this reduction argument can be extended to a nonlinear complementarity system.

The following lemma is the cornerstone of the generalization of Proposition 4.2. It extends an obvious global property of affine functions to a local property of piecewise affine functions. For a proof of the lemma, see section 2.2.2 (particularly expression (2.2)) in [START_REF] Scholtes | Introduction to piecewise differentiable equations[END_REF] and [START_REF] Facchinei | Finite-Dimensional Variational Inequalities and Complementarity Problems[END_REF]Exercise 4.8.10].

Lemma 4.4 (Scholtes). () Let f : ℜ n →ℜ m be a piecewise affine function. For every x ∈ℜ n , there exists a neighborhood N x of x such that f (y)=f (x)+f ′ (x; yx) for all y ∈N x .