English

运筹学学报

• 运筹学 • 上一篇    下一篇

基于一类新方向的宽邻域路径跟踪内点算法

刘长河1  尚有林1,*  李锦睿1   

  1. 1. 河南科技大学数学与统计学院, 河南洛阳 471023
  • 收稿日期:2015-02-14 出版日期:2016-03-15 发布日期:2016-03-15
  • 通讯作者: 尚有林 mathshang@sina.com
  • 基金资助:

    国家自然科学基金(Nos. 11471102, 11426091, 61301229), 河南省高等学校重点科研项目(No. 16A110012)

Path-following interior point algorithms based on wide neighborhoods and a new class of directions

LIU Changhe1  SHANG Youlin1,*  LI Jinrui1   

  1. 1. School of Mathematics and Statistics, Henan University of Science and Technology, Luoyang 471023, Henan, China
  • Received:2015-02-14 Online:2016-03-15 Published:2016-03-15

PDF

556

被引次数

2

摘要：

基于一类带有参数theta的新方向, 提出了求解单调线性互补问题的宽邻 域路径跟踪内点算法, 且当theta=1时即为经典牛顿方向. 当取theta为与问题规模 n无关的常数时, 算法具有O(nL)迭代复杂性, 其中L是输入数据的长度, 这与经典宽邻 域算法的复杂性相同; 当取theta=\sqrt{n/\beta\tau}时, 算法具有O(\sqrt{n}L)迭代复杂性, 这里的\beta, \tau是邻域参数, 这与窄邻域算法的复杂性相同. 这是首次研究包括经典宽邻域路径跟踪算法的一类内点算法, 给出了统一的算法框架和收敛性分析方法.

关键词: 线性互补问题, 内点法, 路径跟踪算法, 宽邻域, 多项式复杂性

Abstract:

This paper presents a class of path-following interior point algorithms for the monotone linear complementarity problems based on wide neighborhoods and the new directions with a parameter \theta. When the parameter \theta=1, the new direction is exactly the classical Newton direction. The algorithms have O(nL) iteration complexity when the parameter \theta is independent of the dimension n, which coincides with the best known iteration complexity for the classical wide neighborhood algorithms. When \theta=\sqrt{n/\beta\tau}, the algorithm has O(\sqrt{n}L) iteration complexity, the best iteration complexity obtained so far by any interior point method for solving linear complementarity problems, where \beta and \tau are neighborhood parameters. To our knowledge this is the first time that a class of interior point algorithms including the classical wide neighborhood path-following algorithm is proposed and analyzed.

Key words: linear complementarity problem, interior-point method, path-following algorithm, wide neighborhood, polynomial complexity