Algorithm Study On Variational Inequality Problem And Nonconvex Nonsmooth Problems With Special Structure

Recently,a large number of variational inequality problem and nonconvex nons-mooth optimization problems with special structure have drawn great attention among traffic,signal and image processing,machine learning.Of special interest are the prob-lems of separable structured variational inequality problem and difference-of-convex(DC)optimization problems.According to the structure and property of these problems,such as large scale,DC structure,linear constaint and separable objective function,how to design simple but efficient methods has thus becomes a hot research direction.This thesis is mainly focuson on the alternating direction method of multipliers(ADMM),prediction-correction method,difference-of-convex algorithm(DCA),stochastic vari-ance reduction strategy and Moreau enevelop function to design some suitable methods for solving these special problems.The main contribution and novelty of this thesis are mainly reflected in three aspects.1.We propose an alternating projection based modified projection-correction method(AP-MPC)for solving structured variational inequality problem and estab-lish its global convergence under some sutiable conditons.At each iteration,AP-MPC uses Armijo line search and alternating projection technique to generate the prediction point,and then gets the next iterate point by some minor computations.AP-MPC over-comes the computational diffculty of some existing proximal ADMM type methods.For instance,the solving of two implicit projection equations is released in AP-MPC.Furthermore,AP-MPC relaxes the Lipschitz continuity assumption of some existing alternating projetion based prediction-correction methods.The numerical experiments on traffic equilibrium problem,separable,convex and quadratic programming and cali-brating least-square convariance matrix prblem show the efficiency of AP-MPC.2.We propose a hybrid Bregman alternating direction method of multipliers(H-BADMM)for sloving the linearly constrained DC optimization problems.On the one hand,H-BADMM combines the subgradient step and proxiaml step to evaluate the concave part,and utilizes extrapolation technique to handle the nonsmooth function part.We use the above mentioned strategies for possible acceleration of the existing method,difference-of-convex based Bregman ADMM(BADMM-DCA for short).On the other hand,by Kurdyka-?ojasiewicz(K?)property and other suitable conditions,we establish the convergence theorem of H-BADMM,which relaxes the Lipschitz continuity assumption of BADMM-DCA on the concave part.Futhermore,we present the numerical experiments on total variation image restoration problem and the least squares problem with l_1-2regularization to show the efficiency of H-BADMM.3.Based on Stochastic Path-Integrated Differential Estimato R(SPIDER),we pro-pose a stochastic variance reduction proximal DCA(SVRPDCA)for solving a large scale difference-of-convex optimziation problem.Then we establish the gradient com-plexity of SVRPDCA to obtain the?-critical point of this problem.Then,based on the Moreau enevelop approximation technique and SVRPDCA,we propose a modified stochastic proximal DCA(MSPDCA for short)for solving a class of nonconvex nons-mooth problem,whose objective function be written as the sum of a smooth function,a convex nonsmooth function,and a nonconvex nonsmooth function.A notable ad-vantage is that SVRPDCA and MSPDCA have better gradient complexity than that of some existing stochastic DCA type methods.Preliminary numerical experiments on non-negative sparse principal component analysis show the efficiency of the proposed methods.