Giuseppe Belgioioso

Huan Peng, Guanpu Chen, Giuseppe Belgioioso et al.

This paper considers a class of aggregative congestion games with uncertain coupling constraints, and devises a distributed algorithm to seek the robust generalized Wardrop equilibrium (RGWE) under worst-case uncertainty. Utilizing robust optimization theory, we reformulate the original aggregative congestion game with uncertainty into a tractable and deterministic augmented problem. Building upon this reformulation, we design a fully distributed algorithm to seek the RGWE by integrating a projected primal-dual scheme and a dynamic tracking technique. The convergence of the proposed algorithm is rigorously guaranteed via singular perturbation theory and LaSalle's invariance principle. Furthermore, we explicitly characterize the relationship between the obtained RGWE and the robust generalized Nash equilibrium, as the latter captures full strategic interactions. Finally, numerical simulations on the charging control of plug-in electric vehicles corroborate our theoretical findings.

Giuseppe Belgioioso, Sergio Grammatico

We show that projected-gradient methods for the distributed computation of generalized Nash equilibria in aggregative games are preconditioned forward-backward splitting methods applied to the KKT operator of the game. Specifically, we adopt the preconditioned forward-backward design, recently conceived by Yi and Pavel in the manuscript "A distributed primal-dual algorithm for computation of generalized Nash equilibria via operator splitting methods" for generalized Nash equilibrium seeking in aggregative games. Consequently, we notice that two projected-gradient methods recently proposed in the literature are preconditioned forward-backward methods. More generally, we provide a unifying operator-theoretic ground to design projected-gradient methods for generalized equilibrium seeking in aggregative games.

Daniel Arnström, Emilio Benenati, Giuseppe Belgioioso

We present \texttt{DR-DAQP}, an open-source solver for strongly monotone affine variational inequaliries that combines Douglas-Rachford operator splitting with an active-set acceleration strategy. The key idea is to estimate the active set along the iterations to attempt a Newton-type correction. This step yields the exact AVI solution when the active set is correctly estimated, thus overcoming the asymptotic convergence limitation inherent in first-order methods. Moreover, we exploit warm-starting and pre-factorization of relevant matrices to further accelerate evaluation of the algorithm iterations. We prove convergence and establish conditions under which the algorithm terminates in finite time with the exact solution. Numerical experiments on randomly generated AVIs show that \texttt{DR-DAQP} is up to two orders of magnitude faster than the state-of-the-art solver \texttt{PATH}. On a game-theoretic MPC benchmark, \texttt{DR-DAQP} achieves solve times several orders of magnitude below those of the mixed-integer solver \texttt{NashOpt}. A high-performing C implementation is available at \textt{https://github.com/darnstrom/daqp}, with easily-accessible interfaces to Julia, MATLAB, and Python.

Panagiotis D. Grontas, Carlo Cenedese, Marta Fochesato et al.

We study the problem of optimally routing plug-in electric and conventional fuel vehicles on a city level. In our model, commuters selfishly aim to minimize a local cost that combines travel time, from a fixed origin to a desired destination, and the monetary cost of using city facilities, parking or service stations. The traffic authority can influence the commuters' preferred routing choice by means of personalized discounts on parking tickets and on the energy price at service stations. We formalize the problem of designing these monetary incentives optimally as a large-scale bilevel game, where constraints arise at both levels due to the finite capacities of city facilities and incentives budget. Then, we develop an efficient decentralized solution scheme with convergence guarantees based on BIG Hype, a recently-proposed hypergradient-based algorithm for hierarchical games. Finally, we validate our model via numerical simulations over the Anaheim's network, and show that the proposed approach produces sensible results in terms of traffic decongestion and it is able to solve in minutes problems with more than 48000 variables and 110000 constraints.

Emilio Benenati, Giuseppe Belgioioso

We present an efficient algorithm to compute the explicit open-loop solution to both finite and infinite-horizon dynamic games subject to state and input constraints. Our approach relies on a multiparametric affine variational inequality characterization of the open-loop Nash equilibria and extends the classical explicit constrained LQR and MPC frameworks to multi-agent non-cooperative settings. A key practical implication is that linear-quadratic game-theoretic MPC becomes viable even at very high sampling rates for multi-agent systems of moderate size. Extensive numerical experiments demonstrate order-of-magnitude improvements in online computation time and solution accuracy compared with state-of-the-art game-theoretic solvers.

Giuseppe Belgioioso, Filippo Fabiani, Franco Blanchini et al.

We adopt an operator-theoretic perspective to study convergence of linear fixed-point iterations and discrete- time linear systems. We mainly focus on the so-called Krasnoselskij-Mann iteration x(k+1) = ( 1 - α(k) ) x(k) + α(k) A x(k), which is relevant for distributed computation in optimization and game theory, when A is not available in a centralized way. We show that convergence to a vector in the kernel of (I-A) is equivalent to strict pseudocontractiveness of the linear operator x -> Ax. We also characterize some relevant operator-theoretic properties of linear operators via eigenvalue location and linear matrix inequalities. We apply the convergence conditions to multi-agent linear systems with vanishing step sizes, in particular, to linear consensus dynamics and equilibrium seeking in monotone linear-quadratic games.

Filippo Fabiani, Giuseppe Belgioioso, Franco Blanchini et al.

State convergence is essential in several scientific areas, e.g. multi-agent consensus/disagreement, distributed optimization, monotone game theory, multi-agent learning over time-varying networks. This paper is the first on state convergence in both continuous- and discrete-time linear systems affected by polytopic uncertainty. First, we characterize state convergence in linear time invariant systems via equivalent necessary and sufficient conditions. In the presence of uncertainty, we complement the canonical definition of (weak) convergence with a stronger notion of convergence, which requires the existence of a common kernel among the generator matrices of the difference/differential inclusion (strong convergence). We investigate under which conditions the two definitions are equivalent. Then, we characterize weak and strong convergence by means of Lyapunov and LaSalle arguments, (linear) matrix inequalities and separability of the eigenvalues of the generator matrices. We also show that, unlike asymptotic stability, state convergence lacks of duality.

Marta Zagorowska, Lukas Ortmann, Giuseppe Belgioioso et al.

Online Feedback Optimization leverages properties of optimization algorithms to develop controllers for systems with limited model availability, which is often the case in process control. The interplay between the parameters of the chosen optimization algorithm, as well as lack of direct connection to the characteristics of the underlying process make their tuning challenging. We propose a method for adaptive tuning of Online Feedback Optimization controllers based on scaled projected gradient descent by using sensitivity of the desired objective to the parameters of the algorithm. The proposed adaptive tuning method limits the operator-tunable parameters to scalar values that represent how much the control inputs and the objective can change between iterations without requiring either additional information about the controlled system or repeated experiments. Numerical studies on a gas lift and a continuously-stirred tank reactor processes confirm that our adaptive scheme improves closed-loop performance of Online Feedback optimization compared to standard manual tuning methods.

Andrea Martin, Giuseppe Belgioioso

We introduce a principled learning to optimize (L2O) framework for solving fixed-point problems involving general nonexpansive mappings. Our idea is to deliberately inject summable perturbations into a standard Krasnosel'skii-Mann iteration to improve its average-case performance over a specific distribution of problems while retaining its convergence guarantees. Under a metric sub-regularity assumption, we prove that the proposed parametrization includes only iterations that locally achieve linear convergence-up to a vanishing bias term-and that it encompasses all iterations that do so at a sufficiently fast rate. We then demonstrate how our framework can be used to augment several widely-used operator splitting methods to accelerate the solution of structured monotone inclusion problems, and validate our approach on a best approximation problem using an L2O-augmented Douglas-Rachford splitting algorithm.

Florian Dörfler, Zhiyu He, Giuseppe Belgioioso et al.

Traditionally, numerical algorithms are seen as isolated pieces of code confined to an {\em in silico} existence. However, this perspective is not appropriate for many modern computational approaches in control, learning, or optimization, wherein {\em in vivo} algorithms interact with their environment. Examples of such {\em open algorithms} include various real-time optimization-based control strategies, reinforcement learning, decision-making architectures, online optimization, and many more. Further, even {\em closed} algorithms in learning or optimization are increasingly abstracted in block diagrams with interacting dynamic modules and pipelines. In this opinion paper, we state our vision on a to-be-cultivated {\em systems theory of algorithms} and argue in favor of viewing algorithms as open dynamical systems interacting with other algorithms, physical systems, humans, or databases. Remarkably, the manifold tools developed under the umbrella of systems theory are well suited for addressing a range of challenges in the algorithmic domain. We survey various instances where the principles of algorithmic systems theory are being developed and outline pertinent modeling, analysis, and design challenges.

Giuseppe Belgioioso, Sergio Grammatico

We address the generalized aggregative equilibrium seeking problem for noncooperative agents playing average aggregative games with affine coupling constraints. First, we use operator theory to characterize the generalized aggregative equilibria of the game as the zeros of a monotone set-valued operator. Then, we massage the Douglas-Rachford splitting to solve the monotone inclusion problem and derive a single layer, semi-decentralized algorithm whose global convergence is guaranteed under mild assumptions. The potential of the proposed Douglas-Rachford algorithm is shown on a simplified resource allocation game, where we observe faster convergence with respect to forward-backward algorithms.