Non-Interior-Point Smoothing Algorithms For A Class Of Affine Variational Inequalities

The complementarity problem (CP) is an important branch in the field of mathematical programming, and it has closely connections with many subjects such as nonlinear programming, max-min problems, game theory and fixed point theory, and so on. The CP is a special case of the affine variational inequality problem (AVIP). After several-decade comprehensive research, a number of methods and relevant techiques for solving CP have been proposed. For examples, earier Lemeke algorithms and its various improved formulations; and some continuation methods presented recently, such as, Interior-Point Algorithms, Non-Interior-Point Algorithms, Smoothing Newton Algorithms , Non-smoothing Newton Algorithms, and so on. The smoothing algorithm is one of the most effective methods for various optimization problems. The main idea of this method is as follows: reformulate the CP as a system of parameterized smooth equations by using some smoothing function, and use some Newton-type method to solve the smooth equations iteratively and make the smoothing parameter reduce to zero so that a solution of the original problem can be found.In this dissertation, we propose a smoothing algorithm for solving a class of AVIPs. We reformulate the AVIP as a family of parameterized smooth equations by using a smoothing function and the KKT condtions of the AVIP, and then design an algorithm to solve this smooth equations iteratively and make the smoothing parameter reduce to zero so that a solution of the original problem can be found. Under the assumption that the AVIP has a solution, we prove that the iteration sequence generated by the proposed algorithm is bounded, and that the algorithm is globally convergent. Moreover, we show that the proposed algorithm can find a maximally complementary solution to the AVIP in a finite number of iterations under suitable assumptions.