Search

This article addresses the problem of learning the optimal control policy for a nonlinear stochastic dynamical. This problem is subject to the “curse of dimensionality” associated with the dynamic programming method. This article proposes a novel decoupled data-based control (D2C) algorithm that addresses this problem using a decoupled, “open-loop–closed-loop,” approach. First, an open-loop deterministic trajectory optimization problem is solved using a black-box simulation model of the dynamical system. Then, closed-loop control is developed around this open-loop trajectory by linearization of the dynamics about this nominal trajectory. By virtue of linearization, a linear quadratic regulator based algorithm can be used for this closed-loop control. We show that the performance of D2C algorithm is approximately optimal. Moreover, simulation performance suggests a significant reduction in training time compared to other state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

We consider the stochastic generalized Nash equilibrium problem (SGNEP) with expected-value cost functions. Inspired by Yi and Pavel (2019), we propose a distributed generalized Nash equilibrium seeking algorithm based on the preconditioned forward–backward operator splitting for SGNEPs, where, at each iteration, the expected value of the pseudogradient is approximated via a number of random samples. Our main contribution is to show almost sure convergence of the proposed algorithm if the pseudogradient mapping is restricted (monotone and) cocoercive. [ABSTRACT FROM AUTHOR]

The objective of this article is to introduce a novel data-driven iterative linear quadratic (LQ) control method for solving a class of nonlinear optimal tracking problems. Specifically, an algorithm is proposed to approximate the Q-factors arising from LQ stochastic optimal tracking problems. This algorithm is then coupled with iterative LQ-methods for determining local solutions to nonlinear optimal tracking problems in a purely data-driven setting. Simulation results highlight the potential of this method for field applications. [ABSTRACT FROM AUTHOR]

In this article, we introduce a class of novel distributed algorithms for solving stochastic big-data convex optimization problems over directed graphs. In the addressed set-up, the dimension of the decision variable can be extremely high and the objective function can be nonsmooth. The general algorithm consists of two main steps: a consensus step and an update on a single block of the optimization variable, which is then broadcast to neighbors. Three special instances of the proposed method, involving particular problem structures, are then presented. In the general case, the convergence of a dynamic consensus algorithm over random row stochastic matrices is shown. Then, the convergence of the proposed algorithm to the optimal cost is proven in expected value. Exact convergence is achieved when using diminishing (local) stepsizes, whereas approximate convergence is attained when constant stepsizes are employed. The convergence rate is shown to be sublinear and an explicit rate is provided in the case of constant stepsizes. Finally, the algorithm is tested on a distributed classification problem, first on synthetic data and, then, on a real, high-dimensional, text dataset. [ABSTRACT FROM AUTHOR]

Asynchronous stochastic approximations (SAs) are an important class of model-free algorithms, tools, and techniques that are popular in multiagent and distributed control scenarios. To counter Bellman's curse of dimensionality, such algorithms are coupled with function approximations. Although the learning/control problem becomes more tractable, function approximations affect stability and convergence. In this article, we present verifiable sufficient conditions for stability and convergence of asynchronous SAs with biased approximation errors. The theory developed herein is used to analyze policy gradient methods and noisy value iteration schemes. Specifically, we analyze the asynchronous approximate counterparts of the policy gradient (A2PG) and value iteration (A2VI) schemes. It is shown that the stability of these algorithms is unaffected by biased approximation errors, provided that they are asymptotically bounded. With respect to convergence (of A2VI and A2PG), a relationship between the limiting set and the approximation errors is established. Finally, experimental results that support the theory are presented. [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]

Temporal logic provides a rigorous and expressive way to model specifications for cyber-physical systems (CPS). Such systems, which are playing increasingly important roles in various domains, are also subject to malicious attacks initiated by intelligent adversaries. Malicious attacks may prevent the system from satisfying the desired specification. In this article, we introduce a control synthesis method to minimize deviations from the desired specification due to adversaries. We consider the scenario where the adversary has limited capability of observing the controller's strategy. We synthesize a minimum violation control strategy for a finite-state stochastic game under cosafe linear temporal logic constraints. We formulate a mixed-integer nonlinear program for computing the optimal controller strategy and present two algorithms. First, we propose an exact algorithm that computes the optimal control strategy with probability one but without guarantees on the convergence rate. Second, we present an approximate algorithm that computes a suboptimal control strategy. The approximate algorithm converges faster compared to the exact algorithm; however, it only returns an optimal solution when the adversary has full observation over the controller's strategy. A numerical case study is presented to evaluate the proposed framework. [ABSTRACT FROM AUTHOR]

In this paper, the unscented Kalman filtering (UKF) problem is investigated for a class of general nonlinear systems with stochastic uncertainties under communication protocols. A modified unscented transformation is put forward to account for stochastic uncertainties caused by modeling errors. For preventing data collisions and mitigating communication burden, the round-robin protocol and the weighted try-once-discard protocol are, respectively, introduced to regulate the data transmission order from sensors to the filter. Then, by employing two kinds of data-holding strategies (i.e., zero-order holder and zero input) for those nodes without transmission privilege, two novel protocol-based measurement models are formulated. Subsequently, by resorting to the sigma point approximation method, two resource-saving UKF algorithms are developed, where the impact from the underlying protocols on the filter design is explicitly quantified. Finally, compared with the protocol-based extended Kalman filtering algorithms, a simulation example is presented to demonstrate the effectiveness of the proposed protocol-based UKF algorithms. [ABSTRACT FROM AUTHOR]

We consider random walks in which the walk originates in one set of nodes and then continues until it reaches one or more nodes in a target set. The time required for the walk to reach the target set is of interest in understanding the convergence of Markov processes, as well as applications in control, machine learning, and social sciences. In this paper, we investigate the computational structure of the random walk times as a function of the set of target nodes, and find that the commute, hitting, and cover times all exhibit submodular structure, even in nonstationary random walks. We provide a unifying proof of this structure by considering each of these times as special cases of stopping times. We generalize our framework to Markov decision processes, in which the target sets and control policies are jointly chosen to minimize the travel times, leading to polynomial-time approximation algorithms for choosing target sets. Our results are validated through numerical study. [ABSTRACT FROM AUTHOR]

This paper investigates the interaction between control and communications in networked systems by studying a class of stochastic approximation algorithms that accommodate random network topology switching processes, time-varying functions, nonlinear dynamics, additive and nonadditive noises, and other uncertainties. Interaction among control strategy and the multiple stochastic processes introduces critical challenges in such problems. By modeling the random switching as a discrete-time Markov chain and studying multiple stochastic uncertainties in a unified framework, it is shown that under broad conditions, the algorithms are convergent. The performance of the algorithms is further analyzed by establishing their rate of convergence and asymptotic characterizations. Simulation case studies are conducted to evaluate the performance of the procedures in various aspects. [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]

In this note, we consider the problem of choosing, which nodes of a linear dynamical system should be actuated so that the state transfer from the system's initial condition to a given final state is possible. Assuming a standard complexity hypothesis, we show that this problem cannot be efficiently solved or approximated in polynomial, or even quasi-polynomial, time. [ABSTRACT FROM AUTHOR]

Cumulative prospect theory (CPT) is a popular approach for modeling human preferences. It is based on probabilistic distortions and generalizes the expected utility theory. We bring the CPT to a stochastic optimization framework and propose algorithms for both estimation and optimization of CPT-value objectives. We propose an empirical distribution function-based scheme to estimate the CPT value, and then, use this scheme in the inner loop of a CPT-value optimization procedure. We propose both gradient based as well as gradient-free CPT-value optimization algorithms that are based on two well-known simulation optimization ideas: simultaneous perturbation stochastic approximation and model-based parameter search, respectively. We provide theoretical convergence guarantees for all the proposed algorithms and also illustrate the potential of CPT-based criteria in a traffic signal control application. [ABSTRACT FROM AUTHOR]

Consensus conditions and convergence speeds are crucial for distributed consensus algorithms of networked systems. Based on a basic first-order average-consensus protocol with time-varying topologies and additive noises, this paper first investigates its critical consensus condition on network topology by stochastic approximation frameworks. A new joint-connectivity condition called extensible joint-connectivity that contains a parameter $\delta$ (termed the extensible exponent) is proposed. With this and a balanced topology condition, we show that a critical value of \delta$ for consensus is 1/2$ . Optimization on convergence rate of this protocol is further investigated. It is proved that the fastest convergence rate, which is the theoretic optimal rate among all controls, is of the order 1/t for the worst topologies, which are balanced and satisfy the extensible joint-connectivity condition. For practical implementation, certain open-loop control strategies are introduced to achieve consensus with a convergence rate of the same order as the fastest convergence rate. Furthermore, a consensus condition is derived for nonstationary and strongly correlated random topologies. The algorithms and consensus conditions are applied to distributed consensus computation of mobile ad-hoc networks; and their related critical exponents are derived from relative velocities of mobile agents for guaranteeing consensus. [ABSTRACT FROM PUBLISHER]

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]

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]

In this paper, the problem of identifying nonlinear systems under adaptive binary-valued output measurements is considered. We follow a nonparametric approach, which directly estimates the value of the nonlinear function representing the system at any fixed point with the help of a recursive kernel-based stochastic approximation algorithm with expanding truncations (SAAWET). The thresholds of the binary sensor are adaptively designed to achieve a sufficient richness of information in the output observations. The constructed estimates are proved to converge to the true values with probability one. Two numerical examples are given showing that the simulation results are consistent with the theoretical analysis. [ABSTRACT FROM AUTHOR]

We consider a tandem two-server fluid network with two fluid types. Each server in the network has two buffers, one for each fluid, and the capacity of each server can be shared among the fluids. An initial amount of fluids is to be processed by both servers and drained through the system. We determine the processing rates for which the servers' capacity is optimally shared, with the objective of minimizing the total flow time. Three cases of the optimal strategy are discussed. [ABSTRACT FROM PUBLISHER]

In this paper we propose a compositional framework for the construction of approximations of the interconnection of a class of stochastic hybrid systems. As special cases, this class of systems includes both jump linear stochastic systems and linear stochastic hybrid automata. In the proposed framework, an approximation is itself a stochastic hybrid system, which can be used as a replacement of the original stochastic hybrid system in a controller design process. We employ a notion of so-called stochastic simulation function to quantify the error between the approximation and the original system. In the first part of the paper, we derive sufficient conditions which facilitate the compositional quantification of the error between the interconnection of stochastic hybrid subsystems and that of their approximations using the quantified error between the stochastic hybrid subsystems and their corresponding approximations. In particular, we show how to construct stochastic simulation functions for approximations of interconnected stochastic hybrid systems using the stochastic simulation function for the approximation of each component. In the second part of the paper, we focus on a specific class of stochastic hybrid systems, namely, jump linear stochastic systems, and propose a constructive scheme to determine approximations together with their stochastic simulation functions for this class of systems. Finally, we illustrate the effectiveness of the proposed results by constructing an approximation of the interconnection of four jump linear stochastic subsystems in a compositional way. [ABSTRACT FROM AUTHOR]

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]

This note considers the problem of Bayesian smoothing in nonlinear state-space models with additive noise using Gaussian approximations. Sigma-point approximations to the general Gaussian Rauch-Tung-Striebel smoother are widely used methods to tackle this problem. These algorithms perform statistical linear regression (SLR) of the nonlinear functions considering only the previous measurements. We argue that SLR should be done taking all measurements into account. We propose the iterated posterior linearization smoother (IPLS), which is an iterated algorithm that performs SLR of the nonlinear functions with respect to the current posterior approximation. The algorithm is demonstrated to outperform conventional Gaussian nonlinear smoothers in two numerical examples. [ABSTRACT FROM AUTHOR]

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]

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]

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]

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]

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]

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]

In this paper, an algorithm for decentralized multi-agent estimation of parameters in linear discrete-time regression models is proposed in the form of a combination of local stochastic approximation algorithms and a global consensus strategy. An analysis of the asymptotic properties of the proposed algorithm is presented, taking into account both the multi-agent network structure and the probabilities of getting local measurements and implementing exchange of inter-agent messages. In the case of non-vanishing gains in the stochastic approximation algorithms, an asymptotic estimation error covariance matrix bound is defined as the solution of a Lyapunov-like matrix equation. In the case of asymptotically vanishing gains, the mean-square convergence is proved and the rate of convergence estimated. In the discussion, the problem of additive communication noise is treated in a methodologically consistent way. It is also demonstrated how the consensus scheme in the algorithm can contribute to the overall reduction of measurement noise influence. Some simulation results illustrate the obtained theoretical results. [ABSTRACT FROM AUTHOR]