一类水平线性互补问题的一个不可行内点算法的收敛性(英文)  

Convergence of an Infeasible Interior Point Algorithm for a Class of Horizontal Complementarity Problem 

作　　者：孟煦 胡昕昕 黄正海 

出　　处：《复旦学报（自然科学版）》1999年第2期247-253,共7页Journal of Fudan University：Natural Science

摘　　要：作为单调水平线性互补问题的推广，引入了Ｐ＊（κ）阵水平线性互补问题（简称Ｐ＊（κ）－ＨＬＣＰ）．证明了Ｙ．张的算法能被推广以解决Ｐ＊（κ）－ＨＬＣＰ问题，这个推广算法在运算过程中是独立于分类数κ的．如果这个算法的起始点是一对任意的正数，那么算法将达到Ｑ－线性收敛；如果起始点是一对足够大的正数，此算法经过至多Ｏ（（ｋ＋１）４ｎ２ｌｎ（（ｘ０）ｒｓ０）／ε次运算得到ε－逼近解，其中（ｘ０。A P (κ) matrices horizontal linear complementarity problem ( P (κ) HLCP) is introduced as a generalization of the monotone horizontal linear complementarity problem (HLCP). It is shown that the algorithm given by Y.Zhang can be extended to solve the P (κ) HLCP.The resulting algorithm is independent of the classification number κ for its implementation. If the algorithm starting from an arbitary positive point pair,then it converges Q linearly.If the algoritehm starting from a big enough positive point,then it can obtain an ε approximate solution in at most O(k+1) 4n 2ln((x 0) Ts 0)/ε) iterations,where (x 0,s 0) is the starting point pair.

关 键 词：线性互补问题 不可行内点算法 全局收敛 收敛性 

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