| |
Records |
Links |
|
Author  |
Chambolle, A.; Contreras, J.P. |
|
| |
Title |
Accelerated Bregman Primal-Dual Methods Applied to Optimal Transport and Wasserstein Barycenter Problems |
Type |
|
| |
Year |
2023 |
Publication |
SIAM Journal on Mathematics of Data Science |
Abbreviated Journal |
SIMODS |
|
| |
Volume |
4 |
Issue |
4 |
Pages |
1369-1395 |
|
| |
Keywords |
primal-dual method; optimal transport; Wasserstein barycenter; saddle-point |
|
| |
Abstract |
This paper discusses the efficiency of Hybrid Primal-Dual (HPD) type algorithms to approximately solve discrete Optimal Transport (OT) and Wasserstein Barycenter (WB) problems, with and without entropic regularization. Our first contribution is an analysis showing that these methods yield state-of-the-art convergence rates, both theoretically and practically. Next, we extend the HPD algorithm with the linesearch proposed by Malitsky and Pock in 2018 to the setting where the dual space has a Bregman divergence, and the dual function is relatively strongly convex to the Bregman's kernel. This extension yields a new method for OT and WB problems based on smoothing of the objective that also achieves state-of-the-art convergence rates. Finally, we introduce a new Bregman divergence based on a scaled entropy function that makes the algorithm numerically stable and reduces the smoothing, leading to sparse solutions of OT and WB problems. We complement our findings with numerical experiments and comparisons. |
|
| |
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 |
2577-0187 |
ISBN |
|
Medium |
|
|
| |
Area |
|
Expedition |
|
Conference |
|
|
| |
Notes |
WOS:000978251900007 |
Approved |
|
|
| |
Call Number |
UAI @ alexi.delcanto @ |
Serial |
1809 |
|
| Permanent link to this record |
| |
|
| |
|
Author |
Contreras, J.P.; Bosch, P.; Varas, M.; Basso, F. |
|
| |
Title |
A New Genetic Algorithm Encoding for Coalition Structure Generation Problems |
Type |
|
| |
Year |
2020 |
Publication |
Mathematical Problems In Engineering |
Abbreviated Journal |
Math. Probl. Eng. |
|
| |
Volume |
2020 |
Issue |
|
Pages |
13 pp |
|
| |
Keywords |
|
|
| |
Abstract |
Genetic algorithms have proved to be a useful improvement heuristic for tackling several combinatorial problems, including the coalition structure generation problem. In this case, the focus lies on selecting the best partition from a discrete set. A relevant issue when designing a Genetic algorithm for coalition structure generation problems is to choose a proper genetic encoding that enables an efficient computational implementation. In this paper, we present a novel hybrid encoding, and we compare its performance against several genetic encoding proposed in the literature. We show that even in difficult instances of the coalition structure generation problem, the proposed approach is a competitive alternative to obtaining good quality solutions in reasonable computing times. Furthermore, we also show that the encoding relevance increases as the number of players increases. |
|
| |
Address |
[Contreras, Juan Pablo] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Santiago, Chile, Email: ju.contreras@alumnos.uai.cl; |
|
| |
Corporate Author |
|
Thesis |
|
|
| |
Publisher |
Hindawi Ltd |
Place of Publication |
|
Editor |
|
|
| |
Language |
English |
Summary Language |
|
Original Title |
|
|
| |
Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
|
| |
Series Volume |
|
Series Issue |
|
Edition |
|
|
| |
ISSN |
1024-123x |
ISBN |
|
Medium |
|
|
| |
Area |
|
Expedition |
|
Conference |
|
|
| |
Notes |
WOS:000530379800011 |
Approved |
|
|
| |
Call Number |
UAI @ eduardo.moreno @ |
Serial |
1141 |
|
| 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 |
Varas, M.; Basso, F.; Bosch, P.; Contreras, J.P.; Pezoa, R. |
|
| |
Title |
A horizontal collaborative approach for planning the wine grape harvesting |
Type |
|
| |
Year |
2022 |
Publication |
Operational Research |
Abbreviated Journal |
Oper. Res. |
|
| |
Volume |
22 |
Issue |
5 |
Pages |
4965-4998 |
|
| |
Keywords |
Wine industry; Harvesting planning; Horizontal collaboration; Cooperative game theory |
|
| |
Abstract |
Horizontal collaboration is a strategy that has increasingly been used for improving supply chain operations. In this paper, we analyze the benefits of using a collaborative approach when optimally planning the wine grape harvesting process. Particularly, we assess how labor and machinery collaborative planning impacts harvesting costs. We model cooperation among wineries as a coalitional game with transferable costs for which the characteristic function vector is computed by solving a new formulation for planning the wine grape harvesting. In order to obtain stable coalitions, we devise an optimization problem that incorporates both rationality and efficiency conditions and uses the Gini index as a fairness criterion. Focusing on an illustrative case, we develop several computational experiments that show the positive effect of collaboration in the harvesting process. Moreover, our computational results reveal that the results depend strongly on the fairness criteria used. The Gini index, for example, favors the formation of smaller coalitions compared to other fairness criteria such as entropy. |
|
| |
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 |
1109-2858 |
ISBN |
|
Medium |
|
|
| |
Area |
|
Expedition |
|
Conference |
|
|
| |
Notes |
WOS:000850030500001 |
Approved |
|
|
| |
Call Number |
UAI @ alexi.delcanto @ |
Serial |
1648 |
|
| Permanent link to this record |
