On the probabilistic feasibility of solutions in multi-agent optimization problems under uncertainty

摘要

We investigate the probabilistic feasibility of randomized solutions to two distinct classes of uncertain multi-agent optimization programs. We first assume that only the constraints of the program are af-fected by uncertainty, while the cost function is arbitrary. Leveraging recent developments on a posteriori analysis within the scenario approach, we provide probabilistic guarantees for all feasible solutions of the program under study. This is particularly useful in cases where the numerical implementation of the solution-seeking algorithm prevents the exact quantification of the optimal solution. Furthermore, this result provides guarantees for the entire solution set of optimization programs with uncertain con-vex constraints and (possibly) non-convex cost function. We then focus on optimization programs with deterministic constraints, where the cost function depends on uncertainty and admits an aggregate repre-sentation of the agents' decisions. By exploiting the structure of the program under study and leveraging the so called support rank notion, we provide agent-independent robustness certificates for the optimal solution, i.e., the constructed bound on the probability of constraint violation does not depend on the number of agents, but only on the dimension of each agent's decision space. This substantially reduces the amount of samples required to achieve a certain level of probabilistic robustness for a larger number of agents. All robustness certificates provided in this paper are distribution-free and can be used along-side any optimization algorithm. Our theoretical results are accompanied by a numerical case study of a charging control problem for a fleet of electric vehicles.(c) 2021 European Control Association. Published by Elsevier Ltd. All rights reserved.