水平线性互补问题的广义中心路径跟踪算法(英文)  

General Central Path Following Algorithm for Horizontal Linear Complementarity Problem

作　　者：陈东海[1] 张明望[1] 

机构地区：[1]三峡大学理学院,湖北宜昌443002

出　　处：《应用数学》2011年第2期304-311,共8页Mathematica Applicata

基　　金：Supported by the Natural Science Foundation of Hubei Province (2008CDZD47)

摘　　要：对水平线性互补问题提出了一种广义中心路径跟踪算法.任意的原始-对偶可行内点均可作为算法的初始点.每步迭代选择"仿射步"与"中心步"的凸组合为新的迭代方向,采用使对偶间隙尽可能减小的最大步长.算法的迭代复杂性为O(nL).In this paper, a general central path following algorithm for monotone horizontal linear complementarity problem is presented. Any primal-dual feasible interior point can be taken as initial point of the algorithm. At each iteration, we choose a new direction with the convex combination of the affine-scaling step and centering step, and use a pure Newton step with the largest possible reduction in complementarity measure （duality gap）. The algorithm maintains the O（√nL ） iteration comolexitv.

关 键 词：水平线性互补问题 内点方法 广义中心路径跟踪算法 多项式复杂性 

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