
Barrera, J., HomemDeMello, T., Moreno, E., Pagnoncelli, B. K., & Canessa, G. (2016). Chanceconstrained problems and rare events: an importance sampling approach. Math. Program., 157(1), 153–189.
Abstract: We study chanceconstrained problems in which the constraints involve the probability of a rare event. We discuss the relevance of such problems and show that the existing samplingbased algorithms cannot be applied directly in this case, since they require an impractical number of samples to yield reasonable solutions. We argue that importance sampling (IS) techniques, combined with a Sample Average Approximation (SAA) approach, can be effectively used in such situations, provided that variance can be reduced uniformly with respect to the decision variables. We give sufficient conditions to obtain such uniform variance reduction, and prove asymptotic convergence of the combined SAAIS approach. As it often happens with IS techniques, the practical performance of the proposed approach relies on exploiting the structure of the problem under study; in our case, we work with a telecommunications problem with Bernoulli input distributions, and show how variance can be reduced uniformly over a suitable approximation of the feasibility set by choosing proper parameters for the IS distributions. Although some of the results are specific to this problem, we are able to draw general insights that can be useful for other classes of problems. We present numerical results to illustrate our findings.



Bravo, M., Cominetti, R., & PavezSigne, M. (2019). Rates of convergence for inexact Krasnosel'skiiMann iterations in Banach spaces. Math. Program., 175(12), 241–262.
Abstract: We study the convergence of an inexact version of the classical Krasnosel'skiiMann iteration for computing fixed points of nonexpansive maps. Our main result establishes a new metric bound for the fixedpoint residuals, from which we derive their rate of convergence as well as the convergence of the iterates towards a fixed point. The results are applied to three variants of the basic iteration: infeasible iterations with approximate projections, the Ishikawa iteration, and diagonal Krasnosels'kiiMann schemes. The results are also extended to continuous time in order to study the asymptotics of nonautonomous evolution equations governed by nonexpansive operators.



Cominetti, R., Dose, V., & Scarsini, M. (2022). The price of anarchy in routing games as a function of the demand. Math. Program., Early Access.
Abstract: The price of anarchy has become a standard measure of the efficiency of equilibria in games. Most of the literature in this area has focused on establishing worstcase bounds for specific classes of games, such as routing games or more general congestion games. Recently, the price of anarchy in routing games has been studied as a function of the traffic demand, providing asymptotic results in light and heavy traffic. The aim of this paper is to study the price of anarchy in nonatomic routing games in the intermediate region of the demand. To achieve this goal, we begin by establishing some smoothness properties of Wardrop equilibria and social optima for general smooth costs. In the case of affine costs we show that the equilibrium is piecewise linear, with break points at the demand levels at which the set of active paths changes. We prove that the number of such break points is finite, although it can be exponential in the size of the network. Exploiting a scaling law between the equilibrium and the social optimum, we derive a similar behavior for the optimal flows. We then prove that in any interval between break points the price of anarchy is smooth and it is either monotone (decreasing or increasing) over the full interval, or it decreases up to a certain minimum point in the interior of the interval and increases afterwards. We deduce that for affine costs the maximum of the price of anarchy can only occur at the break points. For general costs we provide counterexamples showing that the set of break points is not always finite.



Contreras, J. P., & Cominetti, R. (2022). Optimal error bounds for nonexpansive fixedpoint iterations in normed spaces. Math. Program., Early Access.
Abstract: This paper investigates optimal error bounds and convergence rates for general Mann iterations for computing fixedpoints of nonexpansive maps. We look for iterations that achieve the smallest fixedpoint residual after n steps, by minimizing a worstcase bound parallel to x(n) – Tx(n)parallel to <= Rn derived from a nested family of optimal transport problems. We prove that this bound is tight so that minimizing Rn yields optimal iterations. Inspired from numerical results we identify iterations that attain the rate Rn = O(1/n), which we also show to be the best possible. In particular, we prove that the classical Halpern iteration achieves this optimal rate for several alternative stepsizes, and we determine analytically the optimal stepsizes that attain the smallest worstcase residuals at every step n, with a tight bound Rn approximate to 4/n+4. We also determine the optimal Halpern stepsizes for affine nonexpansive maps, for which we get exactly Rn = 1/n+1. Finally, we show that the best rate for the classical Krasnosel'skiiMann iteration is Si (11 Omega(1/root n), and present numerical evidence suggesting that even extended variants cannot reach a faster rate.



RamirezPico, C., & Moreno, E. (2022). Generalized Adaptive Partitionbased Method for TwoStage Stochastic Linear Programs with Fixed Recourse. Math. Program., to appear.
Abstract: We present a method to solve twostage stochastic linear programming problems with fixed recourse when the uncertainty space can have either discrete or continuous distributions. Given a partition of the uncertainty space, the method is addressed to solve a discrete problem with one scenario for each element of the partition (subregions of the uncertainty space). Fixing firststage variables, we formulate a secondstage subproblem for each element, and exploiting information from the dual of these problems, we provide conditions that the partition must satisfy to obtain an optimal solution. These conditions provide guidance on how to refine the partition, iteratively approaching an optimal solution. The results from computational experiments show how the method automatically refines the partition of the uncertainty space in the regions of interest for the problem. Our algorithm is a generalization of the adaptive partitionbased method presented by Song & Luedtke for discrete distributions, extending its applicability to more general cases.

