首页 | 本学科首页   官方微博 | 高级检索  
     检索      

$P_*(\kappa)$线性互补问题的Mehrotra型预估-校正算法
引用本文:李卫滑,张明望,周意元.$P_*(\kappa)$线性互补问题的Mehrotra型预估-校正算法[J].数学研究及应用,2012,32(3):297-312.
作者姓名:李卫滑  张明望  周意元
作者单位:三峡大学理学院, 湖北 宜昌 443002;三峡大学理学院, 湖北 宜昌 443002;三峡大学理学院, 湖北 宜昌 443002
基金项目:湖北省自然科学基金(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 complementarity problems.The way of choosing corrector direction for our algorithm is different from theirs. The new algorithm has been proved to have an ο((1+4κ)(17+19κ) √(1+2κn)3/2log(x0Ts0/ε] worst case iteration complexity bound.An numerical experiment verifies the feasibility of the new algorithm.

关 键 词:P_*(κ)linear  complementarity  problems  Mehrotra-type  predictor-corrector  algo-  rithm  polynomial  iteration  complexity  interior  point  method.
收稿时间:2010/9/18 0:00:00
修稿时间:2011/8/31 0:00:00

A Mehrotra-Type Predictor-Corrector Algorithm for $P_*(\kappa)$ Linear Complementarity Problems
Weihua LI,Mingwang ZHANG and Yiyuan ZHOU.A Mehrotra-Type Predictor-Corrector Algorithm for $P_*(\kappa)$ Linear Complementarity Problems[J].Journal of Mathematical Research with Applications,2012,32(3):297-312.
Authors:Weihua LI  Mingwang ZHANG and Yiyuan ZHOU
Institution:College of Science, China Three Gorges University, Hubei 443002, P. R. China;College of Science, China Three Gorges University, Hubei 443002, P. R. China;College of Science, China Three Gorges University, Hubei 443002, P. R. China
Abstract: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_*(\kappa)$ linear complementarity problems. The way of choosing corrector direction for our algorithm is different from theirs. The new algorithm has been proved to have an ${\mathcal O}((1+4\kappa)(17+19\kappa)\sqrt{1+2\kappa}n^\frac{3}{2}\log \frac{(x^0)^\T s^0}{\varepsilon})$ worst case iteration complexity bound. An numerical experiment verifies the feasibility of the new algorithm.
Keywords:$P_*(\kappa)$ linear complementarity problems  Mehrotra-type predictor-corrector algorithm  polynomial iteration complexity  interior point method  
本文献已被 CNKI 等数据库收录!
点击此处可从《数学研究及应用》浏览原始摘要信息
点击此处可从《数学研究及应用》下载免费的PDF全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号