单调加权互补问题的路径跟踪算法  

Path-following algorithms for monotone weighted complementarity problems

作　　者：韩平 刘长河[1] 尚有林[1] Han Ping;Liu Changhe;Shang Youlin(School of Mathematics and Statistics,Henan University of Science and Technology,Luoyang 471023,China)

机构地区：[1]河南科技大学数学与统计学院,河南洛阳471023

出　　处：《河南师范大学学报（自然科学版）》2018年第4期120-124,共5页Journal of Henan Normal University(Natural Science Edition)

基　　金：国家自然科学基金(11471102;11701150);河南省高等学校重点基础研究项目(16A110012)

摘　　要：加权互补问题是线性互补问题的推广模型,具有重要的应用背景.分析了加权互补问题的中心路径及其邻域,基于新定义的邻域,提出了求解单调加权互补问题的一个路径跟踪算法.取邻域中一点为初始点,证明了算法的O(nL)迭代复杂性.当加权互补问题中的权向量w为零向量时,该中心路径及其邻域和线性互补问题中的定义相同,该算法即为求解线性互补问题的宽邻域路径跟踪算法.Weighted complementary problem is a generalization of the linear complementary problems,and has important application background.In this paper,we analyze the center path and its neighborhood for weighted complementarity problems,and propose a path-following algorithm for the monotone weighted complementarity problems based on the new defined neighborhood.Given a point in this neighborhood as the starting point,we prove that the iteration complexity of this algorithm is O（nL）.When the weight vector is equal to zero vector,the center path and its neighborhood are same with the definition in linear complementarity problems,and our algorithm becomes the path-following algorithm based on wide neighborhood for linear complementarity problem.

关 键 词：单调加权互补问题 路径跟踪算法 中心路径 宽邻域 多项式复杂性 

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