More Like this

1. Perturbation-based Regret Analysis of Predictive Control in Linear Time Varying Systems

   Yiheng Lin, Yang Hu (January 2021, Advances in Neural Information Processing Systems 34 (NeurIPS 2021))

   We study predictive control in a setting where the dynamics are time-varying and linear, and the costs are time-varying and well-conditioned. At each time step, the controller receives the exact predictions of costs, dynamics, and disturbances for the future k time steps. We show that when the prediction window k is sufficiently large, predictive control is input-to-state stable and achieves a dynamic regret of O(λkT), where λ<1 is a positive constant. This is the first dynamic regret bound on the predictive control of linear time-varying systems. We also show a variation of predictive control obtains the first competitive bound for the control of linear time-varying systems: 1+O(λk). Our results are derived using a novel proof framework based on a perturbation bound that characterizes how a small change to the system parameters impacts the optimal trajectory. 

   more » « less
2. Distributed Optimal Resource Allocation with Time-Varying Quadratic Cost Functions and Resources over Switching Agents

   https://doi.org/10.23919/ECC55457.2022.9838317  

   Esteki, Amir-Salar; Kia, Solmaz S. (July 2022, 2022 European Control Conference (ECC))

   This paper proposes a distributed solution for an optimal resource allocation problem with a time-varying cost function and time-varying demand. The objective is to minimize a global cost, which is the summation of local quadratic time-varying cost functions, by allocating time-varying resources. A reformulation of the original problem is developed and is solved in a distributed manner using only local interactions over an undirected connected graph. In the proposed algorithm, the local state trajectories converge to a bounded neighborhood of the optimal trajectory. This bound is characterized in terms the parameters of the cost and topology properties. We also show that despite the tracking error, the trajectories are feasible at all times, meaning that the resource allocation equality constraint is met at every execution time. Our algorithm also considers the possibility of some generators going out of production from time to time and adjusts the solution so that the remaining generators can meet the demands in an optimal manner. Numerical examples demonstrate our results. 

   more » « less
3. Distributed Stochastic Optimization with Gradient Tracking over Time- Varying Directed Networks

   https://doi.org/10.1109/IEEECONF59524.2023.10477004  

   Anh_Nguyen, Duong Thuy; Nguyen, Duong Tung; Nedic, Angelia (October 2023, IEEE)

   We study a distributed method called SAB–TV, which employs gradient tracking to collaboratively minimize the strongly-convex sum of smooth local cost functions for networked agents communicating over a time-varying directed graph. Each agent, assumed to have access to a stochastic first order oracle for obtaining an unbiased estimate of the gradient of its local cost function, maintains an auxiliary variable to asymptotically track the stochastic gradient of the global cost. The optimal decision and gradient tracking are updated over time through limited information exchange with local neighbors using row- and column-stochastic weights, guaranteeing both consensus and optimality. With a sufficiently small constant step-size, we demonstrate that, in expectation, SAB–TV converges linearly to a neighborhood of the optimal solution. Numerical simulations illustrate the effectiveness of the proposed algorithm. 

   more » « less
4. An Efficient Algorithm for Routing and Recharging of Electric Vehicles

   https://doi.org/10.1007/978-3-030-64843-5_48  

   Bahreini, T; Fisher, N; Grosu, D (December 2020, COCOA 2020: Combinatorial Optimization and Applications)

   null (Ed.)

   In this paper, we address the routing and recharging problem for electric vehicles, where charging nodes have heterogeneous prices and waiting times, and the objective is to minimize the total recharging cost. We prove that the problem is NP-hard and propose two algorithms to solve it. The first, is an algorithm which obtains the optimal solution in pseudo-polynomial time. The second, is a polynomial time algorithm that obtains a solution with the total cost of recharging not greater than the optimal cost for a more constrained instance of the problem with the maximum waiting time of (1−ϵ)⋅W , where W is the maximum allowable waiting time. 

   more » « less
5. Distributed Optimization Over Time-Varying Graphs With Imperfect Sharing of Information

   https://doi.org/10.1109/TAC.2022.3207866  

   Reisizadeh, Hadi; Touri, Behrouz; Mohajer, Soheil (July 2023, IEEE Transactions on Automatic Control)

   We study strongly convex distributed optimization problems where a set of agents are interested in solving a separable optimization problem collaboratively. In this article, we propose and study a two-time-scale decentralized gradient descent algorithm for a broad class of lossy sharing of information over time-varying graphs. One time-scale fades out the (lossy) incoming information from neighboring agents, and one time-scale regulates the local loss functions' gradients. We show that assuming a proper choice of step-size sequences, certain connectivity conditions, and bounded gradients along the trajectory of the dynamics, the agents' estimates converge to the optimal solution with the rate of O(T^{−1/2}) . We also provide novel tools to study distributed optimization with diminishing averaging weights over time-varying graphs. 

   more » « less