大规模可分凸优化问题的自适应步随机原始对偶算法

An Adaptive Stochastic Primal-Dual Algorithm for Large Scale Separable Convex Optimization Problems

针对大规模可分凸优化问题,提出自适应步随机原始对偶算法。首先将此问题等价地转换为一个对偶变量可分离的鞍点问题,接着随机选择鞍点问题的对偶变量更新,并按照一定规则自适应选取原始对偶步,证明得到该算法迭代点的遍历序列按期望以O(1/N)的速率收敛。数值实验的结果表明该算法可以有效解决正电子发射断层成像问题。

For a class of large-scale separable convex optimization problems,an adaptive stochastic primal-dual algorithm is proposed.The optimization problem is reformulated as a saddle point problem with separable dual variables.Then,the dual variables of the saddle point problem are randomly updated with adaptively selected step size.The adaptive stochastic primal-dual algorithm almost surely converges with rate O(1/N)in an ergodic sense.The results of numerical experiments indicate that the algorithm can effectively solve the problem of positron emission computed tomography.