×

zbMATH — the first resource for mathematics

Local linear convergence of the alternating direction method of multipliers on quadratic or linear programs. (English) Zbl 1288.65086
The 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.

MSC:
65K05 Numerical mathematical programming methods
90C05 Linear programming
90C20 Quadratic programming
90C06 Large-scale problems in mathematical programming
Software:
ARPACK
PDF BibTeX Cite
Full Text: DOI