Search

This paper studies consensus problems of multi-agent systems with binary-valued communications. Different from most existing works, the agents considered in this paper can only get binary-valued observations of its neighbors’ states with random noises. A consensus algorithm is proposed: first, each agent estimates its neighbors’ states by the recursive projection algorithm; then, each agent designs the control timely based on the estimates. It is proved that the estimates of the states can converge to the true states with a faster convergence rate than that in the parameter estimation. Moreover, the states of the agents can achieve mean-square consensus, and the corresponding consensus speed can achieve $O(1/t)$ under certain conditions. Finally, simulations are given to demonstrate the theoretical results. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the proper orthogonal decomposition (POD) method to numerically solve the forward Kolmogorov equation (FKE). Our method aims to explore the low-dimensional structures in the solution space of the FKE and to develop efficient numerical methods. As an important application and our primary motivation to study the POD method to FKE, we solve the nonlinear filtering (NLF) problems with a real-time algorithm proposed by Yau and Yau combined with the POD method. This algorithm is referred as POD algorithm in this paper. Our POD algorithm consists of offline and online stages. In the offline stage, we construct a small number of POD basis functions that capture the dynamics of the system and compute propagation of the POD basis functions under the FKE operator. In the online stage, we synchronize the coming observations in a real-time manner. Its convergence analysis has also been discussed. Some numerical experiments of the NLF problems are performed to illustrate the feasibility of our algorithm and to verify the convergence rate. Our numerical results show that the POD algorithm provides considerable computational savings over existing numerical methods. [ABSTRACT FROM AUTHOR]

In this paper, two control schemes producing a continuous control signal are presented for a perturbed triple integrator: The continuous twisting algorithm (3-CTA) and the output feedback continuous twisting algorithm (3-OFCTA). The first one is a state feedback controller that ensures global finite-time stability of the origin, despite of Lipschitz, nonvanishing, and matched disturbances. It provides steady-state precision of fourth order of the output w.r.t. sampling step. The second one is an output feedback controller, which uses a third-order robust and exact differentiator as an observer. By requiring only information of the measurable output, the 3-OFCTA preserves all features of robustness, convergence, and precision of the state feedback 3-CTA. Moreover, it is proven that a separation principle applies, so that the gains of the controller and of the observer can be selected independently to assure stability. [ABSTRACT FROM AUTHOR]

This paper considers an unconstrained collaborative optimization of a sum of convex functions, where agents make decisions using local information in the presence of random interconnection topologies. We recast the problem as minimization of the sum of convex functions over a constraint set defined as the set of fixed-value points of a random operator derived from weighted matrices of random graphs. We show that the derived random operator has nonexpansivity property; therefore, this formulation does not need the distribution of random communication topologies. Hence, it includes random networks with/without asynchronous protocols. As an extension of the problem, we define a novel optimization problem, namely minimization of a convex function over the fixed-value point set of a nonexpansive random operator. We propose a discrete-time algorithm using diminishing step size for converging almost surely and in mean square to the global solution of the optimization problem under suitable assumptions. Consequently, as a special case, it reduces to a totally asynchronous algorithm for the distributed optimization problem. We show that fixed-value point is a bridge from deterministic analysis to random analysis of the algorithm. Finally, a numerical example illustrates the convergence of the proposed algorithm. [ABSTRACT FROM AUTHOR]

This paper proposes an iterative learning control (ILC) algorithm with gain adaptation for discrete-time stochastic systems. The algorithm is based on Kesten's accelerated stochastic approximation (SA) algorithm. The gain adaptation uses only tracking error information, and, hence, is a data-driven adaptation approach. If stochastic noises account for a small proportion of the tracking error, the learning gain matrix remains constant with a high probability. If stochastic noises dominate the tracking error, the learning gain matrix is decreasing. Therefore, the new ILC algorithm converges more quickly than existing SA-based algorithms. In addition, the classic P-type ILC law for noise-free systems is a special case of the new ILC algorithm. The behaviors of the proposed ILC algorithm are demonstrated through examples. [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 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]

We consider the problem of two-player zero-sum games. This problem is formulated as a min–max Markov game in this article. The solution of this game, which is the min–max payoff, starting from a given state is called the min–max value of the state. In this article, we compute the solution of the two-player zero-sum game, utilizing the technique of successive relaxation that has been successfully applied in this article to compute a faster value iteration algorithm in the context of Markov decision processes. We extend the concept of successive relaxation to the setting of two-player zero-sum games. We show that, under a special structure on the game, this technique facilitates faster computation of the min–max value of the states. We then derive a generalized minimax Q-learning algorithm, which computes the optimal policy when the model information is not known. Finally, we prove the convergence of the proposed generalized minimax Q-learning algorithm utilizing stochastic approximation techniques, under an assumption on the boundedness of iterates. Through experiments, we demonstrate the [ABSTRACT FROM AUTHOR]

This paper presents a discrete-time distributed and noncooperative routing algorithm, which is proved, via Lyapunov arguments, to asymptotically converge to a specific equilibrium condition among the traffic flows over the network paths, known as Wardrop equilibrium. This convergence result improves the discrete-time algorithms in the literature, which achieve approximate convergence to the Wardrop equilibrium. Numerical simulations show the effectiveness of the proposed approach. [ABSTRACT FROM AUTHOR]

This paper presents a bounded confidence gossip algorithm for describing the process of opinion formation over a communication network. Each agent in the network keeps a time-varying opinion vector (or state), which represents its opinion about a set of matters. A common confidence threshold is set for all of the agents. The states of agents in the network will be updated time by time according to an iterative procedure: At each time, 1) one agent is chosen randomly, then it chooses one of its neighbors on the communication graph to contact with; 2) they exchange their states; and 3) if they have different states and the distance between their states is strictly smaller than the confidence threshold, they update their states as the average of the two. This algorithm converges almost surely to some equilibrium point such that any two adjacent agents either have the same state or have distinct states whose distance is no less than the confidence threshold. This is called the constant confidence threshold algorithm. An increasing confidence threshold algorithm, which repeats the constant confidence threshold algorithm several times with increasing confidence threshold, is also proposed. The algorithm is also convergent almost surely to some equilibrium point. Applicability of the method to clustering problems is shown through numerical examples. [ABSTRACT FROM AUTHOR]

In this paper, we propose a distance-based formation control strategy for a group of mobile agents to achieve almost global convergence to a target formation shape provided that the formation is represented by a complete graph, and each agent is governed by a single-integrator model. The fundamental idea of achieving almost global convergence is to use a virtual formation of which the dimension is augmented with some virtual coordinates. We define a cost function associated with the virtual formation and apply the gradient-descent algorithm to the cost function so that the function has a global minimum at the target formation shape. We show that all agents finally achieve the target formation shape for almost all initial conditions under the proposed control law. [ABSTRACT FROM AUTHOR]

This paper proposes a continuous-time distributed algorithm for multiagent networks to achieve a solution with the minimum $l_1$ -norm to underdetermined linear equations. The proposed algorithm comes from a combination of the Filippov set-valued map with the projection-consensus flow. Given the underlying network is undirected and fixed, it is shown that the proposed algorithm drives all agents’ individual states to converge in finite time to a common value, which is the minimum $l_1$ -norm solution. [ABSTRACT FROM AUTHOR]

We consider distributed computation of generalized Nash equilibrium (GNE) over networks, in games with shared coupling constraints. Existing methods require that each player has full access to opponents’ decisions. In this paper, we assume that players have only partial-decision information, and can communicate with their neighbors over an arbitrary undirected graph. We recast the problem as that of finding a zero of a sum of monotone operators through primal-dual analysis. To distribute the problem, we doubly augment variables, so that each player has local decision estimates and local copies of Lagrangian multipliers. We introduce a single-layer algorithm, fully distributed with respect to both primal and dual variables. We show its convergence to a variational GNE with fixed step sizes, by reformulating it as a forward–backward iteration for a pair of doubly-augmented monotone operators. [ABSTRACT FROM AUTHOR]

Many problems of interest for cyber-physical network systems can be formulated as mixed-integer linear programs in which the constraints are distributed among the agents. In this paper, we propose a distributed algorithmic framework to solve this class of optimization problems in a peer-to-peer network with no coordinator and with limited computation and communication capabilities. At each communication round, agents locally solve a small linear program, generate suitable cutting planes, and communicate a fixed number of active constraints. Within the distributed framework, we first propose an algorithm that, under the assumption of integer-valued optimal cost, guarantees finite-time convergence to an optimal solution. Second, we propose an algorithm for general problems that provides a suboptimal solution up to a given tolerance in a finite number of communication rounds. Both algorithms work under asynchronous, directed, unreliable networks. Finally, through numerical computations, we analyze the algorithm scalability in terms of the network size. Moreover, for a multi-agent multi-task assignment problem, we show, consistently with the theory, its robustness to packet loss. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of achieving average consensus over a random time-varying sequence of directed graphs by extending the class of so-called push-sum algorithms to such random scenarios. Provided that an ergodicity notion, which we term the directed infinite flow property, holds and the auxiliary states of agents are uniformly bounded away from zero infinitely often, we prove the almost sure convergence of the evolutions of this class of algorithms to the average of initial states. Moreover, for a random sequence of graphs generated using a so-called time-varying $B$ -irreducible probability matrix, we establish convergence rates for the proposed push-sum algorithm. [ABSTRACT FROM AUTHOR]

This paper concerns a spectral estimation problem in which we want to find a spectral density function that is consistent with estimated second-order statistics. It is an inverse problem admitting multiple solutions, and selection of a solution can be based on prior functions. We show that the problem is well-posed when formulated in a parametric fashion, and that the solution parameter depends continuously on the prior function. In this way, we are able to obtain a smooth parametrization of admissible spectral densities. Based on this result, the problem is reparametrized via a bijective change of variables out of a numerical consideration, and then a continuation method is used to compute the unique solution parameter. Numerical aspects, such as convergence of the proposed algorithm and certain computational procedures are addressed. A simple example is provided to show the effectiveness of the algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we propose a distributed Newton method for decenteralized optimization of large sums of convex functions. Our proposed method is based on creating a set of separable finite sum minimization problems by utilizing a decomposition technique known as Global Consensus that distributes the computation across nodes of a graph and enforces a consensus constraint among the separated variables. The key idea is to exploit the sparsity of the dual Hessian and recast the computation of the Newton step as one of the efficiently solving symmetric diagonally dominant linear equations. We show that our method outperforms the state-of-the-art algorithms, including ADMM. We validate our algorithm both theoretically and empirically. On the theory side, we demonstrate that our algorithm exhibits superlinear convergence within a neighborhood of optimality. Empirically, we show the superiority of this new method on a variety of large-scale optimization problems. The proposed approach is scalable to large problems and has a low communication overhead. [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]

Consider a connected network of agents endowed with local cost functions representing private objectives. Agents seek to find an agreement on some minimizer of the aggregate cost, by means of repeated communications between neighbors. Consensus on the average over the network, usually addressed by gossip algorithms, is a special instance of this problem, corresponding to quadratic private objectives. Consensus on the median, or more generally, consensus on a given quantile, is also a special instance of this problem. In this paper we show that optimizing the aggregate cost function regularized by a total variation (TV) term has appealing properties. First, it can be done very naturally in a distributed way, yielding algorithms that are efficient on numerical simulations. Secondly, the optimum for the regularized cost is shown to be also the optimum for the initial aggregate cost function under assumptions that are simple to state. Finally, these algorithms are robust to unreliable agents that keep injecting some false value in the network. This is remarkable enough, and is not the case, for instance, of gossip algorithms that are entirely ruled by unreliable agents as detailed in the paper. [ABSTRACT FROM PUBLISHER]

This paper considers the problem of a leader that seeks to optimally influence the opinions of agents in a directed network through connecting with a limited number of the agents (“direct followers”), possibly in the presence of a fixed competing leader. The settings involving a single leader and two competing leaders are unified into a general combinatoric optimization problem, for which two heuristic approaches are developed. The first approach is based on a convex relaxation scheme, possibly in combination with the $\ell _1$ -norm regularization technique, and the second is based on a greedy selection strategy. The main technical novelties of this work are in the establishment of supermodularity of the objective function and convexity of its continuous relaxation. The greedy approach is guaranteed to have a lower bound on the approximation ratio sharper than $(1-1/e)$ , while the convex approach can benefit from efficient (customized) numerical solvers to have practically comparable solutions possibly with faster computation times. The two approaches can be combined to provide improved results. In numerical examples, the approximation ratio can be made to reach ${\text{90}\%}$ or higher depending on the number of direct followers. [ABSTRACT FROM AUTHOR]

In this paper, we study the interacting multiple model (IMM) estimator for networked control systems with packet loss but without packet acknowledgment (ACK). The ACK is a signal sent by the actuator to inform the estimator of whether control packets are lost or not. A system with ACK is usually called a transmission control protocol (TCP) like system; otherwise, it is called a user datagram protocol (UDP) like system. We show that the stability of the IMM estimator for UDP-like systems is determined by the observation packet arrival rate (p.a.r.) and is independent of the control p.a.r. and control inputs. The IMM estimator is stable if the observation p.a.r. is greater than a critical value. We show that this critical value is the same as the critical value for the stability of the optimal estimator for its corresponding TCP-like system. If control inputs eventually tend to zero, the error covariance of the IMM estimator converges to that of the optimal estimator for TCP-like systems. We characterize the impact of the control/observation p.a.r. and the control input on estimation performance. Finally, we prove that the average estimation performance of the IMM estimator approximates that of the optimal estimator within a finite bound, and is superior to that of the linear minimum mean square error estimator. [ABSTRACT FROM AUTHOR]

This paper proposes a distributed model predictive control (MPC) approach for a family of discrete-time linear systems with local (uncoupled) and global (coupled) constraints. The proposed approach is based on the dual problem of an overall MPC optimization problem involving all systems, which is then solved distributively using a modified distributed Nesterov-accelerated-gradient algorithm. To further reduce the computational requirement, this approach allows for early termination of the distributed gradient algorithm. This is made possible via a consensus algorithm that determines the satisfaction of the termination condition and by appropriate tightening of the coupled constraints. Under reasonable assumptions, the approach is able to produce a suboptimal solution as long as the network of the systems is connected while ensuring recursive feasibility and exponential stability of the closed-loop system. The performance of the proposed approach is demonstrated by a numerical example. [ABSTRACT FROM AUTHOR]

The problems discussed in this article are motivated by general ratio consensus algorithms, introduced by Kempe et al. in 2003 in a simple form as the push-sum algorithm, later extended by Bénézit et al. in 2010 under the name weighted gossip algorithm. We consider a communication protocol described by a strictly stationary, ergodic, sequentially primitive sequence of nonnegative matrices, applied iteratively to a pair of fixed initial vectors, the components of which are called values and weights defined at the nodes of a network. The subject of ratio consensus problems is to study the asymptotic properties of ratios of values and weights at each node, expecting convergence to the same limit for all nodes. The main results of this article provide upper bounds for the rate of the almost sure exponential convergence in terms of the spectral gap associated with the given sequence of random matrices. It will be shown that these upper bounds are sharp. Our results complement previous results of Picci and Taylor in 2013 and Iutzeler et al. in 2013. [ABSTRACT FROM AUTHOR]

An accelerated algorithm is proposed in this article for solving the linear quadratic optimal consensus problem of multiagent systems. To optimize the linear quadratic response and the final consensus state simultaneously, a nonseparable multiobjective optimization problem with coupled constraints on decision variables is formulated. The main difficulty in solving the optimization problem lies in the nonlinear coupling of objectives, which is overcome by separating the problem into two independent and solvable single-objective optimization subproblems using the alternating direction method of multipliers. The proximal gradient decent scheme is then introduced to approximate the precise optimal solutions of the subproblems so as to improve the computing efficiency. Convergence analysis is performed to estimate the convergence rate and derive the convergence condition, which is independent of any global information of the system and, therefore, is fully distributed. Furthermore, the solution of each subproblem is obtained in a distributed form, allowing the multiagent system to achieve optimal consensus. Numerical examples show the effectiveness of the accelerated algorithm. [ABSTRACT FROM AUTHOR]

There are only a few learning algorithms applicable to stochastic dynamic teams and games which generalize Markov decision processes to decentralized stochastic control problems involving possibly self-interested decision makers. Learning in games is generally difficult because of the non-stationary environment in which each decision maker aims to learn its optimal decisions with minimal information in the presence of the other decision makers who are also learning. In stochastic dynamic games, learning is more challenging because, while learning, the decision makers alter the state of the system and hence the future cost. In this paper, we present decentralized Q-learning algorithms for stochastic games, and study their convergence for the weakly acyclic case which includes team problems as an important special case. The algorithms are decentralized in that each decision maker has access only to its own decisions and cost realizations as well as the state transitions; in particular, each decision maker is completely oblivious to the presence of the other decision makers. We show that these algorithms converge to equilibrium policies almost surely in large classes of stochastic games. [ABSTRACT FROM AUTHOR]

In this paper, we present complexity certification results for a distributed augmented Lagrangian (AL) algorithm used to solve convex optimization problems involving globally coupled linear constraints. Our method relies on the accelerated distributed AL (ADAL) algorithm, which can handle the coupled linear constraints in a distributed manner based on local estimates of the AL. We show that the theoretical complexity of ADAL to reach an $\epsilon$-optimal solution both in terms of suboptimality and infeasibility is O(\frac{1}{\epsilon }) iterations. Moreover, we provide a valid upper bound for the optimal dual multiplier, which enables us to explicitly specify these complexity bounds. We also show how to choose the step-size parameter to minimize the bounds on the convergence rates. Finally, we discuss a motivating example, a model predictive control problem, involving a finite number of subsystems, which interact with each other via a general network. [ABSTRACT FROM PUBLISHER]

In this paper, source localization by a network of primitive binary sensors under various imperfections are studied. Detailed analysis and mathematical modeling of imperfect binary sensors are presented. Imperfections include sensor failures of two types, drifting, uncertainty, and heterogeneity in binary sensor trigger thresholds, presence of noise, and nonradial symmetry of sensing ranges. Theoretical results, including asymptotical convergence, are established, in particular in the presence of substantial outliers due to sensor failure and large noise. Efficient numerical algorithms are proposed and simulated supporting the theoretical analysis. [ABSTRACT FROM PUBLISHER]

A consensus problem consists of a group of dynamic agents who seek to agree upon certain quantities of interest. This problem can be generalized in the context of convex metric spaces that extend the standard notion of convexity. In this paper we introduce and analyze a randomized gossip algorithm for solving the generalized consensus problem on convex metric spaces, where the communication between agents is controlled by a set of Poisson counters. We study the convergence properties of the algorithm using stochastic calculus. In particular, we show that the distances between the states of the agents converge to zero with probability one and in the r^th mean sense. In the special case of complete connectivity and uniform Poisson counters, we give upper bounds on the dynamics of the first and second moments of the distances between the states of the agents. In addition, we introduce instances of the generalized consensus algorithm for several examples of convex metric spaces together with numerical simulations. [ABSTRACT FROM AUTHOR]

Controlled interacting particle systems such as the ensemble Kalman filter (EnKF) and the feedback particle filter (FPF) are numerical algorithms to approximate the solution of the nonlinear filtering problem in continuous time. The distinguishing feature of these algorithms is that the Bayesian update step is implemented using a feedback control law. It has been noted in the literature that the control law is not unique. This is the main problem addressed in this article. To obtain a unique control law, the filtering problem is formulated here as an optimal transportation problem. An explicit formula for the (mean-field type) optimal control law is derived in the linear Gaussian setting. Comparisons are made with the control laws for different types of EnKF algorithms described in the literature. Via empirical approximation of the mean-field control law, a finite- $N$ controlled interacting particle algorithm is obtained. For this algorithm, the equations for empirical mean and covariance are derived and shown to be identical to the Kalman filter. This allows strong conclusions on convergence and error properties based on the classical filter stability theory for the Kalman filter. It is shown that, under certain technical conditions, the mean squared error converges to zero even with a finite number of particles. A detailed propagation of chaos analysis is carried out for the finite- $N$ algorithm. The analysis is used to prove weak convergence of the empirical distribution as $N\rightarrow \infty$. For a certain simplified filtering problem, analytical comparison of the mse with the importance sampling-based algorithms is described. The analysis helps explain the favorable scaling properties of the control-based algorithms reported in several numerical studies in recent literature. [ABSTRACT FROM AUTHOR]

We study the robustness of accelerated first-order algorithms to stochastic uncertainties in gradient evaluation. Specifically, for unconstrained, smooth, strongly convex optimization problems, we examine the mean-squared error in the optimization variable when the iterates are perturbed by additive white noise. This type of uncertainty may arise in situations where an approximation of the gradient is sought through measurements of a real system or in a distributed computation over a network. Even though the underlying dynamics of first-order algorithms for this class of problems are nonlinear, we establish upper bounds on the mean-squared deviation from the optimal solution that are tight up to constant factors. Our analysis quantifies fundamental tradeoffs between noise amplification and convergence rates obtained via any acceleration scheme similar to Nesterov's or heavy-ball methods. To gain additional analytical insight, for strongly convex quadratic problems, we explicitly evaluate the steady-state variance of the optimization variable in terms of the eigenvalues of the Hessian of the objective function. We demonstrate that the entire spectrum of the Hessian, rather than just the extreme eigenvalues, influences robustness of noisy algorithms. We specialize this result to the problem of distributed averaging over undirected networks and examine the role of network size and topology on the robustness of noisy accelerated algorithms. [ABSTRACT FROM AUTHOR]

In this technical note, the fast alternating minimization algorithm (FAMA) is proposed to solve model predictive control (MPC) problems with polytopic and second-order cone constraints. Two splitting strategies with efficient implementations for MPC problems are presented. We derive computational complexity certificates for both splitting strategies, by providing complexity upper-bounds on the number of iterations required to provide a certain accuracy of the dual function value and, most importantly, of the primal solution. This is of particular relevance in the context of real-time MPC in order to bound the required online computation time. We further address the computation of the complexity bounds, requiring the solution of a non-convex minimization problem. Finally, we demonstrate the performance of FAMA compared to other splitting methods using a quadrotor example. [ABSTRACT FROM PUBLISHER]

A generalized family of adversary robust consensus protocols is proposed and analyzed. These are distributed algorithms for multiagent systems seeking to agree on a common value of a shared variable, even in the presence of faulty or malicious agents, which are updating their local state according to the protocol rules. In particular, we adopt monotone joint-agent interactions, a very general mechanism for processing locally available information and allowing cross-comparisons between state-values of multiple agents simultaneously. The salient features of the proposed class of algorithms are abstracted as a Petri net and convergence criteria for the resulting time evolutions formulated by employing structural invariants of the net. [ABSTRACT FROM AUTHOR]

This article focuses on distributed convex optimization problems over an unbalanced directed multiagent (no central coordinator) network with inequality constraints. The goal is to cooperatively minimize the sum of all locally known convex cost functions. Every single agent in the network only knows its local objective function and local inequality constraint, and is constrained to a privately known convex set. Furthermore, we particularly discuss the scenario in which the interactions among agents over the whole network are subjected to possible link failures. To collaboratively solve the optimization problem, we mainly concentrate on an epigraph form of the original constrained optimization to overcome the unbalancedness of directed networks, and propose a new distributed asynchronous broadcast-based optimization algorithm. The algorithm allows that not only the updates of agents are asynchronous in a distributed fashion, but also the step-sizes of all agents are uncoordinated. An important characteristic of the proposed algorithm is to cope with the constrained optimization problem in the case of unbalanced directed networks whose communications are subjected to possible link failures. Under two standard assumptions that the communication network is directly strongly connected and the subgradients of all local objective functions are bounded, we provide an explicit analysis for convergence of the algorithm. Simulation results obtained by three numerical experiments substantiate the feasibility of the algorithm and validate the theoretical findings. [ABSTRACT FROM AUTHOR]

This article presents a leader–follower scheme for network aggregative games. The followers and leader are selfish cost minimizing agents. The cost function of each follower is affected by its own strategy, the strategy of leader and the aggregate strategy of its neighbors through a communication graph. Also, the leader's cost function depends on its own strategy and the aggregate strategy of all the followers. The leader infinitely often wakes up, receives the aggregate strategy of the followers, updates its decision value, and broadcasts it to all the followers. Then, the followers apply the updated strategy of the leader into their cost functions. The establishment of information exchange between each neighboring pair of followers, and also, decision updating by a follower at each iteration, that is to say the activeness of the follower in that iteration, are both considered to be drawn from two arbitrary distributions. Moreover, a distributed algorithm based on subgradient method is proposed for updating the strategies of leader and followers. The convergence of the proposed algorithm to the unique Stackelberg equilibrium point of the game is proven in both almost sure and mean square senses. [ABSTRACT FROM AUTHOR]

This article investigates the problem of distributed hypothesis testing over networks. By introducing double and triple cumulations of historical observations, two novel distributed learning algorithms are developed to solve the considered problem. Within this framework, we study the convergence rates of the proposed algorithms. More specifically: 1) It is proven that the algorithm with double cumulation of historical observations has a faster convergence rate than those of the existing algorithms. 2) Furthermore, it is proven that the algorithm with triple cumulation of historical observations can be further accelerated. Especially, based on the theoretical results, this article shows that a tradeoff among convergence rate, transient performance, and memory burden exists in the proposed algorithms. Finally, simulation examples verify the theoretical results. [ABSTRACT FROM AUTHOR]

Multi-agent consensus algorithms, with update steps based on so-called balanced asymmetric chains, are analyzed. For such algorithms, it is shown that: (i) the empirical distribution of state values converges asymptotically and (ii) the occurrence of consensus or multiple consensus is directly related to the property of absolute infinite flow of the underlying update chain. An example is provided to illustrate the novelty of the results. [ABSTRACT FROM PUBLISHER]

In this article, we address the design and analysis of multivariable Newton-based extremum seeking (ES) for static locally quadratic maps subject to actuation dynamics governed by diffusion partial differential equations (PDEs). Multi-input systems with distinct diffusion coefficients in each individual input channel are dealt with. The phase compensation of the dither signals is handled as a trajectory generation problem and the inclusion of a multivariable diffusion feedback controller with a perturbation-based (averaging-based) estimate of the Hessian's inverse allow to obtain local exponential convergence results to a small neighborhood of the optimal point. The stability analysis is carried out using backstepping transformation and averaging in infinite dimensions, capturing the infinite-dimensional state due the diffusion PDEs. In addition, the generalization of the results for different classes of parabolic (reaction–advection–diffusion) PDEs, wave equations and/or first-order hyperbolic (transport-dominated) PDEs is also discussed. As for ordinary differential equations case, the proposed Newton approach removes the dependence of the algorithm's convergence rate on the unknown Hessian of the nonlinear map to be optimized, being user-assignable unlike the gradient algorithm. A numerical example illustrates the performance of our multivariable ES for compensating PDE-based systems. [ABSTRACT FROM AUTHOR]

In this article, we provide a distributed optimization algorithm, termed as TV- AB, that minimizes a sum of convex functions over time-varying, random directed graphs. Contrary to the existing work, the algorithm we propose does not require eigenvector estimation to estimate the (non-1) Perron eigenvector of a stochastic matrix. Instead, the proposed approach relies on a novel information mixing approach that exploits both row- and column-stochastic weights to achieve agreement toward the optimal solution when the underlying graph is directed. We show that TV-AB converges linearly to the optimal solution when the global objective is smooth and strongly convex, and the underlying time-varying graphs exhibit bounded connectivity, i.e., a union of every C consecutive graphs is strongly connected. We derive the convergence results based on the stability analysis of a linear system of inequalities along with a matrix perturbation argument. Simulations confirm the findings in this article. [ABSTRACT FROM AUTHOR]

This article develops a proximal primal–dual decentralized strategy for multiagent optimization problems that involve multiple coupled affine constraints, where each constraint may involve only a subset of the agents. The constraints are generally sparse, meaning that only a small subset of the agents are involved in them. This scenario arises in many applications, including decentralized control formulations, resource allocation problems, and smart grids. Traditional decentralized solutions tend to ignore the structure of the constraints and lead to degraded performance. We instead develop a decentralized solution that exploits the sparsity structure. Under constant step-size learning, the asymptotic convergence of the proposed algorithm is established in the presence of nonsmooth terms, and it occurs at a linear rate in the smooth case. We also examine how the performance of the algorithm is influenced by the sparsity of the constraints. Simulations illustrate the superior performance of the proposed strategy. [ABSTRACT FROM AUTHOR]

This article considers resilient cooperative state estimation in unreliable multiagent networks. A network of agents aim to collaboratively estimate the value of an unknown vector parameter, while an unknown subset of agents suffer Byzantine faults. We refer to the faulty agents as Byzantine agents. Byzantine agents malfunction arbitrarily and may send out highly unstructured messages to other agents in the network. As opposed to fault-free networks, reaching agreement in the presence of Byzantine agents is far from trivial. In this article, we propose a computationally efficient algorithm that is provably robust to Byzantine agents. At each iteration of the algorithm, a good agent performs a gradient descent update based on noisy local measurements, exchanges its update with other agents in its neighborhood, and robustly aggregates the received messages using coordinate-wise trimmed means. Under mild technical assumptions, we establish that good agents learn the true parameter asymptotically in almost sure sense. We further complement our analysis by proving (high probability) finite-time convergence rate, encapsulating network characteristics. [ABSTRACT FROM AUTHOR]

Persistent excitation (PE) conditions have been widely used to analyze stability properties of various parameter identification algorithms and to establish uniform global asymptotic stability (UGAS) for a large class of nonlinear time-varying systems. In order to generalize such conditions to a more general setting, a new PE condition is proposed with three basic ingredients: a signal set to represent a family of time functions (e.g., trajectories); a pseudo distance measure to describe the convergence; and some binary relations (e.g., state-to-output relations). Closely related to detectability, this PE condition is a necessary condition to guarantee UGAS. Under uniform global stability and an integral inequality, it becomes a sufficient condition of UGAS. A novel concept: M-pair, which aims at simplifying the checking of the PE condition, is introduced. By using M-pair, it is possible to simplify the structure of the referred signal set (in the spirit of the classic Krasovskii-LaSalle theorem) and to extend the dimension of the reference signal set (similar to the Matrosov theorem). Thus, the framework of M-pair not only unifies these well-known results, but also generates more flexibility in checking the PE conditions. When applied to nonlinear switched systems, three new tools to verify the PE condition are obtained. Finally, an example illustrates that a nonlinear time-varying switched system with arbitrary switching can be shown to be UGAS without using a common Lyapunov function. [ABSTRACT FROM AUTHOR]

Inspired by the subgradient push method developed recently by Nedić et al. we present a distributed dual averaging push algorithm for constrained nonsmooth convex optimization over time-varying directed graph. Our algorithm combines the dual averaging method with the push-sum technique and achieves an $O(1/ \sqrt{k})$ convergence rate. Compared with the subgradient push algorithm, our algorithm, first, addresses the constrained problems, and, second, has a faster convergence rate, and, third, simplifies the convergence analysis. We also generalize the proposed algorithm so that input variables of subgradient oracles have guaranteed convergence. [ABSTRACT FROM AUTHOR]

This note develops a distributed algorithm to solve a convex optimization problem with coupled constraints. Both coupled equality and inequality constraints are considered, where functions in the equality constraints are affine and functions in the inequality constraints are convex. Different from primal-dual subgradient methods with decreasing stepsizes for nonsmooth optimizations, our algorithm focuses on smooth problems and uses a fixed stepsize to find the exact optimal solution. Convergence analysis is derived with rigorous proofs. Our result is also illustrated by simulations. [ABSTRACT FROM AUTHOR]

Operator splitting techniques have recently gained popularity in convex optimization problems arising in various control fields. Being fixed-point iterations of nonexpansive (NE) operators, such methods suffer many well known downsides, which include high sensitivity to ill conditioning and parameter selection, and consequent low accuracy and robustness. As universal solution we propose SuperMann, a Newton-type algorithm for finding fixed points of NE operators. It generalizes the classical Krasnosel'skii–Mann scheme, enjoys its favorable global convergence properties and requires exactly the same oracle. It is based on a novel separating hyperplane projection tailored for nonexpansive mappings which makes it possible to include steps along any direction. In particular, when the directions satisfy a Dennis–Moré condition we show that SuperMann converges superlinearly under mild assumptions, which, surprisingly, do not entail nonsingularity of the Jacobian at the solution but merely metric subregularity. As a result, SuperMann enhances and robustifies all operator splitting schemes for structured convex optimization, overcoming their well known sensitivity to ill conditioning. [ABSTRACT FROM AUTHOR]

This technical note considers the dynamic average consensus problem, where a group of networked agents are required to estimate the average of their time-varying reference signals. Almost all existing solutions to this problem require a specific initialization of the estimator states, and such constraints render the algorithms vulnerable to network disruptions. Here, we present three robust algorithms that do not entail any initialization criteria. Furthermore, the proposed algorithms do not rely on the full knowledge of the dynamics generating the reference signals nor assume access to its time derivatives. Two of the proposed algorithms focus on undirected networks and make use of an adaptive scheme that removes the explicit dependence of the algorithm on any upper bounds on the reference signals or its time derivatives. The third algorithm presented here provides a robust solution to the dynamic average consensus problem on directed networks. Compared to the existing algorithms for directed networks, the proposed algorithm guarantees an arbitrarily small steady-state error bound that is independent of any bounds on the reference signals or its time derivatives. The current formulation allows each agent to select its own performance criteria, and the algorithm parameters are distributedly selected such that the most stringent requirement among them is satisfied. A performance comparison of the proposed approach to existing algorithms is presented. [ABSTRACT FROM AUTHOR]

Self-stabilizing distance estimation algorithms are an important building block of many distributed systems, such as seen in the emerging field of aggregate computing. Their safe use in feedback systems or under persistent perturbations has not previously been formally analyzed. Self-stabilization only involves eventual convergence, and is not endowed with robustness properties associated with global uniform asymptotic stability and thus does not guarantee stability under perturbations or feedback. We formulate a Lyapunov function to analyze the Adaptive Bellman–Ford distance estimation algorithm and use it to prove global uniform asymptotic stability, a property which the classical Bellman–Ford algorithm lacks. Global uniform asymptotic stability assures a measure of robustness to structural perturbations, empirically observed by us in a previous work. We also show that the algorithm is ultimately bounded under bounded measurement error and device mobility and provide a tight bound on the ultimate bound and the time to attain it. [ABSTRACT FROM AUTHOR]

We consider the distributed integer-weight-balancing problem in networks of nodes that are interconnected via directed edges, each able to admit a positive integer weight (or flow) within a certain interval, captured by lower and upper limits. We propose and analyze distributed iterative algorithms for obtaining admissible and balanced integer weights, i.e., integer weights within the given interval constraints, such that, for each node, the sum of the weights of the incoming edges equals the sum of the weights of the outgoing edges. The proposed algorithms assume that communication among pairs of nodes that are interconnected is bidirectional and are shown to lead to a set of admissible and balanced integer weights after a finite number of time steps (as long as the necessary and sufficient integer circulation conditions are satisfied on the given digraph). [ABSTRACT FROM AUTHOR]

We present novel results on the solution of a class of leavable, undiscounted optimal control problems in the minimax sense for nonlinear, continuous-state, discrete-time plants. The problem class includes entry-(exit-)time problems as well as minimum-time, pursuit-evasion, and reach-avoid games as special cases. We utilize auxiliary optimal control problems (“abstractions”) to compute both upper bounds of the value function, i.e., of the achievable closed-loop performance, and symbolic feedback controllers realizing those bounds. The abstractions are obtained from discretizing the problem data, and we prove that the computed bounds and the performance of the symbolic controllers converge to the value function as the discretization parameters approach zero. In particular, if the optimal control problem is solvable on some compact subset of the state space, and if the discretization parameters are sufficiently small, then we obtain a symbolic feedback controller solving the problem on that subset. These results do not assume the continuity of the value function or any problem data, and they fully apply in the presence of hard state and control constraints. [ABSTRACT FROM AUTHOR]

This technical note studies finite-time consensus problem for a team of networked nonlinear agents with unknown Lipschitz terms under communication constraints, where each agent has a limited sensing range. Because the induced interaction graph is typically state-dependent and dynamic, we propose a distributed nonlinear consensus algorithm that is capable of preserving the initial interaction patterns. By using tools from nonsmooth analysis, sufficient conditions are obtained such that finite-time consensus can be reached. An upper bound of the convergence time is derived via a two-step analysis. The validity of the theoretical result is shown by one simulation example. [ABSTRACT FROM AUTHOR]

This paper is concerned with numerical methods for stochastic differential games of regime-switching diffusions. Numerical methods using Markov chain approximation techniques are developed. A new proof of the existence of a saddle point for the stochastic differential game is provided. This new proof enables us to treat certain systems with nonseparable (in controls) structure. Convergence of the algorithms is derived by means of weak convergence methods. In addition, examples are also provided for demonstration purposes. [ABSTRACT FROM AUTHOR]