We show that for any positive integer d, there are families of switched linear systems–in fixed dimension and defined by two matrices only–that are stable under arbitrary switching but do not admit (i) a polynomial Lyapunov function of degree ≤d, or (ii) a polytopic Lyapunov function with ≤d facets, or (iii) a piecewise quadratic Lyapunov function with ≤d pieces. This implies that there cannot be an upper bound on the size of the linear and semidefinite programs that search for such stability certificates. Several constructive and non-constructive arguments are presented which connect our problem to known (and rather classical) results in the literature regarding the finiteness conjecture, undecidability, and non-algebraicity of the joint spectral radius. In particular, we show that existence of an extremal piecewise algebraic Lyapunov function implies the finiteness property of the optimal product, generalizing a result of Lagarias and Wang. As a corollary, we prove that the finiteness property holds for sets of matrices with an extremal Lyapunov function belonging to some of the most popular function classes in controls

چکیده

ما نشان می دهیم که برای هر عدد صحیح مثبت d، خانواده هایی از سیستم های خطی سوئیچ شده در ابعاد ثابت و تعریف شده تنها توسط دو ماتریس وجود دارد که تحت سوئیچینگ دلخواه، پایدار هستند، اما (الف) یک تابع لیاپانوف چند جمله ای از درجه ≤d، یا (ب) یک تابع لیاپانوف پلی تاپیک با ≤d منظر، یا (ج) یک تابع تکه ای لیاپانوف درجه دوم با ≤d قطعه را تصدیق نمی کند. این به معنی این است که نمی تواند یک کران بالا بر اندازه برنامه های خطی و نمیه معین وجود داشته باشد که برای این گواهی های پایداری جستجو کند. چندین دلیل سازنده و غیر سازنده ارائه شده است که مسئله­ ما را به نتایج شناخته شده (و نه کلاسیک) در ادبیات با توجه به حدس تناهی، تصمیم ناپذیری و غیر جبری بودن شعاع طیفی مشترک، متصل می کند. به طور خاص، ما نشان می دهیم که وجود یک تابع لیاپانوف جبری تکه ای اکسترم حاکی از خاصیت محدودیت حاصلضرب مطلوب است، که تعمیم نتیجه Lagarias و Wang می باشد. به عنوان یک نتیجه، ما ثابت می کنیم که ویژگی محدودیت برای مجموعه ای از ماتریس ها با یک تابع لیاپانوف اکسترم متعلق به برخی از محبوب ترین کلاس های تابع در کنترل، برقرار است.

1-مقدمه

در سال های اخیر، سیستم های ترکیبی به خوبی به عنوان یک چارچوب مدلسازی قوی برای سیستم های پیچیده دینامیکی شناخته شده اند. این به نوبه خود منجر به موجی از فعالیت برای طراحی ابزار محاسباتی برای تحلیل و کنترل آنها شده است. بسیاری از این ابزار بر اساس همکاری بین ایده های کلاسیک تئوری لیاپانوف (اغلب بطور مناسب برای مقابله با پیچیدگی های سیستم های ترکیبی اصلاح و یا تعمیم داده شده اند) و تکنیک های مدرن بهینه سازی عددی، به ویژه بهینه سازی محدب توسعه یافته­ اند...