Feasible Interior-point Algorithms Based On Algebraic Equivalent Transformation For Linear Weighted Complementarity Problems

The weighted complementarity problem is an important generalization of the complementarity problem.When the weight vector is a zero vector,the problem becomes a complementarity problem.The weighted complementarity problem can be used to model a large class of problems of science and engineering.The algorithms that establish the weighted complementarity models are more efficient than the complementarity models in some optimization problems.The non-zero weight vector makes the theories and algorithms of weighted complementarity problem more complicated,and there are few algorithms for solving the weighted complementarity problem.In this paper,we present the full-Newton step interior point algorithms for the linear weight complementarity problem.The concrete content is as follows:1.We design a full-Newton interior-point algorithm for solving a general linear weighted complementarity problem.Based on the Newton’s method,we solve the perturbation problem of the original problem.Followed by the algebraic equivalence transformation technique and a continuously differentiable kernel function,we obtain the search direction of the algorithm.The algorithm uses only one full-Newton step for each iteration,and no line search is required.The feasibility and convergence of the algorithm are analyzed,and the polynomial iteration complexity of the algorithm is proved.Finally,some numerical results verify the effectiveness of the algorithm.2.Based on a new algebraic equivalent transformation technique and a continuous differentiable kernel function,a new full-Newton step feasible interior-point algorithm is proposed for solving P_*(K)-linear weighted complementarity problems.By equivalently transforming the central path of the problem,full-Newton step is used along the search direction.The strict feasibility and convergence of the iteration points of the algorithm are analyzed.Some numerical examples show the effects of problem dimensions and update parameters on the iteration times and runtime of the algorithm.3.A predictor-corrector interior-point algorithm is proposed for P_*(K)-linear weighted complementarity problems.The algorithm takes one corrector step and one predictor step in a main iteration.The corrector step stays in the neighbourhood of the central path.In the corrector step,we take a full-Newton step.By choosing update parameters appropriately,the algorithm is proved to be strictly feasible and convergent at each iteration step with polynomial iteration complexity.Numerical results indicate the efficiency of the algorithm.