Search

Emerging applications of control, estimation, and machine learning, from target tracking to decentralized model fitting, pose resource constraints that limit which of the available sensors, actuators, or data can be simultaneously used across time. Therefore, many researchers have proposed solutions within discrete optimization frameworks where the optimization is performed over finite sets. By exploiting notions of discrete convexity, such as submodularity, the researchers have been able to provide scalable algorithms with provable suboptimality bounds. In this article, we consider such problems but in adversarial environments, where in every step a number of the chosen elements in the optimization is removed due to failures/attacks. Specifically, we consider for the first time a sequential version of the problem that allows us to observe the failures and adapt, while the attacker also adapts to our response. We call the novel problem robust sequential submodular maximization (RSM). Generally, the problem is computationally hard and no scalable algorithm is known for its solution. However, in this article, we propose robust and adaptive maximization (RAM), the first scalable algorithm. RAM runs in an online fashion, adapting in every step to the history of failures. Also, it guarantees a near-optimal performance, even against any number of failures among the used elements. Particularly, RAM has both provable per-instance a priori bounds and tight and/or optimal a posteriori bounds. Finally, we demonstrate RAM's near-optimality in simulations across various application scenarios, along with its robustness against several failure types, from worst-case to random. [ABSTRACT FROM AUTHOR]

We investigate a linear-quadratic-Gaussian (LQG) control and sensing codesign problem, where one jointly designs sensing and control policies. We focus on the realistic case where the sensing design is selected among a finite set of available sensors, where each sensor is associated with a different cost (e.g., power consumption). We consider two dual problem instances: sensing-constrained LQG control, where one maximizes a control performance subject to a sensor cost budget, and minimum-sensing LQG control, where one minimizes a sensor cost subject to performance constraints. We prove that no polynomial time algorithm guarantees across all problem instances a constant approximation factor from the optimal. Nonetheless, we present the first polynomial time algorithms with per-instance suboptimality guarantees. To this end, we leverage a separation principle, which partially decouples the design of sensing and control. Then, we frame LQG codesign as the optimization of approximately supermodular set functions; we develop novel algorithms to solve the problems; and we prove original results on the performance of the algorithms and establish connections between their suboptimality and control-theoretic quantities. We conclude the article by discussing two applications, namely, sensing-constrained formation control and resource-constrained robot navigation. [ABSTRACT FROM AUTHOR]

This paper considers a class of stochastic source-seeking problems to drive a mobile robot to the minimizer of a source signal. Our approach is first analyzed in an obstacle-free scenario, where measurements of the signal at the robot location and information of a contact sensor are required. We extend our results to environments with obstacles under mild assumptions on the step size. Our approach builds on the simultaneous perturbation stochastic approximation idea to obtain information of the signal field. We prove the practical convergence of the algorithms to a ball whose size depends on the step size that contains the location of the source. The novelty relies in that we consider nondifferentiable convex functions, a fixed step size, and the environment may contain obstacles. Our proof methods employ nonsmooth Lyapunov function theory, tools from convex analysis, and stochastic difference inclusions. Finally, we illustrate the applicability of the proposed algorithms in a two-dimensional scenarios. [ABSTRACT FROM AUTHOR]

In this paper, we provide a detailed analysis of the global convergence properties of an extensively studied and extremely effective fixed-point algorithm for the Kullback–Leibler approximation of spectral densities, proposed by Pavon and Ferrante in their paper “On the Georgiou–Lindquist approach to constrained Kullback–Leibler approximation of spectral densities.” Our main result states that the algorithm globally converges to one of its fixed points. [ABSTRACT FROM AUTHOR]

A proper abstraction of a large-scale linear consensus network with a dense coupling graph is one whose number of coupling links is proportional to its number of subsystems and its performance is comparable to the original network. Optimal design problems for an abstracted network are more amenable to efficient optimization algorithms. From the implementation point of view, maintaining such networks are usually more favorable and cost-effective due to their reduced communication requirements across a network. Therefore, approximating a given dense linear consensus network by a suitable abstract network is an important analysis and synthesis problem. In this paper, we develop a framework to compute an abstraction of a given large-scale linear consensus network with guaranteed performance bounds using a nearly linear time algorithm. First, the existence of abstractions of a given network is proven. Then, we present an efficient and fast algorithm for computing a proper abstraction of a given network. Finally, we illustrate the effectiveness of our theoretical findings via several numerical simulations. [ABSTRACT FROM AUTHOR]

We consider large-scale Markov decision processes (MDPs) with a time-consistent risk measure of variability in cost under the risk-aware MDP paradigm. Previous studies showed that risk-aware MDPs, based on a minimax approach to handling risk, can be solved using dynamic programming for small- to medium-sized problems. However, due to the “curse of dimensionality,” MDPs that model real-life problems are typically prohibitively large for such approaches. In this technical note, we employ an approximate dynamic programming approach and develop a family of simulation-based algorithms to approximately solve large-scale risk-aware MDPs with time-consistent risk measures. In parallel, we develop a unified convergence analysis technique to derive sample complexity bounds for this new family of algorithms. [ABSTRACT FROM AUTHOR]

We propose an axiomatic approach for design and performance analysis of noisy linear consensus networks by introducing a notion of systemic performance measure. This class of measures are spectral functions of Laplacian eigenvalues of the network that are monotone, convex, and orthogonally invariant with respect to the Laplacian matrix of the network. It is shown that several existing gold-standard and widely used performance measures in the literature belong to this new class of measures. We build upon this new notion and investigate a general form of the combinatorial problem of growing a linear consensus network via minimizing a given systemic performance measure. Two efficient polynomial-time approximation algorithms are devised to tackle this network synthesis problem: a linearization-based method and a simple greedy algorithm based on rank-one updates. Several theoretical fundamental limits on the best achievable performance for the combinatorial problem are derived that assist us to evaluate optimality gaps of our proposed algorithms. A detailed complexity analysis confirms the effectiveness and viability of our algorithms to handle large-scale consensus networks. [ABSTRACT FROM AUTHOR]

Search algorithms for optimizing a complex problem are mainly categorized as gradient-driven and stochastic search, each with its advantages and shortcomings. A newly developed algorithm, GO-POLARS, is proposed with a hyperspherical coordinate framework, which could perturb a given direction with well-controlled variation. It designs a steerable stochastic search algorithm that explores toward a promising direction, such as the gradient, at any desired levels. In this note, we provide an analytical study on the hyperspherical coordinates and the corresponding random distributions and, thus, prove the local convergence property of the GO-POLARS. Extensive numerical experiments are illustrated to show its advantages compared to conventional search algorithms. [ABSTRACT FROM PUBLISHER]

In this paper, the decentralized partially observable Markov decision process (Dec-POMDP) systems with discrete state and action spaces are studied from a gradient point of view. Dec-POMDPs have recently emerged as a promising approach to optimizing multiagent decision making in the partially observable stochastic environment. However, the decentralized nature of the Dec-POMDP framework results in a lack of shared belief state, which makes the decision maker impossible to estimate the system state based on local information. In contrast to the belief-based policy, this paper focuses on optimizing the decentralized observation-based policy, which is easily to be applied and does not have the sharing problem. By analyzing the gradient of the objective function, we have developed a centralized stochastic gradient policy iteration algorithm to find the optimal policy on the basis of gradient estimates from a single sample path. This algorithm does not need any specific assumption and can be applied to most practical Dec-POMDP problems. One numerical example is provided to demonstrate the effectiveness of the algorithm. [ABSTRACT FROM AUTHOR]

The chemical master equation (CME) is well known to provide the highest resolution models of a biochemical reaction network. Unfortunately, even simulating the CME can be a challenging task. For this reason, simpler approximations to the CME have been proposed. In this paper, we focus on one such model, the linear noise approximation (LNA). Specifically, we consider implications of a recently proposed LNA time-scale separation method. We show that the reduced-order LNA converges to the full-order model in the mean square sense. Using this as motivation, we derive a network structure-preserving reduction algorithm based on structured projections. We discuss when these structured projections exist and we present convex optimization algorithms that describe how such projections can be computed. The algorithms are then applied to a linearized stochastic LNA model of the yeast glycolysis pathway. [ABSTRACT FROM PUBLISHER]

We study distributed non-convex optimization on a time-varying multi-agent network. Each node has access to its own smooth local cost function, and the collective goal is to minimize the sum of these functions. The perturbed push-sum algorithm was previously used for convex distributed optimization. We generalize the result obtained for the convex case to the case of non-convex functions. Under some additional technical assumptions on the gradients we prove the convergence of the distributed push-sum algorithm to some critical point of the objective function. By utilizing perturbations on the update process, we show the almost sure convergence of the perturbed dynamics to a local minimum of the global objective function, if the objective function has no saddle points. Our analysis shows that this perturbed procedure converges at a rate of $O(1/t)$ . [ABSTRACT FROM AUTHOR]

We present an on-line sensor selection strategy (SSS) for the Sequential Probability Ratio Test (SPRT) with multiple sensors. Each sensor incurs an associated observation cost. We aim to design an SSS, in which the sensor selection may depend causally on the measurement values, that minimizes the expected total observation cost. In general, the optimal SSS can be obtained by solving a dynamic program; however, the problem is computationally quite demanding. We propose a computationally efficient algorithm in which we partition the state space into three regions and solve for the SSS in each region. The computational complexity of the proposed algorithm is linear in the number of sensors and numerical results show that it can well approximate the optimal SSS. [ABSTRACT FROM PUBLISHER]

We present new algorithms for simulation optimization using random directions stochastic approximation (RDSA). These include first-order (gradient) as well as second-order (Newton) schemes. We incorporate both continuous-valued as well as discrete-valued perturbations into both types of algorithms. The former are chosen to be independent and identically distributed (i.i.d.) symmetric uniformly distributed random variables (r.v.), while the latter are i.i.d. asymmetric Bernoulli r.v.s. Our Newton algorithm, with a novel Hessian estimation scheme, requires $N$-dimensional perturbations and three loss measurements per iteration, whereas the simultaneous perturbation Newton search algorithm of [1] requires $2N$ -dimensional perturbations and four loss measurements per iteration. We prove the asymptotic unbiasedness of both gradient and Hessian estimates and asymptotic (strong) convergence for both first-order and second-order schemes. We also provide asymptotic normality results, which in particular establish that the asymmetric Bernoulli variant of Newton RDSA method is better than 2SPSA of [1]. Numerical experiments are used to validate the theoretical results. [ABSTRACT FROM PUBLISHER]

We investigate the control of evolutionary games on networks, in which each edge represents a two-player repeating game between neighboring agents. After each round of games, agents can imitate the strategies of better performing neighbors, while a subset of agents can be assigned strategies and thus serve as control inputs. We seek here the smallest set of control agents needed to drive the network to a desired uniform strategy state. After presenting exact solutions for complete and star networks and describing a general solution approach that is computationally practical only for small networks, we design a fast algorithm for approximating the solution on arbitrary networks using a weighted minimum spanning tree and strategy propagation algorithm. The resulting approximation is exact for certain classes of games on complete and star networks and simulations suggest that the algorithm performs well in more general cases. [ABSTRACT FROM PUBLISHER]

This paper considers simulation-based optimization of the performance of a regime-switching stochastic system over a finite set of feasible configurations. Inspired by the stochastic fictitious play learning rules in game theory, we propose an adaptive random search algorithm that uses a smooth best-response sampling strategy and tracks the set of global optima, yet distributes the search so that most of the effort is spent on simulating the system performance at the global optima. The algorithm responds properly to the random unpredictable jumps of the global optimum even when the observations data are temporally correlated as long as a weak law of large numbers holds. Numerical examples show that the proposed scheme yields faster convergence and superior efficiency for finite sample lengths compared with several existing random search and pure exploration methods in the literature. [ABSTRACT FROM PUBLISHER]

Motivated by the recent applications of game-theoretical learning to the design of distributed control systems, we study a class of control problems that can be formulated as potential games with continuous action sets. We propose an actor-critic reinforcement learning algorithm that adapts mixed strategies over continuous action spaces. To analyze the algorithm, we extend the theory of finite-dimensional two-timescale stochastic approximation to a Banach space setting, and prove that the continuous dynamics of the process converge to equilibrium in the case of potential games. These results combine to give a provably-convergent learning algorithm in which players do not need to keep track of the controls selected by other agents. [ABSTRACT FROM PUBLISHER]

This paper studies distributed stochastic approximation algorithms based on broadcast gossip on communication networks represented by digraphs. Weak convergence of these algorithms is proved, and an associated ordinary differential equation (ODE) is formulated connecting convergence points with local objective functions and network properties. Using these results, a methodology is proposed for network design, aimed at achieving the desired asymptotic behavior at consensus. Convergence rate of the algorithm is also analyzed and further improved using an attached stochastic differential equation. Simulation results illustrate the theoretical concepts. [ABSTRACT FROM AUTHOR]

Reachability analysis of nonlinear uncertain hybrid systems, i.e., continuous-discrete dynamical systems whose continuous dynamics, guard sets and reset functions are defined by nonlinear functions, can be decomposed in three algorithmic steps: computing the reachable set when the system is in a given operation mode, computing the discrete transitions, i.e., detecting and localizing when (and where) the continuous flowpipe intersects the guard sets, and aggregating the multiple trajectories that result from an uncertain transition once the whole flow-pipe has transitioned so that the algorithm can resume. This paper proposes a comprehensive method that provides a nicely integrated solution to the hybrid reachability problem. At the core of the method is the concept of MSPB, i.e., geometrical object obtained as the Minkowski sum of a parallelotope and an axes aligned box. MSPB are a way to control the over-approximation of the Taylor's interval integration method. As they happen to be a specific type of zonotope, they articulate perfectly with the zonotope bounding method that we propose to enclose in an optimal way the set of flowpipe trajectories generated by the transition process. The method is evaluated both theoretically by analyzing its complexity and empirically by applying it to well-chosen hybrid nonlinear examples. [ABSTRACT FROM AUTHOR]

This technical note presents a method for the identification of Hammerstein Output Error (HOE) models corrupted by bounded noise. The method is based on an iterative scheme using two Optimal Bounding Ellipsoid (OBE) type algorithms. The proposed approach allows the joint estimation of the linear part and of the nonlinear part with a low computational burden. A numerical example is given so as to show the efficiency of the method. [ABSTRACT FROM PUBLISHER]

We investigate stochastic averaging theory for locally Lipschitz discrete-time nonlinear systems with stochastic perturbation and its applications to convergence analysis of discrete-time stochastic extremum seeking algorithms. Firstly, by defining two average systems (one is continuous time, the other is discrete time), we develop discrete-time stochastic averaging theorem for locally Lipschitz nonlinear systems with stochastic perturbation. Our results only need some simple and applicable conditions, which are easy to verify, and remove a significant restriction present in existing results: global Lipschitzness of the nonlinear vector field. Secondly, we provide a discrete-time stochastic extremum seeking algorithm for a static map, in which measurement noise is considered and an ergodic discrete-time stochastic process is used as the excitation signal. Finally, for discrete-time nonlinear dynamical systems, in which the output equilibrium map has an extremum, we present a discrete-time stochastic extremum seeking scheme and, with a singular perturbation reduction, we prove the stability of the reduced system. Compared with classical stochastic approximation methods, while the convergence that we prove is in a weaker sense, the conditions of the algorithm are easy to verify and no requirements (e.g., boundedness) are imposed on the algorithm itself. [ABSTRACT FROM AUTHOR]

Tackling large approximate dynamic programming or reinforcement learning problems requires methods that can exploit regularities of the problem in hand. Most current methods are geared towards exploiting the regularities of either the value function or the policy. We introduce a general classification-based approximate policy iteration (CAPI) framework that can exploit regularities of both. We establish theoretical guarantees for the sample complexity of CAPI-style algorithms, which allow the policy evaluation step to be performed by a wide variety of algorithms, and can handle nonparametric representations of policies. Our bounds on the estimation error of the performance loss are tighter than existing results. [ABSTRACT FROM AUTHOR]

Recently, Chen (2010) presented a new approach to recursive identification for ARMAX systems, which is a three-stage recursive scheme and assumes independent and identically distributed input signals. Here, we observe that, unless the time scale of the algorithm at one stage is reasonably faster than those at the previous stages, convergence to the true value may not take place. To remedy this issue, this note proposes a multi-time-scale modification of the algorithm in [5] such that convergence is achieved. In addition, the new scheme handles a wider class of input signals so that the input can be designed for some purpose.The advantage of the multi-time scale algorithm is verified with numerical examples. [ABSTRACT FROM PUBLISHER]

Recently, much progress has been made on particle swarm optimization (PSO). A number of works have been devoted to analyzing the convergence of the underlying algorithms. Nevertheless, in most cases, rather simplified hypotheses are used. For example, it often assumes that the swarm has only one particle. In addition, more often than not, the variables and the points of attraction are assumed to remain constant throughout the optimization process. In reality, such assumptions are often violated. Moreover, there are no rigorous rates of convergence results available to date for the particle swarm, to the best of our knowledge. In this paper, we consider a general form of PSO algorithms, and analyze asymptotic properties of the algorithms using stochastic approximation methods. We introduce four coefficients and rewrite the PSO procedure as a stochastic approximation type iterative algorithm. Then we analyze its convergence using weak convergence method. It is proved that a suitably scaled sequence of swarms converge to the solution of an ordinary differential equation. We also establish certain stability results. Moreover, convergence rates are ascertained by using weak convergence method. A centered and scaled sequence of the estimation errors is shown to have a diffusion limit. [ABSTRACT FROM AUTHOR]

Discounted, discrete-time, discrete state-space, discrete action-space Markov decision processes (MDPs) form a classical topic in control, game theory, and learning, and as a result are widely applied, increasingly, in very large-scale applications. Many algorithms have been developed to solve large-scale MDPs. Algorithms based on value iteration are particularly popular, as they are more efficient than the generic linear programming approach, by an order of magnitude in the number of states of the MDP. Yet in the case of budget constrained MDPs, no more efficient algorithm than linear programming is known. The theoretically slower running times of linear programming may limit the scalability of constrained MDPs piratically; while, theoretically, it invites the question of whether the increase is somehow intrinsic. In this technical note we show that it is not, and provide two algorithms for budget-constrained MDPs that are as efficient as value iteration. Denoting the running time of value iteration by VI, and the magnitude of the input by U, for an MDP with m expected budget constraints our first algorithm runs in time O(poly(m,\log U)\cdotVI). Given a pre-specified degree of precision, \eta, for satisfying the budget constraints, our second algorithm runs in time O(\log m\cdotpoly(\log U)\cdot(1/\eta^2)\cdotVI), but may produce solutions that overutilize each of the $m$ budgets by a multiplicative factor of $1+\eta$. In fact, one can substitute value iteration with any algorithm, possibly specially designed for a specific MDP, that solves the MDP quickly to achieve similar theoretical guarantees. Both algorithms restrict attention to constrained infinite-horizon MDPs under discounted costs. [ABSTRACT FROM PUBLISHER]

In this paper, we study an approximate projected consensus algorithm for a network to cooperatively compute the intersection of convex sets, where each set corresponds to one network node. Instead of assuming exact convex projection that each node can compute, we allow each node to compute an approximate projection with respect to its own set. After receiving the approximate projection information, nodes update their states by weighted averaging with the neighbors over a directed and time-varying communication graph. The approximate projections are related to projection angle errors, which introduces state-dependent disturbance in the iterative algorithm. Projection accuracy conditions are presented for the considered algorithm to converge. The results indicate how much projection accuracy is required to ensure global consensus to a point in the intersection set when the communication graph is uniformly jointly strongly connected. In addition, we show that $\pi/4$ is a critical angle for the error of the projection approximation to ensure the boundedness. Finally, the results are illustrated by simulations. [ABSTRACT FROM AUTHOR]

We propose and analyze two dual methods based on inexact gradient information and averaging that generate approximate primal solutions for smooth convex problems. The complicating constraints are moved into the cost using the Lagrange multipliers. The dual problem is solved by inexact first-order methods based on approximate gradients for which we prove sublinear rate of convergence. In particular, we provide a complete rate analysis and estimates on the primal feasibility violation and primal and dual suboptimality of the generated approximate primal and dual solutions. Moreover, we solve approximately the inner problems with a linearly convergent parallel coordinate descent algorithm. Our analysis relies on the Lipschitz property of the dual function and inexact dual gradients. Further, we combine these methods with dual decomposition and constraint tightening and apply this framework to linear model predictive control obtaining a suboptimal and feasible control scheme. [ABSTRACT FROM AUTHOR]

We consider a multi-agent optimization problem where agents subject to local, intermittent interactions aim to minimize a sum of local objective functions subject to a global inequality constraint and a global state constraint set. In contrast to previous work, we do not require that the objective, constraint functions, and state constraint sets are convex. In order to deal with time-varying network topologies satisfying a standard connectivity assumption, we resort to consensus algorithm techniques and the Lagrangian duality method. We slightly relax the requirement of exact consensus, and propose a distributed approximate dual subgradient algorithm to enable agents to asymptotically converge to a pair of primal-dual solutions to an approximate problem. To guarantee convergence, we assume that the Slater's condition is satisfied and the optimal solution set of the dual limit is singleton. We implement our algorithm over a source localization problem and compare the performance with existing algorithms. [ABSTRACT FROM AUTHOR]

Common random numbers and the standard clock method are examples of effective variance reduction techniques that also share information and simulation resources when generating realizations of different simulated systems whose performances are being compared. This sharing of computing resources and the potentially widely different computational requirements for different simulation models are important considerations in allocating simulation replications among the candidate designs with the objective of maximizing the probability of selecting the best design, and we formulate the optimal computing budget allocation problem under this scenario. The resulting formulation leads to an optimization problem that can be viewed as a generalization of a correlated version considered in earlier work. An approximation to the problem is introduced to allow a tractable solution, for which a heuristic two-stage sequential allocation algorithm is proposed, and several numerical examples are used to illustrate the potential improvements that can be gained. [ABSTRACT FROM AUTHOR]

Many iterative algorithms employ operators which are difficult to evaluate exactly, but for which a graduated range of approximations exist. In such cases, “coarse-to-fine” algorithms are often used, in which a crude initial operator approximation is gradually refined with new iterations. In such algorithms, because the computational complexity increases over iterations, the algorithm's convergence rate is properly calculated with respect to cumulative computation time. This suggests the problem of determining an optimal rate of refinement for the operator approximation. This paper shows that, for linearly convergent algorithm, the optimal rate of refinement approaches the rate of convergence of the exact algorithm itself, regardless of the tolerance-complexity relationship. We illustrate this result with an analysis of “coarse-to-fine” grid algorithms for Markov decision processes with continuous state spaces. Using the methods proposed here we deduce an algorithm that presents optimal complexity results and consists solely of a non-adaptive schedule for the gradual decrease of grid size. [ABSTRACT FROM AUTHOR]

Sparse identification can be relevant in the automatic control field to solve several problems for nonlinear systems such as identification, control, filtering, fault detection. However, identifying a maximally sparse approximation of a nonlinear function is in general an NP-hard problem. The common approach is to use relaxed or greedy algorithms that, under certain conditions, can provide sparsest solutions. In this technical note, a combined \ell 1-relaxed-greedy algorithm is proposed and conditions are given, under which the approximation derived by the algorithm is a sparsest one. Differently from other conditions available in the literature, the ones provided here can be actually verified for any choice of the basis functions defining the sparse approximation. A Set Membership analysis is also carried out, assuming that the function to approximate is a linear combination of unknown basis functions belonging to a known set of functions. It is shown that the algorithm is able to exactly select the basis functions which define the unknown function and to provide an optimal estimate of their coefficients. [ABSTRACT FROM AUTHOR]

Due to the existence of various uncertainties, the design of distributed estimation algorithms with robustness and high accuracy is an urgent demand for sensor network applications. This paper is aimed at investigating the design of distributed parameter estimation algorithms and the analysis of their convergence properties in uncertain sensing and communication environments. Consensus-based distributed parameter estimation algorithms for both discrete-time and continuous-time cases are established, which are suitable for unreliable communication networks with stochastic communication noises, random link gains and Markovian signal losses. Under mild conditions on stochastic noises, gain function and topology-switching Markov chain, we establish both the mean square and almost sure convergence of the designed algorithms by use of probability limit theory, algebraic graph theory, stochastic differential equation theory and Markov chain theory. The effect of sensor-dependent gain functions on the convergence of the algorithm is also analyzed. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of ensuring trustworthy computation in a linear consensus network. A solution to this problem is relevant for several tasks in multi-agent systems including motion coordination, clock synchronization, and cooperative estimation. In a linear consensus network, we allow for the presence of misbehaving agents, whose behavior deviate from the nominal consensus evolution. We model misbehaviors as unknown and unmeasurable inputs affecting the network, and we cast the misbehavior detection and identification problem into an unknown-input system theoretic framework. We consider two extreme cases of misbehaving agents, namely faulty (non-colluding) and malicious (Byzantine) agents. First, we characterize the set of inputs that allow misbehaving agents to affect the consensus network while remaining undetected and/or unidentified from certain observing agents. Second, we provide worst-case bounds for the number of concurrent faulty or malicious agents that can be detected and identified. Precisely, the consensus network needs to be 2k+1 (resp. k+1) connected for k malicious (resp. faulty) agents to be generically detectable and identifiable by every well behaving agent. Third, we quantify the effect of undetectable inputs on the final consensus value. Fourth, we design three algorithms to detect and identify misbehaving agents. The first and the second algorithm apply fault detection techniques, and affords complete detection and identification if global knowledge of the network is available to each agent, at a high computational cost. The third algorithm is designed to exploit the presence in the network of weakly interconnected subparts, and provides local detection and identification of misbehaving agents whose behavior deviates more than a threshold, which is quantified in terms of the interconnection structure. [ABSTRACT FROM PUBLISHER]

We study a class of random sampling-based algorithms for solving general non-differentiable optimization problems. These are iterative approaches that are based on sampling from and updating an underlying distribution function over the set of feasible solutions. In particular, we propose a novel and systematic framework to investigate the convergence and asymptotic convergence rates of these algorithms by exploiting their connections to the well-known stochastic approximation (SA) method. Such an SA framework unifies our understanding of these randomized algorithms and provides new insight into their design and implementation issues. Our preliminary numerical experiments indicate that new implementations of these algorithms based on the proposed framework may lead to improved performance over existing procedures. [ABSTRACT FROM PUBLISHER]

This paper deals with a method for the approximation of a spectral density function among the solutions of a generalized moment problem à la Byrnes/Georgiou/Lindquist. The approximation is pursued with respect to the Kullback–Leibler pseudo-distance, which gives rise to a convex optimization problem. After developing the variational analysis, we discuss the properties of an efficient algorithm for the solution of the corresponding dual problem, based on the iteration of a nonlinear map in a bounded subset of the dual space. Our main result is the proof of local convergence of the latter, established as a consequence of the central manifold theorem. Supported by numerical evidence, we conjecture that, in the mentioned bounded set, the convergence is actually global. [ABSTRACT FROM AUTHOR]