Asynchronous level bundle methods

• 成果类型: Article
• 署名作者: Iutzeler, Franck; Malick, Jerome; de Oliveira, Welington
• 署名单位: Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Universite PSL; MINES ParisTech
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-019-01414-y
• 发表日期: 2020
• 页码: 319-348
• 关键词: convex-optimization; DECOMPOSITION; Oracles

摘要

In this paper, we consider nonsmooth convex optimization problems with additive structure featuring independent oracles (black-boxes) working in parallel. Existing methods for solving these distributed problems in a general form are synchronous, in the sense that they wait for the responses of all the oracles before performing a new iteration. In this paper, we propose level bundle methods handling asynchronous oracles. These methods require original upper-bounds (using upper-models or scarce coordinations) to deal with asynchronicity. We prove their convergence using variational-analysis techniques and illustrate their practical performance on a Lagrangian decomposition problem.