基于全牛顿求解P_(*)(κ)阵水平线性互补问题的内点算法  

A new Method for P_(κ) Horizontal Linear Complementarity Problem Base on Full Newton Step

作　　者：龚小玉[1] 丁雪峰[1] 王先甲[2] GONG Xiao-yu;DING Xue-feng;WANG Xian-jia(School of Economics and Management,China Three Gorges Uni vers计y,Yichang 443000,China;School of Economics and Management,Wuhan University,Wuhan 430072,China)

机构地区：[1]三峡大学经济与管理学院,湖北宜昌443000 [2]武汉大学经济与管理学院,湖北武汉430072

出　　处：《数学的实践与认识》2021年第7期206-212,共7页Mathematics in Practice and Theory

基　　金：国家自然科学基金(71771139);湖北省教育厅人文社会科学研究项目(16Q052)。

摘　　要：提出一种求解P_(*)(k)阵水平线性互补问题的全牛顿内点算法,全牛顿算法的优势在于每次迭代中不需要线性搜寻.当给定适当的中心路径邻域的阈值和更新势垒参数,证明算法中心邻域的全牛顿是局部二次收敛的,最后给出算法迭代复杂性O(√n)log(n+1+k)/εμ_(0).In this paper,we describe a new primal-dual path-following method for solving P_(k) horizontal linear complementarity problem base on full Newton step and we show that the polynomial complexity of the algorithm is O(√n)log(n+1+k)/εμ_(0).In each iteration the algorithm performs only full-Newton step with the advantage that no line search is required.We prove under a new and appropriate strategy of the threshold that defines the size of the neighborhood of the central-path and of the update barrier parameter that the proposed algorithm is well-defined and the full-Newton step to the central-path is locally quadratically convergent.

关 键 词：水平线性互补问题 内点算法 全牛顿步长 多项式复杂性 

分 类 号：O221[理学—运筹学与控制论]