Association Journal of CSIAM
Supervised by Ministry of Education of PRC
Sponsored by Xi'an Jiaotong University
ISSN 1005-3085  CN 61-1269/O1

Chinese Journal of Engineering Mathematics ›› 2022, Vol. 39 ›› Issue (3): 413-427.doi: 10.3969/j.issn.1005-3085.2022.03.006

Previous Articles     Next Articles

Improved Full-Newton Step Infeasible Interior Point Algorithm for Weighted Linear Complementarity Problem

CHI Xiaoni1,   LIU Sanyang2,   WANG Boda1   

  1. 1. School of Mathematics and Computing Science, Guangxi Key Laboratory of Automatic Detecting Technology and Instruments, Guilin University of Electronic Technology, Guilin 541004
    2. School of Mathematics and Statistics, Xidian University, Xi'an 710071
  • Online:2022-06-15 Published:2022-08-15
  • Supported by:
    The National Natural Science Foundation of China (11861026; 61877046); the Natural Science Foundation of Guangxi (2021GXNSFAA220034); the Guangxi Key Laboratory of Automatic Detecting Technology and Instruments (YQ18112).

Abstract:

The weighted complementarity problem (WCP) aims at finding a pair of vectors belonging to the intersection of a manifold and a cone, such that the product of the vectors under a certain algebra equals a given weighted vector. As a nontrivial generalization of complementarity problems, WCP can be used to solve various equilibrium problems in science, economics and engineering, which in some cases may lead to highly efficient algorithms. Considering a weighted linear complementarity problem (WLCP) over the nonnegative orthant, an improved full-Newton step infeasible interior point algorithm is presented for its numerical solution. By extending a full-Newton infeasible interior-point algorithm for linear optimization, the perturbed problem of WLCP, its central path, and the induced Newton direction are introduced. The algorithm constructs strictly feasible iterates for a sequence of perturbed problems of WLCP. Each main iteration of the algorithm consists of one feasibility step and several central steps, which uses only full-Newton steps, and therefore it is not necessary to calculate the steplength; at each iteration, the algorithm reduces the feasibility residuals and the weight vector residuals at the same rate; based on the quadratic convergence result of the central step, a slightly wider neighborhood is provided for the feasibility step. The feasibility step, centering step and convergence are anaylzed. Then the algorithm is shown to possess global convergence and polynomial-time complexity. Finally, some numerical examples illustrate the efficiency of the proposed algorithm for solving WLCP.

Key words: weighted linear complementarity problem, full-Newton step, interior point algorithm, central path

CLC Number: