A Mehrotra-Type Predictor-Corrector Algorithm for P_*(κ) Linear Complementarity Problems  

作　　者：Weihua LI Mingwang ZHANG Yiyuan ZHOU 

机构地区：[1]College of Science,China Three Gorges University,Hubei 443002,P.R.China

出　　处：《Journal of Mathematical Research with Applications》2012年第3期297-312,共16页数学研究及应用（英文版）

基　　金：Supported by the Natural Science Foundation of Hubei Province(Grant No.2008CDZ047)

摘　　要：Mehrotra-type predictor-corrector algorithm, as one of most efficient interior point methods, has become the backbones of most optimization packages. Salahi et al. proposed a cut strategy based algorithm for linear optimization that enjoyed polynomial complexity and maintained its efficiency in practice. We extend their algorithm to P. （~） linear complementar- ity problems. The way of choosing corrector direction for our algorithm is different from theirs： The new algorithm has been proved to have an O（（1 ＋ 4k）（17 ＋ 19k）√1＋2kn 3/2 log（x0）Ts0/ε） worst case iteration complexity bound. An numerical experiment verifies the feasibility of the new algorithm.Mehrotra-type predictor-corrector algorithm, as one of most efficient interior point methods, has become the backbones of most optimization packages. Salahi et al. proposed a cut strategy based algorithm for linear optimization that enjoyed polynomial complexity and maintained its efficiency in practice. We extend their algorithm to P. （~） linear complementar- ity problems. The way of choosing corrector direction for our algorithm is different from theirs： The new algorithm has been proved to have an O（（1 ＋ 4k）（17 ＋ 19k）√1＋2kn 3/2 log（x0）Ts0/ε） worst case iteration complexity bound. An numerical experiment verifies the feasibility of the new algorithm.

关 键 词：P＊（k） linear complementarity problems Mehrotra-type predictor-corrector algo- rithm polynomial iteration complexity interior point method. 

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