On the probabilistic feasibility of solutions in multi-agent optimization problems under uncertainty. (January 2022) - Pantazis, George; Fele, Filiberto; Margellos, Kostas
Abstract: 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 affected 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 convex 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 representation 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 alongside any optimization algorithm. Our theoretical results are accompanied by a numerical case study of a charging control problem for a fleet of electric vehicles.