Random constraint sampling and duality for convex optimization

Abstract

We are interested in solving convex optimization problems with large numbers of constraints. Randomized algorithms, such as random constraint sampling, have been very successful in giving nearly optimal solutions to such problems. In this paper, we combine random constraint sampling with the classical primal-dual algorithm for convex optimization problems with large numbers of constraints, and we give a convergence rate analysis. We then report numerical experiments that verify the effectiveness of this algorithm.

Substantially revised draft in preparation, with much stronger results

References in corpus (5)

• Proximal Stochastic Dual Coordinate Ascent
• Fast Stochastic Alternating Direction Method of Multipliers
• Accelerated Proximal Stochastic Dual Coordinate Ascent for Regularized Loss Minimization
• On the Efficiency of Random Permutation for ADMM and Coordinate Descent
• Online Stochastic Optimization with Multiple Objectives