Search

We look at a stochastic time-varying optimization problem and we formulate online algorithms to find and track its optimizers in expectation. The algorithms are derived from the intuition that standard prediction and correction steps can be seen as a nonlinear dynamical system and a measurement equation, respectively, yielding the notion of nonlinear filter design. The optimization algorithms are then based on an extended Kalman filter in the unconstrained case, and on a bilinear matrix inequality condition in the constrained case. Some special cases and variations are discussed, notably the case of parametric filters, yielding certificates based on LPV analysis and, if one wishes, matrix sum-of-squares relaxations. Supporting numerical results are presented from real data sets in ride-hailing scenarios. The results are encouraging, especially when predictions are accurate, a case which is often encountered in practice when historical data is abundant., 22 pages

Modern socio-technical systems typically consist of many interconnected users and competing service providers, where notions like market equilibrium are tightly connected to the ``evolution'' of the network of users. In this paper, we model the users' dynamics as a linear dynamical system, and the service providers as agents taking part to a generalized Nash game, whose outcome coincides with the input of the users' dynamics. We thus characterize the notion of co-evolution of the market and the network dynamics and derive dissipativity-based conditions leading to a pertinent notion of equilibrium. We then focus on the control design and adopt the light-touch policy to incentivize or penalize the service providers as little as possible, while steering the networked system to a desirable outcome. We also provide a dimensionality-reduction procedure, which offers network-size independent conditions. Finally, we illustrate our novel notions and algorithms on a simulation setup stemming from digital market regulations for influencers, a topic of growing interest.

Transmission-constrained problems in power systems can be cast as polynomial optimization problems whose coefficients vary over time. We consider the complications therein and suggest several approaches. On the example of the alternating-current optimal power flows (ACOPFs), we illustrate one of the approaches in detail. For the time-varying ACOPF, we provide an upper bound for the difference between the optimal cost for a relaxation using the most recent data and the current approximate optimal cost generated by our algorithm. This bound is a function of the properties of the instance and the rate of change of the coefficients over time. Moreover, we also bound the number of floating-point operations to perform between two subsequent updates to ensure a bounded error., A journal version of Liu et al [arXiv:1710.07119, PSCC 2018] taking into account our recent work [arXiv:2104.05445 and arXiv:2210.08387]

We investigate both stationary and time-varying, nonmonotone generalized Nash equilibrium problems that exhibit symmetric interactions among the agents, which are known to be potential. As may happen in practical cases, however, we envision a scenario in which the formal expression of the underlying potential function is not available, and we design a semi-decentralized Nash equilibrium seeking algorithm. In the proposed two-layer scheme, a coordinator iteratively integrates the (possibly noisy and sporadic) agents' feedback to learn the pseudo-gradients of the agents, and then design personalized incentives for them. On their side, the agents receive those personalized incentives, compute a solution to an extended game, and then return feedback measurements to the coordinator. In the stationary setting, our algorithm returns a Nash equilibrium in case the coordinator is endowed with standard learning policies, while it returns a Nash equilibrium up to a constant, yet adjustable, error in the time-varying case. As a motivating application, we consider the ridehailing service provided by several companies with mobility as a service orchestration, necessary to both handle competition among firms and avoid traffic congestion, which is also adopted to run numerical experiments verifying our results., arXiv admin note: text overlap with arXiv:2111.03854

We consider quadratic, nonmonotone generalized Nash equilibrium problems with symmetric interactions among the agents, which are known to be potential. As may happen in practical cases, we envision a scenario in which an explicit expression of the underlying potential function is not available, and we design a two-layer Nash equilibrium seeking algorithm. In the proposed scheme, a coordinator iteratively integrates the noisy agents' feedback to learn the pseudo-gradients of the agents, and then design personalized incentives for them. On their side, the agents receive those personalized incentives, compute a solution to an extended game, and then return feedback measures to the coordinator. We show that our algorithm returns an equilibrium in case the coordinator is endowed with standard learning policies, and corroborate our results on a numerical instance of a hypomonotone game.

This paper considers the problem of quantum compilation from an optimization perspective by fixing a circuit structure of CNOTs and rotation gates then optimizing over the rotation angles. We solve the optimization problem classically and consider algorithmic tools to scale it to higher numbers of qubits. We investigate stochastic gradient descent and two sketch-and-solve algorithms. For all three algorithms, we compute the gradient efficiently using matrix-vector instead of matrix-matrix computations. Allowing for a runtime on the order of one hour, our implementation using either sketch-and-solve algorithm is able to compile 9 qubit, 27 CNOT circuits; 12 qubit, 24 CNOT circuits; and 15 qubit, 15 CNOT circuits. Without our algorithmic tools, standard optimization does not scale beyond 9 qubit, 9 CNOT circuits, and, beyond that, is theoretically dominated by barren plateaus., 10 pages, 4 figures, 1 table

Equipping current decision-making tools with notions of fairness, equitability, or other ethically motivated outcomes, is one of the top priorities in recent research efforts in machine learning, AI, and optimization. In this paper, we investigate how to allocate limited resources to {locally interacting} communities in a way to maximize a pertinent notion of equitability. In particular, we look at the dynamic setting where the allocation is repeated across multiple periods (e.g., yearly), the local communities evolve in the meantime (driven by the provided allocation), and the allocations are modulated by feedback coming from the communities themselves. We employ recent mathematical tools stemming from data-driven feedback online optimization, by which communities can learn their (possibly unknown) evolution, satisfaction, as well as they can share information with the deciding bodies. We design dynamic policies that converge to an allocation that maximize equitability in the long term. We further demonstrate our model and methodology with realistic examples of healthcare and education subsidies design in Sub-Saharian countries. One of the key empirical takeaways from our setting is that long-term equitability is fragile, in the sense that it can be easily lost when deciding bodies weigh in other factors (e.g., equality in allocation) in the allocation strategy. Moreover, a naive compromise, while not providing significant advantage to the communities, can promote inequality in social outcomes., 12 pages, 7 figures

We propose a novel variational method for solving the sub-graph isomorphism problem on a gate-based quantum computer. The method relies (1) on a new representation of the adjacency matrices of the underlying graphs, which requires a number of qubits that scales logarithmically with the number of vertices of the graphs; and (2) on a new Ansatz that can efficiently probe the permutation space. Simulations are then presented to showcase the approach on graphs up to 16 vertices, whereas, given the logarithmic scaling, the approach could be applied to realistic sub-graph isomorphism problem instances in the medium term., Comment: 30 pages, 14 figures

This paper leverages a framework based on averaged operators to tackle the problem of tracking fixed points associated with maps that evolve over time. In particular, the paper considers the Krasnosel'skii-Mann method in a settings where: (i) the underlying map may change at each step of the algorithm, thus leading to a "running" implementation of the Krasnosel'skii-Mann method; and, (ii) an imperfect information of the map may be available. An imperfect knowledge of the maps can capture cases where processors feature a finite precision or quantization errors, or the case where (part of) the map is obtained from measurements. The analytical results are applicable to inexact running algorithms for solving optimization problems, whenever the algorithmic steps can be written in the form of (a composition of) averaged operators; examples are provided for inexact running gradient methods and the forward-backward splitting method. Convergence of the average fixed-point residual is investigated for the non-expansive case; linear convergence to a unique fixed-point trajectory is showed in the case of inexact running algorithms emerging from contractive operators.

This is the write-up of the talk I gave at the 23rd International Symposium on Mathematical Programming (ISMP) in Bordeaux, France, July 6th, 2018. The talk was a general overview of the state of the art of time-varying, mainly convex, optimization, with special emphasis on discrete-time algorithms and applications in energy and transportation. This write-up is mathematically correct, while its style is somewhat less formal than a standard paper., Comment: 10 pages, v2 corrects a typo in assumption 4

Devising efficient algorithms to solve continuously-varying strongly convex optimization programs is key in many applications, from control systems to signal processing and machine learning. In this context, solving means to find and track the optimizer trajectory of the continuously-varying convex optimization program. Recently, a novel prediction-correction methodology has been put forward to set up iterative algorithms that sample the continuously-varying optimization program at discrete time steps and perform a limited amount of computations to correct their approximate optimizer with the new sampled problem and predict how the optimizer will change at the next time step. Prediction-correction algorithms have been shown to outperform more classical strategies, i.e., correction-only methods. Typically, prediction-correction methods have asymptotic tracking errors of the order of $h^2$, where $h$ is the sampling period, whereas classical strategies have order of $h$. Up to now, Prediction-correction algorithms have been developed in the primal space, both for unconstrained and simply constrained convex programs. In this paper, we show how to tackle linearly constrained continuously-varying problem by prediction-correction in the dual space and we prove similar asymptotic error bounds as their primal versions., 14 pages, 5 figures; updated version of v1 with corrected typos and new simulations

Devising efficient algorithms that track the optimizers of continuously varying convex optimization problems is key in many applications. A possible strategy is to sample the time-varying problem at constant rate and solve the resulting time-invariant problem. This can be too computationally burdensome in many scenarios. An alternative strategy is to set up an iterative algorithm that generates a sequence of approximate optimizers, which are refined every time a new sampled time-invariant problem is available by one iteration of the algorithm. These types of algorithms are called running. A major limitation of current running algorithms is their key assumption of strong convexity and strong smoothness of the time-varying convex function. In addition, constraints are only handled in simple cases. This limits the current capability for running algorithms to tackle relevant problems, such as $\ell_1$-regularized optimization programs. In this paper, these assumptions are lifted by leveraging averaged operator theory and a fairly comprehensive framework for time-varying convex optimization is presented. In doing so, new results characterizing the convergence of running versions of a number of widely used algorithms are derived., Comment: 30 pages, 2 figures -- version 3: add three new sections with additional results and background material

We devise a distributed asynchronous stochastic epsilon-gradient-based algorithm to enable a network of computing and communicating nodes to solve a constrained discrete-time time-varying stochastic convex optimization problem. Each node updates its own decision variable only once every discrete time step. Under some assumptions (among which, strong convexity, Lipschitz continuity of the gradient, persistent excitation), we prove the algorithm's asymptotic convergence in expectation to an error bound whose size is related to the constant stepsize choice alpha, the variability in time of the optimization problem, and to the accuracy epsilon. Moreover, the convergence rate is linear. Then, we show how to compute locally stochastic epsilon-gradients that depend also on the time-varying noise probability density function (PDF) of the neighboring nodes, without requiring the neighbors to send such PDFs at each time step. We devise utility-based policies to allow each node to decide whether to send or not the most up-to-date PDF, which guarantee a given user-specified error level epsilon in the computation of the stochastic epsilon-gradient. Numerical simulations display the added value of the proposed approach and its relevance for estimation and control of time-varying processes and networked systems.