论文标题
具有最佳迭代复杂性的近端束变体，用于大量代理
A proximal bundle variant with optimal iteration-complexity for a large range of prox stepsizes
论文作者
论文摘要
本文提出了一种近端捆绑变体，即放松的近端束（RPB）方法，用于求解凸非平滑复合材料优化问题。与其他近端捆绑型变体一样，RPB解决了一系列Prox束子问题，其目标函数是正规的复合切割平面模型。此外，RPB使用新型条件来决定是否执行不一定会产生功能值降低的严重或无效迭代。在凸面和强烈凸设置中，为RPB建立了最佳的迭代复杂性界限。据我们所知，这是第一次证明近端捆绑变体对于各种代理步骤尺寸都是最佳的。最后，还得出了RPB获得迭代的迭代结果的迭代复杂性结果，也得出了令人满意的实用终止标准，而不是接近最佳解决方案。
This paper presents a proximal bundle variant, namely, the relaxed proximal bundle (RPB) method, for solving convex nonsmooth composite optimization problems. Like other proximal bundle variants, RPB solves a sequence of prox bundle subproblems whose objective functions are regularized composite cutting-plane models. Moreover, RPB uses a novel condition to decide whether to perform a serious or null iteration which does not necessarily yield a function value decrease. Optimal iteration-complexity bounds for RPB are established for a large range of prox stepsizes, both in the convex and strongly convex settings. To the best of our knowledge, this is the first time that a proximal bundle variant is shown to be optimal for a large range of prox stepsizes. Finally, iteration-complexity results for RPB to obtain iterates satisfying practical termination criteria, rather than near optimal solutions, are also derived.
