No Access

An extension for identifying search directions for interior-point methods in linear optimization

Behrouz Kheirfam

Department of Applied Mathematics, Azarbaijan Shahid Madani University, Tabriz, I. R. Iran

E-mail Address: b.kheirfam@azaruniv.ac.ir

Corresponding author.

Search for more papers by this author

and

Afsaneh Nasrollahi

Department of Applied Mathematics, Azarbaijan Shahid Madani University, Tabriz, I. R. Iran

E-mail Address: afsane.nasrolahi@yahoo.com

Search for more papers by this author

https://doi.org/10.1142/S179355712050014XCited by:2 (Source: Crossref)

Abstract

In this paper, based on the transformation $ψ (\frac{x s}{μ}) = ψ (\sqrt{\frac{x s}{μ}})$ $ψ (\frac{x s}{μ}) = ψ (\sqrt{\frac{x s}{μ}})$ introduced by Darvay and Takács [New method for determining search directions for interior-point algorithms in linear optimization, Optim. Lett.12(5) (2018) 1099–1116], we present a full-Newton step interior-point method for linear optimization. They consider the case $ψ (t) = t^{2}$ $ψ (t) = t^{2}$ . Here, we extend this to the case $ψ (t) = t^{q} (q \geq 2)$ $ψ (t) = t^{q} (q \geq 2)$ to obtain our search directions. We show that the iterates lie in the neighborhood of the local quadratic convergence of the proximity measure. Finally, the polynomial complexity of the proposed algorithm is proved.

Communicated by B. K. Dass

Keywords:

AMSC: 90C51

References

1. M. Achache, A new primal-dual path-following method for convex quadratic programming, Comput. Appl. Math. 25(1) (2006) 97–110. Crossref, Web of Science, Google Scholar
2. Z. Darvay, New interior point algorithm in linear programming, Adv. Model. Optim. 5(1) (2003) 51–92. Google Scholar
3. Z. Darvay, I. M. Papp and P. R. Takács, Complexity analysis of a full-Newton step interior-point method for linear optimization, Period. Math. Hung. 73(1) (2016) 27–42. Crossref, Web of Science, Google Scholar
4. Z. Darvay and P. R. Takács, New method for determining search directions for interior-point algorithms in linear optimization, Optim. Lett. 12(5) (2018) 1099–1116. Crossref, Web of Science, Google Scholar
5. E. De Klerk, Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications (Kluwer Acadamic Publishers, Dordrecht, 2002). Crossref, Google Scholar
6. N. K. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica 4 (1984) 373–395. Crossref, Web of Science, Google Scholar
7. B. Kheirfam, A new infeasible interior-point method based on Darvay’s technique for symmetric optimization, Annal. Oper. Res. 211(1) (2013) 209–224. Crossref, Web of Science, Google Scholar
8. B. Kheirfam, A predictor-corrector interior-point algorithm for $P_{*} (κ)$ $P_{*} (κ)$ -horizontal linear complementarity problem, Numer. Algorithms 66(2) (2014) 349–361. Crossref, Web of Science, Google Scholar
9. B. Kheirfam, New complexity analysis of a full Nesterov-Todd step interior-point method for semidefinite optimization, Asian-Eur. J. Math. 10(4) (2017), 1750070 (14 pages). Link, Web of Science, Google Scholar
10. B. Kheirfam and N. Mahdavi-Amiri, A new interior-point algorithm based on modified Nesterov-Todd direction for symmetric cone linear complementarity problem, Optim. Lett. 8(3) (2014) 1017–1029. Crossref, Web of Science, Google Scholar
11. B. Kheirfam and A. Nasrollahi, A full-Newton step interior-point method based on a class of specific algebra transformation, Fundam. Inform. (2018), https://doi.org/10.3233/FI-2018-1670. Crossref, Web of Science, Google Scholar
12. M. Kojima, S. Mizuno and A. Yoshise, A primal-dual interior-point algorithm for linear programming, in Progress in Mathematical Programming: Interior Point and Related Methods, ed. N. Megiddo (Springer, New York, 1989). Crossref, Google Scholar
13. N. Megiddo, Pathways to the optimal set in linear programming, in Progress in Mathematical Programming: Interior Point and Related Methods, ed. N. Megiddo (Springer, New York, 1989). Crossref, Google Scholar
14. C. Roos, T. Terlaky and J.-Ph. Vial, Interior Point Methods for Linear Optimization (Springer, US, 2005). Google Scholar
15. G. Q. Wang and Y. Q. Bai, A new primal-dual path-following interior-point algorithm for semidefinite optimization, J. Math. Anal. Appl. 353 (2009) 339–349. Crossref, Web of Science, Google Scholar
16. G. Q. Wang and Y. Q. Bai, A primal-dual path-following interior-point algorithm for second-order cone optimization with full Nesterov-Todd step, Appl. Math. Comput. 215(3) (2009) 1047–1061. Crossref, Web of Science, Google Scholar
17. G. Q. Wang and Y. Q. Bai, A new full Nesterov-Todd step primal-dual path-following interior-point algorithm for symmetric optimization, J. Optim. Theory Appl. 154(3) (2012) 966–985. Crossref, Web of Science, Google Scholar
18. G. Q. Wang, C. J. Yu and K. L. Teo, A new full Nesterov-Todd step feasible interior-point method for convex quadratic symmetric cone optimization, Appl. Math. Comput. 221 (2013) 329–343. Web of Science, Google Scholar
19. G. Q. Wang, C. J. Yu and K. L. Teo, A full-Newton step feasible interior-point algorithm for $P_{*} (κ)$ $P_{*} (κ)$ -linear complementarity problem, J. Glob. Optim. 59(1) (2014) 81–99. Crossref, Web of Science, Google Scholar
20. L. Zhang and Y. Xu, A full-step interior-point algorithm for linear complementarity problem based on a simple function, J. Inform. Optim. Sci. 32(6) (2011) 1315–1332. Google Scholar