[10-23]Linear Hybrid Systems are Hard: The Case of Linear Complementarity Systems and The Quest For Characterizing Q-matrices
文章来源： | 发布时间：2023-10-17 | 【打印】 【关闭】
Title: Linear Hybrid Systems are Hard: The Case of Linear Complementarity Systems and The Quest For Characterizing Q-matricesSpeaker:Khalil Ghorbal (Researcher, INRIA)
Abstract: Linear complementarity systems (LCS) form a special class of linear hybrid systems with an exponential number of modes and a linear differential algebraic equation in each mode.
While seemingly simple, little is known about the existence (and uniqueness) of continuous solutions for LCS.
The only known sufficient condition is rather strong and requires the existence and uniqueness of solutions for the underlying linear complementarity problem (LCP) which, for a fixed matrix M and a given vector q, asks whether there exists a pair of vectors (w,z) satisfying w - M z = q, w,z >= 0, and w.z = 0. M is said to be a Q-matrix when a solution exists for all q. We start by exposing the inherent difficulty of characterizing Q-matrices by reformulating the problem as a covering problem of R^n. We then investigate the regions where no solution exists (so called holes) and show that they only occur in specific locations.
This property is exploited to fully characterize planar and spatial Q-matrices via a local reduction around the vectors defining the problem.
This is a joint work with Christelle Kozaily.
Bio: I am currently a researcher at Inria (Rennes, France), in the Hycomes group. I am broadly interested in dynamical systems: defining concepts of solutions, proving their existence, approximating their orbits… the tools I have been using so far include: Symbolic and certified numerical computations，Combinatorial optimization，Convex analysis
I was previously a postdoc at Carnegie Mellon University (Pittsburgh, PA, USA), School of Computer Science, Logical Systems Lab and before that at NEC Labs America, System Analysis and Verification Group (Princeton, NJ, USA).