An Algorithmic Framework of Variable Metric Over-Relaxed Hybrid Proximal
  Extra-Gradient Method
  We propose a novel algorithmic framework of Variable Metric Over-Relaxed
Hybrid Proximal Extra-gradient (VMOR-HPE) method with a global convergence
guarantee for the maximal monotone operator inclusion problem. Its iteration
complexities and local linear convergence rate are provided, which
theoretically demonstrate that a large over-relaxed step-size contributes to
accelerating the proposed VMOR-HPE as a byproduct. Specifically, we find that a
large class of primal and primal-dual operator splitting algorithms are all
special cases of VMOR-HPE. Hence, the proposed framework offers a new insight
into these operator splitting algorithms. In addition, we apply VMOR-HPE to the
Karush-Kuhn-Tucker (KKT) generalized equation of linear equality constrained
multi-block composite convex optimization, yielding a new algorithm, namely
nonsymmetric Proximal Alternating Direction Method of Multipliers with a
preconditioned Extra-gradient step in which the preconditioned metric is
generated by a blockwise Barzilai-Borwein line search technique (PADMM-EBB). We
also establish iteration complexities of PADMM-EBB in terms of the KKT
residual. Finally, we apply PADMM-EBB to handle the nonnegative dual graph
regularized low-rank representation problem. Promising results on synthetic and
real datasets corroborate the efficacy of PADMM-EBB.
