摘要
基于一类带有参数θ的新方向,提出了求解单调线性互补问题的宽邻域路径跟踪内点算法,且当θ=1时即为经典牛顿方向.当取θ为与问题规模n无关的常数时,算法具有O(nL)迭代复杂性,其中L是输入数据的长度,这与经典宽邻域算法的复杂性相同;当取θ=(n/βτ)^(1/2)时,算法具有O(n^(1/2)L)迭代复杂性,这里的β,τ是邻域参数,这与窄邻域算法的复杂性相同.这是首次研究包括经典宽邻域路径跟踪算法的一类内点算法,给出了统一的算法框架和收敛性分析方法.
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 θ.When the parameter θ=1,the new direction is exactly the classical Newton direction.The algorithms have O（nL） iteration complexity when the parameter θ is independent of the dimension n,which coincides with the best known iteration complexity for the classical wide neighborhood algorithms.When θ=（n/βτ）-（1/2）,the algorithm has O（n-（1/2）L） iteration complexity,the best iteration complexity obtained so far by any interior point method for solving linear complementarity problems,whereβ and τ 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.
出处
《运筹学学报》
CSCD
北大核心
2016年第1期43-53,共11页
Operations Research Transactions
基金
国家自然科学基金(Nos.11471102
11426091
61301229)
河南省高等学校重点科研项目(No.16A110012)
关键词
线性互补问题
内点法
路径跟踪算法
宽邻域
多项式复杂性
linear complementarity problem
interior-point method
path-following algorithm
wide neighborhood
polynomial complexity
