用于最小化异质组合的普遍最优原始对偶方法

《IMA Journal of Numerical Analysis》：A universally optimal primal–dual method for minimizing heterogeneous compositions

　　

摘要

本文提出了一种针对复合形式的凸最小化问题的通用算法，其形式为 $g_0(x)+h(g_1(x),\dots ,g_m(x))+u(x)$?。我们允许每个 $g_j$ 独立地从非光滑利普希茨性质变化到光滑性质，以及从凸性变化到强凸性，其描述方式涉及霍尔德连续梯度（H?lder continuous gradients）和一致凸性（uniform convexity）等概念。需要注意的是，尽管目标函数由这些具有结构化特征的异质组件组合而成，但它整体上并不一定具备光滑性、利普希茨性或除凸性之外的任何有利结构。尽管如此，我们仍然提供了一个在访问每个 $g_j$? 的（次）梯度预言机方面具有通用最优性的方法。使得我们的最优通用分析得以实现的关键洞察和核心技术贡献是构造了两个新的常数——近似对偶聚合光滑性和强凸性——它们将每种异质结构的优势整合为可分析的单一量。作为一个关键应用，通过将 $h$ 固定为非正指示函数，该模型可以直接捕捉 $g_0(x)+u(x)$ 在 $g_j(x)\le 0$? 约束下的功能性约束最小化问题。特别地，我们的算法和分析直接受到 Zhang 和 Lan 的光滑约束最小化方法的启发，因此恢复了并推广了他们的加速保证。