|   | 
Details
   web
Records
Author Bravo, M.; Cominetti, R.; Pavez-Signe, M.
Title Rates of convergence for inexact Krasnosel'skii-Mann iterations in Banach spaces Type
Year 2019 Publication Mathematical Programming Abbreviated Journal Math. Program.
Volume 175 Issue 1-2 Pages (down) 241-262
Keywords Nonexpansive maps; Fixed point iterations; Rates of convergence; Evolution equations
Abstract We study the convergence of an inexact version of the classical Krasnosel'skii-Mann iteration for computing fixed points of nonexpansive maps. Our main result establishes a new metric bound for the fixed-point 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'kii-Mann 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 0025-5610 ISBN Medium
Area Expedition Conference
Notes WOS:000465626900008 Approved
Call Number UAI @ eduardo.moreno @ Serial 997
Permanent link to this record
 

 
Author Barrera, J.; Homem-De-Mello, T.; Moreno, E.; Pagnoncelli, B.K.; Canessa, G.
Title Chance-constrained problems and rare events: an importance sampling approach Type
Year 2016 Publication Mathematical Programming Abbreviated Journal Math. Program.
Volume 157 Issue 1 Pages (down) 153-189
Keywords Chance-constrained programming; Sample average approximation; Importance sampling; Rare-event simulation
Abstract We study chance-constrained problems in which the constraints involve the probability of a rare event. We discuss the relevance of such problems and show that the existing sampling-based 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 SAA-IS 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 0025-5610 ISBN Medium
Area Expedition Conference
Notes WOS:000375568400007 Approved
Call Number UAI @ eduardo.moreno @ Serial 613
Permanent link to this record
 

 
Author Ramirez-Pico, C.; Moreno, E.
Title Generalized Adaptive Partition-based Method for Two-Stage Stochastic Linear Programs with Fixed Recourse Type
Year 2022 Publication Mathematical Programming Abbreviated Journal Math. Program.
Volume to appear Issue Pages (down)
Keywords
Abstract We present a method to solve two-stage 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 first-stage variables, we formulate a second-stage 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 partition-based 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 0025-5610 ISBN Medium
Area Expedition Conference
Notes Approved
Call Number UAI @ eduardo.moreno @ Serial 1272
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 (down)
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 worst-case 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 0025-5610 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 non-expansive fixed-point iterations in normed spaces Type
Year 2022 Publication Mathematical Programming Abbreviated Journal Math. Program.
Volume Early Access Issue Pages (down)
Keywords Non-expansive maps; Fixed-point iterations; Error bounds; Convergence rates
Abstract This paper investigates optimal error bounds and convergence rates for general Mann iterations for computing fixed-points of non-expansive maps. We look for iterations that achieve the smallest fixed-point residual after n steps, by minimizing a worst-case bound parallel to x(n) – Tx(n)parallel to <= R-n derived from a nested family of optimal transport problems. We prove that this bound is tight so that minimizing R-n yields optimal iterations. Inspired from numerical results we identify iterations that attain the rate R-n = 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 worst-case residuals at every step n, with a tight bound R-n approximate to 4/n+4. We also determine the optimal Halpern stepsizes for affine non-expansive maps, for which we get exactly R-n = 1/n+1. Finally, we show that the best rate for the classical Krasnosel'skii-Mann 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