Coordinate-Update Algorithms can Efficiently Detect Infeasible Optimization Problems

Abstract

Coordinate update/descent algorithms are widely used in large-scale optimization due to their low per-iteration cost and scalability, but their behavior on infeasible or misspecified problems has not been much studied compared to the algorithms that use full updates. For coordinate-update methods to be as widely adopted to the extent so that they can be used as engines of general-purpose solvers, it is necessary to also understand their behavior under pathological problem instances. In this work, we show that the normalized iterates of randomized coordinate-update fixed-point iterations (RC-FPI) converge to the infimal displacement vector and use this result to design an efficient infeasibility detection method. We then extend the analysis to the setup where the coordinates are defined by non-orthonormal basis using the Friedrichs angle and then apply the machinery to decentralized optimization problems.

References in corpus (12)

• OSQP: An Operator Splitting Solver for Quadratic Programs
• ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates
• A Coordinate Descent Primal-Dual Algorithm with Large Step Size and Possibly Non Separable Functions
• COSMO: A conic operator splitting method for convex conic problems
• Circumcentering the Douglas--Rachford method
• A Random Block-Coordinate Douglas-Rachford Splitting Method with Low Computational Complexity for Binary Logistic Regression
• A new projection method for finding the closest point in the intersection of convex sets
• The Douglas-Rachford algorithm in the affine-convex case
• Douglas--Rachford Splitting and ADMM for Pathological Convex Optimization
• On the Asymptotic Behavior of the Douglas-Rachford and Proximal-Point Algorithms for Convex Optimization
• On the Minimal Displacement Vector of the Douglas-Rachford Operator
• Optimal rates of linear convergence of the averaged alternating modified reflections method for two subspaces