Search

This is a companion paper of [Mixed equilibrium solution of time-inconsistent stochastic linear-quadratic problem, SIAM J. Control Optim., vol. 57, no. 1, 533–569, 2019], where general theory has been established to characterize the open-loop equilibrium control, feedback equilibrium strategy and mixed equilibrium solution for a time-inconsistent stochastic linear-quadratic problem. This note is, on the one hand, to test the developed theory of that paper and on the other hand to push the solvability of multiperiod mean-variance portfolio selection. A nondegenerate assumption, which is popular in the existing literature about multiperiod mean-variance portfolio selection, has been removed in this note; and neat conditions have been obtained to characterize the existence of equilibrium solutions. [ABSTRACT FROM AUTHOR]

This paper considers the quadratic control problem of discrete-time Markov jump linear systems with constraints on the norm of the state and control variables. We assume that the Markov chain parameter is not available, and instead, there is a detector, which emits signals providing information on this parameter. It is desired to derive a feedback linear control using the information provided by this detector in order to stochastically stabilize the closed-loop system, satisfy the constraints whenever the initial conditions belong to an invariant set, and minimize an upper bound for the quadratic cost. We show that a linear matrix inequality (LMI) optimization problem can be formulated in order to obtain a solution for this problem. Two other related problems, one for minimizing the guaranteed quadratic cost considering fixed initial conditions and the other for maximizing an estimate of the domain of an invariant set, can also be formulated using our LMI approach. This paper is concluded with some numerical simulations. [ABSTRACT FROM AUTHOR]

This paper proposes scalable, distributed algorithms for solving linear equations by integrating two mechanisms, termed consensus and conservation, in double-layered multiagent networks. The multiagent network considered in this paper is composed of clusters and each cluster consists of an aggregator and a subnetwork of agents. By achieving consensus and conservation through agent–agent communications in the same cluster and aggregator–aggregator communications among different clusters, respectively, distributed algorithms are devised for agents to cooperatively achieve a solution to the overall linear equation. These algorithms outperform existing algorithms, including but not limited to the following aspects—first, each agent does not have to know as much as a complete row or column of the overall equation; second, each agent only needs to control as few as two scalar states when the number of clusters and the number of agents are sufficiently large; third, the dimensions of agents’ states in the proposed algorithms do not have to be the same (while in contrast, algorithms based on the idea of standard consensus inherently require all agents’ states to be of the same dimension). Both analytical proof and simulation results are provided to validate exponential convergence of the proposed distributed algorithms in solving linear equations. [ABSTRACT FROM AUTHOR]

The paper considers normalized gradient descent (NGD), a natural modification of classical gradient descent (GD) in optimization problems. It is shown that, contrary to GD, NGD escapes saddle points “quickly.” A serious shortcoming of GD in nonconvex problems is that it can take arbitrarily long to escape from the neighborhood of a saddle point. In practice, this issue can significantly slow the convergence of GD, particularly in high-dimensional nonconvex problems. The paper focuses on continuous-time dynamics. It is shown that 1) NGD “almost never” converges to saddle points and 2) the time required for NGD to escape from a ball of radius $r$ about a saddle point $x^*$ is at most $5\sqrt{\kappa }r$ , where $\kappa$ is the condition number of the Hessian of $f$ at $x^*$. As a simple application of these results, a global convergence-time bound is established for NGD under mild assumptions. [ABSTRACT FROM AUTHOR]

Recently, Thompson sampling has been shown to achieve good theoretical performance guarantees for stochastic control problems with parameter uncertainty when the state, control, and parameter spaces are all finite. Much less is known however about the performance of Thompson sampling when applied to continuous or more general spaces, which constitutes an important class of problems in practice. In this paper, we study Thompson sampling when applied to a broad class of average cost stochastic control problems where the state, control, and parameter spaces are all general measurable spaces. The main contributions of our paper are establishing theoretical performance guarantees for Thompson sampling as measured by: first, expected posterior sampling error; and second, average per period regret. [ABSTRACT FROM AUTHOR]

In this paper, we address the so-called Liouville control problem for discrete-time SISO linear systems in the class of Gaussian distributions. In particular, we propose a systematic procedure for the characterization of a dynamic output feedback policy that will transfer the output of the system, which is a known Gaussian random variable, to a goal Gaussian distribution after a finite number of stages. In the proposed approach, the Liouville control problem is reduced to two decoupled (finite-dimensional) quadratic programs, one of which is subject to a single affine constraint, which is a convex program, whereas the other one is subject to a single quadratic equality constraint. Despite the fact that the second optimization problem is not convex, one can characterize its exact solution via a systematic procedure without resorting to convex relaxation techniques, which may yield suboptimal or even infeasible solutions to the original (nonconvex) optimization problem. Finally, we present numerical simulations that illustrate the key ideas of this paper. [ABSTRACT FROM AUTHOR]

This paper deals with the estimation of convergence rate and domain of attraction of control-Lyapunov functions in Lyapunov-based control. This pair of estimation problems has been considered only for input-affine systems with constraints on the input norm. In this paper, we propose a novel optimization framework to address the estimation of convergence rate and domain of attraction. Specifically, we formulate the estimation problems as min–max bilevel programs for the decay rate of the Lyapunov function, where the inner problem can be resolved using Karush–Kuhn–Tucker optimality conditions, and the resulting single-level programs can be transformed into and solved as mixed-integer nonlinear programs. The proposed approach is applicable to systems with input-nonaffinity or more general forms of input constraints under an input-convexity assumption. [ABSTRACT FROM AUTHOR]

A fundamental challenge in multiagent systems is to design local control algorithms to ensure a desirable collective behavior. The information available to the agents, gathered either through communication or sensing, naturally restricts the achievable performance. Hence, it is fundamental to identify what piece of information is valuable and can be exploited to design control laws with enhanced performance guarantees. This paper studies the case when such information is uncertain or inaccessible for a class of submodular resource allocation problems termed covering problems. In the first part of this paper, we pinpoint a fundamental risk-reward tradeoff faced by the system operator when conditioning the control design on a valuable but uncertain piece of information, which we refer to as the cardinality, that represents the maximum number of agents that can simultaneously select any given resource. Building on this analysis, we propose a distributed algorithm that allows agents to learn the cardinality while adjusting their behavior over time. This algorithm is proved to perform on par or better to the optimal design obtained when the exact cardinality is known a priori. [ABSTRACT FROM AUTHOR]

This paper considers the optimization problem for partially observable Markov decision processes (POMDPs) with the continuous state, observation, and action spaces. POMDPs with the discrete spaces have emerged as a promising approach to the decision systems with imperfect state information. However, in recent applications of POMDPs, there are many problems that have continuous states, observations, and actions. For such problems, due to the infinite dimensionality of the belief space, the existing studies usually discretize the continuous spaces with the sufficient or nonsufficient statistics, which may cause the curse of dimensionality and performance degradation. In this paper, based on the sensitivity analysis of the performance criteria, we have developed a simulation-based policy iteration algorithm to find the local optimal observation-based policy for POMDPs with the continuous spaces. The proposed algorithm needs none of the specific assumptions and prior information, and has a low computational complexity. One numerical example of the complicated multiple-input multiple-output beamforming problem shows that the algorithm has a significant performance improvement. [ABSTRACT FROM AUTHOR]

This paper investigates the distributed computation of the well-known linear matrix equation in the form of ${{AXB}} = F$ , with the matrices $A$ , $B$ , $X$ , and $F$ of appropriate dimensions, over multiagent networks from an optimization perspective. In this paper, we consider the standard distributed matrix-information structures, where each agent of the considered multiagent network has access to one of the subblock matrices of $A$ , $B$ , and $F$. To be specific, we first propose different decomposition methods to reformulate the matrix equations in standard structures as distributed constrained optimization problems by introducing substitutional variables; we show that the solutions of the reformulated distributed optimization problems are equivalent to least squares solutions to original matrix equations; and we design distributed continuous-time algorithms for the constrained optimization problems, even by using augmented matrices and a derivative feedback technique. Moreover, we prove the exponential convergence of the algorithms to a least squares solution to the matrix equation for any initial condition. [ABSTRACT FROM AUTHOR]

We study in this paper, a class of constrained linear-quadratic (LQ) optimal control problem formulations for the scalar-state stochastic system with multiplicative noise, which has various applications, especially in the financial risk management. The linear constraint on both the control and state variables considered in our model destroys the elegant structure of the conventional LQ formulation and has blocked the derivation of an explicit control policy so far in the literature. We successfully derive in this paper, the analytical control policy for such a class of problems by utilizing the state separation property induced from its structure. We reveal that the optimal control policy is a piecewise affine function of the state and can be computed offline efficiently by solving two coupled Riccati equations. Under some mild conditions, we also obtain the stationary control policy for an infinite time horizon. We demonstrate the implementation of our method via some illustrative examples and show how to calibrate our model to solve dynamic constrained portfolio optimization problems. [ABSTRACT FROM AUTHOR]

This paper is concerned with the optimal static distributed control problem for linear discrete-time deterministic and stochastic systems. The objective is to design a stabilizing static distributed controller whose performance is close to that of the optimal centralized controller. To this end, we first consider deterministic systems, where the initial state is either given or belongs to a known bounded region. Given an arbitrary centralized controller, we derive a condition under which there exists a distributed controller that generates input and state trajectories close to their counterparts in the centralized closed-loop system. This condition for the design of a distributed controller is translated into an optimization problem, where the optimal objective value of this problem quantifies the closeness of the designed distributed and given centralized control systems. The results are then extended to stochastic systems that are subject to input disturbance and measurement noise. The proposed optimization problem has a closed-form solution (explicit formula) and can be efficiently solved for large-scale systems. The mathematical framework developed in this paper is utilized to design a near-globally optimal distributed controller based on the optimal centralized controller, and strong theoretical lower bounds on the global optimality guarantee of the obtained distributed controller are derived. We show that if the optimal objective value of the proposed convex program is sufficiently small, the designed controller is stabilizing and nearly globally optimal. To illustrate the results, case studies on aircraft formation and frequency control of power systems are offered. [ABSTRACT FROM AUTHOR]

This paper considers the problem of selecting the top-m designs using simulation with input uncertainty. The performance of each design is measured by its worst case performance. The objective of this paper is to maximize the probability of correctly selecting the top-m designs given a fixed simulation budget. Due to the complexity of probability of correct selection (PCS), we develop a lower bound for the PCS and derive an asymptotically optimal budget allocation rule. Useful insights on characterizing the efficient budget allocation rule with input uncertainty are provided. Meanwhile, a sequential simulation procedure is suggested to implement the allocation rule. A series of numerical experiments indicate that the proposed simulation budget allocation rule can outperform all existing selection rules. [ABSTRACT FROM AUTHOR]

Autonomous optimization refers to the design of feedback controllers that steer a physical system to a steady state that solves a predefined, possibly constrained, optimization problem. As such, no exogenous control inputs such as set points or trajectories are required. Instead, these controllers are modeled after optimization algorithms that take the form of dynamical systems. The interconnection of this type of optimization dynamics with a physical system is however not guaranteed to be stable unless both dynamics act on sufficiently different timescales. In this paper, we quantify the required timescale separation and give prescriptions that can be directly used in the design of this type of feedback controllers. Using ideas from singular perturbation analysis, we derive stability bounds for different feedback laws that are based on common continuous-time optimization schemes. In particular, we consider gradient descent and its variations, including projected gradient, and Newton gradient. We further give stability bounds for momentum methods and saddle-point flows. Finally, we discuss how optimization algorithms such as subgradient and accelerated gradient descent, while well-behaved in offline settings, are unsuitable for autonomous optimization due to their general lack of robustness. [ABSTRACT FROM AUTHOR]

In this paper, we consider the regularized version of the Jacobi algorithm, a block coordinate descent method for convex optimization with an objective function consisting of the sum of a differentiable function and a block-separable function. Under certain regularity assumptions on the objective function, this algorithm has been shown to satisfy the so-called sufficient decrease condition, and consequently, to converge in objective function value. In this paper, we revisit the convergence analysis of the regularized Jacobi algorithm and show that it also converges in iterates under very mild conditions on the objective function. Moreover, we establish conditions under which the algorithm achieves a linear convergence rate. [ABSTRACT FROM PUBLISHER]

In model predictive control (MPC), the control input is computed by solving a constrained finite-time optimal control (CFTOC) problem at each sample in the control loop. The main computational effort when solving the CFTOC problem using an active-set (AS) method is often spent on computing the search directions, which in MPC corresponds to solving unconstrained finite-time optimal control (UFTOC) problems. This is commonly performed using Riccati recursions or generic sparsity exploiting algorithms. In this paper, the focus is efficient search direction computations for AS type methods. The system of equations to be solved at each AS iteration is changed only by a low-rank modification of the previous one, and exploiting this structured change is important for the performance of AS-type solvers. In this paper, theory for how to exploit these low-rank changes by modifying the Riccati factorization between AS iterations in a structured way is presented. A numerical evaluation of the proposed algorithm shows that the computation time can be significantly reduced by modifying, instead of re-computing, the Riccati factorization. This speedup can be important for AS-type solvers used for linear, nonlinear, and hybrid MPC. [ABSTRACT FROM PUBLISHER]

This paper explores optimal control problems with $l_1$ objectives involving linear discrete-time systems. These problems can be efficiently solved as linear programs. They also have previously been shown to yield sparse solutions, including idle or deadbeat solutions where the input or output is respectively zero along the entire control horizon. The main contribution of this paper is to derive conditions on the problem parameters that specify when idle or deadbeat solutions occur. These results, based on analyzing the dual problem, demonstrate how different types of sparse solutions result from the choice of the problem parameters and, as a consequence, may guide the design of controllers employing $l_1$ objectives. [ABSTRACT FROM PUBLISHER]

This paper is concerned with distributed learning and optimization in large-scale settings. The well-known fictitious play (FP) algorithm has been shown to achieve Nash equilibrium learning in certain classes of multiagent games. However, FP can be computationally difficult to implement when the number of players is large. Sampled FP (SFP) is a variant of FP that mitigates the computational difficulties arising in FP by using a Monte Carlo (i.e., sampling based) approach. Despite its computational advantages, a shortcoming of SFP is that the number of samples that must be drawn at each iteration grows without bound as the algorithm progresses. In this paper, we propose single sample FP (SSFP)—A variant of SFP in which only one sample needs to be drawn in each round of the algorithm. Convergence of SSFP to the set of Nash equilibria is proven. Simulation results show the performance of SSFP is comparable to that of SFP, despite drawing far fewer samples. [ABSTRACT FROM PUBLISHER]

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

A model-based event-triggered control scheme for nonlinear constrained continuous-time uncertain systems in networked configuration is presented in this paper. It is based on the combined use of model-predictive control (MPC) and integral sliding-mode (ISM) control, and it is oriented to reduce the packet transmission over the network both in the direct path and in the feedback path, in order to avoid network congestion. The key elements of the proposed control scheme are the ISM local control law, the MPC remote controller, a smart sensor, and a smart actuator, both containing a copy of the nominal model of the plant. The role of the ISM control law is to compensate matched uncertainties, without amplifying the unmatched ones. The MPC controller with tightened constraints generates the control component oriented to comply with state and control requirements and is asynchronous since the underlying constrained optimization problem is solved only when a triggering event occurs. In the paper, the robustness properties of the controlled system are theoretically analyzed, proving the regional input-to-state practical stability of the overall control scheme. [ABSTRACT FROM AUTHOR]

This paper investigates the mean-square stabilization problem for discrete-time networked control systems (NCSs). Different from most previous studies, we assume transmission delay and data packet dropout may occur simultaneously. The stabilization for such NCSs remains challenging because of the fundamental difficulty in stochastic control. The contributions of this paper are threefold. First, we present two different necessary and sufficient stabilizing conditions in terms of the unique positive solution to delay-dependent algebraic Riccati equation (DARE) or delay-dependent Lyapunov equation (DLE). Second, the maximum packet dropout rate can be calculated with a proposed optimization algorithm. Third, the stabilizing solution to developed DARE is investigated for its existence and uniqueness. We show the existence condition in terms of the Lyapunov operator and the unobservable mean-square eigenvalue, under which the general DARE has a unique stabilizing solution. [ABSTRACT FROM AUTHOR]

In this paper, we propose an event-based sampling policy to implement a constraint-tightening, robust MPC method. The proposed policy enjoys a computationally tractable design and is applicable to perturbed, linear time-invariant systems with polytopic constraints. In particular, the triggering mechanism is suitable for plants with no centralized sensory node as the triggering mechanism can be evaluated locally at each individual sensor. From a geometrical viewpoint, the mechanism is a sequence of hyperrectangles surrounding the optimal state trajectory such that robust recursive feasibility and robust stability are guaranteed. The design of the triggering mechanism is cast as a constrained parametric-in-set optimization problem with the volume of the set as the objective function. Reparameterized in terms of the set vertices, we show that the problem admits a finite tractable convex program reformulation and a linear program relaxation. Several numerical examples are presented to demonstrate the effectiveness and limitations of the theoretical results. [ABSTRACT FROM AUTHOR]

With the increasing prevalence of variable-supply electricity production, dynamic market structures, including time-varying prices and/or peak demand charges are becoming more common for electricity consumers. This framework requires consumers to consider both the time-varying amount of electricity (i.e., energy) consumed throughout the day as well as the maximum rate of electricity purchase (i.e., power) over a given period, typically a month. Because of this complexity, online optimization techniques such as economic model predictive control (MPC) are a natural tool for consumers to use to minimize cost. However, while closed-loop optimization of these pricing structures is already being proposed for various applications, little has been established about stability or performance properties of the closed-loop system. Due in particular to the peak penalty (which violates the principle of optimality if naively included in the objective function), this theoretical gap leaves the potential for pathological closed-loop behavior despite high-quality open-loop solutions. In this paper, we derive asymptotic performance and stability results for general time-varying economic MPC. We then present a novel extended-state formulation to convert peak demand charges into a time-varying stage cost that can be optimized using economic MPC. In addition, we give a terminal cost and constraint for the augmented system that avoids reducing the feasible set in the original space. Finally, we demonstrate these structures and the closed-loop properties that they satisfy via two illustrative examples. [ABSTRACT FROM AUTHOR]

Zero-sum asymmetric information games model decision-making scenarios involving two competing players who have different information about the game being played. A particular case is that of nested information, where one (informed) player has superior information over the other (uninformed) player. This paper considers the case of nested information in repeated zero-sum games and studies the computation of strategies for both the informed and uninformed players for finite-horizon and discounted infinite-horizon nested information games. For finite-horizon settings, we exploit that for both players, the security strategy, and also the opponent's corresponding best response, depend only on the informed player's history of actions. Using this property, we formulate an linear program (LP) computation of player strategies that is linear in the size of the uninformed player's action set. For the infinite-horizon discounted game, we construct LP formulations to compute the approximated security strategies for both players, and show that the worst-case performance difference between the approximated security strategies and the security strategies converges to zero exponentially. Finally, we illustrate the results on a network interdiction game between an informed system administrator and an uniformed intruder. [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]

We study distributed optimization to minimize a sum of smooth and strongly-convex functions. Recent work on this problem uses gradient tracking to achieve linear convergence to the exact global minimizer. However, a connection among different approaches has been unclear. In this paper, we first show that many of the existing first-order algorithms are related with a simple state transformation, at the heart of which lies a recently introduced algorithm known as  $\mathcal {AB}$. We then present distributed heavy-ball, denoted as  $\mathcal {AB}m$ , that combines  $\mathcal {AB}$ with a momentum term and uses nonidentical local step-sizes. By simultaneously implementing both row- and column-stochastic weights,  $\mathcal {AB}m$ removes the conservatism in the related work due to doubly stochastic weights or eigenvector estimation.  $\mathcal {AB}m$ thus naturally leads to optimization and average consensus over both undirected and directed graphs. We show that  $\mathcal {AB}m$ has a global $R$ -linear rate when the largest step-size and momentum parameter are positive and sufficiently small. We numerically show that  $\mathcal {AB}m$ achieves acceleration, particularly when the objective functions are ill-conditioned. [ABSTRACT FROM AUTHOR]

This paper proposes a novel exact asynchronous subgradient-push algorithm (AsySPA) to solve an additive cost optimization problem over digraphs where each node only has access to a local convex function and updates asynchronously with an arbitrary rate. Specifically, each node of a strongly connected digraph does not wait for updates from other nodes but simply starts a new update within any bounded time interval by using local information available from its in-neighbors. “Exact” means that every node of the AsySPA can asymptotically converge to the same optimal solution, even under different update rates among nodes and bounded communication delays. To address uneven update rates, we design a simple mechanism to adaptively adjust stepsizes per update in each node, which is substantially different from the existing works. Then, we construct a delay-free augmented system to address asynchrony and delays, and study its convergence by proposing a generalized subgradient algorithm, which clearly has its own significance and helps us to explicitly evaluate the convergence rate of the AsySPA. Finally, we demonstrate advantages of the AsySPA in both theory and simulation. [ABSTRACT FROM AUTHOR]

This paper investigates distributed control and incentive mechanisms to coordinate distributed energy resources (DERs) with both continuous and discrete decision variables as well as device dynamics in distribution grids. We formulate a multiperiod social welfare maximization problem, and based on its convex relaxation propose a distributed stochastic dual gradient algorithm for managing DERs. We further extend it to an online real-time setting with time-varying operating conditions, asynchronous updates by devices, and feedback being leveraged to account for nonlinear power flows as well as reduce communication overhead. The resulting algorithm provides a general online stochastic optimization algorithm for coordinating networked DERs with discrete power setpoints and dynamics to meet operational and economic objectives and constraints. We characterize the convergence of the algorithm analytically and evaluate its performance numerically. [ABSTRACT FROM AUTHOR]

This paper presents a novel method to compute the distance to instability for linear time-invariant delay systems with multiple delays, subjected to combined uncertainties on the system matrices and the delay parameters. The method is able to fully exploit structure and possible interdependencies between the uncertainties affecting the coefficient matrices, the property that realistic perturbations are real valued, and the structure of the delay equation. The resulting algorithm relies on a characterization in terms of the pseudospectral abscissa and on techniques from optimization over manifolds of matrices. [ABSTRACT FROM AUTHOR]

This paper deals with a new approach to develop an envelope that engulfs all poles of a time-delay system. Through linear matrix inequalities, we are able to determine envelopes for retarded and neutral time-delay systems. The envelopes proposed are not only tighter than the ones in the literature, but, with our procedure, they can also be applied to verify the stability of the system and design state-feedback controllers, which cope with design requirements regarding $\alpha$ -stability. [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]

This paper considers an unconstrained collaborative optimization of a sum of convex functions, where agents make decisions using local information in the presence of random interconnection topologies. We recast the problem as minimization of the sum of convex functions over a constraint set defined as the set of fixed-value points of a random operator derived from weighted matrices of random graphs. We show that the derived random operator has nonexpansivity property; therefore, this formulation does not need the distribution of random communication topologies. Hence, it includes random networks with/without asynchronous protocols. As an extension of the problem, we define a novel optimization problem, namely minimization of a convex function over the fixed-value point set of a nonexpansive random operator. We propose a discrete-time algorithm using diminishing step size for converging almost surely and in mean square to the global solution of the optimization problem under suitable assumptions. Consequently, as a special case, it reduces to a totally asynchronous algorithm for the distributed optimization problem. We show that fixed-value point is a bridge from deterministic analysis to random analysis of the algorithm. Finally, a numerical example illustrates the convergence of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of achieving average consensus over a random time-varying sequence of directed graphs by extending the class of so-called push-sum algorithms to such random scenarios. Provided that an ergodicity notion, which we term the directed infinite flow property, holds and the auxiliary states of agents are uniformly bounded away from zero infinitely often, we prove the almost sure convergence of the evolutions of this class of algorithms to the average of initial states. Moreover, for a random sequence of graphs generated using a so-called time-varying $B$ -irreducible probability matrix, we establish convergence rates for the proposed push-sum algorithm. [ABSTRACT FROM AUTHOR]

This paper investigates the problem of minimizing the global energy cost for multiagent systems to achieve consensus over undirected network topologies. Conventional optimization problems so defined require all-to-all network topologies for interagent communications, which precludes the use of distributed control or otherwise demands that the network be complete. To circumvent this difficulty, we introduce a network approximation (NA) scheme in the optimization criterion, which tends to render the optimization problem to one seemingly over a complete graph network, thus removing the all-to-all communication requirement. With the NA cost, we show that a distributed optimal consensus algorithm always exists for any given connected network topology, which can be determined by solving a single-agent-level parametric algebraic Ricatti equation (PARE). We also investigate the performance of the optimal consensus algorithm, focusing on the minimal energy cost required to achieve consensus optimally, and the speed at which consensus is achieved. Furthermore, for certain more special yet worthy cases, such as single-integrator, double-integrator, and first-order unstable agents, we derive explicit expressions for the energy cost and the consensus speed. It can be seen from these results that the energy cost can be made arbitrarily small for single-integrator and double-integrator systems under the optimal distributed control. On the other hand, for the first-order unstable agents, the energy cost increases and consensus speed decreases monotonically with the value of the agent's real unstable pole. [ABSTRACT FROM AUTHOR]

This paper concerns a spectral estimation problem in which we want to find a spectral density function that is consistent with estimated second-order statistics. It is an inverse problem admitting multiple solutions, and selection of a solution can be based on prior functions. We show that the problem is well-posed when formulated in a parametric fashion, and that the solution parameter depends continuously on the prior function. In this way, we are able to obtain a smooth parametrization of admissible spectral densities. Based on this result, the problem is reparametrized via a bijective change of variables out of a numerical consideration, and then a continuation method is used to compute the unique solution parameter. Numerical aspects, such as convergence of the proposed algorithm and certain computational procedures are addressed. A simple example is provided to show the effectiveness of the algorithm. [ABSTRACT FROM AUTHOR]

As autonomous vehicle technology advances rapidly, the design and operation of networks composed of fully autonomous vehicles have attracted immense interest. It is widely anticipated that fully autonomous vehicle networks will drastically improve performance. In this paper, we consider a widely studied problem, in which autonomous vehicles arriving at an intersection adjust their speeds to traverse the intersection as rapidly as possible, while avoiding collisions. We propose a coordination control algorithm, assuming stochastic models for the arrival times of the vehicles. The proposed algorithm extends the widely studied polling systems analysis to the case involving customers subject to second-order differential constraints. We provide provable guarantees on 1) safety, no collisions occur surely, and 2) performance, rigorous bounds on the expected delay. We also provide a stability analysis for the resulting queueing system. We demonstrate the algorithm in an extensive simulation study, providing one to two orders of magnitude improvement in delays over the traditional traffic light. [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]

This paper is concerned with the robust event-triggered model predictive control (MPC) of discrete-time constrained linear systems subject to bounded additive disturbances. We make use of the interpolation technique to construct a feedback policy and tighten the original system constraint accordingly to fulfill robust constraint satisfaction. A dynamic event trigger that allows the controller to solve the optimization problem only at triggering time instants is developed, where the triggering threshold is related to the interpolating coefficient of the feedback policy and determined via optimization. We show that the proposed algorithm is recursively feasible and the closed-loop system is input-to-state stable in the attraction region. Finally, a numerical example is provided to verify the theoretical results. [ABSTRACT FROM AUTHOR]

The explicit reference governor (ERG) is a simple and systematic approach that provides constraint handling capabilities to prestabilized systems. The basic idea behind this approach is to translate state and input constraints into an upper-bound on the value of the Lyapunov function, which is then enforced by suitably manipulating the derivative of the applied reference. When designing the ERG, one of the main challenges is the determination of an upper-bound on the value of the Lyapunov function that ensures constraints satisfaction. This paper proposes a systematic approach for estimating online the optimal upper-bound for systems subject to the intersection of concave constraints. To do this, the Barrier function method is used. The effect of the estimation error caused by the time-varying nature of the auxiliary reference on the constraint satisfaction capability of the ERG is studied analytically. A procedure is proposed to modify the estimated upper-bound to avoid constraints violation in the presence of estimation errors. The effectiveness of the proposed scheme is demonstrated through a simulation study on an overhead gantry crane system. [ABSTRACT FROM AUTHOR]

This paper is devoted to distributed continuous-time and discrete-time optimization problems with nonuniform convex constraint sets and nonuniform stepsizes for general differentiable convex objective functions. The communication graphs are not required to be strongly connected at any time, the gradients of the local objective functions are not required to be bounded when their independent variables tend to infinity, and the constraint sets are not required to be bounded. For continuous-time multiagent systems, a distributed continuous algorithm is first introduced where the stepsizes and the convex constraint sets are both nonuniform. It is shown that all agents reach a consensus while minimizing the team objective function even when the constraint sets are unbounded. After that, the obtained results are extended to discrete-time multiagent systems and then the case where each agent remains in a corresponding convex constraint set is studied. To ensure all agents to remain in a bounded region, a switching mechanism is introduced in the algorithms. It is shown that the distributed optimization problems can be solved, even though the discretization of the algorithms might deviate the convergence of the agents from the minimum of the objective functions. [ABSTRACT FROM AUTHOR]

This paper is concerned with model predictive control (MPC) for multi-loop networked control systems over shared bandwidth-limited communication networks. The plants are described by linear discrete-time systems with additive disturbances and input constraints. At each time instant, only a limited number of loops can communicate over the networks, and the scheduling sequence is determined by a network manager. Algorithms are proposed for co-designing the MPC and the scheduling protocol to stabilize all loops with conflict-free transmissions. We give conditions to ensure recursive feasibility of the optimization problems and the stability of all loops. Finally, two numerical examples show that the algorithms work well. [ABSTRACT FROM AUTHOR]

Internal model control (IMC), which explicitly incorporates a plant model and a plant inverse model as its components, has an intuitive control structure and simple tuning procedure. Within the IMC structure, we propose composite adaptive IMC (CAIMC) which simultaneously identifies the plant and the plant inverse to minimize modeling errors and further reduce the tracking error. In this paper, the design procedure of CAIMC is generalized to an $n$ -th-order SISO plant. The main challenge in the generalization is to find an identification algorithm for an $n$ -th order system that satisfies the stability constraint, while assuring closed-loop stability. In the literature, stability-constrained identification has been formulated as a convex programming problem by re-parameterizing the constraint as a linear matrix inequality, but boundedness and continuity of the estimated parameters, which are critical for closed-loop stability of an adaptive control algorithm, are not guaranteed. We propose a modified stability-constrained identification method with established boundedness and continuity properties. Closed-loop stability and asymptotic performance of CAIMC are then established under proper conditions. The effectiveness of the proposed algorithm is demonstrated with an example. [ABSTRACT FROM AUTHOR]

This paper investigates reverse auctions that involve continuous values of different types of goods, general nonconvex constraints, and second stage costs. We seek to design the payment rules and conditions under which coalitions of participants cannot influence the auction outcome in order to obtain higher collective utility. Under the incentive compatible Vickrey–Clarke–Groves mechanism, we show that coalition-proof outcomes are achieved if the submitted bids are convex and the constraint sets are of a polymatroid-type. These conditions, however, do not capture the complexity of the general class of reverse auctions under consideration. By relaxing the property of incentive compatibility, we investigate further payment rules that are coalition-proof without any extra conditions on the submitted bids and the constraint sets. Our results are verified with several case studies based on electricity market data. [ABSTRACT FROM AUTHOR]

This paper studies analysis and synthesis problems for diffusively coupled multi-agent systems. We focus on networks comprised of multi-input multi-output nonlinear systems that possess a property we term maximal equilibrium-independent cyclically monotone passivity (MEICMP), which is an extension of recent passivity results. We demonstrate that networks comprised of MEICMP systems are related to a pair of dual network optimization problems. In particular, we show that the steady-state behavior of the multi-agent system correspond to the minimizers of appropriately defined network optimization problems. This optimization perspective leads to a synthesis procedure for designing the network controllers to achieve a desired output. We provide detailed examples of networked systems satisfying these properties and demonstrate the results for a network of damped planar oscillators. [ABSTRACT FROM AUTHOR]

This paper aims to reduce the communication and computation costs of the Nash equilibrium seeking strategy for the $N$ -coalition noncooperative games. The objective is achieved by the following two manners: 1) an interference graph is introduced to describe the interactions among the agents in each coalition and 2) the Nash equilibrium seeking strategy is designed with the interference graphs considered. The convergence property of the proposed Nash equilibrium seeking strategy is analytically investigated. It is shown that the agents’ actions generated by the proposed method converge to a neighborhood of the Nash equilibrium of the graphical $N$ -coalition noncooperative games under certain conditions. Several special cases where there is only one coalition and/or there are coalitions with only one agent are considered. The results for the special cases demonstrate that the proposed seeking strategy achieves the solution seeking for noncooperative games, social cost minimization problems, and single-agent optimization problems in a unified framework. Numerical examples are presented to support the theoretical results. [ABSTRACT FROM AUTHOR]

Average consensus underpins key functionalities of distributed systems ranging from distributed information fusion, decision-making, distributed optimization, to load balancing and decentralized control. Existing distributed average consensus algorithms require each node to exchange and disclose state information to its neighbors, which is undesirable in cases where the state is private or contains sensitive information. In this paper, we propose a novel approach that avoids disclosing individual state information in average consensus by letting each node decompose its state into 2 substates. For each node, one of the two substates involves in computation and internode interactions as if it were the original state, while the other substate interacts only with the first substate of the same node, being completely invisible to other nodes. The initial values of the two substates are chosen randomly but with their mean fixed to the initial value of the original state, which is key to guarantee convergence to the desired consensus value. In direct contrast to differential-privacy based privacy-preserving average-consensus approaches, which enable privacy by compromising accuracy in the consensus value, the proposed approach can guarantee convergence to the exact desired value without any error. Not only is the proposed approach able to prevent the disclosure of a node's initial state to honest-but-curious neighbors, it can also provide protection against inference by external eavesdroppers able to wiretap communication links. Numerical simulations demonstrate the effectiveness of the approach and its advantages over state-of-the-art counterparts. [ABSTRACT FROM AUTHOR]

This paper considers the set membership fusion estimation problem for the general multisensor dynamic systems with unknown but bounded noises. In order to achieve the ellipsoidal fusion formulae, we divide the set membership filter problem into two steps: the prediction step and the fusion update step. The proposed method has the following nice properties. First, each step can be converted into a semidefinite programming problem, which can be efficiently computed. Second, part-analytical formulae of the shape matrix and the center of the bounding ellipsoid can be derived by using a decoupled technique, which can significantly reduce the computational complexity. Moreover, the relationship between the fusion center and local sensors can be clearly revealed based on the ellipsoidal fusion formula. Finally, it is interesting that the ellipsoidal fusion formula is similar in form to the classic mean-squared error filter fusion, although they are of the different optimization frameworks. However, the fusion weights of the information matrix provided by the different sensors are different and the optimal fusion weights can be calculated by solving a convex optimization problem. A typical numerical example in target tracking demonstrates the effectiveness of the proposed centralized and distributed fusion formula. [ABSTRACT FROM AUTHOR]

This paper focuses on a distributed convex optimization problem with set constraints, where the local objective functions are convex but not necessarily differentiable. We employ an exact penalty method for the constrained optimization problem to avoid the projection of subgradients to convex sets, which may result in problems about algorithm trajectories caused by maybe nonconvex differential inclusions and quite high computational cost. To effectively find a suitable gain of the penalty function online, we propose an adaptive distributed algorithm with the help of the adaptive control idea in order to achieve an exact solution without any a priori computation or knowledge of the objective functions. By virtue of convex and nonsmooth analysis, we give a rigorous proof for the convergence of the proposed continuous-time algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new framework for model-predictive control (MPC) with generalized zone tracking. The proposed zone MPC tracks a generalized target set of system state and input which is not necessarily control-invariant. In this context, the classical MPC theory no longer applies because the target zone may not be stable in the sense of Lyapunov. We extend LaSalle's invariance principle and develop new theories for stability analysis of zone MPC. It is proved that under the zone MPC design, the system converges to the maximal control invariant set in the target zone. Sufficient conditions for asymptotic stability of the maximal control-invariant set are also discussed. By tracking the generalized target zone, the proposed zone MPC is able to: (i) yield smaller zone tracking errors than all existing methods which essentially track some steady-state subset of the target zone, and (ii) allow more admissible operations and release more degrees of freedom to achieve other economic objectives. Further discussions are made on extending the prediction horizon of the zone MPC based on an auxiliary control law as well as handling a secondary economic objective via a second-step economic optimization. [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]