Search

Multi-dimensional stochastic optimization plays an important role in analysis and control of many technical systems. To solve the challenging multidimensional problems of nonstationary optimization, it is suggested to use a stochastic approximation algorithm (like SPSA) with perturbed input and constant step-size which has simple form. We get a finite bound of residual between estimates and time-varying unknown parameters when observations are made under an unknown but bounded noise. Applications of the algorithm are considered for a random walk, an optimization of UAV's flight, and a load balancing problem. [ABSTRACT FROM AUTHOR]

This paper deals with the update step of Gaussian MAP filtering. In this framework, we seek a Gaussian approximation to the posterior probability density function (PDF) whose mean is given by the maximum a posteriori (MAP) estimator. We propose two novel optimization algorithms which are quite suitable for finding the MAP estimate although they can also be used to solve general optimization problems. These are based on the design of a sequence of PDFs that become increasingly concentrated around the MAP estimate. The resulting algorithms are referred to as Kalman optimization (KO) methods. We also provide the important relations between these KO methods and their conventional optimization algorithms (COAs) counterparts, i.e., Newton's and Levenberg-Marquardt algorithms. Our simulations indicate that KO methods are more robust than their COA equivalents. [ABSTRACT FROM AUTHOR]

We apply diffusion strategies to develop a fully-distributed cooperative reinforcement learning algorithm in which agents in a network communicate only with their immediate neighbors to improve predictions about their environment. The algorithm can also be applied to off-policy learning, meaning that the agents can predict the response to a behavior different from the actual policies they are following. The proposed distributed strategy is efficient, with linear complexity in both computation time and memory footprint. We provide a mean-square-error performance analysis and establish convergence under constant step-size updates, which endow the network with continuous learning capabilities. The results show a clear gain from cooperation: when the individual agents can estimate the solution, cooperation increases stability and reduces bias and variance of the prediction error; but, more importantly, the network is able to approach the optimal solution even when none of the individual agents can (e.g., when the individual behavior policies restrict each agent to sample a small portion of the state space). [ABSTRACT FROM AUTHOR]

We propose a novel algorithm to compute low-complexity polytopic robust control invariant (RCI) sets, along with the corresponding state-feedback gain, for linear discrete-time systems subject to norm-bounded uncertainty, additive disturbances and state/input constraints. Using a slack variable approach, we propose new results to transform the original nonlinear problem into a convex/LMI problem whilst introducing only minor conservatism in the formulation. Through numerical examples, we illustrate that the proposed algorithm can yield improved maximal/minimal volume RCI set approximations in comparison with the schemes given in the literature. [ABSTRACT FROM AUTHOR]

The mixed-norm cost functions arise in many applied optimization problems. As an important example, we consider the state estimation problem for a linear dynamic system under a nonclassical assumption that some entries of state vector admit jumps in their trajectories. The estimation problem is solved by means of mixed l1/l2 -norm approximation. This approach combines the advantages of the well-known quadratic smoothing and the robustness of the least absolute deviations method. For the implementation of the mixed-norm approximation, a dynamic iterative estimation algorithm is proposed. This algorithm is based on weight and time recursions and demonstrates the high efficiency. It well identifies the rare jumps in the state vector and has some advantages over more customary methods in the typical case of a large amount of measurements. Nonoptimality levels for current iterations of the algorithm are constructed. Computation of these levels allows to check the accuracy of iterations. [ABSTRACT FROM AUTHOR]

Approximate dynamic programming (ADP) has proven itself in a wide range of applications spanning large-scale transportation problems, health care, revenue management, and energy systems. The design of effective ADP algorithms has many dimensions, but one crucial factor is the stepsize rule used to update a value function approximation. Many operations research applications are computationally intensive, and it is important to obtain good results quickly. Furthermore, the most popular stepsize formulas use tunable parameters and can produce very poor results if tuned improperly. We derive a new stepsize rule that optimizes the prediction error in order to improve the short-term performance of an ADP algorithm. With only one, relatively insensitive tunable parameter, the new rule adapts to the level of noise in the problem and produces faster convergence in numerical experiments. [ABSTRACT FROM PUBLISHER]

Most of the controllers designed for systems with timedelays involve finite impulse response (FIR) filters in their structure, in particular prediction based controllers for systems with input/output delays. We present theory, algorithms and software to evaluate the frequency response, to approximate the filters by stable linear timeinvariant systems and to compute their induced \cal L2 gain. The approach is based on the theory of functions of matrices. In the approach pole zero cancelations in frequency domain representations are explicitly taken into account. [ABSTRACT FROM AUTHOR]

Matrix measures, also known as logarithmic norms, have historically been used to provide bounds on the divergence of trajectories of a system of ordinary differential equations. In this technical note we use them to compute guaranteed overapproximations of reachable sets for nonlinear continuous-time systems using numerically simulated trajectories and to bound the accumulation of numerical simulation errors along simulation traces. Our method employs a user-supplied bound on the matrix measure of the system's Jacobian matrix to compute bounds on the behavior of nearby trajectories, leading to efficient computation of reachable sets when such bounds are available. We demonstrate that the proposed technique scales well to systems with a large number of states. [ABSTRACT FROM PUBLISHER]

Modern data acquisition routinely produces massive amounts of network data. Though many methods and models have been proposed to analyze such data, the research of network data is largely disconnected with the classical theory of statistical learning and signal processing. In this paper, we present a new framework for modeling network data, which connects two seemingly different areas: network data analysis and compressed sensing. From a nonparametric perspective, we model an observed network using a large dictionary. In particular, we consider the network clique detection problem and show connections between our formulation with a new algebraic tool, namely Randon basis pursuit in homogeneous spaces. Such a connection allows us to identify rigorous recovery conditions for clique detection problems. Though this paper is mainly conceptual, we also develop practical approximation algorithms for solving empirical problems and demonstrate their usefulness on real-world datasets. [ABSTRACT FROM AUTHOR]

We propose a decentralized subspace algorithm for the identification of large-scale, interconnected systems that are described by sparse (multi) banded state-space matrices. First, we prove that the state of a local subsystem can be approximated by a linear combination of inputs and outputs of local subsystems that are in its neighborhood. Furthermore, we prove that for interconnected systems with well-conditioned, finite-time observability Gramians (or observability matrices), the size of this neighborhood is relatively small. On the basis of these results, we develop the subspace identification algorithm that identifies the state-space model of a local subsystem from the local input-output data. Consequently, the developed algorithm is computationally feasible for interconnected systems with a large number of local subsystems. Numerical results confirm the effectiveness of the new identification algorithm. [ABSTRACT FROM PUBLISHER]

The control vector parameterization (CVP) approach is popular to solve nonlinear dynamic optimization problems, but handling inequality path constraints within its framework is a challenge. This study deals with inequality path constraints by using the l1 penalty function and a novel smoothing technique. After clarifying some theories of the proposed approach, a concomitant algorithm is also put forward and verified. [ABSTRACT FROM PUBLISHER]

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]

The classical approach to system identification is based on stochastic assumptions about the measurement error, and provides estimates that have random nature. Worst-case identification, on the other hand, only assumes the knowledge of deterministic error bounds, and establishes guaranteed estimates, thus being in principle better suited for the use in control design. However, a main limitation of such deterministic bounds lies in their potential conservatism, thus leading to estimates of restricted use. In this paper, we propose a rapprochement between the stochastic and worst-case system identification viewpoints, which is based on the probabilistic setting of information-based complexity. The main idea in this line of research is to “discard” sets of measure at most $\epsilon$, where $\epsilon$ is a probabilistic accuracy, from the set of deterministic estimates. Therefore, we are decreasing the so-called worst-case radius of information at the expense of a given probabilistic “risk.” In the case of uniformly distributed noise, we derive new computational results, and in particular we compute a trade-off curve, called violation function, which shows how the radius of information decreases as a function of the accuracy. To this end, we construct randomized and deterministic algorithms which provide approximations of this function. We report extensive simulations showing numerical comparisons between the stochastic, worst-case and probabilistic approaches, thus demonstrating the efficacy of the methods proposed in this paper. [ABSTRACT FROM AUTHOR]

In this paper, we propose a stochastic search algorithm for solving general optimization problems with little structure. The algorithm iteratively finds high quality solutions by randomly sampling candidate solutions from a parameterized distribution model over the solution space. The basic idea is to convert the original (possibly non-differentiable) problem into a differentiable optimization problem on the parameter space of the parameterized sampling distribution, and then use a direct gradient search method to find improved sampling distributions. Thus, the algorithm combines the robustness feature of stochastic search from considering a population of candidate solutions with the relative fast convergence speed of classical gradient methods by exploiting local differentiable structures. We analyze the convergence and converge rate properties of the proposed algorithm, and carry out numerical study to illustrate its performance. [ABSTRACT FROM AUTHOR]

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]

In a leader-follower multi-agent system (MAS), the leader agents act as control inputs and influence the states of the remaining follower agents. The rate at which the follower agents converge to their desired states, as well as the errors in the follower agent states prior to convergence, are determined by the choice of leader agents. In this paper, we study leader selection in order to minimize convergence errors experienced by the follower agents, which we define as a norm of the distance between the follower agents' intermediate states and the convex hull of the leader agent states. By introducing a novel connection to random walks on the network graph, we show that the convergence error has an inherent supermodular structure as a function of the leader set. Supermodularity enables development of efficient discrete optimization algorithms that directly approximate the optimal leader set, provide provable performance guarantees, and do not rely on continuous relaxations. We formulate two leader selection problems within the supermodular optimization framework, namely, the problem of selecting a fixed number of leader agents in order to minimize the convergence error, as well as the problem of selecting the minimum-size set of leader agents to achieve a given bound on the convergence error. We introduce algorithms for approximating the optimal solution to both problems in static networks, dynamic networks with known topology distributions, and dynamic networks with unknown and unpredictable topology distributions. Our approach is shown to provide significantly lower convergence errors than existing random and degree-based leader selection methods in a numerical study. [ABSTRACT FROM PUBLISHER]

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 present a fast distributed solution to the convex network flow optimization problem. Our approach uses a family of dual descent algorithms that approximate the Newton direction to achieve faster convergence rates than existing distributed methods. The approximate Newton directions are obtained through matrix splitting techniques and sparse Taylor approximations of the inverse Hessian. We couple this descent direction with a distributed line search algorithm which requires the same information as our descent direction to compute. We show that, similarly to conventional Newton methods, the proposed algorithm exhibits super-linear convergence within a neighborhood of the optimal value. Numerical experiments corroborate that convergence times are between one to two orders of magnitude faster than existing distributed optimization methods. A connection with recent developments that use consensus to compute approximate Newton directions is also presented. [ABSTRACT FROM PUBLISHER]

We reformulate a deterministic optimization problem as a filtering problem, where the goal is to compute the conditional distribution of the unobserved state given the observation history. We prove that in our formulation the conditional distribution converges asymptotically to a degenerate distribution concentrated on the global optimum. Hence, the goal of searching for the global optimum can be achieved by computing the conditional distribution. Since this computation is often analytically intractable, we approximate it by particle filtering, a class of sequential Monte Carlo methods for filtering, which has proven convergence in “tracking” the conditional distribution. The resultant algorithmic framework unifies some randomized optimization algorithms and provides new insights into their connection. [ABSTRACT FROM PUBLISHER]

In this paper, we consider a general problem setup for a wide class of convex and robust distributed optimization problems in peer-to-peer networks. In this setup, convex constraint sets are distributed to the network processors who have to compute the optimizer of a linear cost function subject to the constraints. We propose a novel fully distributed and asynchronous algorithm, named cutting-plane consensus, to solve the problem, based on a polyhedral outer approximation of the constraint sets. Processors running the algorithm compute and exchange linear approximations of their locally feasible sets. Independently of the number of processors in the network, each processor stores only a small number of linear constraints, making the algorithm scalable to large networks. The cutting-plane consensus algorithm is presented and analyzed for the general framework. Specifically, we prove the correctness of the algorithm, and show its robustness against communication or processor failures. Then, the cutting-plane consensus algorithm is specified to three different classes of distributed optimization problems, namely 1) inequality constrained problems, 2) robust optimization problems, and 3) almost separable optimization problems. For each one of these problem classes we solve a concrete problem and present computational results. That is, we show how to solve: position estimation in wireless sensor networks, a distributed robust linear program, and a distributed microgrid control problem. [ABSTRACT FROM AUTHOR]

The nu-gap metric was originally developed to evaluate robustness of a plant-controller feedback loop and it has many attractive properties. For example, performance of the closed loop changes continuously and stability is robust with respect to small perturbations of the plant (or the controller) in the nu-gap metric. In light of these properties, one can state that the nu-gap metric provides a good measure of distance between systems in a closed loop setting. This is very useful in model approximation, which is the focus of this technical note. The presented nu-gap approximation method is based on semidefinite programming and frequency response matching, which allows to extend the method to account for frequency-dependent weights in the objective function. The frequency-weighted extension is the major advantage of the presented method in comparison with other nu-gap model reduction methods. This extension is applied to approximation of controllers obtained by loop shaping and illustrated on a numerical example. [ABSTRACT FROM PUBLISHER]

We prove convergence of an approximate dynamic programming algorithm for a class of high-dimensional stochastic control problems linked by a scalar storage device, given a technical condition. Our problem is motivated by the problem of optimizing energy flows for a power grid supported by grid-level storage. The problem is formulated as a stochastic, dynamic program, where we estimate the value of resources in storage using a piecewise linear value function approximation. Given the technical condition, we provide a rigorous convergence proof for an approximate dynamic programming algorithm, which can capture the presence of both the amount of energy held in storage as well as other exogenous variables. Our algorithm exploits the natural concavity of the problem to avoid any need for explicit exploration policies. [ABSTRACT FROM PUBLISHER]

This paper deals with the explicit solution and approximation of the constrained linear finite time optimal control problem for systems with fast sampling rates. To this aim, the recently developed explicit model predictive control (eMPC) is reformulated and characterized using the \delta -operator to enjoy its promising advantages compared to the time-shift operator. Using the proposed \delta -model eMPC formulation, a systematic method is proposed for first designing a low-complexity approximate eMPC solution and then improving its closed loop action without first determining an exact optimal solution that might be of prohibitive complexity. It is shown that the stability and feasibility of the proposed sub-optimal solution is guaranteed. [ABSTRACT FROM PUBLISHER]

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]

The technical note deals with state estimation of nonlinear stochastic dynamic systems. Traditional filters providing local estimates of the state, such as the extended Kalman filter, unscented Kalman filter, or the cubature Kalman filter, are based on computationally efficient but approximate integral evaluations. On the other hand, the Monte Carlo based Kalman filter takes an advantage of asymptotically exact integral evaluations but at the expense of substantial computational demands. The aim of the technical note is to propose a new local filter that utilises stochastic integration methods providing the asymptotically exact integral evaluation with computational complexity similar to the traditional filters. The technical note will demonstrate that the unscented and cubature Kalman filters are special cases of the proposed stochastic integration filter. The proposed filter is illustrated by a numerical example. [ABSTRACT FROM AUTHOR]

New nonlinear filtering algorithms are designed based on a receding horizon strategy, i.e., a finite impulse response (FIR) structure, and square root information filtering to achieve high accuracy and good performance in empirical error covariance tests. The new nonlinear receding horizon filters reduce approximation errors in nonlinear filtering by considering a set of recent observations with non-informative initial conditions. By applying information filtering, we are able to manage the non-informative initial conditions, and thus propose the square root version of the algorithm as a means of retaining the positive definiteness of the error covariance. Based on the proposed strategy, we then implement known nonlinear filtering frameworks. Simulation results confirm that the new nonlinear receding horizon filters outperform existing nonlinear filters in well-known nonlinear examples. [ABSTRACT FROM AUTHOR]

This technical note is dedicated to model order reduction of linear time-invariant systems. The main contribution of this technical note is the derivation of two scalable stability-preserving model reduction algorithms. Both algorithms constitute a development of a recently proposed model reduction method. The algorithms perform a curve fitting procedure using frequency response samples of a model and semidefinite programming methods. Computation of these samples can be done efficiently even for large scale models. Both algorithms are obtained from a reformulation of the model reduction problem. One proposes a semidefinite relaxation, while the other is an iterative semidefinite approach. The relaxation approach is similar to Hankel model reduction, which is a well-known and established method in the control literature. Due to this resemblance, the accuracy of approximation is also similar to the one of Hankel model reduction. An appealing quality of the proposed algorithms is the ability to easily perform extensions, e.g., introduce frequency-weighting, positive-real and bounded-real constraints. [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]

This technical note deals with the estimation of the whole trajectory of a stochastic dynamic system with highest probability, conditionally upon the past observation process, using a maximum Gaussian mixture. We first recall the Gaussian sum technique applied to minimum variance filtering. It is then shown that the same concept of Gaussian mixture can be applied in that context, provided we replace the Sum operator by the Max operator. [ABSTRACT FROM AUTHOR]

Stochastic approximation (SA) algorithms are proposed to identify a multi-input and multi-output (MIMO) Wiener system, in which the system input is taken to be a sequence of independent and identically distributed (i.i.d.) Gaussian random vectors uk\in{\cal N}(0,I). The algorithm for identifying the nonlinear part is designed with multi-variable kernel functions. Under suitable conditions, we show that the estimates of the coefficients of the linear subsystem and of the values of the nonlinear function converge to the respective true values with probability one. [ABSTRACT FROM AUTHOR]

We propose a new approximate value iteration method, namely near-value iteration (NVI), to solve continuous-state optimal stopping problems under partial observation, which in general cannot be solved analytically and also pose a great challenge to numerical solutions. NVI is motivated by the expression of the value function as the supremum over an uncountable set of linear functions in the belief state. After a smart manipulation of the operations in the updating equation for the value function, we reduce the set to only two functions at every time step, so as to achieve significant computational savings. NVI yields a value function approximation bounded by the tightest lower and upper bounds that can be achieved by existing algorithms in the same class, so the NVI approximation is closer to the true value function than at least one of these bounds. We demonstrate the effectiveness of our approach on an example of pricing American options under stochastic volatility. [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]

In this note, we study the consensus problem for multiagent systems with measurement noises. Different from the existing approach, the consensus problem is converted to a root finding problem for which the stochastic approximation theory can be applied. By choosing an appropriate regression function, we propose a consensus algorithm which is applicable to systems with more general measurement noise processes, including stationary autoregressive and moving average (ARMA) processes and infinite moving average (MA) processes. Further, we establish a relationship between the convergence rate and the exponent of the step size of the algorithm. Particularly, strong convergence rate for systems with a leader-follower topology is studied. [ABSTRACT FROM AUTHOR]

This paper considers both synchronous and asynchronous consensus algorithms with noisy measurements. For stochastic approximation based consensus algorithms, the existing convergence analysis with dynamic topologies heavily relies on quadratic Lyapunov functions, whose existence, however, may be difficult to ensure for switching directed graphs. Our main contribution is to introduce a new analytical approach. We first show a fundamental role of ergodic backward products for mean square consensus in algorithms with additive noise. Subsequently, we develop ergodicity results for backward products of degenerating stochastic matrices converging to a 0–1 matrix via a discrete time dynamical system approach. These results complement the existing ergodic theory of stochastic matrices and provide an effective tool for analyzing consensus problems. Under a joint connectivity assumption, our approach may deal with switching topologies, delayed measurements and correlated noises, and it does not require the double stochasticity condition typically assumed for the existence of quadratic Lyapunov functions. [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]

We consider the problem of designing controllers to steer mobile robots to the source (the minimizer) of a signal field. In addition to the mobility constraints, e.g., posed by the nonholonomic dynamics, we assume that the field is completely unknown to the robot and the robot has no knowledge of its own position. Furthermore, the unknown field is randomly switching. In the case where the information of the field (e.g., the gradient) is completely known, standard motion planning techniques for mobile robots would converge to the known source. In the absence of mobility constraints, convergence to the minimum of unknown fields can be pursued using the framework of numerical optimization. By considering these facts, this paper exploits an idea of the stochastic approximation for solving the problem mentioned in the beginning and proposes a source seeking controller which sequentially generates the next waypoints such that the resulting discrete trajectory converges to the unknown source and which steers the robot along the waypoints, under the assumption that the robot can move to any point in the body fixed coordinate frame. To this end, we develop a rotation-invariant and forward-sided version of the simultaneous-perturbation stochastic approximation algorithm as a method to generate the next waypoints. Based on this algorithm, we design source seeking controllers. Furthermore, it is proven that the robot converges to a small set including the source in a probabilistic sense if the signal field switches periodically and sufficiently fast. The proposed controllers are demonstrated by numerical simulations. [ABSTRACT FROM AUTHOR]

Probabilistic discrete event systems (PDES) are modeled as generators of probabilistic languages and the supervisors employed are a probabilistic generalization of deterministic supervisors used in standard supervisory control theory. In the case when there exists no probabilistic supervisor such that the behavior of a plant under control exactly matches the probabilistic language given as the requirements specification, we want to find a probabilistic control such that the behavior of the plant under control is “as close as possible” to the desired behavior. First, as a measure of this proximity, a pseudometric on states of generators is defined. Two algorithms for the calculation of the distance between states in this pseudometric are described. Then, an algorithm to synthesize a probabilistic supervisor that minimizes the distance between generators representing the achievable and required behavior of the plant is presented. [ABSTRACT FROM PUBLISHER]

The convex approach to the absolute stability problem is considered. Gapski and Geromel's algorithm for computing Zames–Falb multipliers, used in determining stability, treats the problem as an optimization problem. It is found that their algorithm may terminate prematurely in some cases, failing to find the optimal multiplier. We propose an improvement that always finds an ascent direction and a multiplier that improves the objective function whenever one exists. [ABSTRACT FROM PUBLISHER]

We study the traveling salesman problem for a Dubins vehicle. We prove that this problem is NP-hard, and provide lower bounds on the approximation ratio achievable by some recently proposed heuristics. We also describe new algorithms for this problem based on heading discretization, and evaluate their performance numerically. [ABSTRACT FROM PUBLISHER]

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]

Event-based optimization (EBO) provides a unified framework for problems in which decisions can be made only when certain events occur. Because the event sequence usually is not Markovian, the optimal policy could depend on the entire event history, which is hard to implement in practice. So most existing studies focus on memoryless policies, which make decisions only based on the current observable events. But it remains open how to find the optimal memoryless policies in general, leaving alone to solve the EBO optimally. In this technical note, we address these two important questions for infinite-stage EBOs with finite state and action spaces and make the following three major contributions. First, we extend our previous studies on finite-stage EBOs and convert infinite-stage EBOs to partially observable Markov decision processes (POMDPs). The belief process of this POMDP is called belief-event decision process (BEDP). Under certain well-known conditions, the optimal policies of BEDPs can be achieved within stationary Markov deterministic policies. Second, assuming optimal stationary policies exist, the performance difference and derivative formulas are developed. Potentials of memoryless event-based policies are shown to be piecewise linear functions, and thus can be efficiently estimated through sample paths. Third, a potential-based approximate policy iteration algorithm is developed to obtain near-optimal memoryless policies. The convergence and performance loss bound of this algorithm are analyzed. [ABSTRACT FROM AUTHOR]

We consider the problem of monitoring spatial phenomena, such as road speeds on a highway, using wireless sensors with limited battery life. A central question is to decide where to locate these sensors to best predict the phenomenon at the unsensed locations. However, given the power constraints, we also need to determine when to activate these sensors in order to maximize the performance while satisfying lifetime requirements. Traditionally, these two problems of sensor placement and scheduling have been considered separately; one first decides where to place the sensors, and then when to activate them. [ABSTRACT FROM AUTHOR]

We propose a model for deterministic distributed function computation by a network of identical and anonymous nodes. In this model, each node has bounded computation and storage capabilities that do not grow with the network size. Furthermore, each node only knows its neighbors, not the entire graph. Our goal is to characterize the class of functions that can be computed within this model. In our main result, we provide a necessary condition for computability which we show to be nearly sufficient, in the sense that every function that violates this condition can at least be approximated. The problem of computing (suitably rounded) averages in a distributed manner plays a central role in our development; we provide an algorithm that solves it in time that grows quadratically with the size of the network. [ABSTRACT FROM AUTHOR]

Limits on the storage space or the computation time restrict the applicability of model predictive controllers (MPC) in many real problems. Currently available methods either compute the optimal controller online or derive an explicit control law. In this paper we introduce a new approach combining the two paradigms of explicit and online MPC to overcome their individual limitations. The algorithm computes a piecewise affine approximation of the optimal solution that is used to warm-start an active set linear programming procedure. A preprocessing method is introduced that provides hard real-time execution, stability and performance guarantees for the proposed controller. By choosing a combination of the quality of the approximation and the number of online active set iterations the presented procedure offers a tradeoff between the warm-start and online computational effort. We show how the problem of identifying the optimal combination for a given set of requirements on online computation time, storage and performance can be solved. Finally, we demonstrate the potential of the proposed warm-start procedure on numerical examples. [ABSTRACT FROM PUBLISHER]

This technical note proposes a method for low order H-infinity synthesis where the constraint on the order of the controller is formulated as a rational equation. The resulting nonconvex optimization problem is then solved by applying a quasi-Newton primal-dual interior point method. [ABSTRACT FROM AUTHOR]

In this paper, we derive an efficient Chebyshev algorithm for solving optimal control problems. The Chebyshev expansions are employed to approximate both the control and the state functions. The discretizing process and the related techniques are unique compared to existing methods. The optimal control problems are transformed into the resulting mathematical programming problems. Theoretical analysis is given to support the method. Further numerical examples and comparisons are presented to illustrate the efficiency of the method. [ABSTRACT FROM AUTHOR]