在线咨询
中国工业与应用数学学会会刊
主管:中华人民共和国教育部
主办:西安交通大学
ISSN 1005-3085  CN 61-1269/O1

工程数学学报 ›› 2022, Vol. 39 ›› Issue (3): 413-427.doi: 10.3969/j.issn.1005-3085.2022.03.006

• • 上一篇    下一篇

线性权互补问题的改进全牛顿步不可行内点算法

迟晓妮1,   刘三阳2,   王博妲1   

  1. 1. 桂林电子科技大学数学与计算科学学院 广西自动检测技术与仪器重点实验室,桂林 541004
    2. 西安电子科技大学数学与统计学院,西安 710071
  • 出版日期:2022-06-15 发布日期:2022-08-15
  • 基金资助:
    国家自然科学基金 (11861026; 61877046);广西自然科学基金 (2021GXNSFAA220034);广西自动检测技术与仪器重点实验室基金 (YQ18112).

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

中图分类号: