We study predictive control in a setting where the dynamics are timevarying and linear, and the costs are timevarying and wellconditioned. 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 inputtostate 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 timevarying systems. We also show a variation of predictive control obtains the first competitive bound for the control of linear timevarying 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
Distributed Unconstrained Optimization with Timevarying Cost Functions
This paper proposes a novel solution for the distributed unconstrained optimization problem where the total cost is the summation of timevarying local cost functions of a group networked agents. The objective is to track the optimal trajectory that minimizes the total cost at each time instant. Our approach consists of a twostage dynamics, where the first one samples the first and second derivatives of the local costs periodically to construct an estimate of the descent direction towards the optimal trajectory, and the second one uses this estimate and a consensus term to drive local states towards the timevarying solution while reaching consensus. The first part is carried out by a weighted average consensus algorithm in the discretetime framework and the second part is performed with a continuoustime dynamics. Using the Lyapunov stability analysis, an upper bound on the gradient of the total cost is obtained which is asymptotically reached. This bound is characterized by the properties of the local costs. To demonstrate the performance of the proposed method, a numerical example is conducted that studies tuning the algorithm’s parameters and their effects on the convergence of local states to the optimal trajectory.
more »
« less
 Award ID(s):
 1653838
 NSFPAR ID:
 10507029
 Publisher / Repository:
 IEEE
 Date Published:
 Journal Name:
 European Control Conference (ECC)
 ISBN:
 9783907144084
 Page Range / eLocation ID:
 1 to 6
 Format(s):
 Medium: X
 Location:
 Bucharest, Romania
 Sponsoring Org:
 National Science Foundation
More Like this


This paper proposes a distributed solution for an optimal resource allocation problem with a timevarying cost function and timevarying demand. The objective is to minimize a global cost, which is the summation of local quadratic timevarying cost functions, by allocating timevarying 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

We study a distributed method called SAB–TV, which employs gradient tracking to collaboratively minimize the stronglyconvex sum of smooth local cost functions for networked agents communicating over a timevarying 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 columnstochastic weights, guaranteeing both consensus and optimality. With a sufficiently small constant stepsize, 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

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 NPhard and propose two algorithms to solve it. The first, is an algorithm which obtains the optimal solution in pseudopolynomial 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

We consider an innetwork optimal resource allocation problem in which a group of agents interacting over a connected graph want to meet a demand while minimizing their collective cost. The contribution of this paper is to design a distributed continuoustime algorithm for this problem inspired by a recently developed firstorder transformed primaldual method. The solution applies to clusterbased setting where each agent may have a set of subagents, and its local cost is the sum of the cost of these subagents. The proposed algorithm guarantees an exponential convergence for strongly convex costs and asymptotic convergence for convex costs. Exponential convergence when the local cost functions are strongly convex is achieved even when the local gradients are only locally Lipschitz. For convex local cost functions, our algorithm guarantees asymptotic convergence to a point in the minimizer set. Through numerical examples, we show that our proposed algorithm delivers a faster convergence compared to existing distributed resource allocation algorithms.more » « less