<p>We present the stochastic origin Frank–Wolfe method, which is a special case of the block-coordinate Frank–Wolfe algorithm, applied to the problem of finding equilibrium flow distributions. We refer to existing theoretical convergence guarantees for generalized coordinate Frank–Wolfe methods and extend the analysis by providing a convergence proof for a batched version of the block-coordinate Frank–Wolfe algorithm, which was not covered in the original work. We demonstrate the practical effectiveness of our approach through experimental results. In particular, our findings show that the proposed method significantly outperforms the classical Frank–Wolfe algorithm and its variants on large-scale datasets. On smaller datasets, the stochastic origin Frank–Wolfe method remains effective, though the performance gap relative to classical methods becomes less pronounced. In such cases, there is a trade-off between solution quality, iteration time complexity, and memory usage. Bibliography: 16 titles. Illustrations: 3 figures.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

STOCHASTIC ORIGIN FRANK–WOLFE METHOD FOR TRAFFIC ASSIGNMENT

  • Igor Ignashin,
  • Demyan Yarmoshik,
  • Andrei Raigorodskii

摘要

We present the stochastic origin Frank–Wolfe method, which is a special case of the block-coordinate Frank–Wolfe algorithm, applied to the problem of finding equilibrium flow distributions. We refer to existing theoretical convergence guarantees for generalized coordinate Frank–Wolfe methods and extend the analysis by providing a convergence proof for a batched version of the block-coordinate Frank–Wolfe algorithm, which was not covered in the original work. We demonstrate the practical effectiveness of our approach through experimental results. In particular, our findings show that the proposed method significantly outperforms the classical Frank–Wolfe algorithm and its variants on large-scale datasets. On smaller datasets, the stochastic origin Frank–Wolfe method remains effective, though the performance gap relative to classical methods becomes less pronounced. In such cases, there is a trade-off between solution quality, iteration time complexity, and memory usage. Bibliography: 16 titles. Illustrations: 3 figures.