30 August 2017 in IEEE Transactions on Automatic Control
We provide a unifying framework for distributed convex optimization over time-varying networks, in the presence of constraints and uncertainty, features that are typically treated separately in the literature. We adopt a proximal minimization perspective and show that this set-up allows us to bypass the difficulties of existing algorithms while simplifying the underlying mathematical analysis. We develop an iterative algorithm and show the convergence of the resulting scheme to some optimizer of the centralized problem. To deal with the case where the agents' constraint sets are affected by a possibly common uncertainty vector, we follow a scenario-based methodology and offer probabilistic guarantees regarding the feasibility properties of the resulting solution. To this end, we provide a distributed implementation of the scenario approach, allowing agents to use a different set of uncertainty scenarios in their local optimization programs. The efficacy of our algorithm is demonstrated by means of a numerical example related to a regression problem subject to regularization.
13 October 2020 in IEEE Transactions on Automatic Control
We consider a multiagent noncooperative game with agents' objective functions being affected by uncertainty. Following a data driven paradigm, we represent uncertainty by means of scenarios and seek a robust Nash equilibrium solution. We treat the Nash equilibrium computation problem within the realm of probably approximately correct learning. Building upon recent developments in scenario-based optimization, we accompany the computed Nash equilibrium with a priori and a posteriori probabilistic robustness certificates, providing confidence that the computed equilibrium remains unaffected (in probabilistic terms) when a new uncertainty realization is encountered. For a wide class of games, we also show that the computation of the so called compression set-which is at the core of scenario-based optimization-can be directly obtained as a byproduct of the proposed methodology. We demonstrate the efficacy of our approach on an electric vehicle charging control problem.
22 February 2024 in IEEE Transactions on Automatic Control
We propose fully-distributed algorithms for Nash equilibrium seeking in aggregative games over networks. We first consider the case where local constraints are present and we design an algorithm combining, for each agent, (i) the projected pseudo-gradient descent and (ii) a tracking mechanism to locally reconstruct the aggregative variable. To handle coupling constraints arising in generalized settings, we propose another distributed algorithm based on (i) a recently emerged augmented primal-dual scheme and (ii) two tracking mechanisms to reconstruct, for each agent, both the aggregative variable and the coupling constraint satisfaction. Leveraging tools from singular perturbations analysis, we prove linear convergence to the Nash equilibrium for both schemes. Finally, we run extensive numerical simulations to confirm the effectiveness of our methods and compare them with state-of-the-art distributed equilibrium-seeking algorithms.
6 April 2022 in IEEE Transactions on Automatic Control
We revisit the so-called sampling and discarding approach used to quantify the probability of constraint violation of a solution to convex scenario programs when some of the original samples are allowed to be discarded. Motivated by two scenario programs that possess analytic solutions and the fact that the existing bound for scenario programs with discarded constraints is not tight, we analyze a removal scheme that consists of a cascade of optimization problems, where, at each step, we remove a superset of the active constraints. By relying on results from compression learning theory, we show that such a removal scheme leads to less conservative bounds for the probability of constraint violation than the existing ones. We also show that the proposed bound is tight by characterizing a class of optimization problems which achieves the given upper bound. The performance improvement of the proposed methodology is illustrated by an example that involves a resource sharing linear program.
6 June 2018 in IEEE Control Systems Letters
We deal with decision making in a large-scale multi-agent system, where each agent aims at minimizing a local cost function subject to local constraints, and the local decision variables of all agents are coupled through a global constraint. We consider a cooperative framework where the multi-agent decision problem is formulated as a constrained optimization program with the sum of the local costs as global cost to be minimized with respect to the local decision variables of all agents, subject to both local and global constraints. We focus on a non-convex linear set-up where all costs and constraints are linear but local decision variables are discrete or include a discrete component, and propose a distributed iterative scheme based on dual decomposition and consensus to solve the resulting Mixed Integer Linear Program (MILP). Our approach extends recent results in the literature to a distributed set-up with a time-varying communication network and allows to: reduce the computational and communication effort, achieve resilience to communication failures, and also preserve privacy of local information. The approach is demonstrated on a numerical example of optimal charging of plug-in electric vehicles.
21 June 2018 in IEEE Control Systems Letters
This paper addresses the actuator selection problem, i.e., given an interconnection of asymptotically stable linear dynamical systems on a network and m possible actuators choose ν among them to achieve a certain objective. In general, this is a combinatorial optimisation problem which is hard to solve; convex relaxations do not usually yield an optimal solution for the original problem. In this paper we focus on a particular instance of the actuator selection problem, namely the formulation with the trace of the controllability gramian matrix as the optimisation metric, and show that such a choice gives rise to an integer linear program. Using properties of integral polyhedra, we show through a sequence of reformulations that the optimal solution of this problem can be determined by means of a linear program without introducing any relaxation gap. This allows us to obtain the optimal solution using a primal-dual distributed algorithm, thus providing a scalable approach to the problem of actuator placement which has been up to now performed in a centralised manner enumerating all possible placement alternatives. We illustrate the main features of our approach by means of a case study involving a simplified model of the European power grid.