First-order Algorithms For Some Special Generalized Variational Inequality Problems And Their Applications

The generalized variational inequality problem is a kind of widely used problem.It is an inequality problem with respect to two continuous mappings.When the two mappings in the generalized variational inequality problem satisfy various conditions,it can be transformed into different variational inequality type problems.In this thesis,we consider two variational inequality type problems,one is the inverse variational inequality problem,and the other is the separable convex optimization problem which can be transformed into a variational inequality problem under specific conditions.The two problems are widely used in real life.Therefore,it is of practical significance to study the first-order algorithms for solving them.In Chapter 1 and 2,the background of the two considered problems are introduced and some preliminaries are provided.In Chapter 3,we consider the inverse variational inequality problem,similar to the classical variational inequality problem,which is widely used in the fields of economy,management,transportation,communication and so on.The inverse variational inequality problems are mostly formed under the circumstances that the decisionmakers and managers want to seek some system equilibrium state from the perspective of policy control management.In mathematical form,the inverse variational inequality problem can be simply regarded as the variational inequality problem with the positions of variable and function swapped.When the function is a multivalued mapping,this exchange does not hold.In general,there is no explicit forms for the function/mapping in inverse variational inequalities,the values of function can only be evaluated or observed for given variables.In this thesis,we consider a theory named “market clearing” can be applied into the circumstance that the government/manager is making certain decision design,which can make the system quickly achieve a certain equilibrium.This theory is ignored in the existing research of inverse variational inequality.Specifically,a spatial price equilibrium control problem with a market clearance constraint forms an inverse variational inequality problem with a linear equality constraint.For the optimization problem with special separable structure,we consider using alternating direction method of multipliers to solve it,and in which case that the considered inverse variational inequality problem with separable structure becomes to a general variational inequality.Thus we design an alternating direction method of multipliers based algorithm for solving the general variational inequality formulation of structural inverse variational inequality,and analyze the convergence of the proposed algorithm.Further,in order to improve the efficiency of the algorithm,we consider reducing the computation cost of the general variational inequality subproblems.We also propose an improved version of the algorithm and present the corresponding convergence analysis.Finally,we apply the proposed algorithm and its improved version to the spatial price equilibrium control problem,and verify the effectiveness of the two proposed algorithms.In Chapter 4,we consider a class of differentiable convex optimization problems with linear constraints and separable structures.For this kind of problems,it can also be abstracted from many practical application scenarios.It is well known that differentiable convex optimization problems can be transformed into variational inequality problems,so solving such a class of differentiable convex optimization problems can be regarded as solving their equivalent variational inequality problems.In order to distinguish from the common two-block separable convex optimization problems,we study solving three-block separable convex optimization problems.Because alternating direction method of multipliers is one of the most popular algorithms for solving separable convex optimization problems,we once again consider using alternating direction method of multipliers to solve the three-block separable convex optimization problems.The classical alternating direction method of multipliers is only applicable for two-block separable convex optimization problems.If the classical alternating direction multiplier method is directly extended to the case where the objective function is divided into three blocks,the convergence of the algorithm cannot be guaranteed.Therefore,this thesis proposes a partial parallel splitting algorithm,which adopts a prediction-correction framework and combines the idea of Gauss-Seidel iteration and parallel computing,thus the convergence of the algorithm can be ensured and the cost of computation time can be reduced simultaneously.In addition,different from the existing partial parallel splitting algorithm in which the stepsize of the primal and dual variables in the correction step are set to be the same.This thesis sets the stepsize of the primal and dual variables in the correction step to be different.We present both ergodic and non-ergodic convergence rate analysis.Moreover,the linear convergence of the algorithm under additional assumptions are given.In order to further verify the effectiveness of the algorithm,we apply the algorithm for solving two class of application problems,one is image processing problem,the other is robust principal component analysis problem.For the two class of problems,we also investigate the influence of the ratio of the primal and dual correction stepsize for the numerical results.