Search

Mixed-integer optimisation problems can be computationally challenging. Here, we introduce and analyse two efficient algorithms with a specific sequential design that are aimed at dealing with sampled problems within this class. At each iteration step of both algorithms, we first test the feasibility of a given test solution for each and every constraint associated with the sampled optimisation at hand, while also identifying those constraints that are violated. Subsequently, an optimisation problem is constructed with a constraint set consisting of the current basis -- namely, the smallest set of constraints that fully specifies the current test solution -- as well as constraints related to a limited number of the identified violating samples. We show that both algorithms exhibit finite-time convergence towards the optimal solution. Algorithm 2 features a neural network classifier that notably improves the computational performance compared to Algorithm 1. We quantitatively establish these algorithms' efficacy through three numerical tests: robust optimal power flow, robust unit commitment, and robust random mixed-integer linear program.

In this paper, a novel control strategy namely disturbance observer-based control is first applied to stabilization and disturbance rejection for an anti-stable stochastic heat equation with Neumann boundary actuation and unknown boundary external disturbance generated by an exogenous system. A disturbance observer-based boundary control is designed based on the backstepping approach and estimation/cancellation strategy, where the unknown disturbance is estimated in real time by a disturbance observer and rejected in the closed-loop, while the in-domain multiplicative noise whose intensity is within a known finite interval is attenuated. It is shown that the resulting closed-loop system is exponentially stable in the sense of both mean square and almost surely. A numerical example is demonstrated to validate the effectiveness of the proposed control approach.

We illustrate the potential of PDE-based traffic flow control in cardiovascular flow analysis, monitoring, and control, presenting a PDE-based control-oriented formulation, for 1-D blood flow dynamics in the presence of stenosis. This is achieved adopting an approach for modeling and analysis that relies on the potential correspondence of 1-D blood flow dynamics in the presence of stenosis, with 1-D traffic flow dynamics in the presence of bottleneck. We reveal such correspondence in relation to the respective (for the two flow types), speed dynamics and a (consistent with them) fundamental diagram-based reduction; bottleneck dynamic effects description and resulting boundary conditions; and free-flow/congested regimes characterization., Comment: Submitted to IEEE Transactions on Automatic Control on October 22, 2021

Linear models with additive unknown-but-bounded input disturbances are extensively used to model uncertainty in robust control systems design. Typically, the disturbance set is either assumed to be known a priori or estimated from data through set-membership identification. However, the problem of computing a suitable input disturbance set in case the set of possible output values is assigned a priori has received relatively little attention. This problem arises in many contexts, such as in supervisory control, actuator design, decentralized control, and others. In this paper, we propose a method to compute input disturbance sets (and the corresponding set of states) such that the resulting set of outputs matches as closely as possible a given set of outputs, while additionally satisfying strict (inner or outer) inclusion constraints. We formulate the problem as an optimization problem by relying on the concept of robust invariance. The effectiveness of the approach is demonstrated in numerical examples that illustrate how to solve safe reference set and input-constraint set computation problems.

In this paper, we address the efficient implementation of moving horizon state estimation of constrained discrete-time linear systems. We propose a novel iteration scheme which employs a proximity-based formulation of the underlying optimization algorithm and reduces computational effort by performing only a limited number of optimization iterations each time a new measurement is received. We outline conditions under which global exponential stability of the underlying estimation errors is ensured. Performance guarantees of the iteration scheme in terms of regret upper bounds are also established. A combined result shows that both exponential stability and a sublinear regret which can be rendered smaller by increasing the number of optimization iterations can be guaranteed. The stability and regret results of the proposed estimator are showcased through numerical simulations.

The rate-regulation tradeoff, defined between two objective functions, one penalizing the packet rate and one the regulation cost, can express the fundamental performance bound of networked control systems. However, the characterization of the set of globally optimal solutions in this tradeoff for multi-dimensional Gauss-Markov processes has been an open problem. In the present article, we characterize a policy profile that belongs to this set without imposing any restrictions on the information structure or the policy structure. We prove that such a policy profile consists of a symmetric threshold triggering policy based on the value of information and a certainty-equivalent control policy based on a non-Gaussian linear estimator. These policies are deterministic and can be designed separately. Besides, we provide a global optimality analysis for the value of information $\text{VoI}_k$, a semantic metric that emerges from the rate-regulation tradeoff as the difference between the benefit and the cost of a data packet. We prove that it is globally optimal that a data packet containing sensory information at time $k$ be transmitted to the controller only if $\text{VoI}_k$ becomes nonnegative. These results have important implications in the areas of communication and control., Comment: arXiv admin note: text overlap with arXiv:1812.07534

While noise is generally associated with uncertainties and often has a negative connotation in engineering, living organisms have evolved to adapt to (and even exploit) such uncertainty to ensure the survival of a species or implement certain functions that would have been difficult or even impossible otherwise. In this article, we review the role and impact of noise in systems and synthetic biology, with a particular emphasis on its role in the genetic control of biological systems, an area we refer to as Cybergenetics. The main modeling paradigm is that of stochastic reaction networks, whose applicability goes beyond biology, as these networks can represent any population dynamics system, including ecological, epidemiological, and opinion dynamics networks. We review different ways to mathematically represent these systems, and we notably argue that the concept of ergodicity presents a particularly suitable way to characterize their stability. We then discuss noise-induced properties and show that noise can be both an asset and a nuisance in this setting. Finally, we discuss recent results on (stochastic) Cybergenetics and explore their relationships to noise. Along the way, we detail the different technical and biological constraints that need to be respected when designing synthetic biological circuits. Finally, we discuss the concepts, problems, and solutions exposed in the article; raise criticisms and concerns about current ideas and approaches; suggest current (open) problems with potential solutions; and provide some ideas for future research directions., 36 pages; 6 Figures

A dual adaptive model predictive control (MPC) algorithm is presented for linear, time-invariant systems subject to bounded disturbances and parametric uncertainty in the state-space matrices. Online set-membership identification is performed to reduce the uncertainty and thus control affects both the informativity of identification and the system’s performance. The main contribution of the paper is to include this dual effect in the MPC optimization problem using a predicted worst-case cost in the objective function. This allows the controller to perform active exploration, that is, the control input reduces the uncertainty in the regions of the parameter space that have most influence on the performance. Additionally, the MPC algorithm ensures robust constraint satisfaction of state and input constraints. Advantages of the proposed algorithm are shown by comparing it to a passive adaptive MPC algorithm from the literature., IEEE Transactions on Automatic Control, 68 (5), ISSN:0018-9286, ISSN:1558-2523

In the past few years, Online Convex Optimization (OCO) has received notable attention in the control literature thanks to its flexible real-time nature and powerful performance guarantees. In this paper, we propose new step-size rules and OCO algorithms that simultaneously exploit gradient predictions, function predictions and dynamics, features particularly pertinent to control applications. The proposed algorithms enjoy static and dynamic regret bounds in terms of the dynamics of the reference action sequence, gradient prediction error, and function prediction error, which are generalizations of known regularity measures from the literature. We present results for both convex and strongly convex costs. We validate the performance of the proposed algorithms in a trajectory tracking case study, as well as portfolio optimization using real-world datasets.

This paper considers the distributed online convex optimization problem with time-varying constraints over a network of agents. This is a sequential decision making problem with two sequences of arbitrarily varying convex loss and constraint functions. At each round, each agent selects a decision from the decision set, and then only a portion of the loss function and a coordinate block of the constraint function at this round are privately revealed to this agent. The goal of the network is to minimize the network-wide loss accumulated over time. Two distributed online algorithms with full-information and bandit feedback are proposed. Both dynamic and static network regret bounds are analyzed for the proposed algorithms, and network cumulative constraint violation is used to measure constraint violation, which excludes the situation that strictly feasible constraints can compensate the effects of violated constraints. In particular, we show that the proposed algorithms achieve $\mathcal{O}(T^{\max\{\kappa,1-\kappa\}})$ static network regret and $\mathcal{O}(T^{1-\kappa/2})$ network cumulative constraint violation, where $T$ is the time horizon and $\kappa\in(0,1)$ is a user-defined trade-off parameter. Moreover, if the loss functions are strongly convex, then the static network regret bound can be reduced to $\mathcal{O}(T^{\kappa})$. Finally, numerical simulations are provided to illustrate the effectiveness of the theoretical results.

Mirror descent (MD) is a powerful first-order optimization technique that subsumes several optimization algorithms including gradient descent (GD). In this work, we develop a semi-definite programming (SDP) framework to analyze the convergence rate of MD in centralized and distributed settings under both strongly convex and non-strongly convex assumptions. We view MD with a dynamical system lens and leverage quadratic constraints (QCs) to provide explicit convergence rates based on Lyapunov stability. For centralized MD under strongly convex assumption, we develop a SDP that certifies exponential convergence rates. We prove that the SDP always has a feasible solution that recovers the optimal GD rate as a special case. We complement our analysis by providing the $O(1/k)$ convergence rate for convex problems. Next, we analyze the convergence of distributed MD and characterize the rate using SDP. To the best of our knowledge, the numerical rate of distributed MD has not been previously reported in the literature. We further prove an $O(1/k)$ convergence rate for distributed MD in the convex setting. Our numerical experiments on strongly convex problems indicate that our framework certifies superior convergence rates compared to the existing rates for distributed GD.

Determining the reachable set for a given nonlinear control system is crucial for system control and planning. However, computing such a set is impossible if the system's dynamics are not fully known. This paper is motivated by a scenario where a system suffers an adverse event mid-operation, resulting in a substantial change to the system's dynamics, rendering them largely unknown. Our objective is to conservatively approximate the system's reachable set solely from its local dynamics at a single point and the bounds on the rate of change of its dynamics. We translate this knowledge about the system dynamics into an ordinary differential inclusion. We then derive a conservative approximation of the velocities available to the system at every system state. An inclusion using this approximation can be interpreted as a control system; the trajectories of the derived control system are guaranteed to be trajectories of the unknown system. To illustrate the practical implementation and consequences of our work, we apply our algorithm to a simplified model of an unmanned aerial vehicle.

We develop a probabilistic control algorithm, $\texttt{GTLProCo}$, for swarms of agents with heterogeneous dynamics and objectives, subject to high-level task specifications. The resulting algorithm not only achieves decentralized control of the swarm but also significantly improves scalability over state-of-the-art existing algorithms. Specifically, we study a setting in which the agents move along the nodes of a graph, and the high-level task specifications for the swarm are expressed in a recently-proposed language called graph temporal logic (GTL). By constraining the distribution of the swarm over the nodes of the graph, GTL can specify a wide range of properties, including safety, progress, and response. $\texttt{GTLProCo}$, agnostic to the number of agents comprising the swarm, controls the density distribution of the swarm in a decentralized and probabilistic manner. To this end, it synthesizes a time-varying Markov chain modeling the time evolution of the density distribution under the GTL constraints. We first identify a subset of GTL, namely reach-avoid specifications, for which we can reduce the synthesis of such a Markov chain to either linear or semi-definite programs. Then, in the general case, we formulate the synthesis of the Markov chain as a mixed-integer nonlinear program (MINLP). We exploit the structure of the problem to provide an efficient sequential mixed-integer linear programming scheme with trust regions to solve the MINLP. We empirically demonstrate that our sequential scheme is at least three orders of magnitude faster than off-the-shelf MINLP solvers and illustrate the effectiveness of $\texttt{GTLProCo}$ in several swarm scenarios., Comment: Initial submission to TAC

This work contributes to the field of optimal control of bilinear systems. It concerns a continuous time, finite dimensional, bilinear state equation with a quadratic performance index to be minimized. The state equation is non-autonomous and comprises a deterministic, a-priori known excitation. The control trajectory is constrained to an admissible set without a specific structure. The performance index is a functional, quadratic in the state variables and control signals. Krotov's method is used for solving this problem by means of an improving sequence. To this end, the required sequence of an improving functions is formulated. Finally, the solution is encapsulated in an algorithm form and a numerical example of structural control problem is provided., \copyright 2022 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works

In this work, we study decentralized convex constrained optimization problems in networks. We focus on the dual averaging-based algorithmic framework that is well-documented to be superior in handling constraints and complex communication environments simultaneously. Two new decentralized dual averaging (DDA) algorithms are proposed. In the first one, a second-order dynamic average consensus protocol is tailored for DDA-type algorithms, which equips each agent with a provably more accurate estimate of the global dual variable than conventional schemes. We rigorously prove that the proposed algorithm attains $\mathcal{O}(1/t)$ convergence for general convex and smooth problems, for which existing DDA methods were only known to converge at $\mathcal{O}(1/\sqrt{t})$ prior to our work. In the second one, we use the extrapolation technique to accelerate the convergence of DDA. Compared to existing accelerated algorithms, where typically two different variables are exchanged among agents at each time, the proposed algorithm only seeks consensus on local gradients. Then, the extrapolation is performed based on two sequences of primal variables which are determined by the accumulations of gradients at two consecutive time instants, respectively. The algorithm is proved to converge at $\mathcal{O}(1)\left(\frac{1}{t^2}+\frac{1}{t(1-\beta)^2}\right)$, where $\beta$ denotes the second largest singular value of the mixing matrix. We remark that the condition for the algorithmic parameter to guarantee convergence does not rely on the spectrum of the mixing matrix, making itself easy to satisfy in practice. Finally, numerical results are presented to demonstrate the efficiency of the proposed methods., Comment: 15 pages, 4 figures

Distributed linear algebraic equation over networks, where nodes hold a part of problem data and cooperatively solve the equation via node-to-node communications, is a basic distributed computation task receiving an increasing research attention. Communications over a network have a stochastic nature, with both temporal and spatial dependence due to link failures, packet dropouts or node recreation, etc. In this paper, we study the convergence and convergence rate of distributed linear equation protocols over a $\ast$-mixing random network, where the temporal and spatial dependencies between the node-to-node communications are allowed. When the network linear equation admits exact solutions, we prove the mean-squared exponential convergence rate of the distributed projection consensus algorithm, while the lower and upper bound estimations of the convergence rate are also given for independent and identically distributed (i.i.d.) random graphs. Motivated by the randomized Kaczmarz algorithm, we also propose a distributed randomized projection consensus algorithm, where each node randomly selects one row of local linear equations for projection per iteration, and establish an exponential convergence rate. When the network linear equation admits no exact solution, we prove that a distributed gradient-descent-like algorithm with diminishing step-sizes can drive all nodes' states to a least-squares solution at a sublinear rate. These results collectively illustrate that distributed computations may overcome communication correlations if the prototype algorithms enjoy certain contractive properties or are designed with suitable parameters., 17 pages

This paper studies the adaptive optimal stationary control of continuous-time linear stochastic systems with both additive and multiplicative noises, using reinforcement learning techniques. Based on policy iteration, a novel off-policy reinforcement learning algorithm, named optimistic least-squares-based policy iteration, is proposed which is able to find iteratively near-optimal policies of the adaptive optimal stationary control problem directly from input/state data without explicitly identifying any system matrices, starting from an initial admissible control policy. The solutions given by the proposed optimistic least-squares-based policy iteration are proved to converge to a small neighborhood of the optimal solution with probability one, under mild conditions. The application of the proposed algorithm to a triple inverted pendulum example validates its feasibility and effectiveness., Comment: 10 pages, 3 figures

We present a parallelized primal-dual algorithm for solving constrained convex optimization problems. The algorithm is "block-based," in that vectors of primal and dual variables are partitioned into blocks, each of which is updated only by a single processor. We consider four possible forms of asynchrony: in updates to primal variables, updates to dual variables, communications of primal variables, and communications of dual variables. We construct a family of explicit counterexamples to show the need to eliminate asynchronous communication of dual variables, though the other forms of asynchrony are permitted, all without requiring bounds on delays. A first-order primal-dual update law is developed and shown to be robust to asynchrony. We then derive convergence rates to a Lagrangian saddle point in terms of the operations agents execute, without specifying any timing or pattern with which they must be executed. These convergence rates include an "asynchrony penalty" that we quantify and present ways to mitigate. Numerical results illustrate these developments., Comment: arXiv admin note: text overlap with arXiv:2004.05142

We present a Model Predictive Control (MPC) algorithm for energy management in aircraft with hybrid electric propulsion systems consisting of gas turbine and electric motor components. Series and parallel configurations are considered. By combining a point-mass aircraft dynamical model with models of electrical losses and losses in the gas turbine, the fuel consumed over a given future flight path is minimised subject to constraints on the battery, electric motor and gas turbine. The optimization is formulated as a convex problem under mild assumptions and its solution is used to define a predictive energy management control law that takes into account the variation in aircraft mass during flight. We investigate the performance of algorithms for solving this problem. An Alternating Direction Method of Multipliers (ADMM) algorithm is proposed and compared with a general purpose convex interior point solver. We also show that the ADMM implementation reduces the required computation time by orders of magnitude in comparison with a general purpose nonlinear programming solver, making it suitable for real-time supervisory energy management control., Comment: arXiv admin note: text overlap with arXiv:2004.02582

In this paper, we study accelerating a Laplacian-based dynamic average consensus algorithm by splitting the conventional delay-free disagreement feedback into weighted summation of a current and an outdated term. We determine for what weighted sum there exists a range of time delay that results in the higher rate of convergence for the algorithm. For such weights, using the Lambert W function, we obtain the rate increasing range of the time delay, the maximum reachable rate and comment on the value of the corresponding maximizer delay. We also study the effect of use of outdated feedback on the control effort of the agents and show that only for some specific affine combination of the immediate and outdated feedback the control effort of the agents does not go beyond that of the delay-free algorithm. Additionally, we demonstrate that using outdated feedback does not increase the steady state tracking error of the average consensus algorithm. Lastly, we determine the optimum combination of the current and the outdated feedback weights to achieve the maximum increase in the rate of convergence without increasing the control effort of the agents. We demonstrate our results through a numerical example.

Existing frameworks for transfer learning are incomplete from a systems theoretic perspective. They place emphasis on notions of domain and task, and neglect notions of structure and behavior. In doing so, they limit the extent to which formalism can be carried through into the elaboration of their frameworks. Herein, we use Mesarovician systems theory to define transfer learning as a relation on sets and subsequently characterize the general nature of transfer learning as a mathematical construct. We interpret existing frameworks in terms of ours and go beyond existing frameworks to define notions of transferability, transfer roughness, and transfer distance. Importantly, despite its formalism, our framework avoids the detailed mathematics of learning theory or machine learning solution methods without excluding their consideration. As such, we provide a formal, general systems framework for modeling transfer learning that offers a rigorous foundation for system design and analysis.

This paper considers distributed stochastic optimization, in which a number of agents cooperate to optimize a global objective function through local computations and information exchanges with neighbors over a network. Stochastic optimization problems are usually tackled by variants of projected stochastic gradient descent. However, projecting a point onto a feasible set is often expensive. The Frank-Wolfe (FW) method has well-documented merits in handling convex constraints, but existing stochastic FW algorithms are basically developed for centralized settings. In this context, the present work puts forth a distributed stochastic Frank-Wolfe solver, by judiciously combining Nesterov's momentum and gradient tracking techniques for stochastic convex and nonconvex optimization over networks. It is shown that the convergence rate of the proposed algorithm is $\mathcal{O}(k^{-\frac{1}{2}})$ for convex optimization, and $\mathcal{O}(1/\mathrm{log}_2(k))$ for nonconvex optimization. The efficacy of the algorithm is demonstrated by numerical simulations against a number of competing alternatives., Comment: 15 pages, 11 figures, 2 tables

Motivated by various distributed control applications, we consider a linear system with Gaussian noise observed by multiple sensors which transmit measurements over a dynamic lossy network. We characterize the stationary optimal sensor scheduling policy for the finite horizon, discounted, and long-term average cost problems and show that the value iteration algorithm converges to a solution of the average cost problem. We further show that the suboptimal policies provided by the rolling horizon truncation of the value iteration also guarantee stability and provide near-optimal average cost. Lastly, we provide qualitative characterizations of the multidimensional set of measurement loss rates for which the system is stabilizable for a static network, significantly extending earlier results on intermittent observations., 25 pages

The decision making and management of many engineering networks involves multiple parties with conflicting interests, while each party is constituted with multiple agents. Such problems can be casted as a multi-cluster game. Each cluster is treated as a self-interested player in a non-cooperative game where agents in the same cluster cooperate together to optimize the payoff function of the cluster. In a large-scale network, the information of agents in a cluster can not be available immediately for agents beyond this cluster, which raise challenges to the existing Nash equilibrium seeking algorithms. Hence, we consider a partial-decision information scenario in generalized Nash equilibrium seeking for multi-cluster games in a distributed manner. We reformulate the problem as finding zeros of the sum of preconditioned monotone operators by the primal-dual analysis and graph Laplacian matrix. Then a distributed generalized Nash equilibrium seeking algorithm is proposed without requiring fully awareness of its opponent clusters' decisions based on a forward-backward-forward method. With the algorithm, each agent estimates the strategies of all the other clusters by communicating with neighbors via an undirected network. We show that the derived operators can be monotone when the communication strength parameter is sufficiently large. We prove the algorithm convergence resorting to the fixed point theory by providing a sufficient condition. We discuss its potential application in Energy Internet with numerical studies.

Robustness is a basic property of any control system. In the context of linear output regulation, it was proved that embedding an internal model of the exogenous signals is necessary and sufficient to achieve tracking of the desired reference signals in spite of external disturbances and parametric uncertainties. This result is commonly known as "internal model principle". A complete extension of such linear result to general nonlinear systems is still an open problem, which is exacerbated by the large number of alternative definitions of uncertainty and desired control goals that are possible in a nonlinear setting. In this paper, we develop a general framework in which all these different notions can be formally characterized in a unifying way. Classical results are reinterpreted in the proposed setting, and new results and insights are presented with a focus on robust rejection/tracking of arbitrary harmonic content. Moreover, we show by counter-example that, in the relevant case of continuous unstructured uncertainties, there are problems for which no smooth finite-dimensional robust regulator exists ensuring exact regulation., updated version 04.2021

Semidefinite and sum-of-squares (SOS) optimization are fundamental computational tools in many areas, including linear and nonlinear systems theory. However, the scale of problems that can be addressed reliably and efficiently is still limited. In this paper, we introduce a new notion of block factor-width-two matrices and build a new hierarchy of inner and outer approximations of the cone of positive semidefinite (PSD) matrices. This notion is a block extension of the standard factor-width-two matrices, and allows for an improved inner-approximation of the PSD cone. In the context of SOS optimization, this leads to a block extension of the scaled diagonally dominant sum-of-squares (SDSOS) polynomials. By varying a matrix partition, the notion of block factor-width-two matrices can balance a trade-off between the computation scalability and solution quality for solving semidefinite and SOS optimization problems. Numerical experiments on a range of large-scale instances confirm our theoretical findings., Accepted for publication as a regular paper at IEEE TAC. Code is available through https://github.com/zhengy09/SDPfw

The persistence of excitation (PE) condition is sufficient to ensure parameter convergence in adaptive estimation problems. Recent results on adaptive estimation in reproducing kernel Hilbert spaces (RKHS) introduce PE conditions for RKHS. This paper presents sufficient conditions for PE for the particular class of uniformly embedded reproducing kernel Hilbert spaces (RKHS) defined over smooth Riemannian manifolds. This paper also studies the implications of the sufficient condition in the case when the RKHS is finite or infinite-dimensional. When the RKHS is finite-dimensional, the sufficient condition implies parameter convergence as in the conventional analysis. On the other hand, when the RKHS is infinite-dimensional, the same condition implies that the function estimate error is ultimately bounded by a constant that depends on the approximation error in the infinite-dimensional RKHS. We illustrate the effectiveness of the sufficient condition in a practical example., Comment: 11 pages, 2 figures

Alternating Direction Method of Multipliers (ADMM) algorithm has been widely adopted for solving the distributed optimization problem (DOP). In this paper, a new distributed parallel ADMM algorithm is proposed, which allows the agents to update their local states and dual variables in a completely distributed and parallel manner by modifying the existing distributed sequential ADMM. Moreover, the updating rules and storage method for variables are illustrated. It is shown that all the agents can reach a consensus by asymptotically converging to the optimal solution. Besides, the global cost function will converge to the optimal value at a rate of O(1/k). Simulation results on a numerical example are given to show the effectiveness of the proposed algorithm.

In this paper, a necessary and sufficient condition for the controllability of networked systems with heterogeneous dynamics is established where the nodes are higher dimensional linear time invariant systems and the network topology is directed and weighted. The controllability of networked system over some specific topologies are also examined and some non-controllability results are obtained. The theoretical results are demonstrated with examples.

In this paper, we investigate the architecture of an optimal controller that maximizes the convergence speed of a consensus protocol with single-integrator dynamics. Under the assumption that communication delays increase with the number of hops from which information is allowed to reach each agent, we address the optimal control design under delayed feedback and show that the optimal controller features, in general, a sparsely connected architecture., 6 pages, 7 figures; published on IEEE Control Systems Letters

This paper presents a family of algorithms for decentralized convex composite problems. We consider the setting of a network of agents that cooperatively minimize a global objective function composed of a sum of local functions plus a regularizer. Through the use of intermediate consensus variables, we remove the need for inner communication loops between agents when computing curvature-guided updates. A general scheme is presented which unifies the analysis for a plethora of computing choices, including gradient descent, Newton updates, and BFGS updates. Our analysis establishes sublinear convergence rates under convex objective functions with Lipschitz continuous gradients, as well as linear convergence rates when the local functions are further assumed to be strongly convex. Moreover, we explicitly characterize the acceleration due to curvature information. Last but not the least, we present an asynchronous implementation for the proposed algorithms, which removes the need for a central clock, with linear convergence rates established in expectation under strongly convex objectives. We ascertain the effectiveness of the proposed methods with numerical experiments on benchmark datasets.

Urban air mobility is a concept that promotes aerial modes of transport in urban areas. In these areas, the location and capacity of the vertiports--where the travelers embark and disembark the aircraft--not only affect the flight delays of the aircraft, but can also aggravate the congestion of ground vehicles by creating extra ground travel demands. We introduce a mathematical model for selecting the location and capacity of the vertiports that minimizes the traffic congestion in hybrid air-ground transportation networks. Our model is based on a mathematical program with bilinear equilibrium constraints. Furthermore, we show how to compute a global optimal solution of this mathematical program by solving a mixed integer linear program. We demonstrate our results via the Anaheim transportation network model, which contains more than 400 nodes and 900 links.

This paper builds Wasserstein ambiguity sets for the unknown probability distribution of dynamic random variables leveraging noisy partial-state observations. The constructed ambiguity sets contain the true distribution of the data with quantifiable probability and can be exploited to formulate robust stochastic optimization problems with out-of-sample guarantees. We assume the random variable evolves in discrete time under uncertain initial conditions and dynamics, and that noisy partial measurements are available. All random elements have unknown probability distributions and we make inferences about the distribution of the state vector using several output samples from multiple realizations of the process. To this end, we leverage an observer to estimate the state of each independent realization and exploit the outcome to construct the ambiguity sets. We illustrate our results in an economic dispatch problem involving distributed energy resources over which the scheduler has no direct control.

In this paper, we introduce a fast row-stochastic decentralized algorithm, referred to as FRSD, to solve consensus optimization problems over directed communication graphs. The proposed algorithm only utilizes row-stochastic weights, leading to certain practical advantages in broadcast communication settings over those requiring column-stochastic weights. Under the assumption that each node-specific function is smooth and strongly convex, we show that the FRSD iterate sequence converges with a linear rate to the optimal consensus solution. In contrast to the existing methods for directed networks, FRSD enjoys linear convergence without employing a gradient tracking (GT) technique explicitly, rather it implements GT implicitly with the use of a novel momentum term, which leads to a significant reduction in communication and storage overhead for each node when FRSD is implemented for solving high-dimensional problems over small-to-medium scale networks. In the numerical tests, we compare FRSD with other state-of-the-art methods, which use row-stochastic and/or column-stochastic weights.

Communication has been seen as a significant bottleneck in industrial applications over large-scale networks. To alleviate the communication burden, sign-based optimization algorithms have gained popularity recently in both industrial and academic communities, which is shown to be closely related to adaptive gradient methods, such as Adam. Along this line, this paper investigates faster convergence for a variant of sign-based gradient descent, called scaled signGD, in three cases: 1) the objective function is strongly convex; 2) the objective function is nonconvex but satisfies the Polyak-Lojasiewicz (PL) inequality; 3) the gradient is stochastic, called scaled signGD in this case. For the first two cases, it can be shown that the scaled signGD converges at a linear rate. For case 3), the algorithm is shown to converge linearly to a neighborhood of the optimal value when a constant learning rate is employed, and the algorithm converges at a rate of $O(1/k)$ when using a diminishing learning rate, where $k$ is the iteration number. The results are also extended to the distributed setting by majority vote in a parameter-server framework. Finally, numerical experiments on logistic regression are performed to corroborate the theoretical findings.

A trading system is said to be {robust} if it generates a robust return regardless of market direction. To this end, a consistently positive expected trading gain is often used as a robustness metric for a trading system. In this paper, we propose a new class of trading policies called the {double linear policy} in an asset trading scenario when the transaction costs are involved. Unlike many existing papers, we first show that the desired robust positive expected gain may disappear when transaction costs are involved. Then we quantify under what conditions the desired positivity can still be preserved. In addition, we conduct heavy Monte-Carlo simulations for an underlying asset whose prices are governed by a geometric Brownian motion with jumps to validate our theory. A more realistic backtesting example involving historical data for cryptocurrency Bitcoin-USD is also studied., Submitted to for possible publication. arXiv admin note: substantial text overlap with arXiv:2202.02300

This work considered an online distributed optimization problem, with a group of agents whose local objective functions vary with time. Moreover, the value of the objective function is revealed to the corresponding agent after the decision is executed per time-step. Thus, each agent can only update the decision variable based on the revealed value and information collected from the neighbors, without the knowledge on the explicit expression of the objective function. To solve this problem, an online gradient-free distributed projected gradient descent (DPGD) algorithm is presented, where each agent locally approximates the gradient based on two point values. With some standard assumptions on the communication graph and the objective functions, we provide the bound for the dynamic regret as a function of the minimizer path length, step-size and smoothing parameter. Under appropriate selections of the step-size and smoothing parameter, we prove that the dynamic regret is sublinear with respect to the time duration $T$ if the minimizer path length also grows sublinearly. Finally, the effectiveness of the proposed algorithm is illustrated through numerical simulations.

We study the spread of a novel state in a network, in the presence of an exogenous control. The considered controlled evolutionary dynamics is a non-homogeneous Markov process that describes the evolution of the states of all nodes in the network. Through a rigorous analysis, we estimate the performance of the system by establishing upper and lower bounds on the expected time needed for the novel state to replace the original one. Such bounds are expressed in terms of the support and intensity of the control policy (specifically, the set of nodes that can be controlled and its energy) and of the network topology and establish fundamental limitations on the system's performance. Leveraging these results, we are able to classify network structures depending on the possibility to control the system using simple open-loop control policies. Finally, we propose a feedback control policy that, using little knowledge of the network topology and of the system's evolution at a macroscopic level, allows for a substantial speed up of the spreading process with respect to simple open-loop control policies. All these theoretical results are presented together with explanatory examples, for which Monte Carlo simulations corroborate our analytical findings., Comment: 15 pages; 7 Figures

This paper presents a data-learned linear Koopman embedding of nonlinear networked dynamics and uses it to enable real-time model predictive emergency voltage control in a power network. The approach involves a novel data-driven ``basis-dictionary free" lifting of the system dynamics into a higher dimensional linear space over which an MPC (model predictive control) is exercised, making it both scalable and rapid for practical real-time implementation. A Koopman-inspired deep neural network (KDNN) encoder-decoder architecture for the linear embedding of the underlying dynamics under distributed controls is presented, in which the end-to-end components of the KDNN comprising of a triple of transforms is learned from the system trajectory data in one go: A Neural Network (NN)-based lifting to a higher dimension, a linear dynamics within that higher dimension, and an NN-based projection to the original space. This data-learned approach relieves the burden of the ad-hoc selection of the nonlinear basis functions (e.g., polynomial or radial) used in conventional approaches for lifting to higher dimensional linear space. We validate the efficacy and robustness of the approach via application to the standard IEEE 39-bus system.

Many robotic tasks, such as human-robot interactions or the handling of fragile objects, require tight control and limitation of appearing forces and moments alongside sensible motion control to achieve safe yet high-performance operation. We propose a learning-supported model predictive force and motion control scheme that provides stochastic safety guarantees while adapting to changing situations. Gaussian processes are used to learn the uncertain relations that map the robot's states to the forces and moments. The model predictive controller uses these Gaussian process models to achieve precise motion and force control under stochastic constraint satisfaction. As the uncertainty only occurs in the static model parts -- the output equations -- a computationally efficient stochastic MPC formulation is used. Analysis of recursive feasibility of the optimal control problem and convergence of the closed loop system for the static uncertainty case are given. Chance constraint formulation and back-offs are constructed based on the variance of the Gaussian process to guarantee safe operation. The approach is illustrated on a lightweight robot in simulations and experiments.

A control system is called self-powered if the only energy it requires for operation is that which it absorbs from the plant. For a linear feedback law to be feasible for a self-powered control system, its feedback signal must be colocated with the control inputs, and its input-output mapping must satisfy an associated passivity constraint. The imposition of such a feedback law can be viewed equivalently as the imposition of a linear passive shunt admittance at the actuation ports of the plant. In this paper we consider the use of actively-controlled electronics to impose a self-powered linear feedback law. To be feasible, it is insufficient that the imposed admittance be passive, because parasitic losses must additionally be overcome. We derive sufficient feasibility conditions which explicitly account for these losses. In the finite-dimensional, time-invariant case, the feasibility condition distills to a more conservative version of the Positive Real Lemma, which is parametrized by various loss parameters. Three examples are given, in which this condition is used to determine the least-efficient loss parameters necessary to realize a desired feedback law.

This paper studies the problem of controlling a multi-robot system to achieve a polygon formation in a self-organized manner. Different from the typical formation control strategies where robots are steered to satisfy the predefined control variables, such as pairwise distances, relative positions and bearings, the foremost idea of this paper is to achieve polygon formations by injecting control inputs randomly to a few robots (say, vertex robots) of the group, and the rest follow the simple principles of moving towards the midpoint of their two nearest neighbors in the ring graph without any external inputs. In our problem, a fleet of robots is initially distributed in the plane. The socalled vertex robots take the responsibility of determining the geometric shape of the entire formation and its overall size, while the others move so as to minimize the differences with two direct neighbors. In the first step, each vertex robot estimates the number of robots in its associated chain. Two types of control inputs that serve for the estimation are designed using the measurements from the latest and the last two time instants respectively. In the second step, the self-organized formation control law is proposed where only vertex robots receive external information. Comparisons between the two estimation strategies are carried out in terms of the convergence speed and robustness. The effectiveness of the whole control framework is further validated in both simulation and physical experiments.

In this paper, we study the landscape of an online nonconvex optimization problem, for which the input data vary over time and the solution is a trajectory rather than a single point. To understand the complexity of finding a global solution of this problem, we introduce the notion of \textit{spurious (i.e., non-global) local trajectory} as a generalization to the notion of spurious local solution in nonconvex (time-invariant) optimization. We develop an ordinary differential equation (ODE) associated with a time-varying nonlinear dynamical system which, at limit, characterizes the spurious local solutions of the time-varying optimization problem. We prove that the absence of spurious local trajectory is closely related to the transient behavior of the developed system. In particular, we show that if the problem is time-varying, the data variation may force all of the ODE trajectories initialized at arbitrary local minima at the initial time to gradually converge to the global solution trajectory. We study the Jacobian of the dynamical system along a local minimum trajectory and show how its eigenvalues are manipulated by the natural data variation in the problem, which may consequently trigger escaping poor local minima over time.

Geometric optimal control utilizes tools from differential geometry to analyze the structure of a problem to determine the control and state trajectories to reach a desired outcome while minimizing some cost function. For a controlled mechanical system, the control usually manifests as an external force which, if conservative, can be added to the Hamiltonian. In this work, we focus on mechanical systems with controls added to the symplectic form rather than the Hamiltonian. In practice, this translates to controlling the magnetic field for an electrically charged system. We develop a basic theory deriving necessary conditions for optimality of such a system subjected to nonholonomic constraints. We consider the representative example of a magnetically charged Chaplygin Sleigh, whose resulting optimal control problem is completely integrable., Comment: 6 pages

Recent developments in communication technologies, such as 5G, together with innovative computing paradigms, such as edge computing, provide further possibilities for the implementation of real-time networked control systems. However, privacy and cyber-security concerns arise when sharing private data between sensors, agents and a third-party computing facility. In this paper, a secure version of the distributed formation control is presented, analyzed and simulated, where gradient-based formation control law is implemented in the edge, with sensor and actuator information being secured by fully homomorphic encryption method based on learning with error (FHE-LWE) combined with a proposed mixed uniform-logarithmic quantizer (MULQ). The novel quantizer is shown to be suitable for realizing secure control systems with FHE-LWE where the critical real-time information can be quantized into a prescribed bounded space of plaintext while satisfying a sector bound condition whose lower and upper-bound can be made sufficiently close to an identity. An absolute stability analysis is presented, that shows the asymptotic stability of the closed-loop secure control system.

This letter proposes a parallelizable algorithm for linear-quadratic model predictive control (MPC) problems with state and input constraints. The algorithm itself is based on a parallel MPC scheme that has originally been designed for systems with input constraints. In this context, one contribution of this letter is the construction of time-varying yet separable constraint margins ensuring recursive feasibility and asymptotic stability of sub-optimal parallel MPC in a general setting, which also includes state constraints. Moreover, it is shown how to tradeoff online run-time guarantees versus the conservatism that is introduced by the tightened state constraints. The corresponding performance of the proposed method as well as the cost of the recursive feasibility guarantees is analyzed in the context of controlling a large-scale mechatronic system. This is illustrated by numerical experiments for a large-scale control system with more than 100 states and 60 control inputs leading to run-times in the millisecond range.

This paper studies periodic event-triggered networked control for nonlinear systems, where the plants and controllers are connected by multiple independent communication channels. Several network-induced imperfections are considered simultaneously, including time-varying inter-sampling times, sensor node scheduling, and especially, large time-varying transmission delays, where the transmitted signal may arrive at the destination node after the next transmission occurs. A new hybrid system approach is provided to model the closed-loop system that contains all communication related behavior. Then, by constructing new storage functions on the system state and updating errors, the relationship between the maximum allowable sampling period (MASP) and maximum allowable delay number in sampling (MADNS) is analyzed, where the latter denotes how many inter-sampling periods can be included in one transmission delay. Moreover, to efficiently reduce unnecessary transmissions, a new dynamic event-triggered control scheme is proposed, where the event-triggering conditions are detected only at aperiodic and asynchronous sampling instants. From emulation-based method, where the controllers are initially designed by ignoring all the network-induced imperfections, sufficient conditions on the dynamic event-triggered control are given to ensure closed-loop input-to-state stability with respect to external disturbances. Moreover, according to different capacities of the communication channels, the corresponding implementation strategies of the designed dynamic event-triggered control schemes are discussed. Finally, two nonlinear examples are simulated to illustrate the feasibility and efficiency of the theoretical results., Comment: 18 pages, 6 figures, 3 tables

We propose a neural network approach that yields approximate solutions for high-dimensional optimal control problems and demonstrate its effectiveness using examples from multi-agent path finding. Our approach yields controls in a feedback form, where the policy function is given by a neural network (NN). Specifically, we fuse the Hamilton-Jacobi-Bellman (HJB) and Pontryagin Maximum Principle (PMP) approaches by parameterizing the value function with an NN. Our approach enables us to obtain approximately optimal controls in real-time without having to solve an optimization problem. Once the policy function is trained, generating a control at a given space-time location takes milliseconds; in contrast, efficient nonlinear programming methods typically perform the same task in seconds. We train the NN offline using the objective function of the control problem and penalty terms that enforce the HJB equations. Therefore, our training algorithm does not involve data generated by another algorithm. By training on a distribution of initial states, we ensure the controls' optimality on a large portion of the state-space. Our grid-free approach scales efficiently to dimensions where grids become impractical or infeasible. We apply our approach to several multi-agent collision-avoidance problems in up to 150 dimensions. Furthermore, we empirically observe that the number of parameters in our approach scales linearly with the dimension of the control problem, thereby mitigating the curse of dimensionality., 17 pages, 12 figures. This work has been submitted for possible publication. Copyright may be transferred without notice, after which this version may no longer be available

We propose a distributed Quantum State Tomography (QST) protocol, named Local Stochastic Factored Gradient Descent (Local SFGD), to learn the low-rank factor of a density matrix over a set of local machines. QST is the canonical procedure to characterize the state of a quantum system, which we formulate as a stochastic nonconvex smooth optimization problem. Physically, the estimation of a low-rank density matrix helps characterizing the amount of noise introduced by quantum computation. Theoretically, we prove the local convergence of Local SFGD for a general class of restricted strongly convex/smooth loss functions, i.e., Local SFGD converges locally to a small neighborhood of the global optimum at a linear rate with a constant step size, while it locally converges exactly at a sub-linear rate with diminishing step sizes. With a proper initialization, local convergence results imply global convergence. We validate our theoretical findings with numerical simulations of QST on the Greenberger-Horne-Zeilinger (GHZ) state.

Chlorine is a widely used disinfectant and proxy for water quality (WQ) monitoring in water distribution networks (WDN). Chlorine-based WQ regulation and control aims to maintain pathogen-free water. Chlorine residual evolution within WDN is commonly modeled using the typical single-species decay and reaction dynamics that account for network-wide, spatiotemporal chlorine concentrations only. Prior studies have proposed more advanced and accurate descriptions via multi-species dynamics. This paper presents a host of novel state-space, control-theoretic representations of multi-species water quality dynamics. These representations describe decay, reaction, and transport of chlorine and a fictitious reactive substance to reflect realistic complex scenarios in WDN. Such dynamics are simulated over space- and time-discretized grids of the transport partial differential equation and the nonlinear reaction ordinary differential equation. To that end, this paper (i) provides a full description on how to formulate a high fidelity model-driven state-space representation of the multi-species water quality dynamics and (ii) investigates the applicability and performance of different Eulerian-based schemes (Lax-Wendroff, backward Euler, and Crank- Nicolson) and Lagrangian-based schemes (method of characteristics) in contrast with EPANET and its EPANET-MSX extension. Numerical case studies reveal that the Lax-Wendroff scheme and method of characteristics outperform other schemes with reliable results under reasonable assumptions and limitations.