Search

In this article, we consider an online distributed composite optimization problem over a time-varying multiagent network that consists of multiple interacting nodes, where the objective function of each node consists of two parts: a loss function that changes over time and a regularization function. This problem naturally arises in many real-world applications ranging from wireless sensor networks to signal processing. We propose a class of online distributed optimization algorithms that are based on approximate mirror descent, which utilizes the Bregman divergence as a distance-measuring function that includes the Euclidean distances as a special case. We consider two standard information feedback models when designing the algorithms, that is, full-information feedback and bandit feedback. For the full-information feedback model, the first algorithm attains an average regularized regret of order O(1/√T) with the total number of rounds T. The second algorithm, which only requires the information of the values of the loss function at two predicted points instead of the gradient information, achieves the same average regularized regret as that of the first algorithm. Simulation results of a distributed online regularized linear regression problem are provided to illustrate the performance of the proposed algorithms. [ABSTRACT FROM AUTHOR]

This article studies the infinite-horizon adaptive optimal control of continuous-time linear periodic (CTLP) systems. A novel value iteration (VI) based off-policy adaptive dynamic programming (ADP) algorithm is proposed for a general class of CTLP systems, so that approximate optimal solutions can be obtained directly from the collected data, without the exact knowledge of system dynamics. Under mild conditions, the proofs on uniform convergence of the proposed algorithm to the optimal solutions are given for both the model-based and model-free cases. The VI-based ADP algorithm is able to find suboptimal controllers without assuming the knowledge of an initial stabilizing controller. Application to the optimal control of a triple inverted pendulum subjected to a periodically varying load demonstrates the feasibility and effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

This article proposes a data-driven iterative feedback control method to efficiently solve finite time horizon, nonlinear, input constrained optimal control problems. The proposed method introduces a novel approach to combine an inexact system model with measured state information to reduce the cost and provide near-optimal control by approximately solving the optimal control problem along the trajectory of the real system, as opposed to solving it along the trajectory predicted by the inexact model. We present a new algorithm that implements the proposed method, establish the convergence and optimality properties of the proposed algorithm, and compare it to optimal feedback control and model predictive control that solve the same optimal control problem along the trajectory predicted by the inexact model. Finally, we illustrate the generality of the proposed algorithm by approximately solving a challenging optimal control problem with unknown and changing dynamics. [ABSTRACT FROM AUTHOR]

This article presents a multicommodity, discrete-time, distributed, and noncooperative routing algorithm, which is proved to converge to an equilibrium in the presence of heterogeneous, unknown, time-varying but bounded delays. Under mild assumptions on the latency functions, which describe the cost associated with the network paths, two algorithms are proposed: The former assumes that each commodity relies only on measurements of the latencies associated with its own paths; the latter assumes that each commodity has (at least indirectly) access to the measures of the latencies of all the network paths. Both algorithms are proven to drive the system state to an invariant set that approximates and contains the Wardrop equilibrium, defined as a network state in which no traffic flow over the network paths can improve its routing unilaterally, with the latter achieving a better reconstruction of the Wardrop equilibrium. Numerical simulations show the effectiveness of the proposed approach. [ABSTRACT FROM AUTHOR]

This article deals with output feedback selection in linear time-invariant structured systems. We assume that the inputs and the outputs are dedicated, i.e., each input directly actuates a single state and each output directly senses a single state. Given a structured system with dedicated inputs and outputs and a cost matrix that denotes the cost of each feedback connection, our aim is to select a minimum cost set of feedback connections such that the closed-loop system satisfies arbitrary pole-placement. This problem is referred to as the optimal feedback selection problem for dedicated i/o. The optimal feedback selection problem for dedicated i/o is NP-hard and inapproximable to a constant factor of log n, where n denotes the system dimension. To this end, we propose an algorithm to find an approximate solution to the problem. The proposed algorithm consists of a potential function incorporated with a greedy scheme and attains a solution with a guaranteed approximation ratio. We consider two special network topologies of practical importance, referred to as back-edge feedback structure and hierarchical networks. For the first case, which is NP-hard and inapproximable to a multiplicative factor of log n, we provide a log n-approximate solution. For hierarchical networks, we give a dynamic programming based algorithm to obtain an optimal solution in polynomial time. [ABSTRACT FROM AUTHOR]

With the development of large-scale sensor networks, there is an increasing interest for high dimensional distributed decision fusion problem in statistical decision, machine learning, control theory, etc. In this article, we investigate the optimal sensor quantized rules of the distributed decision under a given fusion rule for conditionally dependent and high dimensional sensor observations. We provide a Monte Carlo importance sampling method to reduce the computational complexity of the distributed decision fusion. For the K-out-of-L rule, we derive a group of analytic sensor rules based on the necessary and sufficient condition of the optimal sensor rules. In term of efficiency, it is significantly better than the traditional iterative search algorithms, such as the Riemann sum approximation iteration algorithm. The analytic solution is also a general result since it does not rely on the specific K value of the K-out-of-L rule, the specific conditional probability density function and the dimension of sensor observations. Thus, it can be applied to multisensor decision fusion problems with high dimensional dependent sensor observations. For the general fusion rules rather than the K-out-of-L rule, the Monte Carlo Gauss–Seidel algorithm is also provided. The numerical examples demonstrate the effectiveness of the analytic solution and the Monte Carlo Gauss–Seidel algorithm. [ABSTRACT FROM AUTHOR]

This article focuses on developing a strategy for control of systems, whose dynamics are almost entirely unknown. This situation arises naturally in a scenario, where a system undergoes a critical failure. In that case, it is imperative to retain the ability to satisfy basic control objectives in order to avert an imminent catastrophe. To deal with limitations on the knowledge of system dynamics, we develop a theory of myopic control. At any given time, myopic control optimizes the current direction of the system trajectory, given solely the knowledge about system dynamics obtained from data until that time. We propose an algorithm that uses small perturbations in the control effort to learn system dynamics around the current system state, while ensuring that the system moves in a nearly optimal direction, and provide bounds for its suboptimality. [ABSTRACT FROM AUTHOR]

In this article, we propose a novel family of higher order sliding mode (HOSM) controllers with discontinuous integral term for a class of single-input–single-output (SISO) nonlinear systems. They belong to a recently introduced class of controllers, named continuous HOSM since they are able to compensate exactly and in finite-time perturbations/uncertainties using a continuous control signal. They are obtained by introducing a discontinuous integral action at the input of the plant. Here, continuously differentiable Lyapunov functions are used to rigorously prove the stability of the closed-loop system. We also investigate an approximation of this strategy, where a continuous integral term replaces the discontinuous one. The robustness properties of the closed-loop controller with continuous and discontinuous integral term are studied. [ABSTRACT FROM AUTHOR]

Security issues in cyber-physical systems (CPSs) have gained increasing attention in recent years due to the importance and unavoidable vulnerability of CPSs. This article focuses on designing an intelligent online attack, which can compromise a sensor, eavesdrop measurements, and inject false feedback information, against remote state estimation. From the viewpoint of the attacker, we design an event-based attack strategy to degrade the estimation quality with an arbitrary communication rate stealthy constraint. The approximate minimum mean-squared error estimation algorithm from the viewpoint of the attacker is derived under a Gaussian assumption. Furthermore, the relation between the attack threshold and the scheduling threshold is obtained in a closed form. We show that the mean-squared stability condition of the estimation is weakened under the attack. Two examples are provided to demonstrate the main results. [ABSTRACT FROM AUTHOR]

Directed acyclic graphs (DAGs) are emerging as an attractive alternative to traditional blockchain architectures for distributed ledger technology. In particular, DAG ledgers with stochastic attachment mechanisms potentially offer many advantages over blockchain, including scalability and faster transaction speeds. However, the random nature of the attachment mechanism coupled with the requirement of protection against double-spending transactions might result in an unstable system in which not all transactions get eventually validated. Such transactions are said to be orphaned, and will never be validated. Our principal contribution is to propose a simple modification to the attachment mechanism for the Tangle (the IOTA DAG architecture). This modification ensures that all transactions are validated in finite time, and preserves essential features of the popular Monte Carlo selection algorithm. In order to demonstrate these results, we derive a fluid approximation for the Tangle (in the limit of infinite arrival rate) and prove that this fluid model exhibits the desired behavior. We also present simulations that validate the results for finite arrival rates. [ABSTRACT FROM AUTHOR]

An online reinforcement learning algorithm called renewal Monte Carlo (RMC) is presented. RMC works for infinite horizon Markov decision processes with a designated start state. RMC is a Monte Carlo algorithm that retains the key advantages of Monte Carlo—viz., simplicity, ease of implementation, and low bias—while circumventing the main drawbacks of Monte Carlo—viz., high variance and delayed updates. Given a parameterized policy $\pi _\theta$ , the algorithm consists of three parts: estimating the expected discounted reward $\mathsf {R}_{\theta }$ and the expected discounted time $\mathsf {T}_\theta$ over a regenerative cycle; estimating the derivatives $\nabla _\theta \mathsf {R}_\theta$ and $\nabla _\theta \mathsf {T}_\theta$ ; and updating the policy parameters using stochastic approximation to find the roots of $\mathsf {R}_\theta \nabla _\theta \mathsf {T}_\theta - \mathsf {T}_\theta \nabla _\theta \mathsf {R}_\theta$. It is shown that under mild technical conditions, RMC converges to a locally optimal policy. It is also shown that RMC works for postdecision state models as well. An approximate version of RMC is proposed where a regenerative cycle is defined as successive visits to a prespecified “renewal set”. It is shown that if the value function of the system is locally Lipschitz on the renewal set, then RMC converges to an approximate locally optimal policy. Three numerical experiments are presented to illustrate RMC and compare it with other state-of-the-art reinforcement learning algorithms. [ABSTRACT FROM AUTHOR]

One of the most important problems in the field of distributed optimization is the problem of minimizing a sum of local convex objective functions over a networked system. Most of the existing work in this area focuses on developing distributed algorithms in a synchronous setting under the presence of a central clock, where the agents need to wait for the slowest one to finish the update, before proceeding to the next iterate. Asynchronous distributed algorithms remove the need for a central coordinator, reduce the synchronization wait, and allow some agents to compute faster and execute more iterations. In the asynchronous setting, the only known algorithms for solving this problem could achieve an either linear or sublinear rate of convergence. In this paper, we build upon the existing literature to develop and analyze an asynchronous Newton-based method to solve a penalized version of the problem. We show that this algorithm guarantees almost sure convergence with a global linear and local quadratic rate in expectation. Numerical studies confirm the superior performance of our algorithm against other asynchronous methods. [ABSTRACT FROM AUTHOR]

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

We introduce deterministic perturbation (DP) schemes for the recently proposed random directions stochastic approximation, and propose new first-order and second-order algorithms. In the latter case, these are the first second-order algorithms to incorporate DPs. We show that the gradient and/or Hessian estimates in the resulting algorithms with DPs are asymptotically unbiased, so that the algorithms are provably convergent. Furthermore, we derive convergence rates to establish the superiority of the first-order and second-order algorithms, for the special case of a convex and quadratic optimization problem, respectively. Numerical experiments are used to validate the theoretical results. [ABSTRACT FROM AUTHOR]

We consider discrete-time dynamics for cascading failure in DC networks whose map is a composition of failure rule with control actions. Supply–demand at the nodes is monotonically nonincreasing under admissible control. Under the failure rule, a link is removed permanently if its flow exceeds capacity. We consider finite horizon optimal control to steer the network from an arbitrary initial state, defined in terms of active link set and supply–demand at the nodes, to a feasible state, i.e., a state which is invariant under the failure rule. There is no running cost and the reward associated with a feasible terminal state is the associated cumulative supply–demand. We propose two approaches for computing optimal control. The first approach, geared toward tree reducible networks, decomposes the global problem into a system of coupled local problems, which can be solved to optimality in two iterations. When restricted to the class of one-shot control actions, the optimal solutions to the local problems possess a piecewise affine property, which facilitates analytical solutions. The second approach computes optimal control by searching over the reachable set, which is shown to admit an equivalent finite representation by aggregation of control actions leading to the same reachable active link set. An algorithmic procedure to construct this representation is provided by leveraging and extending tools for arrangement of hyperplanes and polytopes. Illustrative simulations, including showing the effectiveness of projection-based approximation algorithms, are also presented. [ABSTRACT FROM AUTHOR]

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

In this paper, 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]

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

When using standard learning techniques for uncertainty approximation, persistently exciting inputs are necessary in order to achieve good parameter estimation. It has been shown in recent years that, through concurrent learning (CL), it is possible to achieve better learning without requiring persistency of excitation. We define good learning here by how well an uncertainty can be reconstructed given the estimated parameters. Most studies concerning CL have however been done in the continuous-time (CT) framework. While working with discrete-time (DT) structured uncertainties, we have shown in an earlier study that the concept of CL could be used to solve the parameter identification problem granted, much like in the CT domain, a less restrictive condition compared to that of persistency of excitation is verified. This paper furthers our fundamental study of CL in the DT framework while drawing comparisons with the traditional but fundamental gradient descent technique. As a main contribution, via formal derivations, we present a generalized gradient-based CL motivated DT algorithm for online approximation of both DT structured and unstructured uncertainties. Numerical simulations are provided to show how well the designed algorithm leverages memory usage to achieve better learning. [ABSTRACT FROM AUTHOR]

This technical note is aimed to derive the Chandrasekhar-type recursion for the maximum correntropy criterion (MCC) Kalman filtering (KF). For the classical KF, the first Chandrasekhar difference equation was proposed at the beginning of 1970s. This is the alternative to the traditionally used Riccati recursion and it yields the so-called fast implementations known as the Morf–Sidhu–Kailath–Sayed KF algorithms. They are proved to be computationally cheap because of propagating the matrices of a smaller size than $n \times n$ error covariance matrix in the Riccati recursion. The problem of deriving the Chandrasekhar-type recursion within the MCC estimation methodology has never been raised yet in engineering literature. In this technical note, we do the first step and derive the Chandrasekhar MCC-KF estimators for the case of adaptive kernel size selection strategy, which implies a constant scalar adjusting weight. Numerical examples substantiate a practical feasibility of the newly suggested MCC-KF implementations and correctness of the presented theoretical derivations. [ABSTRACT FROM AUTHOR]

In this paper, we propose two iterative algorithms to identify transfer functions of two-dimensional (2-D) systems. The proposed algorithms are modifications of the 2-D adaptive Fourier decomposition (AFD) and weak pre-orthogonal adaptive Fourier decomposition (W-POAFD). 2-D AFD and W-POAFD are newly established adaptive representation theories for multivariate functions utilizing, respectively, the product-TM system and the product-Szegö dictionary. The proposed algorithms give rise to rational approximations with real coefficients to transfer functions. Owing to the modified maximal selection principles, the algorithms achieve a fast convergence rate $\boldsymbol {O(n^{-\frac{1}{2}})}$. To use 2-D AFD and W-POAFD for system identification not only the theory is revised, but also the practical algorithm codes are provided. Experimental examples show that the proposed algorithms give promising results. The theory and algorithms studied in this paper are valid for any ${n}$ -D case, ${n\geq 2}$. [ABSTRACT FROM AUTHOR]

In this paper, a novel distributed stochastic approximation algorithm (DSAA) is proposed to seek roots of the sum of local functions, each of which is associated with an agent from multiple agents connected over a network. At each iteration, each agent updates its estimate for the root utilizing the noisy observations of its local function and the information derived from the neighboring agents. The key difference of the proposed algorithm from the existing ones consists in the expanding truncations (so it is called the DSAAWET), by which the boundedness of the estimates can be guaranteed without imposing the growth-rate constraints on the local functions. The estimates generated by the DSAAWET are shown to converge almost surely to a consensus set, which belongs to a connected subset of the root set of the sum function. In comparison with the existing results, we impose weaker conditions on the local functions and on the observation noise. We then apply the proposed algorithm to two applications, one from signal processing and the other one from distributed optimization, and establish the almost sure convergence. Numerical simulation results are also included. [ABSTRACT FROM AUTHOR]

We propose universal randomized function approximation-based empirical value learning (EVL) algorithms for Markov decision processes. The “empirical” nature comes from each iteration being done empirically from samples available from simulations of the next state. This makes the Bellman operator a random operator. A parametric and a nonparametric method for function approximation using a parametric function space and a reproducing kernel Hilbert space respectively are then combined with EVL. Both function spaces have the universal function approximation property. Basis functions are picked randomly. Convergence analysis is performed using a random operator framework with techniques from the theory of stochastic dominance. Finite time sample complexity bounds are derived for both universal approximate dynamic programming algorithms. Numerical experiments support the versatility and computational tractability of this approach. [ABSTRACT FROM AUTHOR]

We describe a nonlinear generalization of dual dynamic programming (DP) theory and its application to value function estimation for deterministic control problems over continuous state and action spaces, in a discrete-time infinite horizon setting. We prove, using a Benders-type argument leveraging the monotonicity of the Bellman operator, that the result of a one-stage policy evaluation can be used to produce nonlinear lower bounds on the optimal value function that are valid over the entire state space. These bounds contain terms reflecting the functional form of the system's costs, dynamics, and constraints. We provide an iterative algorithm that produces successively better approximations of the optimal value function, and prove under certain assumptions that it achieves an arbitrarily low desired Bellman optimality tolerance at preselected points in the state space, in a finite number of iterations. We also describe means of certifying the quality of the approximate value function generated. We demonstrate the efficacy of the approach on systems whose dimensions are too large for conventional DP approaches to be practical. [ABSTRACT FROM AUTHOR]

We show that two widely accepted model reduction techniques, balanced truncation (BT) and balanced singular perturbation approximation (BSPA), can be derived as limiting approximations of a carefully constructed parameterization of linear time invariant systems by employing the model boundary approximation method (MBAM). We also show that MBAM provides a novel way to interpolate between BT and BSPA, by exploring the set of approximations on the boundary of the “model manifold,” which is associated with the specific choice of model parameterization and initial condition and is embedded in a sample space of measured outputs, between the elements that correspond to the two model reduction techniques. This paper suggests similar types of approximations may be obtainable in topologically similar places (i.e., on certain boundaries) on the associated model manifold of nonlinear systems if analogous parameterizations can be achieved, therefore extending these widely accepted model reduction techniques to nonlinear systems. [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]

Q-learning is a sample-based model-free algorithm that solves Markov decision problems asymptotically, but in finite time, it can perform poorly when random rewards and transitions result in large variance of value estimates. We pinpoint its cause to be the estimation bias due to the maximum operator in Q-learning algorithm, and present the evidence of max-operator bias in its Q value estimates. We then present an asymptotically optimal bias-correction strategy and construct an extension to bias-corrected Q-learning algorithm to multistate Markov decision processes, with asymptotic convergence properties as strong as those from Q-learning. We report the empirical performance of the bias-corrected Q-learning algorithm with multistate extension in two model problems: A multiarmed bandit version of Roulette and an electricity storage control simulation. The bias-corrected Q-learning algorithm with multistate extension is shown to control max-operator bias effectively, where the bias-resistance can be tuned predictably by adjusting a correction parameter. [ABSTRACT FROM AUTHOR]

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

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]

We consider the leader selection problem in a network with consensus dynamics where both leader and follower agents are subject to stochastic external disturbances. The performance of the system is quantified by the total steady-state variance of the node states, and the goal is to identify the set of leaders that minimizes this variance. We first show that this performance measure can be expressed as a submodular set function over the nodes in the network. We then use this result to analyze the performance of two greedy, polynomial-time algorithms for leader selection, showing that the leader sets produced by the greedy algorithms are within provable bounds of optimal. [ABSTRACT FROM AUTHOR]

We are interested in understanding stability (almost sure boundedness) of stochastic approximation algorithms (SAs) driven by a “controlled Markov” process. Analyzing this class of algorithms is important, since many reinforcement learning (RL) algorithms can be cast as SAs driven by a “controlled Markov” process. In this paper, we present easily verifiable sufficient conditions for stability and convergence of SAs driven by a “controlled Markov” process. Many RL applications involve continuous state spaces. While our analysis readily ensures stability for such continuous state applications, traditional analyses do not. As compared to literature, our analysis presents a two-fold generalization: 1) the Markov process may evolve in a continuous state space and 2) the process need not be ergodic under any given stationary policy. Temporal difference (TD) learning is an important policy evaluation method in RL. The theory developed herein, is used to analyze generalized $\text{TD}(0)$ , an important variant of TD. Our theory is also used to analyze a TD formulation of supervised learning for forecasting problems. [ABSTRACT FROM AUTHOR]

A regularized optimization problem over a large unstructured graph is studied, where the regularization term is tied to the graph geometry. Typical regularization examples include the total variation and the Laplacian regularizations over the graph. When the graph is a simple path without loops, efficient off-the-shelf algorithms can be used. However, when the graph is large and unstructured, such algorithms cannot be used directly. In this paper, an algorithm, referred to as “Snake,” is proposed to solve such regularized problems over general graphs. The algorithm consists in properly selecting random simple paths in the graph and performing the proximal gradient algorithm over these simple paths. This algorithm is an instance of a new general stochastic proximal gradient algorithm, whose convergence is proven. Applications to trend filtering and graph inpainting are provided among others. Numerical experiments are conducted over large graphs. [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]

This paper proposes a new optimal control synthesis algorithm for multirobot systems under global temporal logic tasks. Existing planning approaches under global temporal goals rely on graph search techniques applied to a product automaton constructed among the robots. In this paper, we propose a new sampling-based algorithm that builds incrementally trees that approximate the state space and transitions of the synchronous product automaton. By approximating the product automaton by a tree rather than representing it explicitly, we require much fewer memory resources to store it and motion plans can be found by tracing sequences of parent nodes without the need for sophisticated graph search methods. This significantly increases the scalability of our algorithm compared to existing optimal control synthesis methods. We also show that the proposed algorithm is probabilistically complete and asymptotically optimal. Finally, we present numerical experiments showing that our approach can synthesize optimal plans from product automata with billions of states, which is not possible using standard optimal control synthesis algorithms or model checkers. [ABSTRACT FROM AUTHOR]

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

Direct method for Yau filtering system has been studied since 1990s and all these work are limited in time-invariant systems. In this work, we extend the direct method so that it is applicable to time-varying cases. We need less assumptions compared with our previous work. The novelty of this work is that we propose several transformations on the forward Kolmogorov equation so that it can be solved by means of solving some ordinary differential equations if the initial distribution is Gaussian. The corresponding results for any non-Gaussian initial distributions can be obtained via Gaussian approximation. It can be seen that our new scheme direct method can treat nearly most general Yau filtering problems under natural assumptions. Our algorithm has been compared with the extended Kalman filter, multilevel particle filter, and ensemble Kalman filter by numerical examples and the simulation results show the efficiency of our method. [ABSTRACT FROM AUTHOR]

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

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

In this paper, we study the problem of computing the distance between a given singular descriptor system $ (E,A)$ , and a nearest descriptor system that has impulsive initial conditions. The link between existence of impulsive initial conditions and zeros at infinity for the associated matrix pencil $sE - A$ is well-known. Much of the literature focusses on the case when only one of $E$ and $A$ is perturbed. We give a closed form expression of the distance to a nearest descriptor system having impulsive solutions via rank-1 perturbations when both $E$ and $A$ are perturbed. Next, for the case of perturbations without rank restrictions, we propose and evaluate the bounds for the distance. In the context of structured perturbations, we formulate and obtain an explicit expression for the distance, when $E$ and $A$ are Hermitian and are perturbed by Hermitian matrices. For a suitable class of systems, we also show that upper and lower bounds are within a factor of $\sqrt{2}$. We finally construct examples and compare the bounds obtained from our results with those from the literature as well as with computed values of the distance obtained via three numerical optimization techniques such as the structured low rank approximation, the Broyden–Fletcher–Goldfarb–Shanno algorithm, and direct optimization tools like globalsearch. [ABSTRACT FROM AUTHOR]

Separable nonlinear least-squares (SNLLS) problems arise frequently in many research fields, such as system identification and machine learning. The variable projection (VP) method is a very powerful tool for solving such problems. In this paper, we consider the regularization of ill-conditioned SNLLS problems based on the VP method. Selecting an appropriate regularization parameter is difficult because of the nonlinear optimization procedure. We propose to determine the regularization parameter using the weighted generalized cross-validation method at every iteration. This makes the original objective function changing during the optimization procedure. To circumvent this problem, we use an inequation to produce a consistent demand of decreasing at successive iterations. The approximation of the Jacobian of the regularized problem is also discussed. The proposed regularized VP algorithm is tested by the parameter estimation problem of several statistical models. Numerical results demonstrate the effectiveness of the proposed algorithm. [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]

This paper investigates the remote state estimation problem over a bandwidth-limited channel. To improve the estimation quality, an event-based schedule is proposed to determine whether to transmit the current measurement to the remote estimator or not. We first show that it is erroneous to apply the widely used Gaussian-approximation assumption in the event-based scheduling. As a replacement, the generalized closed skew normal (GCSN) distribution is introduced to accurately portray the system state distribution in the event-based scheduling. Furthermore, we present the probability density functions of the minimum mean-squared error estimation algorithm exactly without approximation for the first time. The closed-form expressions for the mean and covariance of the GCSN distribution are derived as well. Numerical examples validate the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

This paper addresses optimal feedback selection for arbitrary pole placement of structured systems when each feedback edge is associated with a cost. Given a structured system and a feedback cost matrix, our aim is to find a feasible feedback matrix of minimum cost that guarantees arbitrary pole placement of the closed-loop structured system. The same problem but with uniform costs has been considered recently, but the claim and the NP-hardness proof there has subtle flaws: we mention this briefly in our paper and then prove the NP-hardness of the feedback selection problem using a reduction from the weighted set cover problem. We next prove the polynomial time constant factor inapproximability of the problem by showing that a constant factor approximation for the problem does not exist, unless the weighted set cover problem can also be approximated within a constant factor. We study a subclass of systems whose directed acyclic graph constructed using the strongly connected components of the state digraph is a line graph and the state bipartite graph has a perfect matching. We propose a polynomial time algorithm based on dynamic programming principles for optimal feedback selection on this class of systems. Further, over the same class of systems we relax the perfect matching assumption, and provide a polynomial time 2-optimal solution using a minimum cost perfect matching algorithm. [ABSTRACT FROM AUTHOR]

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

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

We consider distributed convex optimization problems that involve a separable objective function and nontrivial functional constraints, such as linear matrix inequalities. We propose a decentralized and computationally inexpensive algorithm, which is based on the concept of approximate projections. Our algorithm is one of the consensus-based methods in that, at every iteration, each agent performs a consensus update of its decision variables followed by an optimization step of its local objective function and local constraints. Unlike other methods, the last step of our method is not a Euclidean projection onto the feasible set, but instead a subgradient step in the direction that minimizes the local constraint violation. We propose two different averaging schemes to mitigate the disagreements among the agents’ local estimates. We show that the algorithms converge almost surely, i.e., every agent agrees on the same optimal solution, under the assumption that the objective functions and constraint functions are nondifferentiable and their subgradients are bounded. We provide simulation results on a decentralized optimal gossip averaging problem, which involves semidefinite programming constraints, to complement our theoretical results. [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]

This paper deals with minimum cost constrained input selection (minCCIS) for state-space structured systems. Our goal is to optimally select an input set from the given inputs such that the system is structurally controllable when the set of states that each input can influence is prespecified and each input has a cost associated with it. This problem is known to be NP-hard. First, we give a flow-network-based novel necessary and sufficient graph theoretic condition for checking structural controllability. Using this condition, we propose a polynomial time reduction of the problem to a known NP-hard problem: the minimum-cost fixed-flow problem (MCFF). Subsequently, we show that approximation schemes of MCFF directly apply to the minCCIS problem. Using the special structure of the flow-network constructed for the structured system, we formulate a polynomial time approximation algorithm based on minimum weight bipartite matching problem and a greedy scheme for solving the MCFF problem on the system flow-network. The proposed algorithm gives a so-called $\Delta$ -approximate solution to MCFF, where $\Delta$ denotes the maximum in-degree of input vertices in the flow-network of the structured system. [ABSTRACT FROM AUTHOR]