Records 
Author 
Barrera, J.; HomemDeMello, T.; Moreno, E.; Pagnoncelli, B.K.; Canessa, G. 
Title 
Chanceconstrained problems and rare events: an importance sampling approach 
Type 

Year 
2016 
Publication 
Mathematical Programming 
Abbreviated Journal 
Math. Program. 
Volume 
157 
Issue 
1 
Pages 
153189 
Keywords 
Chanceconstrained programming; Sample average approximation; Importance sampling; Rareevent simulation 
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. 
Address 
[Barrera, Javiera; Moreno, Eduardo] Univ Adolfo Ibanez, Fac Sci & Engn, Santiago, Chile, Email: javiera.barrera@uai.cl 
Corporate Author 

Thesis 

Publisher 
Springer Heidelberg 
Place of Publication 

Editor 

Language 
English 
Summary Language 

Original Title 

Series Editor 

Series Title 

Abbreviated Series Title 

Series Volume 

Series Issue 

Edition 

ISSN 
00255610 
ISBN 

Medium 

Area 

Expedition 

Conference 

Notes 
WOS:000375568400007 
Approved 

Call Number 
UAI @ eduardo.moreno @ 
Serial 
613 
Permanent link to this record 



Author 
Bravo, M.; Cominetti, R.; PavezSigne, M. 
Title 
Rates of convergence for inexact Krasnosel'skiiMann iterations in Banach spaces 
Type 

Year 
2019 
Publication 
Mathematical Programming 
Abbreviated Journal 
Math. Program. 
Volume 
175 
Issue 
12 
Pages 
241262 
Keywords 
Nonexpansive maps; Fixed point iterations; Rates of convergence; Evolution equations 
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. 
Address 
[Bravo, Mario] Univ Santiago Chile, Dept Matemat & Ciencia Comp, Alameda Libertador Bernardo Ohiggins 3363, Santiago, Chile, Email: mario.bravo.g@usach.cl; 
Corporate Author 

Thesis 

Publisher 
Springer Heidelberg 
Place of Publication 

Editor 

Language 
English 
Summary Language 

Original Title 

Series Editor 

Series Title 

Abbreviated Series Title 

Series Volume 

Series Issue 

Edition 

ISSN 
00255610 
ISBN 

Medium 

Area 

Expedition 

Conference 

Notes 
WOS:000465626900008 
Approved 

Call Number 
UAI @ eduardo.moreno @ 
Serial 
997 
Permanent link to this record 



Author 
Cominetti, R.; Dose, V.; Scarsini, M. 
Title 
The price of anarchy in routing games as a function of the demand 
Type 

Year 
2022 
Publication 
Mathematical Programming 
Abbreviated Journal 
Math. Program. 
Volume 
Early Access 
Issue 

Pages 

Keywords 
Nonatomic routing games; Price of anarchy; Affine cost functions; Variable demand 
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. 
Address 

Corporate Author 

Thesis 

Publisher 

Place of Publication 

Editor 

Language 

Summary Language 

Original Title 

Series Editor 

Series Title 

Abbreviated Series Title 

Series Volume 

Series Issue 

Edition 

ISSN 
00255610 
ISBN 

Medium 

Area 

Expedition 

Conference 

Notes 
WOS:000693858200001 
Approved 

Call Number 
UAI @ alexi.delcanto @ 
Serial 
1468 
Permanent link to this record 



Author 
Contreras, J.P.; Cominetti, R. 
Title 
Optimal error bounds for nonexpansive fixedpoint iterations in normed spaces 
Type 

Year 
2022 
Publication 
Mathematical Programming 
Abbreviated Journal 
Math. Program. 
Volume 
Early Access 
Issue 

Pages 

Keywords 
Nonexpansive maps; Fixedpoint iterations; Error bounds; Convergence rates 
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. 
Address 

Corporate Author 

Thesis 

Publisher 

Place of Publication 

Editor 

Language 

Summary Language 

Original Title 

Series Editor 

Series Title 

Abbreviated Series Title 

Series Volume 

Series Issue 

Edition 

ISSN 

ISBN 

Medium 

Area 

Expedition 

Conference 

Notes 
WOS:000805887100002 
Approved 

Call Number 
UAI @ alexi.delcanto @ 
Serial 
1577 
Permanent link to this record 



Author 
RamirezPico, C.; Moreno, E. 
Title 
Generalized Adaptive Partitionbased Method for TwoStage Stochastic Linear Programs with Fixed Recourse 
Type 

Year 
2022 
Publication 
Mathematical Programming 
Abbreviated Journal 
Math. Program. 
Volume 
to appear 
Issue 

Pages 

Keywords 

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. 
Address 

Corporate Author 

Thesis 

Publisher 

Place of Publication 

Editor 

Language 

Summary Language 

Original Title 

Series Editor 

Series Title 

Abbreviated Series Title 

Series Volume 

Series Issue 

Edition 

ISSN 
00255610 
ISBN 

Medium 

Area 

Expedition 

Conference 

Notes 

Approved 

Call Number 
UAI @ eduardo.moreno @ 
Serial 
1272 
Permanent link to this record 