| A Mehrotra-Type Predictor-Corrector Algorithm for $P_*(\kappa)$ Linear Complementarity Problems |
| Received:September 18, 2010 Revised:August 31, 2011 |
| Key Words:
$P_*(\kappa)$ linear complementarity problems Mehrotra-type predictor-corrector algorithm polynomial iteration complexity interior point method.
|
| Fund Project:Supported by the Natural Science Foundation of Hubei Province (Grant No.2008CDZ047). |
|
| Hits: 2838 |
| Download times: 3905 |
| 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. |
| Citation: |
| DOI:10.3770/j.issn:2095-2651.2012.03.004 |
| View Full Text View/Add Comment |
