On complexity of a new Mehrotra-type interior point algorithm for P∗(κ) $P_{*}(\kappa )$ linear complementarity problems
Abstract In this paper, a variant of Mehrotra-type predictor–corrector algorithm is proposed for P∗(κ) $P_{*}(\kappa )$ linear complementarity problems. In this algorithm, a safeguard step is used to avoid small step sizes and a new corrector direction is adopted. The algorithm has polynomial iterat...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
SpringerOpen
2019-01-01
|
| Series: | Journal of Inequalities and Applications |
| Subjects: | |
| Online Access: | http://link.springer.com/article/10.1186/s13660-019-1954-5 |
| _version_ | 1828875921282564096 |
|---|---|
| author | Yiyuan Zhou Mingwang Zhang Zhengwei Huang |
| author_facet | Yiyuan Zhou Mingwang Zhang Zhengwei Huang |
| author_sort | Yiyuan Zhou |
| collection | DOAJ |
| description | Abstract In this paper, a variant of Mehrotra-type predictor–corrector algorithm is proposed for P∗(κ) $P_{*}(\kappa )$ linear complementarity problems. In this algorithm, a safeguard step is used to avoid small step sizes and a new corrector direction is adopted. The algorithm has polynomial iteration complexity and the iteration bound is O((14κ+11)(1+4κ)(1+2κ)nlog(x0)Ts0ε) $O ((14\kappa +11)\sqrt{(1+4 \kappa )(1+2\kappa )}~n\log \frac{(x^{0})^{T}s^{0}}{\varepsilon } )$. Some numerical results are reported as well. |
| first_indexed | 2024-12-13T08:09:33Z |
| format | Article |
| id | doaj.art-ecb489d6d1a5487793894998515f0fb1 |
| institution | Directory Open Access Journal |
| issn | 1029-242X |
| language | English |
| last_indexed | 2024-12-13T08:09:33Z |
| publishDate | 2019-01-01 |
| publisher | SpringerOpen |
| record_format | Article |
| series | Journal of Inequalities and Applications |
| spelling | doaj.art-ecb489d6d1a5487793894998515f0fb12022-12-21T23:54:15ZengSpringerOpenJournal of Inequalities and Applications1029-242X2019-01-012019111310.1186/s13660-019-1954-5On complexity of a new Mehrotra-type interior point algorithm for P∗(κ) $P_{*}(\kappa )$ linear complementarity problemsYiyuan Zhou0Mingwang Zhang1Zhengwei Huang2College of Science, China Three Gorges UniversityCollege of Science, China Three Gorges UniversityCollege of Economics and Management, China Three Gorges UniversityAbstract In this paper, a variant of Mehrotra-type predictor–corrector algorithm is proposed for P∗(κ) $P_{*}(\kappa )$ linear complementarity problems. In this algorithm, a safeguard step is used to avoid small step sizes and a new corrector direction is adopted. The algorithm has polynomial iteration complexity and the iteration bound is O((14κ+11)(1+4κ)(1+2κ)nlog(x0)Ts0ε) $O ((14\kappa +11)\sqrt{(1+4 \kappa )(1+2\kappa )}~n\log \frac{(x^{0})^{T}s^{0}}{\varepsilon } )$. Some numerical results are reported as well.http://link.springer.com/article/10.1186/s13660-019-1954-5Interior point algorithmP ∗ ( κ ) $P_{*}(\kappa )$ linear complementarity problemMehrotra-type algorithmPolynomial complexity |
| spellingShingle | Yiyuan Zhou Mingwang Zhang Zhengwei Huang On complexity of a new Mehrotra-type interior point algorithm for P∗(κ) $P_{*}(\kappa )$ linear complementarity problems Journal of Inequalities and Applications Interior point algorithm P ∗ ( κ ) $P_{*}(\kappa )$ linear complementarity problem Mehrotra-type algorithm Polynomial complexity |
| title | On complexity of a new Mehrotra-type interior point algorithm for P∗(κ) $P_{*}(\kappa )$ linear complementarity problems |
| title_full | On complexity of a new Mehrotra-type interior point algorithm for P∗(κ) $P_{*}(\kappa )$ linear complementarity problems |
| title_fullStr | On complexity of a new Mehrotra-type interior point algorithm for P∗(κ) $P_{*}(\kappa )$ linear complementarity problems |
| title_full_unstemmed | On complexity of a new Mehrotra-type interior point algorithm for P∗(κ) $P_{*}(\kappa )$ linear complementarity problems |
| title_short | On complexity of a new Mehrotra-type interior point algorithm for P∗(κ) $P_{*}(\kappa )$ linear complementarity problems |
| title_sort | on complexity of a new mehrotra type interior point algorithm for p∗ κ p kappa linear complementarity problems |
| topic | Interior point algorithm P ∗ ( κ ) $P_{*}(\kappa )$ linear complementarity problem Mehrotra-type algorithm Polynomial complexity |
| url | http://link.springer.com/article/10.1186/s13660-019-1954-5 |
| work_keys_str_mv | AT yiyuanzhou oncomplexityofanewmehrotratypeinteriorpointalgorithmforpkpkappalinearcomplementarityproblems AT mingwangzhang oncomplexityofanewmehrotratypeinteriorpointalgorithmforpkpkappalinearcomplementarityproblems AT zhengweihuang oncomplexityofanewmehrotratypeinteriorpointalgorithmforpkpkappalinearcomplementarityproblems |