  The Potts model has many applications. It is equivalent to some min-cut and
max-flow models. Primal-dual algorithms have been used to solve these problems.
Due to the special structure of the models, convergence proof is still a
difficult problem. In this work, we developed two novel, preconditioned, and
over-relaxed alternating direction methods of multipliers (ADMM) with
convergence guarantee for these models. Using the proposed preconditioners or
block preconditioners, we get accelerations with the over-relaxation variants
of preconditioned ADMM. The preconditioned and over-relaxed Douglas-Rachford
splitting methods are also considered for the Potts model. Our framework can
handle both the two-labeling or multi-labeling problems with appropriate block
preconditioners based on Eckstein-Bertsekas and Fortin-Glowinski splitting
techniques.

Optimization and Control