| 李卫滑,张明望,周意元.$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). |
|
| 摘要点击次数: 2839 |
| 全文下载次数: 3905 |
| 中文摘要: |
| 作为最有效的内点算法之一, 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阅读器 |
