Homotopy Methods For Variational Inequality Problems

In this dissertation, homotopy methods for solving variational inequality problems are studied. For box constrained VIPs, ball constrained VIPs and as well as VIPs at general abstract convex sets, by using smooth approximations of their equivalent nonsmooth equations, smooth homotopy are constructed, and existence and convergence of smooth paths are proven under similar conditions with existing combined homotopy methods. The proposed homotopy methods have the same advantage with combined homotopy methods that convergence can be obtained under weak conditions and, nevertheless, it does not introduce in multiplier variables and hence is more efficient in cases that the projection function is easy to compute. Additionally, a new efficient algorithm for numerically tracing the combined homotopy path of the variational inequality problems is given, and its global convergence and polynomial complexity are proven under some conditions.Chapter 1 devotes to reviewing the history and development of the variational inequality problem and the homotopy method.In Chapter 2, by using the Gabriel-More smoothing function of the mid function, a smooth homotopy method for solving nonsmooth equation reformulation of bounded box constrained variational inequality problem VIP(l,u, F) is given. Without any monotonic-ity condition on the defining map F, for starting point chosen almost everywhere in R~n, existence and convergence of the homotopy pathway are proven. Nevertheless, it is also proven that, if the starting point is chosen to be an interior point of the box, the proposed homotopy method can also serve as an interior point method. The numerical results show the method is promising.Utilizing a similar Chen-Harker-Kanzow-Smale function to smooth Robinson's normal equation in Chapter 3, the author presents a smoothing homotopy method for solving ball constrained variational inequalities. Without any monotonicity condition on the defining map F, for the starting point chosen almost everywhere in R~n, existence and convergence of the homotopy pathway are proven. Numerical experiments illustrate the method is feasible and efficient.In Chapter 4, a smoothing homotopy method for solving the variational inequality problem on a general nonempty closed convex subset of R~n is proposed. The homotopy equation is constructed based on the smooth approximation to Robinson's normal equa- tion of variational inequality problem, where the smooth approximation function of the projection function belongs to the interior of the feasible set. Under a weak condition, which is needed for the existence of a solution to variational inequality problem, for the starting point chosen almost everywhere in R~n, existence and convergence of a smooth homotopy pathway are proved. Several numerical experiments indicate that the method is efficient.In Chapter 5, a new algorithm for tracing the combined homotopy path of the variational inequality problems is proposed, and its global convergence and polynomial complexity are established under some conditions. The residual control criteria, which ensures that the obtained iterative points are interior points, is given by the condition that ensures theβ-cone neighborhood to be included in the interior part of the feasible region. Hence, the algorithm avoids judging whether the iterative points are the interior points or not in every predictor step and corrector step so that the computation is reduced greatly. The preliminary numerical experiments demonstrate that the algorithm is efficient and promising.