BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Raphaël M. Jungers

Raphaël M. Jungers appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.OCSystems and Controleess.SYmath.DSDiscrete MathematicsComputational ComplexityFormal Languages and Automata TheoryData Structures and Algorithmsmath.COmath.NAMultiagent SystemsNumerical AnalysisDistributed, Parallel, and Cluster ComputingSocial and Information Networks

Catalog footprint

What is connected

35works
14topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

35 published item(s)

preprint2023arXiv

Learning stability of partially observed switched linear systems

This paper deals with learning stability of partially observed switched linear systems under arbitrary switching. Such systems are widely used to describe cyber-physical systems which arise by combining physical systems with digital components. In many real-world applications, the internal states cannot be observed directly. It is thus more realistic to conduct system analysis using the outputs of the system. Stability is one of the most frequent requirement for safety and robustness of cyber-physical systems. Existing methods for analyzing stability of switched linear systems often require the knowledge of the parameters and/or all the states of the underlying system. In this paper, we propose an algorithm for deciding stability of switched linear systems under arbitrary switching based purely on observed output data. The proposed algorithm essentially relies on an output-based Lyapunov stability framework and returns an estimate of the joint spectral radius (JSR). We also prove a probably approximately correct error bound on the quality of the estimate of the JSR from the perspective of statistical learning theory.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Almost sure Stability of Stochastic Switched Systems: Graph lifts-based Approach

In this paper, we develop tools to establish almost sure stability of stochastic switched systems whose switching signal is constrained by an automaton. After having provided the necessary generalizations of existing results in the setting of stochastic graphs, we provide a characterization of almost sure stability in terms of multiple Lyapunov functions. We introduce the concept of lifts, providing formal expansions of stochastic graphs, together with the guarantee of conserving the underlying probability framework. We show how these techniques, firstly introduced in the deterministic setting, provide hierarchical methods in order to compute tight upper bounds for the almost sure decay rate. The theoretical developments are finally illustrated via a numerical example.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Computation of invariant sets via immersion for discrete-time nonlinear systems

In this paper, we propose an approach for computing invariant sets of discrete-time nonlinear systems by lifting the nonlinear dynamics into a higher dimensional linear model. In particular, we focus on the \emph{maximal admissible invariant set} contained in some given constraint set. For special types of nonlinear systems, which can be exactly immersed into higher dimensional linear systems with state transformations, invariant sets of the original nonlinear system can be characterized using the higher dimensional linear representation. For general nonlinear systems without the immersibility property, \emph{approximate immersions} are defined in a local region within some tolerance and linear approximations are computed by leveraging the fixed-point iteration technique for invariant sets. Given the bound on the mismatch between the linear approximation and the original system, we provide an invariant inner approximation of the \emph{maximal admissible invariant set} by a tightening procedure.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Data-driven control of switched linear systems with probabilistic stability guarantees

This paper tackles state feedback control of switched linear systems under arbitrary switching. We propose a data-driven control framework that allows to compute a stabilizing state feedback using only a finite set of observations of trajectories with quadratic and sum of squares (SOS) Lyapunov functions. We do not require any knowledge on the dynamics or the switching signal, and as a consequence, we aim at solving \emph{uniform} stabilization problems in which the feedback is stabilizing for all possible switching sequences. In order to generalize the solution obtained from trajectories to the actual system, probabilistic guarantees on the obtained quadratic or SOS Lyapunov function are derived in the spirit of scenario optimization. For the quadratic Lyapunov technique, the generalization relies on a geometric analysis argument, while, for the SOS Lyapunov technique, we follow a sensitivity analysis argument. In order to deal with high-dimensional systems, we also develop parallelized schemes for both techniques. We show that, with some modifications, the data-driven quadratic Lyapunov technique can be extended to LQR control design. Finally, the proposed data-driven control framework is demonstrated on several numerical examples.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Data-driven invariant subspace identification for black-box switched linear systems

We present an algorithmic framework for the identification of candidate invariant subspaces for switched linear systems. Namely, the framework allows to compute an orthonormal basis in which the matrices of the system are close to block-triangular matrices, based on a finite set of observed one-step trajectories and with a priori confidence level. The link between the existence of an invariant subspace and a common block-triangularization of the system matrices is well known. Under some assumptions on the system, one can also infer the existence of an invariant subspace when the matrices are close to be block-triangular. Our approach relies on quadratic Lyapunov analysis and recent tools in scenario optimization. We present two applications of our results for problems of consensus and opinion dynamics; the first one allows to identify the disconnected components in a switching hidden network, while the second one identifies the stationary opinion vector of a switching gossip process with antagonistic interactions.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Equivalent Polyadic Decompositions of Matrix Multiplication Tensors

Invariance transformations of polyadic decompositions of matrix multiplication tensors define an equivalence relation on the set of such decompositions. In this paper, we present an algorithm to efficiently decide whether two polyadic decompositions of a given matrix multiplication tensor are equivalent. With this algorithm, we analyze the equivalence classes of decompositions of several matrix multiplication tensors. This analysis is relevant for the study of fast matrix multiplication as it relates to the question of how many essentially different fast matrix multiplication algorithms there exist. This question has been first studied by de~Groote, who showed that for the multiplication of $2\times2$ matrices with $7$ active multiplications, all algorithms are essentially equivalent to Strassen's algorithm. In contrast, the results of our analysis show that for the multiplication of larger matrices, (e.g., $2\times3$ by $3\times2$ or $3\times3$ by $3\times3$ matrices), two decompositions are very likely to be essentially different. We further provide a necessary criterion for a polyadic decomposition to be equivalent to a polyadic decomposition with integer entries. Decompositions with specific integer entries, e.g., powers of two, provide fast matrix multiplication algorithms with better efficiency and stability properties. This condition can be tested algorithmically and we present the conclusions obtained for the decompositions of small/medium matrix multiplication tensors.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Learning stability guarantees for data-driven constrained switching linear systems

We consider stability analysis of constrained switching linear systems in which the dynamics is unknown and whose switching signal is constrained by an automaton. We propose a data-driven Lyapunov framework for providing probabilistic stability guarantees based on data harvested from observations of the system. By generalizing previous results on arbitrary switching linear systems, we show that, by sampling a finite number of observations, we are able to construct an approximate Lyapunov function for the underlying system. Moreover, we show that the entropy of the language accepted by the automaton allows to bound the number of samples needed in order to reach some pre-specified accuracy.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Optimal Intermittent Particle Filter

The problem of the optimal allocation (in the expected mean square error sense) of a measurement budget for particle filtering is addressed. We propose three different optimal intermittent filters, whose optimality criteria depend on the information available at the time of decision making. For the first, the stochastic program filter, the measurement times are given by a policy that determines whether a measurement should be taken based on the measurements already acquired. The second, called the offline filter, determines all measurement times at once by solving a combinatorial optimization program before any measurement acquisition. For the third one, which we call online filter, each time a new measurement is received, the next measurement time is recomputed to take all the information that is then available into account. We prove that in terms of expected mean square error, the stochastic program filter outperforms the online filter, which itself outperforms the offline filter. However, these filters are generally intractable. For this reason, the filter estimate is approximated by a particle filter. Moreover, the mean square error is approximated using a Monte-Carlo approach, and different optimization algorithms are compared to approximately solve the combinatorial programs (a random trial algorithm, greedy forward and backward algorithms, a simulated annealing algorithm, and a genetic algorithm). Finally, the performance of the proposed methods is illustrated on two examples: a tumor motion model and a common benchmark for particle filtering.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Probabilistic guarantees on the objective value for the scenario approach via sensitivity analysis

This paper is concerned with objective value performance of the scenario approach for robust convex optimization. A novel method is proposed to derive probabilistic bounds for the objective value from scenario programs with a finite number of samples. This method relies on a max-min reformulation and the concept of complexity of robust optimization problems. With additional continuity and regularity conditions, via sensitivity analysis, we also provide explicit bounds which outperform an existing result in the literature. To illustrate the improvements of our results, we also provide a numerical example.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Stability of Switched Affine Systems: Arbitrary and Dwell-Time Switching

The dynamical behavior of switched affine systems is known to be more intricate than that of the well-studied switched linear systems, essentially due to the existence of distinct equilibrium points for each subsystem. First, under arbitrary switching rules, the stability analysis must be generally carried out with respect to a compact set with non-empty interior rather than to a singleton. We provide a novel proof technique for existence and outer approximation of attractive invariant sets of a switched affine system, under the hypothesis of global uniform stability of its linearization. On the other hand, considering dwell-time switching signals, forward invariant sets need not exist for this class of switched systems, even for stable ones. Hence, more general notions of stability/boundedness are introduced and studied, highlighting the relations of these concepts to the uniform stability of the linear part of the system under the same class of dwell-time switching signals. These results reveal the main differences and specificities of switched affine systems with respect to linear ones, providing a first step for the analysis of switched systems composed by subsystems not sharing the same equilibrium. Numerical methods based on linear matrix inequalities and sum-of-squares programming are presented and illustrate the developed theory.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Stabilization of rank-deficient continuous-time switched affine systems

This paper treats the global stabilization problem of continuous-time switched affine systems that have rank-deficient convex combinations of their dynamic matrices. For these systems, the already known set of attainable equilibrium points has higher dimensionality than in the full-rank case due to the existence of what we define as singular equilibrium points. Our main goal is to design a state-dependent switching function to ensure global asymptotic stability of a chosen point inside this set with conditions expressed in terms of linear matrix inequalities. For this class of systems, global exponential stability is generally impossible to be guaranteed. Hence, the proposed switching function is shown to ensure global asymptotic and local exponential stability of the desired equilibrium point. The position control and the velocity control with integral action of a dc motor driven by an h-bridge fed via a boost converter are used for validation. This practical application example is composed of eight subsystems, and all possible convex combinations of the dynamic matrices are singular.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Chance-constrained quasi-convex optimization with application to data-driven switched systems control

We study quasi-convex optimization problems, where only a subset of the constraints can be sampled, and yet one would like a probabilistic guarantee on the obtained solution with respect to the initial (unknown) optimization problem. Even though our results are partly applicable to general quasi-convex problems, in this work we introduce and study a particular subclass, which we call "quasi-linear problems". We provide optimality conditions for these problems. Thriving on this, we extend the approach of chance-constrained convex optimization to quasi-linear optimization problems. Finally, we show that this approach is useful for the stability analysis of black-box switched linear systems, from a finite set of sampled trajectories. It allows us to compute probabilistic upper bounds on the JSR of a large class of switched linear systems.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Geometric control of algebraic systems

In this paper, we present a geometric approach for computing the controlled invariant set of a continuous-time control system. While the problem is well studied for in the ellipsoidal case, this family is quite conservative for constrained or switched linear systems. We reformulate the invariance of a set as an inequality for its support function that is valid for any convex set. This produces novel algebraic conditions for the invariance of sets with polynomial or piecewise quadratic support function. We compare it with the common algebraic approach for polynomial sublevel sets and show that it is significantly more conservative than our method.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Finite Data-Rate Feedback Stabilization of Continuous-Time Switched Linear Systems with Unknown Switching Signal

In this paper, we study the problem of stabilizing switched linear systems when only limited information about the state and the mode of the system is available, which occurs in many applications involving networked switched systems (such as cyber-physical systems, IoT, etc.). First, we show that switched linear systems with arbitrary switching, i.e., with no constraint on the switching signal, are in general not stabilizable with a finite data rate. Then, drawing on this result, we restrict our attention to systems satisfying a fairly mild slow-switching assumption, in the sense that the switching signal has an average dwell time bounded away from zero. We show that under this assumption, switched linear systems that are stabilizable in the classical sense remain stabilizable with a finite data rate. A practical coder-controller that stabilizes the system is presented and its applicability is demonstrated on numerical examples.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On the Quality of First-Order Approximation of Functions with Hölder Continuous Gradient

We show that Hölder continuity of the gradient is not only a sufficient condition, but also a necessary condition for the existence of a global upper bound on the error of the first-order Taylor approximation. We also relate this global upper bound to the Hölder constant of the gradient. This relation is expressed as an interval, depending on the Hölder constant, in which the error of the first-order Taylor approximation is guaranteed to be. We show that, for the Lipschitz continuous case, the interval cannot be reduced. An application to the norms of quadratic forms is proposed, which allows us to derive a novel characterization of Euclidean norms.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Optimal measurement budget allocation for particle filtering

Particle filtering is a powerful tool for target tracking. When the budget for observations is restricted, it is necessary to reduce the measurements to a limited amount of samples carefully selected. A discrete stochastic nonlinear dynamical system is studied over a finite time horizon. The problem of selecting the optimal measurement times for particle filtering is formalized as a combinatorial optimization problem. We propose an approximated solution based on the nesting of a genetic algorithm, a Monte Carlo algorithm and a particle filter. Firstly, an example demonstrates that the genetic algorithm outperforms a random trial optimization. Then, the interest of non-regular measurements versus measurements performed at regular time intervals is illustrated and the efficiency of our proposed solution is quantified: better filtering performances are obtained in 87.5% of the cases and on average, the relative improvement is 27.7%.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Piecewise semi-ellipsoidal control invariant sets

Computing control invariant sets is paramount in many applications. The families of sets commonly used for computations are ellipsoids and polyhedra. However, searching for a control invariant set over the family of ellipsoids is conservative for systems more complex than unconstrained linear time invariant systems. Moreover, even if the control invariant set may be approximated arbitrarily closely by polyhedra, the complexity of the polyhedra may grow rapidly in certain directions. An attractive generalization of these two families are piecewise semi-ellipsoids. We provide in this paper a convex programming approach for computing control invariant sets of this family.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Stability of Planar Switched Systems under Delayed Event Detection

In this paper, we analyse the impact of delayed event detection on the stability of a 2-mode planar hybrid automata. We consider hybrid automata with a unique equilibrium point for all the modes, and we find the maximum delay that preserves stability of that equilibrium point. We also show for the class of hybrid automata treated that the instability of the equilibrium point for the equivalent hybrid automaton with delay in the transitions is equivalent to the existence of a closed orbit in the hybrid state space, a result that is inspired by the Joint Spectral Radius theorem. This leads to an algorithm for computing the maximum stable delay exactly. Other potential applications of our technique include co-simulation, networked control systems and delayed controlled switching with a state feedback control.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On feedback stabilization of linear switched systems via switching signal control

Motivated by recent applications in control theory, we study the feedback stabilizability of switched systems, where one is allowed to chose the switching signal as a function of $x(t)$ in order to stabilize the system. We propose new algorithms and analyze several mathematical features of the problem which were unnoticed up to now, to our knowledge. We prove complexity results, (in-)equivalence between various notions of stabilizability, existence of Lyapunov functions, and provide a case study for a paradigmatic example introduced by Stanford and Urbano.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Path-Complete Graphs and Common Lyapunov Functions

A Path-Complete Lyapunov Function is an algebraic criterion composed of a finite number of functions, called its pieces, and a directed, labeled graph defining Lyapunov inequalities between these pieces. It provides a stability certificate for discrete-time switching systems under arbitrary switching. In this paper, we prove that the satisfiability of such a criterion implies the existence of a Common Lyapunov Function, expressed as the composition of minima and maxima of the pieces of the Path-Complete Lyapunov function. The converse, however, is not true even for discrete-time linear systems: we present such a system where a max-of-2 quadratics Lyapunov function exists while no corresponding Path-Complete Lyapunov function with 2 quadratic pieces exists. In light of this, we investigate when it is possible to decide if a Path-Complete Lyapunov function is less conservative than another. By analyzing the combinatorial and algebraic structure of the graph and the pieces respectively, we provide simple tools to decide when the existence of such a Lyapunov function implies that of another.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Primitive sets of nonnegative matrices and synchronizing automata

A set of nonnegative matrices $\mathcal{M}=\{M_1, M_2, \ldots, M_k\}$ is called primitive if there exist indices $i_1, i_2, \ldots, i_m$ such that $M_{i_1} M_{i_2} \ldots M_{i_m}$ is positive (i.e. has all its entries $>0$). The length of the shortest such product is called the exponent of $\mathcal{M}$. The concept of primitive sets of matrices comes up in a number of problems within control theory, non-homogeneous Markov chains, automata theory etc. Recently, connections between synchronizing automata and primitive sets of matrices were established. In the present paper, we significantly strengthen these links by providing equivalence results, both in terms of combinatorial characterization, and computational aspects. We study the maximal exponent among all primitive sets of $n \times n$ matrices, which we denote by $\exp(n)$. We prove that $\lim_{n\rightarrow\infty} \tfrac{\log \exp(n)}{n} = \tfrac{\log 3}{3}$, and moreover, we establish that this bound leads to a resolution of the Černý problem for carefully synchronizing automata. We also study the set of matrices with no zero rows and columns, denoted by $\mathcal{NZ}$, due to its intriguing connections to the Černý conjecture and the recent generalization of Perron-Frobenius theory for this class. We characterize computational complexity of different problems related to the exponent of $\mathcal{NZ}$ matrix sets, and present a quadratic bound on the exponents of sets belonging to a special subclass. Namely, we show that the exponent of a set of matrices having total support is bounded by $2n^2 -5n +5$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Stability of discrete-time switching systems with constrained switching sequences

We introduce a novel framework for the stability analysis of discrete-time linear switching systems with switching sequences constrained by an automaton. The key element of the framework is the algebraic concept of multinorm, which associates a different norm per node of the automaton, and allows to exactly characterize stability. Building upon this tool, we develop the first arbitrarily accurate approximation schemes for estimating the constrained joint spectral radius r, that is the exponential growth rate of a switching system with constrained switching sequences. More precisely, given a relative accuracy a > 0, the algorithms compute an estimate of r within the range [r; (1 + a)r]. These algorithms amount to solve a well defined convex optimization program with known time-complexity, and whose size depends on the desired relative accuracy a > 0.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Tight Bounds for Consensus Systems Convergence

We analyze the asymptotic convergence of all infinite products of matrices taken in a given finite set, by looking only at finite or periodic products. It is known that when the matrices of the set have a common nonincreasing polyhedral norm, all infinite products converge to zero if and only if all infinite periodic products with period smaller than a certain value converge to zero, and bounds exist on that value. We provide a stronger bound holding for both polyhedral norms and polyhedral seminorms. In the latter case, the matrix products do not necessarily converge to 0, but all trajectories of the associated system converge to a common invariant space. We prove our bound to be tight, in the sense that for any polyhedral seminorm, there is a set of matrices such that not all infinite products converge, but every periodic product with period smaller than our bound does converge. Our technique is based on an analysis of the combinatorial structure of the face lattice of the unit ball of the nonincreasing seminorm. The bound we obtain is equal to half the size of the largest antichain in this lattice. Explicitly evaluating this quantity may be challenging in some cases. We therefore link our problem with the Sperner property: the property that, for some graded posets, -- in this case the face lattice of the unit ball -- the size of the largest antichain is equal to the size of the largest rank level. We show that some sets of matrices with invariant polyhedral seminorms lead to posets that do not have that Sperner property. However, this property holds for the polyhedron obtained when treating sets of stochastic matrices, and our bound can then be easily evaluated in that case. In particular, we show that for the dimension of the space $n \geq 8$, our bound is smaller than the previously known bound by a multiplicative factor of $\frac{3}{2 \sqrt{πn}}$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A complexity analysis of Policy Iteration through combinatorial matrices arising from Unique Sink Orientations

Unique Sink Orientations (USOs) are an appealing abstraction of several major optimization problems of applied mathematics such as for instance Linear Programming (LP), Markov Decision Processes (MDPs) or 2-player Turn Based Stochastic Games (2TBSGs). A polynomial time algorithm to find the sink of a USO would translate into a strongly polynomial time algorithm to solve the aforementioned problems---a major quest for all three cases. In addition, we may translate MDPs and 2TBSGs into the problem of finding the sink of an acyclic USO of a cube, which can be done using the well-known Policy Iteration algorithm (PI). The study of its complexity is the object of this work. Despite its exponential worst case complexity, the principle of PI is a powerful source of inspiration for other methods. As our first contribution, we disprove Hansen and Zwick's conjecture claiming that the number of steps of PI should follow the Fibonacci sequence in the worst case. Our analysis relies on a new combinatorial formulation of the problem---the so-called Order-Regularity formulation (OR). Then, for our second contribution, we (exponentially) improve the $Ω(1.4142^n)$ lower bound on the number of steps of PI from Schurr and Szabó in the case of the OR formulation and obtain an $Ω(1.4269^n)$ bound.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Computing the domain of attraction of switching systems subject to non-convex constraints

We characterize and compute the maximal admissible positively invariant set for asymptotically stable constrained switching linear systems. Motivated by practical problems found, e.g., in obstacle avoidance, power electronics and nonlinear switching systems, in our setting the constraint set is formed by a finite number of polynomial inequalities. First, we observe that the so-called Veronese lifting allows to represent the constraint set as a polyhedral set. Next, by exploiting the fact that the lifted system dynamics remains linear, we establish a method based on reachability computations to characterize and compute the maximal admissible invariant set, which coincides with the domain of attraction when the system is asymptotically stable. After developing the necessary theoretical background, we propose algorithmic procedures for its exact computation, based on linear or semidefinite programs. The approach is illustrated in several numerical examples.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Deciding the boundedness and dead-beat stability of constrained switching systems

We study computational questions related with the stability of discrete-time linear switching systems with switching sequences constrained by an automaton. We first present a decidable sufficient condition for their boundedness when the maximal exponential growth rate equals one. The condition generalizes the notion of the irreducibility of a matrix set, which is a well known sufficient condition for boundedness in the arbitrary switching (i.e. unconstrained) case. Second, we provide a polynomial time algorithm for deciding the dead-beat stability of a system, i.e. that all trajectories vanish to the origin in finite time. The algorithm generalizes one proposed by Gurvits for arbitrary switching systems, and is illustrated with a real-world case study.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Efficient Algorithms for the Consensus Decision Problem

We address the problem of determining if a discrete time switched consensus system converges for any switching sequence and that of determining if it converges for at least one switching sequence. For these two problems, we provide necessary and sufficient conditions that can be checked in singly exponential time. As a side result, we prove the existence of a polynomial time algorithm for the first problem when the system switches between only two subsystems whose corresponding graphs are undirected, a problem that had been suggested to be NP-hard by Blondel and Olshevsky.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the Synchronizing Probability Function and the Triple Rendezvous Time for Synchronizing Automata

Cerny's conjecture is a longstanding open problem in automata theory. We study two different concepts, which allow to approach it from a new angle. The first one is the triple rendezvous time, i.e., the length of the shortest word mapping three states onto a single one. The second one is the synchronizing probability function of an automaton, a recently introduced tool which reinterprets the synchronizing phenomenon as a two-player game, and allows to obtain optimal strategies through a Linear Program. Our contribution is twofold. First, by coupling two different novel approaches based on the synchronizing probability function and properties of linear programming, we obtain a new upper bound on the triple rendezvous time. Second, by exhibiting a family of counterexamples, we disprove a conjecture on the growth of the synchronizing probability function. We then suggest natural follow-ups towards Cernys conjecture.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Reachability of Consensus and Synchronizing Automata

We consider the problem of determining the existence of a sequence of matrices driving a discrete-time consensus system to consensus. We transform this problem into one of the existence of a product of the transition (stochastic) matrices that has a positive column. We then generalize some results from automata theory to sets of stochastic matrices. We obtain as a main result a polynomial-time algorithm to decide the existence of a sequence of matrices achieving consensus.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Converse Lyapunov theorems for discrete-time linear switching systems with regular switching sequences

We present a stability analysis framework for the general class of discrete-time linear switching systems for which the switching sequences belong to a regular language. They admit arbitrary switching systems as special cases. Using recent results of X. Dai on the asymptotic growth rate of such systems, we introduce the concept of multinorm as an algebraic tool for stability analysis. We conjugate this tool with two families of multiple quadratic Lyapunov functions, parameterized by an integer T >= 1, and obtain converse Lyapunov Theorems for each. Lyapunov functions of the first family associate one quadratic form per state of the automaton defining the switching sequences. They are made to decrease after every T successive time steps. The second family is made of the path-dependent Lyapunov functions of Lee and Dullerud. They are parameterized by an amount of memory (T-1) >= 0. Our converse Lyapunov theorems are finite. More precisely, we give sufficient conditions on the asymptotic growth rate of a stable system under which one can compute an integer parameter T >= 1 for which both types of Lyapunov functions exist. As a corollary of our results, we formulate an arbitrary accurate approximation scheme for estimating the asymptotic growth rate of switching systems with constrained switching sequences.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Improved bound on the worst case complexity of Policy Iteration

Solving Markov Decision Processes (MDPs) is a recurrent task in engineering. Even though it is known that solutions for minimizing the infinite horizon expected reward can be found in polynomial time using Linear Programming techniques, iterative methods like the Policy Iteration algorithm (PI) remain usually the most efficient in practice. This method is guaranteed to converge in a finite number of steps. Unfortunately, it is known that it may require an exponential number of steps in the size of the problem to converge. On the other hand, many open questions remain considering the actual worst case complexity. In this work, we provide the first improvement over the fifteen years old upper bound from Mansour & Singh (1999) by showing that PI requires at most k/(k-1)*k^n/n + o(k^n/n) iterations to converge, where n is the number of states of the MDP and k is the maximum number of actions per state. Perhaps more importantly, we also show that this bound is optimal for an important relaxation of the problem.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Graph diameter, eigenvalues, and minimum-time consensus

We consider the problem of achieving average consensus in the minimum number of linear iterations on a fixed, undirected graph. We are motivated by the task of deriving lower bounds for consensus protocols and by the so-called "definitive consensus conjecture" which states that for an undirected connected graph G with diameter D there exist D matrices whose nonzero-pattern complies with the edges in G and whose product equals the all-ones matrix. Our first result is a counterexample to the definitive consensus conjecture, which is the first improvement of the diameter lower bound for linear consensus protocols. We then provide some algebraic conditions under which this conjecture holds, which we use to establish that all distance-regular graphs satisfy the definitive consensus conjecture.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

PageRank Optimization by Edge Selection

The importance of a node in a directed graph can be measured by its PageRank. The PageRank of a node is used in a number of application contexts - including ranking websites - and can be interpreted as the average portion of time spent at the node by an infinite random walk. We consider the problem of maximizing the PageRank of a node by selecting some of the edges from a set of edges that are under our control. By applying results from Markov decision theory, we show that an optimal solution to this problem can be found in polynomial time. Our core solution results in a linear programming formulation, but we also provide an alternative greedy algorithm, a variant of policy iteration, which runs in polynomial time, as well. Finally, we show that, under the slight modification for which we are given mutually exclusive pairs of edges, the problem of PageRank optimization becomes NP-hard.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

An Efficient Algorithm for Partial Order Production

We consider the problem of partial order production: arrange the elements of an unknown totally ordered set T into a target partially ordered set S, by comparing a minimum number of pairs in T. Special cases include sorting by comparisons, selection, multiple selection, and heap construction. We give an algorithm performing ITLB + o(ITLB) + O(n) comparisons in the worst case. Here, n denotes the size of the ground sets, and ITLB denotes a natural information-theoretic lower bound on the number of comparisons needed to produce the target partial order. Our approach is to replace the target partial order by a weak order (that is, a partial order with a layered structure) extending it, without increasing the information theoretic lower bound too much. We then solve the problem by applying an efficient multiple selection algorithm. The overall complexity of our algorithm is polynomial. This answers a question of Yao (SIAM J. Comput. 18, 1989). We base our analysis on the entropy of the target partial order, a quantity that can be efficiently computed and provides a good estimate of the information-theoretic lower bound.

0 citations0 reviewsNo code linkedOpen access