李卫滑,张明望,周意元.$P_*(\kappa)$线性互补问题的Mehrotra型预估-校正算法[J].数学研究及应用,2012,32(3):297~312
$P_*(\kappa)$线性互补问题的Mehrotra型预估-校正算法
A Mehrotra-Type Predictor-Corrector Algorithm for $P_*(\kappa)$ Linear Complementarity Problems
投稿时间:2010-09-18  最后修改时间:2011-08-31
DOI:10.3770/j.issn:2095-2651.2012.03.004
中文关键词:  $P_*(\kappa)$线性互补问题  Mehrotra型预估-校正算法  多项式复杂性  内点算法.
英文关键词:$P_*(\kappa)$ linear complementarity problems  Mehrotra-type predictor-corrector algorithm  polynomial iteration complexity  interior point method.
基金项目:湖北省自然科学基金(Grant No.2008CDZ047).
作者单位
李卫滑 三峡大学理学院, 湖北 宜昌 443002 
张明望 三峡大学理学院, 湖北 宜昌 443002 
周意元 三峡大学理学院, 湖北 宜昌 443002 
摘要点击次数: 1572
全文下载次数: 2818
中文摘要:
      作为最有效的内点算法之一, Mehrotra型预估-校正算法作已成为众多优化软件包的核心算法. 2008年, Salahi等人对线性规划提出一种基于削减(cut)策略的Mehrotra型预估-校正算法.该算法在具有多项式复杂性的同时还保持了实际有效性.通过选择与Salahi文中不同的校正方向,本文将该算法推广到$P_*(\kappa)$线性互补问题,并证明了在最坏情况下新算法的迭代复杂性界为$O((1+4\kappa)(17+19\kappa)\sqrt{1+2\kappa}n^\frac{3}{2}\log\frac{(x^0)^\T s^0}{\varepsilon})$.数值实验验证了算法的可行性.
英文摘要:
      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.
查看全文  查看/发表评论  下载PDF阅读器