Search

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]

Under a Bayesian framework, we formulate the fully sequential sampling and selection decision in statistical ranking and selection as a stochastic control problem, and derive the associated Bellman equation. Using a value function approximation, we derive an approximately optimal allocation policy. We show that this policy is not only computationally efficient but also possesses both one-step-ahead and asymptotic optimality for independent normal sampling distributions. Moreover, the proposed allocation policy is easily generalizable in the approximate dynamic programming paradigm. [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]

This note studies the identification of individual systems operating in a large-scale distributed network by considering the interconnection signals between neighboring systems to be unmeasurable. The unmeasurable interconnections act as unknown system inputs to the individual systems in a network, which poses a challenge for the identification problem. A subspace identification framework is proposed in this note for the consistent identification of individual systems using only local input and output information. The key step of this identification framework is the accurate estimation of the unknown system inputs of individual systems using local observations. Sufficient identifiability conditions are provided for the proposed identification framework and a simulation example is given to demonstrate its performance. [ABSTRACT FROM PUBLISHER]

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]

We develop algorithms that find and track the optimal solution trajectory of time-varying convex optimization problems that consist of local and network-related objectives. The algorithms are derived from the prediction-correction methodology, which corresponds to a strategy where the time-varying problem is sampled at discrete time instances, and then, a sequence is generated via alternatively executing predictions on how the optimizers at the next time sample are changing and corrections on how they actually have changed. Prediction is based on how the optimality conditions evolve in time, while correction is based on a gradient or Newton method, leading to decentralized prediction-correction gradient and decentralized prediction-correction Newton. We extend these methods to cases where the knowledge on how the optimization programs are changing in time is only approximate and propose decentralized approximate prediction-correction gradient and decentralized approximate prediction-correction Newton. Convergence properties of all the proposed methods are studied and empirical performance is shown on an application of a resource allocation problem in a wireless network. We observe that the proposed methods outperform existing running algorithms by orders of magnitude. The numerical results showcase a tradeoff between convergence accuracy, sampling period, and network communications. [ABSTRACT FROM PUBLISHER]

This paper presents a noise adaptive variational Bayesian cubature information filter based on Wishart distribution. In the frame of recursive Bayesian estimation, the noise adaptive information filter propagating the information matrix and information state is derived. And the integration of recursive Bayesian estimation is approximated by cubature integration rule. Then, the inverse of measurement noise matrix is modeled as a Wishart distribution, so the joint distribution of posterior state and measurement noise can be approximated by the product of independent Gaussian and Wishart. Furthermore, the corresponding square root version is also derived to improve numerical characteristics. Simulation results with unknown and correlated measurement noise demonstrate the effectiveness of the proposed algorithms. [ABSTRACT FROM AUTHOR]

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]

Decentralized optimization algorithms have received much attention due to the recent advances in network information processing. However, conventional decentralized algorithms based on projected gradient descent are incapable of handling high-dimensional constrained problems, as the projection step becomes computationally prohibitive. To address this problem, this paper adopts a projection-free optimization approach, a.k.a. the Frank–Wolfe (FW) or conditional gradient algorithm. We first develop a decentralized FW (DeFW) algorithm from the classical FW algorithm. The convergence of the proposed algorithm is studied by viewing the decentralized algorithm as an inexact FW algorithm. Using a diminishing step size rule and letting t be the iteration number, we show that the DeFW algorithm's convergence rate is {\mathcal O}(1/t) for convex objectives; is {\mathcal O}(1/t^2)$ for strongly convex objectives with the optimal solution in the interior of the constraint set; and is {\mathcal O}(1/\sqrt{t}) toward a stationary point for smooth but nonconvex objectives. We then show that a consensus-based DeFW algorithm meets the above guarantees with two communication rounds per iteration. We demonstrate the advantages of the proposed DeFW algorithm on low-complexity robust matrix completion and communication efficient sparse learning. Numerical results on synthetic and real data are presented to support our findings. [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]

Underapproximations (UAs) of backward reachable sets play an important role in controller synthesis and trajectory analysis for constrained nonlinear dynamical systems, but there are few methods available to compute them. Given a nonlinear system, a target region of simply connected compact type and a time duration, we present a method using boundary analysis to compute an UA of the backward reachable set. The UA is represented as a semialgebraic set, formed by what we term polynomial \mathtt level-set functions. The polynomial \mathtt level-set function is a semidefinite positive function with one real root, such that the interior and closure of a semialgebraic set formed by it are both simply connected and have the same boundary. The function can be computed by solving a convex program, which is constructed based on sum-of-squares decomposition and linear interval inequalities. We test our method on several examples and compare them with existing methods. The results show that our method can obtain better estimations more efficiently in terms of time for these special examples. [ABSTRACT FROM AUTHOR]

In this paper, we propose a distributed algorithm for optimization problems that involve a separable, possibly nonconvex objective function subject to convex local constraints and linear coupling constraints. The method is based on the accelerated distributed augmented Lagrangians (ADAL) algorithm that was recently developed by the authors to address convex problems. Here, we extend this line of work in two ways. First, we establish convergence of the method to a local minimum of the problem, using assumptions that are common in the analysis of nonconvex optimization methods. To the best of our knowledge, this is the first work that shows convergence to local minima specifically for a distributed augmented Lagrangian (AL) method applied to nonconvex optimization problems; distributed AL methods are known to perform very well when used to solve convex problems. Second, we propose a more general and decentralized rule to select the stepsizes of the method. This improves on the authors’ original ADAL method, where the stepsize selection used global information at initialization. Numerical results are included to verify the correctness and efficiency of the proposed distributed method. [ABSTRACT FROM AUTHOR]

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 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 consider controllable linear discrete-time systems with bounded perturbations and present two methods to compute robust controlled invariant sets. The first method tolerates an arbitrarily small constraint violation to compute an arbitrarily precise outer approximation of the maximal robust controlled invariant set, while the second method provides an inner approximation. The outer approximation scheme is $\delta$ -complete, given that the constraint sets are formulated as finite unions of polytopes. [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]

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]

Actor-critic algorithms solve dynamic decision making problems by optimizing a performance metric of interest over a user-specified parametric class of policies. They employ a combination of an actor, making policy improvement steps, and a critic, computing policy improvement directions. Many existing algorithms use a steepest ascent method to improve the policy, which is known to suffer from slow convergence for ill-conditioned problems. In this paper, we first develop an estimate of the (Hessian) matrix containing the second derivatives of the performance metric with respect to policy parameters. Using this estimate, we introduce a new second-order policy improvement method and couple it with a critic using a second-order learning method. We establish almost sure convergence of the new method to a neighborhood of a policy parameter stationary point. We compare the new algorithm with some existing algorithms in two applications and demonstrate that it leads to significantly faster convergence. [ABSTRACT FROM AUTHOR]

The problem of designing a switching and control policy for regulating the state of a switched linear system to zero while minimizing a quadratic cost appears in numerous applications. However, obtaining the optimal policy is in general computationally intractable. Here, we propose a class of suboptimal policies that exploit information, in terms of upper or lower bounds, on the optimal cost. We analyze the performance of these novel policies, obtaining new bounds on the optimal cost which are tighter than the initial ones. The usefulness of these policies and performance bounds is illustrated in the context of resource-aware control. [ABSTRACT FROM AUTHOR]

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]

System identification extracts information from a system's operational data to derive a representative model for the system so that a decision can be made with desired accuracy and reliability. When resources are limited, especially for networked systems sharing data and communication power and bandwidth, identification must consider complexity as a critical limitation. Focusing on optimal resource allocation under a given reliability requirement, this paper studies identification complexity and its relations to decision making. Dynamic resource assignments are investigated. Algorithms are developed and their convergence properties are established, including strong convergence, almost sure convergence rate, and asymptotic normality. By a suitable design of resource updating step sizes, the algorithms are shown to achieve the CR lower bound asymptotically, and hence are asymptotically efficient. Illustrative examples demonstrate significant advantages of our real-time and individualized resource allocation methodologies over population-based worst-case strategies. [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]

In this paper, a time-varying distributed convex optimization problem is studied for continuous-time multi-agent systems. The objective is to minimize the sum of local time-varying cost functions, each of which is known to only an individual agent, through local interaction. Here, the optimal point is time varying and creates an optimal trajectory. Control algorithms are designed for the cases of single-integrator and double-integrator dynamics. In both cases, a centralized approach is first introduced to solve the optimization problem. Then, this problem is solved in a distributed manner and a discontinuous algorithm based on the signum function is proposed in each case. In the case of single-integrator (respectively, double-integrator) dynamics, each agent relies only on its own position and the relative positions (respectively, positions and velocities) between itself and its neighbors. A gain adaption scheme is introduced in both algorithms to eliminate certain global information requirement. To relax the restricted assumption imposed on feasible cost functions, an estimator based algorithm using the signum function is proposed, where each agent uses dynamic average tracking as a tool to estimate the centralized control input. As a tradeoff, the estimator-based algorithm necessitates communication between neighbors. Then, in the case of double-integrator dynamics, the proposed algorithms are further extended. Two continuous algorithms based on, respectively, a time-varying and a fixed boundary layer are proposed as continuous approximations of the signum function. To account for interagent collision for physical agents, a distributed convex optimization problem with swarm tracking behavior is introduced for both single-integrator and double-integrator dynamics. It is shown that the center of the agents tracks the optimal trajectory, the connectivity of the agents is maintained, and interagent collision is avoided. [ABSTRACT FROM AUTHOR]

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]

We consider the classical TD(0) algorithm implemented on a network of agents wherein the agents also incorporate updates received from neighboring agents using a gossip-like mechanism. The combined scheme is shown to converge for both discounted and average cost problems. [ABSTRACT FROM AUTHOR]

We consider the problem of optimal statistical filtering in general nonlinear non-Gaussian Markov dynamic systems. The novelty of the proposed approach consists in approximating the nonlinear system by a recent Markov switching process, in which one can perform exact and optimal filtering with a linear time complexity. All we need to assume is that the system is stationary (or asymptotically stationary), and that one can sample its realizations. We evaluate our method using two stochastic volatility models and results show its efficiency. [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]

In the context of sensor networks, gossip algorithms are a popular, well established technique for achieving consensus when sensor data are encoded in linear spaces. Gossip algorithms also have several extensions to non linear data spaces. Most of these extensions deal with Riemannian manifolds and use Riemannian gradient descent. This paper, instead, exhibits a very simple metric property that does not rely on any differential structure. This property strongly suggests that gossip algorithms could be studied on a broader family than Riemannian manifolds. And it turns out that, indeed, (local) convergence is guaranteed as soon as the data space is a mere \textCAT(\kappa) metric space. We also study convergence speed in this setting and establish linear rates for \textCAT(0) spaces, and local linear rates for \textCAT(\kappa) spaces with $\kappa>0$. Numerical simulations on several scenarii, with corresponding state spaces that are either Riemannian manifolds—as in the problem of positive definite matrices consensus—or bare metric spaces—as in the problem of arms consensus—validate the results. This shows that our metric approach not only allows for a simpler and more general mathematical analysis but also paves the way for new kinds of applications that go beyond the Riemannian setting. [ABSTRACT FROM AUTHOR]

Numerical aspects are of central importance in identification and control. Many computations in these fields involve approximations using polynomial or rational functions that are obtained using orthogonal or oblique projections. The aim of this paper is to develop a new and general theoretical framework to solve a large class of relevant problems. The proposed method is built on the introduction of bi-orthonormal polynomials with respect to a data-dependent bi-linear form. This bi-linear form generalises the conventional inner product and allows for asymmetric and indefinite problems. The proposed approach is shown to lead to optimal numerical conditioning $(\kappa=1)$ in a recent frequency-domain instrumental variable system identification algorithm. In comparison, it is shown that these recent algorithms exhibit extremely poor numerical properties when solved using traditional approaches. [ABSTRACT FROM PUBLISHER]

We present a novel distributed algorithm for convex constrained optimization problems that are subject to noise corruption and uncertainties. The proposed scheme can be classified as a distributed stochastic approximation method, where a unique feature here is that we allow for multiple noise terms to appear in both the computation and communication stages of the distributed iterative process. Specifically, we consider problems that involve multiple agents optimizing a separable convex objective function subject to convex local constraints and linear coupling constraints. This is a richer class of problems compared to those that can be handled by existing distributed stochastic approximation methods which consider only consensus constraints and fewer sources of noise. The proposed algorithm utilizes the augmented Lagrangian (AL) framework, which has been widely used recently to solve deterministic optimization problems in a distributed way. We show that the proposed method generates sequences of primal and dual variables that converge to their respective optimal sets almost surely. [ABSTRACT FROM AUTHOR]

We present and examine a novel method for obtaining solutions to specific discrete-time optimal control problems. Our approach is based on linear state dynamics and convexity assumptions commonly satisfied in practical applications. We show that the important class of optimal switching problems under partial observation is covered by our methodology, and we exploit specific model features to achieve simple algorithmic form of a numerical solution. [ABSTRACT FROM AUTHOR]

We consider an optimization problem for a dynamical system whose evolution depends on a collection of binary decision variables. We develop scalable approximation algorithms with provable suboptimality bounds to provide computationally tractable solution methods even when the dimension of the system and the number of the binary variables are large. The proposed method employs a linear approximation of the objective function such that the approximate problem is defined over the feasible space of the binary decision variables, which is a discrete set. To define such a linear approximation, we propose two different variation methods: one uses continuous relaxation of the discrete space and the other uses convex combinations of the vector field and running payoff. The approximate problem is a 0-1 linear program, which can be solved by existing polynomial-time exact or approximation algorithms, and does not require the solution of the dynamical system. Furthermore, we characterize a sufficient condition ensuring the approximate solution has a provable suboptimality bound. We show that this condition can be interpreted as the concavity of the objective function or that of a reformulated objective function. [ABSTRACT FROM PUBLISHER]

This technical note addresses a tradeoff in the tree based trajectory optimization algorithms for open-loop optimal control problem of rigid body system. In this technical note, linear prediction based uniform state sampling method (LPUSS), which relaxes the tradeoff between solutions' quality and computational efficiency, is proposed on the basis of the local linearity of motion equations. LPUSS has a lower calculation order than randomized kinodynamic planning (RKP) and rapid semi-optimal motion planning (RASMO). In the validation using multi degree-of-freedom (DOF) under actuated manipulator models, the solutions' quality and the computational efficiency of LPUSS were better than those of RKP and RASMO. LPUSS finished the optimization for the 6 DOF model within 40 minutes. This was the world's first success of the optimization of the swing up motion of a 6 DOF under actuated manipulator model. [ABSTRACT FROM PUBLISHER]

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]

We develop a gradient algorithm for optimizing the performance of product-form networks through online adjustment of control parameters. The use of standard algorithms for finding optimal parameter settings is hampered by the prohibitive computational burden of calculating the gradient in terms of the stationary probabilities. The proposed approach instead relies on measuring empirical frequencies of the various states through simulation or online operation so as to obtain estimates for the gradient. Besides the reduction in computational effort, a further benefit of the online operation lies in the natural adaptation to slow variations in ambient parameters as commonly occurring in dynamic environments. On the downside, the measurements result in inherently noisy and biased estimates. We exploit mixing time results in order to overcome the impact of the bias and establish sufficient conditions for convergence to a globally optimal solution. We discuss our algorithm in the context of different systems, including queueing networks, loss networks, and wireless networks. We also illustrate how the algorithm can be used in such systems to optimize a service/cost trade-off, to map parameter regions that lead to systems meeting specified constraints, and to achieve target performance measures. For the latter application, we first identify which performance measures can be controlled depending on the set of configurable parameters. We then characterize the achievable region of performance measures in product-form networks, and finally we describe how our algorithm can be used to achieve the target performance in an online, distributed fashion, depending on the application context. [ABSTRACT FROM PUBLISHER]

We analyze the problem of stability of a continuous time linear switching system (LSS) versus the stability of its Euler discretization. In case of matrices with real spectrum, we obtain a lower bound for the Euler step size to decide stability. This leads to a method for computing the Lyapunov exponent with a given accuracy and with a guaranteed computational cost. Our approach is based on the analysis of Chebyshev systems of exponents. [ABSTRACT FROM AUTHOR]

This technical note extends the feedback particle filter (FPF) methodology and algorithms to the problem of filtering a continuous-time Markov chain. The main contribution is the development of a feedback control-based transformation of the Wonham filter, where the control input is realized via a time-modulated Poisson counter process. A complete characterization of the feedback mechanism that defines the FPF is obtained, which leads to tractable algorithms for the nonlinear filtering problem even for large state spaces. Numerical examples are introduced to help illustrate the application of these techniques. [ABSTRACT FROM PUBLISHER]

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]

We apply first- and second-order splitting schemes to the differential Riccati equation. Such equations are very important in, e.g., linear quadratic regulator (LQR) problems, where they provide a link between the state of the system and the optimal input. The methods can also be extended to generalized Riccati equations, e.g., arising from LQR problems given in implicit form. In contrast to previously proposed schemes such as BDF or Rosenbrock methods, the splitting schemes exploit the fact that the nonlinear and affine parts of the problem, when considered in isolation, have closed-form solutions. We show that if the solution possesses low-rank structure, which is frequently the case, then this is preserved by the method. This feature is used to implement the methods efficiently for large-scale problems. The proposed methods are expected to be competitive, as they at most require the solution of a small number of linear equation systems per time step. Finally, we apply our low-rank implementations to the Riccati equations arising from two LQR problems. The results show that the rank of the solutions stay low, and the expected orders of convergence are observed. [ABSTRACT FROM PUBLISHER]

We investigate the connections between compression learning and scenario based optimization. We first show how to strengthen, or relax the consistency assumption at the basis of compression learning and provide novel learnability conditions for the underlying algorithms. We then consider different constrained optimization problems affected by uncertainty represented by means of scenarios. We show that the compression learning perspective provides a unifying framework for scenario based optimization, since the issue of providing guarantees on the probability of constraint violation reduces to a learning problem for an appropriately chosen algorithm that satisfies some consistency assumption. To illustrate this, we revisit the scenario approach within the developed context. Moreover, using the compression learning machinery we provide novel results on the probability of constraint violation for the class of cascading optimization problems. [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]

We consider a cooperative conflict resolution problem that finds application, for example, in vehicle intersection crossing. We seek to determine minimally restrictive supervisors, which allow agents to choose all possible control actions that keep the system safe, that is, conflict free. This is achieved by determining the maximal controlled invariant set, and then by determining control actions that keep the system state inside this set. By exploiting the natural monotonicity of the agents dynamics along their paths, we translate this problem into an equivalent scheduling problem. This allows us to leverage existing results in the scheduling literature to obtain both exact and approximate solutions. The approximate algorithms have polynomial complexity and can handle large problems with guaranteed approximation bounds. We illustrate the application of the proposed algorithms through simulations in which vehicles crossing an intersection are overridden by the supervisor only when necessary to maintain safety. [ABSTRACT FROM AUTHOR]