Bregman primal–dual first-order method and application to sparse semidefinite programming
提出一种带Bregman距离的Chambolle-Pock原始对偶算法新变体，通过线搜索自动选择步长，无需估计约束矩阵范数；应用于大规模稀疏半定规划的中心化问题，其Bregman近端算子计算成本仅相当于稀疏Cholesky分解。
Abstract We present a new variant of the Chambolle–Pock primal–dual algorithm with Bregman distances, analyze its convergence, and apply it to the centering problem in sparse semidefinite programming. The novelty in the method is a line search procedure for selecting suitable step sizes. The line search obviates the need for estimating the norm of the constraint matrix and the strong convexity constant of the Bregman kernel. As an application, we discuss the centering problem in large-scale semidefinite programming with sparse coefficient matrices. The logarithmic barrier function for the cone of positive semidefinite completable sparse matrices is used as the distance-generating kernel. For this distance, the complexity of evaluating the Bregman proximal operator is shown to be roughly proportional to the cost of a sparse Cholesky factorization. This is much cheaper than the standard proximal operator with Euclidean distances, which requires an eigenvalue decomposition.