Mathematics

CLC number: O221

A Full-Newton Step Interior-Point Algorithm Based on a New Search Direction for P_*(κ)-Linear Complementarity Problem

基于新搜索方向求解P_*(κ)-线性互补问题的全牛顿步内点算法

¹ Department of Mathematics, Anhui Institute of Information Technology, Wuhu 241000, Anhui, China
² College of Science, China Three Gorges University, Yichang 443002, Hubei, China

^† Corresponding author. E-mail: zmwang@ctgu.edu.cn

Received: 15 July 2024

Abstract

In this paper, a full-Newton step interior-point algorithm is proposed for solving $P_{\mathrm{*}}\left(\kappa \right)$-linear complementarity problem based on a new search direction, which is an extension of Grimes' algorithm. It is proved that the number of iterations of the algorithm is $O\left(\sqrt[]{n}\left(\mathrm{1}+\mathrm{4}\kappa \right)\mathrm{l}\mathrm{o}\mathrm{g}\frac{n}{\epsilon }\right)$, which matches the best known iteration bound of the interior-point method for $P_{\mathrm{*}}\left(\kappa \right)$-linear complementarity problem. Some numerical results have proved the feasibility and efficiency of the proposed algorithm.

摘要

为了求解$P_{\mathrm{*}}\left(\kappa \right)$-线性互补问题，本文提出了一种基于新搜索方向的全牛顿内点算法。此算法是 Grimes 算法的扩展。研究证明，该算法的迭代次数为$O\left(\sqrt[]{n}\left(\mathrm{1}+\mathrm{4}\kappa \right)\mathrm{l}\mathrm{o}\mathrm{g}\frac{n}{\epsilon }\right)$，与已知的求解$P_{\mathrm{*}}\left(\kappa \right)$-线性互补问题的最佳迭代复杂度一致。一些数值结果证明了所提出的算法的可行性和有效性。