P*(κ)线性互补问题的预估-校正内点算法

吉林大学学报(理学版)

P*(κ)线性互补问题的预估-校正内点算法

刘新泽^1,2, 刘红卫¹, 刘长河³

1. 西安电子科技大学数学系, 西安 710071； 2. 临沧高等师范专科学校数理系, 云南临沧 677000；3. 河南科技大学数学与统计学院, 河南洛阳 471003

收稿日期:2012-12-18 出版日期:2013-09-26 发布日期:2013-09-17
通讯作者: 刘红卫 E-mail:hwliu@mail.xidian.edu.cn

A PredictorCorrector InteriorPoint Algorithm forP*(κ)Linear Complementarity Problems

LIU Xinze^1,2, LIU Hongwei¹, LIU Changhe³

1. Department of Mathematics, Xidian University, Xi’an 710071, China; 2. Department ofMathematics and Science, Lincang Teachers’ College, Lincang 677000, Yunnan Province, China; 3. School ofMathematics and Statistics, Henan University of Science and Technology, Luoyang 471003, Henan Province, China

Received:2012-12-18 Online:2013-09-26 Published:2013-09-17
Contact: LIU Hongwei E-mail:hwliu@mail.xidian.edu.cn

摘要/Abstract

摘要：

通过修正大邻域跟踪算法的搜索方向, 提出一种新的求解P*(κ)线性互补问题(LCP)的不可行预估-校正内点算法, 并对算法进行了收敛性分析, 证明了该算法具有目前最好的理论复杂度O((1+κ)^5/2nL). 数值结果验证了算法的有效性.

关键词: 线性互补问题, 内点算法, 预估校正算法, 多项式复杂度

Abstract:

Based on modifying the search direction of neighborhoodfollowing interiorpoint algorithm for linear programming, a new infeasible predictorcorrector interiorpoint algorithm for P*(κ)linear complementarity problem (LCP) was presented. The facts that P*(κ)LCP is nonmonotone and the corresponding search directions is nonorthogonal make the convergence analysis of the presented algorithm more complex. We have obtained the best
known iteration complexity bound of the proposed algorithm so far, i.e., O((1+κ)^5/2nL), where κ is the handicap of the problem. Numerical results show that the algorithm is feasible.

Key words: linear complementarity problem, interiorpoint algorithm, predictorcorrector algorithm, polynomial complexity

中图分类号:

O221.1

刘新泽, 刘红卫, 刘长河. P*(κ)线性互补问题的预估-校正内点算法[J]. 吉林大学学报(理学版), 2013, 51(05): 789-794.

LIU Xinze, LIU Hongwei, LIU Changhe. A PredictorCorrector InteriorPoint Algorithm forP*(κ)Linear Complementarity Problems[J]. Journal of Jilin University Science Edition, 2013, 51(05): 789-794.

[1]	姜兴武, 姜舶洋, 王秀玉. 线性互补问题解存在的一个正则性条件[J]. 吉林大学学报(理学版), 2019, 57(3): 535-538.
[2]	甘小艇, 徐登国, 豆铨煜. 基于有限差分离散的模方法定价美式债券期权[J]. 吉林大学学报(理学版), 2018, 56(4): 837-844.
[3]	甘梦婷, 杨绍蓉, 李朝迁. BNekrasov矩阵线性互补问题的最优误差界[J]. 吉林大学学报(理学版), 2018, 56(2): 263-267.
[4]	王峰, 彭小平. B矩阵线性互补问题的误差界估计[J]. 吉林大学学报(理学版), 2018, 56(2): 257-262.
[5]	杨泰山, 姜舶洋. 隐线性互补问题解存在的一个条件[J]. 吉林大学学报(理学版), 2017, 55(02): 262-266.
[6]	刘铭, 王明明, 王秀玉. 线性互补问题解存在的一个条件[J]. 吉林大学学报(理学版), 2017, 55(01): 29-32.
[7]	王磊, 王秀玉. 广义线性互补问题解存在的条件[J]. 吉林大学学报(理学版), 2016, 54(06): 1277-1281.
[8]	姜兴武, 王明明, 王秀玉. P₀水平线性互补问题解的存在性[J]. 吉林大学学报(理学版), 2015, 53(04): 671-674.
[9]	杨泰山, 王秀玉, 姜舶洋. 混合线性互补问题解的存在条件[J]. 吉林大学学报(理学版), 2015, 53(02): 251-254.
[10]	魏潇, 张璐. 求解随机线性互补问题的半光滑投影牛顿算法[J]. 吉林大学学报(理学版), 2015, 53(01): 27-32.
[11]	薛冬梅, 姜舶洋, 王秀玉. P混合线性互补问题的同伦方法[J]. 吉林大学学报(理学版), 2014, 52(05): 933-936.
[12]	杨喜美, 刘红卫, 刘长河. 弧搜索内点算法[J]. 吉林大学学报(理学版), 2014, 52(04): 693-697.
[13]	雍龙泉, 刘三阳, 拓守恒, 邓方安, 高凯. 线性互补问题与绝对值方程的转化[J]. 吉林大学学报(理学版), 2014, 52(04): 682-686.
[14]	汪威威, 刘红卫, 毕红梅. 线性规划基于修正牛顿方向的宽邻域内点算法[J]. 吉林大学学报(理学版), 2014, 52(03): 408-412.
[15]	杨泰山, 姜兴武, 王秀玉. 线性互补问题解的存在性[J]. 吉林大学学报(理学版), 2013, 51(06): 1063-1067.