A wide neighborhood predictor-infeasible corrector interior-point algorithm for linear optimization

1. Ai, W., Zhang, S.: An \(O(\sqrt{n}L)\) iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone LCP. SAIM J. Optim. 16(2), 400–417 (2005)

   Article  MathSciNet  Google Scholar 

2. Asadi, S., Mansouri, H., Darvay, Zs, Zangiabadi, M., Mahdavi-Amiri, N.: Large-neighborhood infeasible predictor-corrector algorithm for horizontal linear complementarity problems over Cartesian product of symmetric cones. J. Optim. Theory Appl. 180(3), 811–829 (2019)

   Article  MathSciNet  Google Scholar 

3. Feng, Z.Z.: A new \(O(\sqrt{n}L)\) iteration large update primal-dual interior-point method for second-order cone programming. Numer. Funct. Anal. Optim. 33, 397–414 (2012)

   Article  MathSciNet  Google Scholar 

4. Feng, Z., Fang, L.: A new \(O(\sqrt{n}L)\)-iteration predictor-corrector algorithm with wide neighborhood for semidefinite programming. J. Comput. Appl. Math. 256, 65–76 (2014)

   Article  MathSciNet  Google Scholar 

5. Jansen, B., Roos, C., Terlaky, T., Vial, J.-P.: Primal-dual algorithms for linear programming based on the logarithmic barrier method. J. Optim. Theory Appl. 83(1), 1–26 (1994)

   Article  MathSciNet  Google Scholar 

6. Karmarkar, N.K.: A new polynomial-time algorithm for linear programming. Combinatorica 4, 373–395 (1984)

   Article  MathSciNet  Google Scholar 

7. Kheirfam, B., Chitsaz, M.: Polynomial convergence of two higher order interior-point methods for \(P_*(\kappa )\)-LCP in a wide neighborhood of the central path. Period. Math. Hung. 76(2), 243–264 (2018)

   Article  Google Scholar 

8. Kheirfam, B., Haghighi, M.: A wide neighborhood interior-point algorithm for linear optimization based on a specific kernel function. Period. Math. Hung. 97(1), 94–105 (2019)

   Article  MathSciNet  Google Scholar 

9. Kheirfam, B.: A predictor-corrector infeasible-interior-point algorithm for semidefinite optimization in a wide neighborhood. Fundam. Inf. 152, 33–50 (2017)

   Article  MathSciNet  Google Scholar 

10. Kheirfam, B.: An arc-search infeasible interior point algorithm for HLCP in the \({\cal{N}}^-_{\infty }\) neighborhood of the central path. Int. J. Comput. Math. 94(12), 2271–2282 (2017)

    Article  MathSciNet  Google Scholar 

11. Li, Y., Terlaky, T.: A new class of large neighborhood path-following interior-point algorithms for semidefinite optimization with \({\cal{O}}\big (\sqrt{n}\log (\frac{tr(X^{0}S^{0})}{\varepsilon })\big )\) iteration complexity. SIAM J. Optim. 8, 2853–2875 (2010)

    Article  Google Scholar 

12. Liu, C.H., Huang, Y.Y., Shang, Y.L.: Polynomial convergence of primal-dual path-following algorithms for symmetric cone programming based on wide neighborhoods and a new class of directions. J. Oer. Res. Soc. China 5, 333–346 (2017)

    Article  MathSciNet  Google Scholar 

13. Liu, H., Yang, X., Liu, C.: A new wide neighborhood primal-dual infeasible-interior-point method for symmetric cone programming. J. Optim. Theory Appl. 158, 796–815 (2013)

    Article  MathSciNet  Google Scholar 

14. Liu, C.H., Wu, D., Shang, Y.L.: A new infeasible-interior-point algorithm based on wide neighborhoods for symmetric cone programming. J. Oper. Res. Soc. China 4, 147–165 (2016)

    Article  MathSciNet  Google Scholar 

15. Liu, C., Shang, Y., Han, P.: A new infeasible-interior-point algorithm for linear programming over symmetric cones. Acta Math. Appl. Sinica 33(3), 771–788 (2017)

    Article  MathSciNet  Google Scholar 

16. Lustig, I.J.: Feasible issues in a primal-dual interior-point method for linear programming. Math. Program. 49(1–3), 145–162 (1990)

    Article  Google Scholar 

17. Mizuno, S., Todd, M.J., Ye, Y.: On adaptive step primalual interior-point algorithms for linear programming. Math. Oper. Res. 18, 964–981 (1993)

    Article  MathSciNet  Google Scholar 

18. Peng, J., Roos, C., Terlaky, T.: Self-Regular Functions: A New Paradigm for Primal-Dual Interior-Point Methods. Princeton University Press, Princeton (2002)

    MATH  Google Scholar 

19. Potra, F.A.: The Mizuno–Todd–Ye algorithm in a larger neighborhood of the central path. Eur. J. Oper. Res. 143, 257–267 (2002)

    Article  MathSciNet  Google Scholar 

20. Potra, F.A.: Interior point methods for sufficient horizontal LCP in a wide neighborhood of the central path with best known iteration complexity. SIAM J. Optim. 24(1), 1–28 (2014)

    Article  MathSciNet  Google Scholar 

21. Roos, C., Terlaky, T., Vial, J.-Ph: Interior Point Methods for Linear Optimization. Springer Science, Heidelberg/Boston, (2006)

22. Sonnevend, G., Stoer, J., Zhao, G.: On the complexity of following the central path of linear programming by linear extrapolation. Methods Oper. Res. 63, 19–31 (1989)

    MATH  Google Scholar 

23. Wright, S.J.: Primal-Dual Interior-Point Methods. SIAM, Philadelphia, USA (1997)

    Book  Google Scholar 

24. Yang, X., Zhang, Y., Liu, H.: A wide neighborhood infeasible-interior-point method with arc-search for linear programming. J. Appl. Math. Comput. 51(1–2), 209–225 (2016)

    Article  MathSciNet  Google Scholar 

25. Ye, Y., Todd, M., Mizuno, S.: An \(O(\sqrt{n}L)\)-iteration homogeneous and self-dual linear programming algorithm. Math. Oper. Res. 19, 53–67 (1994)

    Article  MathSciNet  Google Scholar 

26. Ye, Y.: Interior Point Algorithms. Theory and Analysis. Wiley, Chichester (1997)

    Book  Google Scholar 

27. Zhang, Y., Zhang, D.: On polynomiality of the Mehrotra-type predictor-corrector interior-point algorithms. Math. Program. 68, 303–318 (1995)

    Article  MathSciNet  Google Scholar 

28. Zhang, J., Zhang, K.: Polynomial complexity of an interior point algorithm with a second order corrector step for symmetric cone programming. Math. Meth. Oper. Res. 73, 75–90 (2011)

    Article  MathSciNet  Google Scholar 

29. Yang, X., Zhang, Y., Liu, H., Shen, P.: A new second-order infeasible primal-dual path-following algorithm for symmetric optimization. Numer. Func. Anal. Optim. 37(4), 499–519 (2016)

    Article  MathSciNet  Google Scholar 

Download references