Full-newton Step Interior Point Algorithm For Weighted Linear Complementarity

The weighted complementary problem(WCP)is obtained by generalizing the standard complementarity problem(CP).The WCP is a hot optimization problem,which consists of finding a pair of vectors belonging to the intersection of a manifold with a cone such that their product in a certain algebra,equals a given weight vector.Several equilibrium problems in economics can be formulated in a natural way as WCPs.For example,Fisher market equilibrium problem,which can be modeled as a nonlinear CP,can also be modeled as a linear WCP.The latter can be solved more efficiently than the former.With nonzero weight vectors,the theory of WCP becomes more complicated than the theory of CP.Therefore,there are few algorithms for the WCP.The purpose of this paper is to design the full-Newton step interior-point algorithm to solve the LWCP.The main results are as follows:1.We propose a full-Newton step feasible interior point algorithm for solving the LWCP based on the full-Newton search direction.We improve the interior-point algorithm and and apply it to the LWCP.By defining the central path,we design the full-Newtonian step interior point algorithm for solving the LWCP.We show the feasibility and the complexity of the algorithm.Finally,numerical experiment indicates the efficiency of this algorithm.2.We present an improved full-Newton step feasible interior point algorithm for LWCP by constructing a new equivalent substitution.Then we analyze the convergence and complexity of the algorithm based on the full-Newton step search direction.The algorithm can find the g-approximate solution of the problem only by O(log(?)/g)step.The algorithm is illustrated by some random numerical examples.3.We present an improved full-Newton step infeasible interior point algorithm for solving the LWCP.Each iteration of the algorithm consists of one feasibility step and several centering steps.Then the convergence and complexity of algorithm is given by theory analysis.The algorithm can find the g-approximate solution of the problem only after O(nlog(?)/g)iterations.Finally,some examples are given to illustrate the effectiveness of the algorithm.