Local linear convergence of the alternating direction method of multipliers on quadratic or linear programs.

*(English)*Zbl 1288.65086The alternating direction method of multipliers is effective and scalable in solving large-scale convex optimization problems. This paper introduces a spectral analysis of the local transient convergence behavior of the alternating direction method of multipliers on a quadratic or linear program by modeling it as a matrix recurrence, and examines a particular splitting in which the inequality and equality constraints are separated. Bounds on the local behavior of a specific variation of the alternating direction method during the course of the iteration is established. The method is shown to pass through several regimes of four different types as it searches for the correct set of active constraints. When the method settles on the correct set of active constraints, convergence can be linear at a rate depending on the absolute value of the second largest eigenvalue of the matrix recurrence.

Reviewer: Hang Lau (MontrĂ©al)

##### MSC:

65K05 | Numerical mathematical programming methods |

90C05 | Linear programming |

90C20 | Quadratic programming |

90C06 | Large-scale problems in mathematical programming |