| Records |
| 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 |
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 |
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 |
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 |
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 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 |
|
| 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 |
| |
|
| |
| 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 |
|
| 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 |
