Search

We present the concept of a Generalized Feedback Nash Equilibrium (GFNE) in dynamic games, extending the Feedback Nash Equilibrium concept to games in which players are subject to state and input constraints. We formalize necessary and sufficient conditions for (local) GFNE solutions at the trajectory level, which enable the development of efficient numerical methods for their computation. Specifically, we propose a Newton-style method for finding game trajectories which satisfy necessary conditions for an equilibrium, which can then be checked against sufficiency conditions. We show that the evaluation of the necessary conditions in general requires computing a series of nested, implicitly-defined derivatives, which quickly becomes intractable. To this end, we introduce an approximation to the necessary conditions which is amenable to efficient evaluation, and in turn, computation of solutions. We term the solutions to the approximate necessary conditions Generalized Feedback Quasi-Nash Equilibria (GFQNE), and we introduce numerical methods for their computation. In particular, we develop a Sequential Linear-Quadratic Game approach, in which a LQ local approximation of the game is solved at each iteration. The development of this method relies on the ability to compute a GFNE to inequality- and equality-constrained LQ games, and therefore specific methods for the solution of these special cases are developed in detail. We demonstrate the effectiveness of the proposed solution approach on a dynamic game arising in an autonomous driving application.

Facet-defining inequalities of the symmetric traveling salesman problem (TSP) polytope play a prominent role in both polyhedral TSP research and state-of-the-art TSP solvers. In this paper, we introduce a new class of facet-defining inequalities, the circlet inequalities. These inequalities were first conjectured in Gutekunst and Williamson [Gutekunst SC, Williamson DP (2019) Characterizing the integrality gap of the subtour LP for the circulant traveling salesman problem. SIAM J. Discrete Math. 33(4):2452–2478] when studying the circulant TSP, and they provide a bridge between polyhedral TSP research and number-theoretic investigations of Hamiltonian cycles stemming from a conjecture from Marco Buratti in 2007. The circlet inequalities exhibit circulant symmetry by placing the same weight on all edges of a given length; our main proof exploits this symmetry to prove the validity of the circlet inequalities. We then show that the circlet inequalities are facet-defining and compute their strength following Goemans [Goemans MX (1995) Worst-case comparison of valid inequalities for the TSP. Math. Programming 69:335–349]; they achieve the same worst case strength as the similarly circulant crown inequalities of Naddef and Rinaldi [Naddef D, Rinaldi G (1992) The crown inequalities for the symmetric traveling salesman polytope. Math. Oper. Res. 17(2):308–326] but are generally stronger. Funding: This material is based upon work supported by the National Science Foundation Graduate Research Fellowship Program [Grant DGE-1650441] and by the National Science Foundation Division of Computing and Communications Foundations [Grant CCF-1908517].

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

In this paper, we present a unified analysis of methods for such a wide class of problems as variational inequalities, which includes minimization problems and saddle point problems. We develop our analysis on the modified Extra-Gradient method (the classic algorithm for variational inequalities) and consider the strongly monotone and monotone cases, which corresponds to strongly-convex-strongly-concave and convex-concave saddle point problems. The theoretical analysis is based on parametric assumptions about Extra-Gradient iterations. Therefore, it can serve as a strong basis for combining the already existing type methods and also for creating new algorithms. In particular, to show this we develop new robust methods, which include methods with quantization, coordinate methods, distributed randomized local methods, and others. Most of these approaches have never been considered in the generality of variational inequalities and have previously been used only for minimization problems. The robustness of the new methods is also confirmed by numerical experiments with GANs., Comment: in Russian, 57 pages, 3 figures, 1 table

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

We develop provably efficient reinforcement learning algorithms for two-player zero-sum finite-horizon Markov games with simultaneous moves. To incorporate function approximation, we consider a family of Markov games where the reward function and transition kernel possess a linear structure. Both the offline and online settings of the problems are considered. In the offline setting, we control both players and aim to find the Nash Equilibrium by minimizing the duality gap. In the online setting, we control a single player playing against an arbitrary opponent and aim to minimize the regret. For both settings, we propose an optimistic variant of the least-squares minimax value iteration algorithm. We show that our algorithm is computationally efficient and provably achieves an $\tilde O(\sqrt{d^3 H^3 T} )$ upper bound on the duality gap and regret, where $d$ is the linear dimension, $H$ the horizon and $T$ the total number of timesteps. Our results do not require additional assumptions on the sampling model. Our setting requires overcoming several new challenges that are absent in Markov decision processes or turn-based Markov games. In particular, to achieve optimism with simultaneous moves, we construct both upper and lower confidence bounds of the value function, and then compute the optimistic policy by solving a general-sum matrix game with these bounds as the payoff matrices. As finding the Nash Equilibrium of a general-sum game is computationally hard, our algorithm instead solves for a Coarse Correlated Equilibrium (CCE), which can be obtained efficiently. To our best knowledge, such a CCE-based scheme for optimism has not appeared in the literature and might be of interest in its own right., Accepted for presentation at COLT 2020

The problem considered in this paper is the weighted obnoxious facility location in the convex hull of demand points. The objective function is to maximize the smallest weighted distance between a facility and a set of demand points. Three new optimal solution approaches are proposed. Two variants of the "Big Triangle Small Triangle" global optimization method, and a procedure based on intersection points between Apollonius circles. We also compared the results with a multi-start approach using the non-linear multi-purpose software SNOPT. Problems with 1,000 demand points are optimally solved in a fraction of a second of computer time., Comment: 25 pages, 8 figures

This paper presents a computational approach for finding the optimal shapes of peristaltic pumps transporting rigid particles in Stokes flow. In particular, we consider shapes that minimize the rate of energy dissipation while pumping a prescribed volume of fluid, number of particles and/or distance traversed by the particles over a set time period. Our approach relies on a recently developed fast and accurate boundary integral solver for simulating multiphase flows through periodic geometries of arbitrary shapes. In order to fully capitalize on the dimensionality reduction feature of the boundary integral methods, shape sensitivities must ideally involve evaluating the physical variables on the particle or pump boundaries only. We show that this can indeed be accomplished owing to the linearity of Stokes flow. The forward problem solves for the particle motion in a slip-driven pipe flow while the adjoint problems in our construction solve quasi-static Dirichlet boundary value problems backwards in time, retracing the particle evolution. The shape sensitivities simply depend on the solution of one forward and one adjoint (for each shape functional) problems. We validate these analytic shape derivative formulas by comparing against finite-difference based gradients and present several examples showcasing optimal pump shapes under various constraints., Comment: 24 pages, 8 figures

In this paper we study and compare two multigrid relaxation schemes with coarsening by two, three, and four for solving elliptic sparse optimal control problems with control constraints. First, we perform a detailed local Fourier analysis (LFA) of a well-known collective Jacobi relaxation (CJR) scheme, where the optimal smoothing factors are derived. This insightful analysis reveals that the optimal relaxation parameters depend on mesh size and regularization parameters, which was not investigated in literature. Second, we propose and analyze a new mass-based Braess-Sarazin relaxation (BSR) scheme, which is proven to provide smaller smoothing factors than the CJR scheme when $\alpha\ge ch^4$ for a small constant $c$. Here $\alpha$ is the regularization parameter and $h$ is the spatial mesh step size. These schemes are successfully extended to control-constrained cases through the semi-smooth Newton method. Coarsening by three or four with BSR is competitive with coarsening by two. Numerical examples are presented to validate our theoretical outcomes. The proposed inexact BSR (IBSR) scheme, where two preconditioned conjugate gradients iterations are applied to the Schur complement system, yields better computational efficiency than the CJR scheme., Comment: 23 pages; 2 tables and 5 figures

In this work, the novel Distributed Bayesian (D-Bay) algorithm is presented for solving multi-agent problems within the continuous Distributed Constraint Optimization Problem (DCOP) framework. This framework extends the classical DCOP framework towards utility functions with continuous domains. Traditional DCOP solvers discretize the continuous domains, which increases the problem size exponentially. D-Bay overcomes this problem by utilizing Bayesian optimization for the adaptive sampling of variables to avoid discretization entirely. We theoretically show that D-Bay converges to the global optimum of the DCOP for Lipschitz continuous utility functions. The performance of the algorithm is evaluated empirically based on the sample efficiency. The proposed algorithm is compared to a centralized approach with equidistant discretization of the continuous domains for the sensor coordination problem. We find that our algorithm generates better solutions while requiring less samples., 31 pages, 7 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.

The aim of this paper is to compare the performance of a local solution technique—namely Sequential Linear Programming (SLP) employing random starting points—with state-of-the-art global solvers such as Baron and more sophisticated local solvers such as Sequential Quadratic Programming and Interior Point for the pooling problem. These problems can have many local optima, and we present a small example that illustrates how this can occur.We demonstrate that SLP—usually deemed obsolete since the arrival of fast reliable SQP solvers, Interior Point Methods and sophisticated global solvers—is still the method of choice for an important class of pooling problems when the criterion is the quality of the solution found within a given acceptable time budget. On this measure SLP significantly ourperforms all other tested algorithms.In addition we introduce a new formulation, the qq-formulation, for the case of fixed demands, that exclusively uses proportional variables. We compare the performance of SLP and the global solver Baron on the qq-formulation and other common formulations. While Baron with the qq-formulation generates weaker bounds than with the other formulations tested, for both SLP and Baron the qq-formulation finds the best solutions within a given time budget. The qq-formulation can be strengthened by pq-like cuts in which case the same bounds as for the pq-formulation are obtained. However the associated time penalty due to the additional constraints results in poorer solution quality within the time budget.

One of the essential elements in implementing a closed-loop irrigation system is soil moisture estimation based on a limited number of available sensors. One associated problem is the determination of the optimal locations to install the sensors such that good soil moisture estimation can be obtained. In our previous work, the modal degree of observability was employed to address the problem of optimal sensor placement for soil moisture estimation of agro-hydrological systems. It was demonstrated that the optimally placed sensors can improve the soil moisture estimation performance. However, it is unclear whether the optimal sensor placement can significantly improve the soil moisture estimation performance in actual applications. In this work, we investigate the impact of sensor placement in soil moisture estimation for an actual agricultural field in Lethbridge, Alberta, Canada. In an experiment on the studied field, 42 soil moisture sensors were installed at different depths to collect the soil moisture measurements for one growing season. A three-dimensional agro-hydrological model with heterogeneous soil parameters of the studied field is developed. The modal degree of observability is applied to the three-dimensional system to determine the optimal sensor locations. The extended Kalman filter (EKF) is chosen as the data assimilation tool to estimate the soil moisture content of the studied field. Soil moisture estimation results for different scenarios are obtained and analyzed to investigate the effects of sensor placement on the performance of soil moisture estimation in the actual applications.

The distance geometry problem asks to find a realization of a given simple edge-weighted graph in a Euclidean space of given dimension K, where the edges are realized as straight segments of lengths equal (or as close as possible) to the edge weights. The problem is often modelled as a mathematical programming formulation involving decision variables that determine the position of the vertices in the given Euclidean space. Solution algorithms are generally constructed using local or global nonlinear optimization techniques. We present a new modelling technique for this problem where, instead of deciding vertex positions, formulations decide the length of the segments representing the edges in each cycle in the graph, projected in every dimension. We propose an exact formulation and a relaxation based on a Eulerian cycle. We then compare computational results from protein conformation instances obtained with stochastic global optimization techniques on the new cycle-based formulation and on the existing edge-based formulation. While edge-based formulations take less time to reach termination, cycle-based formulations are generally better on solution quality measures.

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

In this paper, we present and study a robust unit commitment model and some variants that consider complex temperature and demand uncertainties. Since there is a strong relationship among the efficiency of gas generators, demand, and temperature in practical systems, our robust models have both left- and right-hand-side (LHS and RHS, respectively) uncertainties. Unlike many existing robust models with RHS uncertainty only, the introduction of LHS uncertainty imposes a huge challenge in computing robust solutions. For those complex formulations, we analyze their structures, derive important properties, and design exact and fast approximation solution strategies under the column-and-constraint generation framework. Numerical experiments are conducted on typical IEEE test systems, which showcase the great performance of our solution methods and demonstrate a clear impact of complex and correlated uncertainties in system operations.

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.

Random feature methods have been successful in various machine learning tasks, are easy to compute, and come with theoretical accuracy bounds. They serve as an alternative approach to standard neural networks since they can represent similar function spaces without a costly training phase. However, for accuracy, random feature methods require more measurements than trainable parameters, limiting their use for data-scarce applications or problems in scientific machine learning. This paper introduces the sparse random feature expansion to obtain parsimonious random feature models. Specifically, we leverage ideas from compressive sensing to generate random feature expansions with theoretical guarantees even in the data-scarce setting. In particular, we provide generalization bounds for functions in a certain class (that is dense in a reproducing kernel Hilbert space) depending on the number of samples and the distribution of features. The generalization bounds improve with additional structural conditions, such as coordinate sparsity, compact clusters of the spectrum, or rapid spectral decay. In particular, by introducing sparse features, i.e. features with random sparse weights, we provide improved bounds for low order functions. We show that the sparse random feature expansions outperforms shallow networks in several scientific machine learning tasks.

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.

We propose a new inexact column-and-constraint generation (i-C&CG) method to solve two-stage robust optimization problems. The method allows solutions to the master problems to be inexact, which is desirable when solving large-scale and/or challenging problems. It is equipped with a backtracking routine that controls the trade-off between bound improvement and inexactness. Importantly, this routine allows us to derive theoretical finite convergence guarantees for our i-C&CG method. Numerical experiments demonstrate computational advantages of our i-C&CG method over state-of-the-art column-and-constraint generation methods.

Starting from the vector multipliers, the inner product, norm, distance, as well as addition of two vectors of different dimensions are proposed, which makes the spaces into a topological vector space, called the Euclidean space of different dimension (ESDD). An equivalence is obtained via distance. As a quotient space of ESDDs w.r.t. equivalence, the dimension-free Euclidean spaces (DFESs) and dimension-free manifolds (DFMs) are obtained, which have bundled vector spaces as its tangent space at each point. Using the natural projection from a ESDD to a DFES, a fiber bundle structure is obtained, which has ESDD as its total space and DFES as its base space. Classical objects in differential geometry, such as smooth functions, (co-)vector fields, tensor fields, etc., have been extended to the case of DFMs with the help of projections among different dimensional Euclidean spaces. Then the dimension-varying dynamic systems (DVDSs) and dimension-varying control systems (DVCSs) are presented, which have DFM as their state space. The realization, which is a lifting of DVDSs or DVCSs from DFMs into ESDDs, and the projection of DVDSs or DVCSs from ESDDs onto DFMs are investigated.

Binary polynomial optimization is equivalent to the problem of minimizing a linear function over the intersection of the multilinear set with a polyhedron. Many families of valid inequalities for the multilinear set are available in the literature, though giving a polyhedral characterization of the convex hull is not tractable in general as binary polynomial optimization is NP-hard. In this paper, we study the cardinality constrained multilinear set in the special case when the number of monomials is exactly two. We give an extended formulation, with two more auxiliary variables and exponentially many inequalities, of the convex hull of solutions of the standard linearization of this problem. We also show that the separation problem can be solved efficiently.

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.

We develop multi-stage linear decision rules (LDRs) for dynamic power system generation and energy storage investment planning under uncertainty and propose their chance-constrained optimization with performance guarantees. First, the optimized LDRs guarantee operational and carbon policy feasibility of the resulting dynamic investment plan even when the planning uncertainty distribution is ambiguous. Second, the optimized LDRs internalize the tolerance of the system planner towards the stochasticity (variance) of uncertain investment outcomes. They can eventually produce a quasi-deterministic investment plan, which is insensitive to uncertainty (as in deterministic planning) but robust to its realizations (as in stochastic planning). Last, we certify the performance of the optimized LDRs with the bound on their sub-optimality due to their linear functional form. Using this bound, we guarantee that the preference of LDRs over less restrictive -- yet poorly scalable -- scenario-based optimization does not lead to financial losses exceeding this bound. We use a testbed of the U.S. Southeast power system to reveal the trade-offs between the cost, stochasticity, and feasibility of LDR-based investments. We also conclude that the LDR sub-optimality depends on the amount of uncertainty and the tightness of chance constraints on operational, investment and policy variables.

The main purpose of this article is to prove a logarithmic convexity estimate for the solution of a linear heat equation subject to dynamic boundary conditions in a bounded convex domain. As an application, we prove the impulsive null approximate controllability for an impulsive heat equation with dynamic boundary conditions.

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.

This paper proposes a novel CTA (Combine-Then-Adapt)-based decentralized algorithm for solving convex composite optimization problems over undirected and connected networks. The local loss function in these problems contains both smooth and nonsmooth terms. The proposed algorithm uses uncoordinated network-independent constant stepsizes and only needs to approximately solve a sequence of proximal mappings, which is advantageous for solving decentralized composite optimization problems where the proximal mappings of the nonsmooth loss functions may not have analytical solutions. For the general convex case, we prove an O(1/k) convergence rate of the proposed algorithm, which can be improved to o(1/k) if the proximal mappings are solved exactly. Furthermore, with metric subregularity, we establish a linear convergence rate for the proposed algorithm. Numerical experiments demonstrate the efficiency of the algorithm.

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

We present a new neural network to approximate convex functions. This network has the particularity to approximate the function with cuts and can be easily adapted to partial convexity. We give an universal approximation theorem in the full convex case and give many numerical results proving it efficiency., 10 pages 16 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.

Adaptive networks (ANs) are effective real time techniques to process and track events observed by sensor networks and, more recently, to equip Internet of Things (IoT) applications. ANs operate over nodes equipped with collaborative adaptive filters that solve distributively an estimation problem common to the whole network. However, they do not guarantee that nodes do not lose from cooperation, as compared to its non-cooperative operation; that poor nodes are rejected and exceptional nodes estimates reach the entire network; and that performance is uniform over all nodes. In order to enforce such properties, this work introduces the concept of distributed universal estimation, which encompasses the new concepts of local universality, global universality and universality with respect to the non-cooperative operation. We then construct a new cooperation protocol that is proven to be distributively universal, outperforming direct competitors from the literature, as shown by several simulations. Mean and mean-square analytical models are developed, with good agreement between theory and simulations.

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.

In this paper, we consider distributed optimization problems where $n$ agents, each possessing a local cost function, collaboratively minimize the average of the local cost functions over a connected network. To solve the problem, we propose a distributed random reshuffling (D-RR) algorithm that invokes the random reshuffling (RR) update in each agent. We show that D-RR inherits favorable characteristics of RR for both smooth strongly convex and smooth nonconvex objective functions. In particular, for smooth strongly convex objective functions, D-RR achieves $\mathcal{O}(1/T^2)$ rate of convergence (where $T$ counts epoch number) in terms of the squared distance between the iterate and the global minimizer. When the objective function is assumed to be smooth nonconvex, we show that D-RR drives the squared norm of gradient to $0$ at a rate of $\mathcal{O}(1/T^{2/3})$. These convergence results match those of centralized RR (up to constant factors) and outperform the distributed stochastic gradient descent (DSGD) algorithm if we run a relatively large number of epochs. Finally, we conduct a set of numerical experiments to illustrate the efficiency of the proposed D-RR method on both strongly convex and nonconvex distributed optimization problems., 20 pages, 13 figures

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

Compared with large-scale physical batteries, aggregated and coordinated generic energy storage (GES) resources provide low-cost, but uncertain, flexibility for power grid operations. While GES can be characterized by different types of uncertainty, the literature mostly focuses on decision-independent uncertainties (DIUs), such as exogenous stochastic disturbances caused by weather conditions. Instead, this manuscript focuses on newly-introduced decision-dependent uncertainties (DDUs) and considers an optimal GES dispatch that accounts for uncertain available state-of-charge (SoC) bounds that are affected by incentive signals and discomfort levels. To incorporate DDUs, we present a novel chance-constrained optimization (CCO) approach for the day-ahead economic dispatch of GES units. Two tractable methods are presented to solve the proposed CCO problem with DDUs: (i) a robust reformulation for general but incomplete distributions of DDUs, and (ii) an iterative algorithm for specific and known distributions of DDUs. Furthermore, reliability indices are introduced to verify the applicability of the proposed approach with respect to the reliability of the response of GES units. Simulation-based analysis shows that the proposed methods yield conservative, but credible, GES dispatch strategies and reduced penalty cost by incorporating DDUs in the constraints and leveraging data-driven parameter identification. This results in improved availability and performance of coordinated GES units., Comment: Decision-dependent uncertainty; Generic Energy Storage

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.

In this survey, we describe controlled interacting particle systems (CIPS) to approximate the solution of the optimal filtering and the optimal control problems. Part I of the survey is focussed on the feedback particle filter (FPF) algorithm, its derivation based on optimal transportation theory, and its relationship to the ensemble Kalman filter (EnKF) and the conventional sequential importance sampling-resampling (SIR) particle filters. The central numerical problem of FPF -- to approximate the solution of the Poisson equation -- is described together with the main solution approaches. An analytical and numerical comparison with the SIR particle filter is given to illustrate the advantages of the CIPS approach. Part II of the survey is focussed on adapting these algorithms for the problem of reinforcement learning. The survey includes several remarks that describe extensions as well as open problems in this subject.

Robustness and stability of image-reconstruction algorithms have recently come under scrutiny. Their importance to medical imaging cannot be overstated. We review the known results for the topical variational regularization strategies ($\ell_2$ and $\ell_1$ regularization) and present novel stability results for $\ell_p$-regularized linear inverse problems for $p\in(1,\infty)$. Our results guarantee Lipschitz continuity for small $p$ and H\"{o}lder continuity for larger $p$. They generalize well to the $L_p(\Omega)$ function spaces., Comment: 11 pages, 6 figures, 1 appendix