A Class Of Variable Metric Over-relaxed Hybrid Proximal Extra-gradient Algorithm

The maximal monotone operator inclusion problem,as an extension of the KKT generalized equation for nonsmooth convex optimization,is a class of important problems in optimization,which has an extensive application in a diverse set of fields such as statistics,machine learning,signal and image processing,economics,and so on.In this dissertation,for the maximal monotone operator inclusion problem,we pro-pose a variable metric over-relaxed hybrid proximal extra-gradient algorithm.This algo-rithm,contrast to the existing hybrid proximal extra-gradient(HPE)algorithms,gener-ates the iteration sequences in terms of a novel inexact system and introduces an over-relaxed step-size in the extra-gradient step to improve the performance of algorithm.In particular,the extra-gradient step-size here can be set as a fixed constant,instead of the one obtained from a projection problem,which saves some extra computation work.For the proposed variable metric over-relaxed HPE algorithm,we establish its global conver-gence,pointwise O(1/(?))iteration complexity and O(1/k)weighted iteration complexity,and the local linear convergence rate under the metric subregularity of the maximal monotone operator.To the best of our knowledge,the metric subregularity of maximal monotone operators is the current weakest condition to guarantee the local linear convergence.Another contribution of this dissertation is to propose a primal-dual three term op-erator splitting algorithm and a corrected majorized semi-proximal alternating direction of multiplier method(ADMM)for multi-block nosmooth convex optimization problems,and show that they are the special cases of the proposed variable metric over-relaxed HPE algorithm.From the convergence results of the variable metric HPE algorithm,we obtain their global convergence,O(1/(?))pointwise iteration complexity and O(1/k)weighted iteration complexity for the KKT residuals,and local linear convergence under the met-ric subregularity of the KKT mapping.Very interestingly,a large class of primal-dual splitting algorithms in the literature(such as primal-dual hybrid gradient algorithms[34,49],Chambolle and Pock's primal-dual algorithms[18,19]and Condat's primal-dual operator[24,53])are shown to be the special case of our primal-dual three term operator splitting algorithm.In addition,we also verifly that a large class of primal operator s-plitting algorithms in the literature(such as the over-relaxed Korpelevich extra-gradient algorithm,Spingarn's operator splitting algorithms,and the non-cocoercive composite operator splitting algorithms)and He's prediction and correction algorithm[50]are the special cases of the fixed metric over-relaxed HPE algorithm.Thus,the proposed vari-able metric over-relaxed HPE algorithm not only offers a new insight into these splitting algorithms,but also provides a unified analysis framework for them.Last,we apply a special variable metric primal-dual splitting algorithm,i.e.,the corrected semi-proximal ADMM,to the nonnegative positive semidefinite(SDP)problems with linear equality and inequality constraints,and confirm its efficiency via numerical experiment.Numerical results indicate that the the corrected semi-proximal ADMM are comparable to the directly extended ADMM with step-size 1.618 and the ADMM3c[79].