Primal-dual proximal bundle and conditional gradient methods for convex problems

• 成果类型: Article; Early Access
• 署名作者: Liang, Jiaming
• 署名单位: University of Rochester; University of Rochester
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-025-02307-z
• 发表日期: 2025-12-01
• 关键词: Convex nonsmooth composite optimization; saddle-point problem; proximal bundle method; Conditional gradient method; iteration-complexity; Primal-dual convergence; UNIFIED ANALYSIS; optimization; CONVERGENCE

摘要

This paper studies the primal-dual convergence and iteration-complexity of proximal bundle methods for solving nonsmooth problems with convex structures. More specifically, we develop a family of primal-dual proximal bundle methods for solving convex nonsmooth composite optimization problems and establish the iteration-complexity in terms of a primal-dual gap. We also propose a class of proximal bundle methods for solving convex-concave nonsmooth composite saddle-point problems and establish the iteration-complexity to find an approximate saddle-point. This paper places special emphasis on the primal-dual perspective of the proximal bundle method. In particular, we discover an interesting duality between the conditional gradient method and the cutting-plane scheme used within the proximal bundle method. Leveraging this duality, we further develop novel variants of both the conditional gradient method and the cutting-plane scheme. Additionally, we report numerical experiments to demonstrate the effectiveness and efficiency of the proposed proximal bundle methods in comparison with the subgradient method for solving a regularized matrix game.