  We consider a family of parallel methods for constrained optimization based
on projected gradient descents along individual coordinate directions. In the
case of polyhedral feasible sets, local convergence towards a regular solution
occurs unconstrained in a reduced space, allowing for the computation of tight
asymptotic convergence rates by sensitivity analysis, this even when global
convergence rates are unavailable or too conservative. We derive linear
asymptotic rates of convergence in polyhedra for variants of the coordinate
descent approach, including cyclic, synchronous, and random modes of
implementation. Our results find application in stochastic optimization, and
with recently proposed optimization algorithms based on Taylor approximations
of the Newton step.
