A Full-newton Step Feasible Interior-point Algorithms For Linear Weighted Complementarity Problems

The weighted complementarity problem(WCP)is an important class of new optimization problems,which can reduce to the complementarity problem when the weight vector is zero.A large class of equilibrium problems in science and engineering can be modeled as the weighted complementarity models,even better than complementary model in some cases.Therefore,it is important to study the theory and algorithm of the weighted complementarity problem.Compared to the complementary problem,the existence of non-zero weight vector makes the theory and algorithm of the weighted complementary problem more complicated.So far,there are only a few papers and results about the weighted complementary problem.In this dissertation,we present full-Newton step feasible interior-point algorithms for solving the linear weighted complementarity problems(LWCP).The main contents are described as follows:1.A modified full-Newton step feasible interior-point algorithm is developed for solving the weight complementarity problem over non-negative orthant.This algorithm uses full-modified-Newton step and avoids the linear search,which simplifies the iteration process.We analyze the strict feasibility and polynomial-time iteration complexity of the algorithm.Preliminary numerical results for solving the linear weighted complementarity problem illustrate the validity of the algorithm.2.Based on a kernel function,a full-Newton step feasible interior-point method is presented for solving the linear weighted complementarity problem.The equivalent transformation of central path is introduced by using a local kernel function.Only one linear system of equations is required to be solved in each iteration,which saves computing time and memory.By choosing appropriate parameters in each iteration,we analyze the strict feasibility of the algorithm and show that the iteration complexity of the algorithm is polynomial.The numerical results illustrate that the efficiency of the algorithm.3.Based on a continuously differentiable function,we propose a new full-Newton step feasible interior-point algorithm for the weighted complementarity problem over non-negative orthant.This algorithm defines the proximity measure of iteration points to central path and avoids linear search at each iteration.Under suitable assumption,we analyze the strict feasibility and show that the iteration complexity of the algorithm is as good as the best-known polynomial time complexity for linear optimization.We analyze the numerical results of the algorithm for solving the linear weighted complementarity problem.The results illustrate the efficiency of the algorithm and the effect of different parameter values on the algorithm iteration.