Path-following algorithms for monotone weighted complementarity problems

Number of views: 13
  • 分享到:

摘要:

加权互补问题是线性互补问题的推广模型,具有重要的应用背景.分析了加权互补问题的中心路径及其邻域,基于新定义的邻域,提出了求解单调加权互补问题的一个路径跟踪算法.取邻域中一点为初始点,证明了算法的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.

作者:

韩平 刘长河 尚有林

Han Ping;Liu Changhe;Shang Youlin(School of Mathematics and Statistics,Henan University of Science and Technology,Luoyang 471023,China)

机构地区:

河南科技大学数学与统计学院

出处:

《betway官方app 学报:自然科学版》 CAS 北大核心 2018年第4期120-124,共5页

基金:

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

关键词:

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

monotone weighted complementarity problems path-following algorithm central path wide neiglaborhood polynomial complexity

分类号:

O221.2 [理学—运筹学与控制论]


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

Baidu
map