Search

This paper studies linear stochastic approximation (SA) algorithms and their application to multiagent systems in engineering and sociology. As main contribution, we provide necessary and sufficient conditions for convergence of linear SA algorithms to a deterministic or random final vector. We also characterize the system convergence rate, when the system is convergent. Moreover, differing from non-negative gain functions in traditional SA algorithms, this paper considers also the case when the gain functions are allowed to take arbitrary real numbers. Using our general treatment, we provide necessary and sufficient conditions to reach consensus and group consensus for first-order discrete-time multiagent system over random signed networks and with state-dependent noise. Finally, we extend our results to the setting of multidimensional linear SA algorithms and characterize the behavior of the multidimensional Friedkin–Johnsen model over random interaction networks. [ABSTRACT FROM AUTHOR]

This paper presents a novel method to compute the distance to instability for linear time-invariant delay systems with multiple delays, subjected to combined uncertainties on the system matrices and the delay parameters. The method is able to fully exploit structure and possible interdependencies between the uncertainties affecting the coefficient matrices, the property that realistic perturbations are real valued, and the structure of the delay equation. The resulting algorithm relies on a characterization in terms of the pseudospectral abscissa and on techniques from optimization over manifolds of matrices. [ABSTRACT FROM AUTHOR]

In this paper, a numerically robust solver for least-square problems with bounded variables (BVLS) is presented for applications including, but not limited to, model predictive control (MPC). The proposed BVLS algorithm solves the problem efficiently by employing a recursive QR factorization method based on Gram–Schmidt orthogonalization. A reorthogonalization procedure that iteratively refines the QR factors provides numerical robustness for the described primal active-set method, which solves a system of linear equations in each of its iterations via recursive updates. The performance of the proposed BVLS solver, which is implemented in C without external software libraries, is compared in terms of computational efficiency against state-of-the-art quadratic programming solvers for small- to medium-sized random BVLS problems and a typical example of embedded linear MPC application. The numerical tests demonstrate that the solver performs very well even when solving ill-conditioned problems in single-precision floating-point arithmetic. [ABSTRACT FROM AUTHOR]

This paper deals with the dead-beat stabilizability of autonomous discrete-time switched linear systems. Based on a constructive necessary and sufficient condition for dead-beat stabilizability, we propose two algorithms. The first one is concerned with the problem of testing dead-beat stabilizability and computing the shorter stabilizing mode sequence, whenever it exists. The other one implements a method to construct a switched system whose shorter dead-beat stabilizing sequence has a prescribed length. Then, we present numerical assessments and possible applications. [ABSTRACT FROM AUTHOR]

The paper studies digital redesign of linear time-invariant analog controllers under intermittent sampling. The sampling pattern is only assumed to be uniformly bounded, but otherwise irregular and unknown a priori. The contribution of the paper is twofold. First, it proposes a constructive algorithm to redesign any analog stabilizing controller so that the closed-loop stability is preserved. Second, it is shown that when applied to (sub) optimal \boldsymbolH^2 and \boldsymbolH^\infty controllers, the algorithm produces (sub) optimal sampled-data solutions under any a priori unknown sampling pattern. The proposed solutions are analytic, computationally simple, implementable, and transparent. Transparency pays off in showing the optimality, under a fixed sampling density, of uniform sampling for both performance measures studied. [ABSTRACT FROM AUTHOR]

The leader-following consensus problem for linear discrete-time multiagent systems has been studied in the literature using $H_{\infty }$ Riccati inequality design and $H_{2}$ Riccati equation design methods, respectively. These two methods lead to a solvability condition in terms of an inequality that relies on a scaling gain and a fixed weighting vector called nominal weighting vector. In this paper, we further study this problem by proposing a more general class of distributed state feedback control laws, which not only depends on a scaling gain, but also a set of weighting vectors. We first establish a spectral property of a weighted graph matrix, which will be instrumental in solving the problem. Then, we present a solvability condition based on a modified algebraic Riccati equation, which is somehow more general than $H_{\infty }$ and $H_{2}$ Riccati methods, in that the solvability condition can be made satisfied by tuning the weighting vector. We show that our solvability condition is also necessary for single-input follower systems and is always satisfied for leader systems without exponentially growing modes. Moreover, in case the solvability condition is not satisfied under the nominal weighting vector, we show that our solvability condition can always be made satisfied by choosing a weighting vector other than the nominal one for multiagent systems over acyclic digraphs. [ABSTRACT FROM AUTHOR]

This paper is concerned with the $H_2$ control of linear systems with multiple quantization channels. The quantization parameters of each channel are not required to be identical. The resultant mismatches are represented by polytopic uncertainties. A composite controller composed of linear and nonlinear parts is designed to meet the required $H_2$ performance and offset the quantization error. Resorting to a vertex separation technique and Finsler lemma instead of matrix inverse operations, new synthesis conditions for the desired linear part are derived in terms of linear matrix inequalities, which are further extended to treat systems with norm-bounded uncertainties. A comparison of conservativeness between the proposed methods and the existing ones is demonstrated by two numerical examples. [ABSTRACT FROM AUTHOR]

For a system matrix $M$ , this paper explores the smallest (Frobenius) norm additive structured perturbation $\delta M$ for which a system property $\mathcal {P}$ (e.g., controllability, observability, stability, etc.) fails to hold, i.e., $\delta M$ is the structured perturbation with smallest Frobenius norm such that there exists a property matrix $R\in \mathcal {P}$ for which $M{-}\delta M{-}R$ drops rank. The Frobenius norm is used because of its direct dependence on the magnitude of each entry in the perturbation matrix. Necessary conditions on a locally minimum norm structured rank-reducing perturbation $\delta M$ and associated property matrix $R$ are set forth and proven. An iterative algorithm is also set forth that computes a locally minimum norm structured perturbation and associated property matrix satisfying the necessary conditions. Algorithm convergence is proven using a discrete Lyapunov function. [ABSTRACT FROM AUTHOR]

In this paper, we address the optimal control problem for Boolean control networks (BCNs). We first consider the problem of finding the input sequences that minimize a given cost function over a finite time horizon. The problem solution is obtained by means of a recursive algorithm that represents the analogue for BCNs of the difference Riccati equation for linear systems. We prove that a significant number of optimal control problems for BCNs can be easily reframed into the present setup. In particular, the cost function can be adjusted so as to include penalties on the switchings, provided that we augment the size of the BCN state variable. In the second part of the paper, we address the infinite horizon optimal control problem and we provide necessary and sufficient conditions for the problem solvability. The solution is obtained as the limit of the solution over the finite horizon [0,T], and it is always achieved in a finite number of steps. Finally, the average cost problem over the infinite horizon, investigated in “Optimal control of logical control networks” (Y. Zhao , IEEE Trans. Autom. Control, vol 56, no. 8, pp. 1766–1776, Aug. 2011), is addressed by making use of the results obtained in the previous sections. [ABSTRACT FROM AUTHOR]

Recently, several convergence rate results for Douglas-Rachford splitting and the alternating direction method of multipliers (ADMM) have been presented in the literature. In this paper, we show global linear convergence rate bounds for Douglas-Rachford splitting and ADMM under strong convexity and smoothness assumptions. We further show that the rate bounds are tight for the class of problems under consideration for all feasible algorithm parameters. For problems that satisfy the assumptions, we show how to select step-size and metric for the algorithm that optimize the derived convergence rate bounds. For problems with a similar structure that do not satisfy the assumptions, we present heuristic step-size and metric selection methods. [ABSTRACT FROM PUBLISHER]

Abstract-In this paper, we propose a general methodology for designing fixed order controllers for single-input single-output plants. The controller parameters are classified into two classes: randomized and deterministically designed. For the first class, we study randomized algorithms. In particular, we present two low-complexity algorithms based on the Chernoff bound and on a related bound (often called "log-over-log" bound) which is generally used for optimization problems. Secondly, for the deterministically designed parameters, we reformulate the original problem as a set of linear equations. Then, we develop a technique which efficiently solves it using a combination of matrix inversions and sensitivity methods. A detailed complexity analysis of this technique is carried on, showing its superiority (from the computational point of view) to existing algorithms based on linear programming. In the second part of the paper, these results are extended to H∞ performance. One of the contributions is to prove that the deterministically designed parameters enjoy a special convex characterization. This characterization is then exploited in order to design fixed order controllers efficiently. We then show further extensions of these methods for stabilization of interval plants. In particular, we derive a simple one-parameter formula for computing the so-called critical frequencies which are required by the algorithms. [ABSTRACT FROM AUTHOR]

By using a delay line as a signal generator, we design a simple robust controller for the approximate regulation (i.e., approximate asymptotic tracking and rejection) of almost periodic signals for linear systems. As opposed to the related existing results, our controller design does not require online parameter tuning. Besides the usual assumptions about stabilizability, detectability, and nonexistence of transmission zeros for the plant, the controller design algorithm of this paper only requires knowledge of the desired tracking accuracy ϵ > 0. Based on this information alone, we can only design a robust controller achieving, in the presence of unknown trigonometric polynomial disturbances and additive perturbations to the plant and the controller, lim supt→ ∞ ∥ y(t) - yref(t) ∥ < ϵ ∥ yref ∥. Here, y is the output of the plant and yref is an arbitrary almost periodic reference signal taken from an infinite-dimensional generalized Sobolev space of almost periodic functions. In this paper, we also study robust output regulation in the limiting case where ϵ → 0. It turns out that, due to the general loss of exponential closed loop stability, asymptotic tracking/rejection can also be lost as ϵ → 0, unless the exogenous signals are smooth enough. This last result extends some recent theorems on (nonrobust) open loop output regulation for infinite-dimensional exosystems. The results of this paper are new and potentially useful for finite-dimensional plants, but the main results are also true for infinite-dimensional systems with bounded control and observation operators. [ABSTRACT FROM AUTHOR]

Arbitrary high precision output tracking is one of the most desirable control objectives found in industrial applications regardless of measurement errors. The main purpose of this paper is to supply to the iterative learning control (ILC) designer guide- lines to select the corresponding learning gain in order to achieve this control objective. For example, if certain conditions are met, then it is necessary for the learning gain to converge to zero in the learning iterative domain. In particular, this paper presents necessary and sufficient conditions for boundedness of trajectories and uniform tracking in presence of measurement noise and a class of random reinitialization errors for a simple ILC algorithm. The system under consideration is a class of discrete-time affine non-linear systems with arbitrary relative degree and arbitrary number of system inputs and outputs. The state function does not need to satisfy a Lipschitz condition. This work also provides a recursive algorithm that generates the appropriate learning gain functions that meet the arbitrary high precision output tracking objective. The resulting tracking output error is shown to converge to zero at a rate inversely proportional to square root of the number of learning iterations in presence of measurement noise and a class of reinitialization errors. Two illustrative numerical examples are presented. [ABSTRACT FROM AUTHOR]

In this paper, we develop a method to automatically generate a control policy for a dynamical system modeled as a Markov Decision Process (MDP). The control specification is given as a Linear Temporal Logic (LTL) formula over a set of propositions defined on the states of the MDP. Motivated by robotic applications requiring persistent tasks, such as environmental monitoring and data gathering, we synthesize a control policy that minimizes the expected cost between satisfying instances of a particular proposition over all policies that maximize the probability of satisfying the given LTL specification. Our approach is based on the definition of a novel optimization problem that extends the existing average cost per stage problem. We propose a sufficient condition for a policy to be optimal, and develop a dynamic programming algorithm that synthesizes a policy that is optimal for a set of LTL specifications. [ABSTRACT FROM AUTHOR]

This paper studies the quadratic regulation problem for discrete-time switched linear systems (DSLQR problem) on an infinite time horizon. A general relaxation framework is developed to simplify the computation of the value iterations. Based on this framework, an efficient algorithm is developed to solve the infinite-horizon DSLQR problem with guaranteed closed-loop stability and suboptimal performance. Due to these guarantees, the proposed algorithm can be used as a general controller synthesis tool for switched linear systems. [ABSTRACT FROM PUBLISHER]

The nonlinear equivalences of both finite and infinite zero structures of linear systems have been well understood for single input single output systems and have found many applications in nonlinear control theory. The extensions of these notions to multiple input multiple output systems have proven to be highly sophisticated. In this paper, we propose constructive algorithms for decomposing a nonlinear system that is affine in control. These algorithms require modest assumptions on the system and apply to general multiple input multiple output systems that do not necessarily have the same number of inputs and outputs. They lead to various normal form representations and reveal the structure at infinity, the zero dynamics and the invertibility properties, all of which represent nonlinear equivalences of relevant linear system structural properties. [ABSTRACT FROM AUTHOR]

This paper is concerned with development of novel fault detection and isolation (FDI) strategies for the Markovian jump linear systems (MJLS's) and the MJLS's with time-delays (MJLSD's). First a geometric property that is related to the unobservable subspace of MJLS's is presented. The notion of a finite unobservable subspace is then introduced for the MJLSD's. The concept of unobservability subspace is introduced for both the MJLS's and the MJLSD's and an algorithm for its construction is described. The necessary and sufficient conditions for solvability of the fundamental problem of residual generation (FPRG) for the MJLS's are developed by utilizing our introduced unobservability subspace. Furthermore, sufficient solvability conditions of the FPRG for the MJLSD's are also derived. Finally, sufficient conditions for designing an H∞-based FDI algorithm for the MJLS's with an unknown transition matrix that are also subject to input and output disturbances are developed. [ABSTRACT FROM AUTHOR]

One of the fundamental problems in the area of large-scale optimization is to study locality features of spatially distributed optimization problems in which the variables are coupled in the cost function as well as constraints. Such problems can motivate the development of fast and well-conditioned distributed algorithms. In this paper, we study spatial locality features of large-scale multi-parametric quadratic programming (MPQP) problems with linear inequality constraints. Our main application focus is receding horizon control of spatially distributed linear systems with input and state constraints. We propose a new approach for analysis of large-scale MPQP problems by blending tools from duality theory with operator theory. The class of spatially decaying matrices is introduced to capture couplings between optimization variables in the cost function and the constraints. We show that the optimal solution of a convex MPQP is piecewise affine- represented as convolution sums. More importantly, we prove that the kernel of each convolution sum decays in the spatial domain at a rate proportional to the inverse of the corresponding coupling function of the optimization problem. [ABSTRACT FROM AUTHOR]

For ẋ = Ax + Bu, the problem of structural assignment via sensor selection is to find an output equation, y = Cx + Du, such that the resulting system (A, B, C, D) has the pre-specified structural properties, such as the finite and infinite zero structures as well as the invertibility properties. In this paper, we establish a set of necessary and sufficient conditions under which a complete set of system structural properties can be assigned, and an explicit algorithm for constructing the required matrix pair (C, D). [ABSTRACT FROM AUTHOR]

Much of the research on network modeling and analysis has focused on the design of end controllers and network algorithms with the objective of stability and convergence of the transmission rate. However, a network is typically composed of a mixture of both controlled elastic flows and uncontrolled real-time flows. In this paper, we study the effects of marking elasticity (which characterizes how aggressively the marking function responds to congestion) on queue overflow probability for uncontrolled real-time flows. First, we derive lower and upper bounds on the queue overflow probability at a router of a single bottleneck system. Using this, we quantify the trade-off between stability for controlled flows and queue overflow probability for uncontrolled real-time flows as a function of marking elasticity. Next, we compare the capacity required at a router with only FIFO scheduling versus a router with priority scheduling (priority given to the real-time flows) for supporting a given queue overflow probability. We quantify the "scheduling-gain" of priority scheduling over FIFO scheduling, as a function of marking elasticity. We show that this scheduling gain decreases with more elastic marking functions. [ABSTRACT FROM AUTHOR]

This paper develops a generalization of the balanced truncation algorithm applicable to a class of discrete-time stochastic jump linear systems. The approximation error, which is captured by means of the stochastic L2 gain, is bounded from above by twice the sum of singular numbers associated to the truncated states, similar to the case of linear time-invariant systems. A two step model reduction algorithm for hidden Markov models is also developed. The first step relies on the aforementioned balanced truncation algorithm due to a topological equivalence established between hidden Markov models and a subclass of stochastic jump linear systems. In a second step the positivity constraints, which reflect the hidden Markov model structure, are enforced by solving a low dimensional optimization problem. [ABSTRACT FROM AUTHOR]

Abstract-This paper is concerned with the study of observability in a structural framework. It turns out that the system is structurally observable if and only if the system is output connected and contains no contraction. We focus our attention on the observability preservation under sensor failure. We consider linear observable systems and we wonder if a given system remains observable in case of sensor failure. More precisely, we will characterize among the sensors those which are critical, i.e., which failure leads to observability loss, those which are useless for observability purpose and the set of those which are useful without being critical. Using a graph approach we classify the sensors with respect to their importance for output connection preservation, contraction avoidance and then observability preservation under sensor failure. [ABSTRACT FROM AUTHOR]

A systematic approach to the chattering analysis in systems with second-order sliding modes is developed. The neglected actuator dynamics is considered to be the main cause of chattering in real systems. The magnitude of oscillations in nonlinear systems with unmodeled fast nonlinear actuators driven by second-order sliding-mode control generalized suboptimal (2-SMC G-SO) algorithms is evaluated. Sufficient conditions for the existence of orbitally stable periodic motions are found in terms of the properties of corresponding Poincaré maps. For linear systems driven by 2-SMC G-SO algorithms, analysis tools based on the frequency-domain methods are developed. The first of these techniques is based on the describing function method and provides for a simple approximate approach to evaluate the frequency and the amplitude of possible periodic motions. The second technique represents a modified Tsypkin's method and provides for a relatively simple, theoretically exact, approach to evaluate the periodic motion parameters. Examples of analysis and simulation results are given throughout this paper. [ABSTRACT FROM AUTHOR]

In a problem on the realization of digital filters, initiated by Gersho and Gopinath, we extend and complete a remarkable result of Benvenuti, Farina and Anderson on decomposing the transfer function t(z) of an arbitrary linear, asymptotically stable, discrete, time-invariant single-input-single-output system as a difference t(z) = t1 (z) - t2 (z) of two positive, asymptotically stable linear systems. We give an easy-to-compute algorithm to handle the general problem, in particular, also the case of transfer functions t(z) with multiple poles, which was left open in a previous paper. One of the appearing positive, asymptotically stable systems is always one-dimensional, while the other has dimension depending on the order and, in the case of nonreal poles, also on the location of the poles of t(z). The appearing dimension is seen to be minimal in some cases and it can always be calculated before carrying out the realization. [ABSTRACT FROM AUTHOR]

This note continues on the results proposed in two previous papers for computing vector 1- or „-norm based Lyapunov functions for linear discrete-time systems by presenting a finitely terminating algorithm for the construction of Lyapunov functions of that class. The algorithm utilizes the solution of a finite sequence of feasibility linear programs (LPs) with very few constraints or, equivalently, very simple algebraic tests in contrast to solving the original problem where a bilinear matrix equation with rank and norm constraint needs to be solved. [ABSTRACT FROM AUTHOR]

We consider the constrained finite and infinite time optimal control problem for the class of discrete-time linear hybrid systems. When a linear performance index is used the finite and infinite time optimal solution is a piecewise affine state feedback control law. In this paper, we present algorithms that compute the optimal solution to both problems in a computationally efficient manner and with guaranteed convergence and error bounds. Both algorithms combine a dynamic programming exploration strategy with multiparametric linear programming and basic polyhedral manipulation. [ABSTRACT FROM AUTHOR]

This paper describes an approach to the control of continuous systems through the use of symbolic models describing the system behavior only at a finite number of points in the state space. These symbolic models can be seen as abstract representations of the continuous dynamics enabling the use of algorithmic controller design methods. We identify a class of linear control systems for which the loss of information incurred by working with symbolic subsystems can be compensated by feedback. We also show how to transform symbolic controllers designed for a symbolic subsystem mb controllers for the original system. The resulting controllers combine symbolic controller dynamics with continuous feedback control laws and can thus be seen as hybrid systems. Furthermore, if the symbolic controller already accounts for software/hardware requirements, the hybrid controller is guaranteed to enforce the desired specifications by construction thereby reducing the need for formal verification. [ABSTRACT FROM AUTHOR]

Iterative algorithms for continuous numerical optimization typically need to adapt their step lengths in the course of the search. While some strategies employ fixed schedules, others attempt to adapt dynamically in response to the outcome of trial steps or the history of the search process. Evolutionary algorithms are of the latter kind. A control strategy that is commonly used in evolution strategies is the cumulative step length adaptation approach. This paper presents a theoretical analysis of that adaptation strategy. The analysis includes the practically relevant case of noise interfering in the optimization process. Recommendations are made with respect to choosing appropriate population sizes. [ABSTRACT FROM AUTHOR]

Abstracts are presented for papers published in the journal including for "Attack Detection and Identification in Cyber-Physical Systems," by F. Pasqualetti, F. Dörfler and F. Bullo, "Nonuniform Coverage Control On The Line," by N. E. Leonard and A. Olshevsky, and "Coordinated One-Step Optimal Distributed State Prediction For A Networked Dynamical System," by T. Zhou.