Indefinite Linearized Peaceman-Rachford Splitting Methods For Convex Programming

There are numerous important applications of two-block separable convex programming problems in science and engineering.The alternating direction method of multipliers(ADMM)and the Peaceman-Rachford splitting method(PRSM)are the classical algorithms to solve these problems.The convergence of PRSM can not be guaranteed only under the convexity of the objective function,but because of twice multiplier update,the numerical effect of PRSM is relatively better than ADMM.As we all know,the traditional ADMM and PRSM take the augmented Lagrangian function as the benefit function.When it is difficult to solve the subproblem,the linearization technique is widely used.On the basis of augmented Lagrangian function,by adding a semi-positive definite or positive definite proximal term,taking the newly generated function as the benefit function,then using the proximity operator can obtain the closed form solution of the benefit function in less time.However,when the weight of the proximity term is too large,it will lead to the decrease of the step size of the original problem and the slow improvement of the solution.Therefore,it is of great theoretical and practical value to study the improved PRSM with good numerical performance,convergence guarantee and indefinite proximal term.For the two-block convex optimization problem,using the ADMM and PRSM iterative scheme,combined with a variety of theories and technologies such as indefinite linearization,step adjustment strategy,inertial and substitution step,this paper designs several small amount of calculation and effective algorithms.Based on the proof framework of variational inequality,the convergent property of each algorithm is studied.The complexity and parameter sensitivity are analyzed.The feasibility and efficiency of these algorithms are verified by simulation and practical problems.The main work and innovations are as follows:Firstly,using the substitution step,a generalized proximal PRSM with substitution step is designed.First,the first dual variable update of the PRSM is added with a step size,then the second subproblem and the second dual variable update formula of the PRSM are rewritten by the generalized ADMM,and the second subproblem is indefinitely linearized in order to find a closed solution in a shorter time.The main contribution of the algorithm is that the value range of the second dual step is extended from(0,1)to(0,2),and the indefinite linearization is made,which can effectively improve the numerical results of the algorithm.The main difficulty lies in the proof of convergence.Here we add a substitution step.It can guarantee the global convergence and the convergence rate in ergodic sense.Secondly,using the inertial step,an inertial generalized proximal PRSM is proposed.The algorithm is divided into two steps.The first step is the inertial step,the second step is the generalized proximal PRSM step.The main contribution of the algorithm is that the value range of the second dual step is extended from(0,1)to(0,2).Under several mild assumptions,the global convergence of the algorithm is proved.Thirdly,combining the SCPRSM and the substitution step,a SCPRSM with substitution procedure is introduced.First,we conduct the SCPRSM step and then carry out the substitution step.The predicted sequence is generated by strictly contractive PRSM step,and the corrected sequence is generated by the substitution step.We find that the inertial step and the substitution step are equivalent in some sense,and we can prove the global convergence and the nonergodic convergence rate of the algorithm by using the variational inequality framework.We find that the influence of adaptive adjustment of inertial parameter or substitution parameter on the numerical effect is not much different from that of fixed constant.Finally,combining the SCPRSM and the inertial step,an inertial proximal SCPRSM is developed.The first step is the inertial step,the second step is the SCPRSM step.First,a prediction correction result is obtained by using the framework of variational inequality.Then,a necessary assumption is added to the inertial parameters.Next,we use inertial proximal point and fundamental inequalities to reduce and expand the result.The residual convergence,the object function value convergence and the global convergent properties of the algorithm for solving two-block separable convex problem are proved.The complexity of the algorithm is analyzed by using the best objective function and the residual values of the constraint.Finally,the optimal value of the linearization parameter is proved by a counterexample.Through the LASSO model,isotropic and anisotropic total variation denoising models,the numerical experiments of image carton texture decomposition and computer tomography,it can be seen that the improvement of numerical results by indefinite linearization,step adjustment strategy,inertial and substitution step is feasible.The proposed algorithms are very advantageous even compared with the more mature methods.The sensitivity analysis shows that the numerical performance of the introduced algorithms are very effective and robust.