A path-following interior-point algorithm for monotone LCP based on a modified Newton search direction

Open Access

Issue		RAIRO-Oper. Res. Volume 57, Number 3, May-June 2023


Page(s)		1059 - 1073
DOI		https://doi.org/10.1051/ro/2023054
Published online		11 May 2023

M. Achache, A weighted-path-following method for the linear complementarity problem. Studia Universitatis Babeş-Bolyai. Series Informatica 49 (2004) 61–73. [Google Scholar]
M. Achache, A new primal-dual path-following method for convex quadratic programming. Comput. Appl. Math. 25 (2006) 97–110. [CrossRef] [MathSciNet] [Google Scholar]
M. Achache, Complexity analysis and numerical implementation of a short-step primal-dual algorithm for linear complementarity problems. Appl. Math. Comput. 216 (2010) 1889–1895. [MathSciNet] [Google Scholar]
M. Achache, Complexity analysis of an interior point algorithm for the semidefinite optimization based on a kernel function with a double barrier term. Acta Math. Sin. 31 (2015) 543–556. [CrossRef] [MathSciNet] [Google Scholar]
M. Achache, A new parameterized kernel function for LO yielding the best known iteration bound for a large-update interior point algorithm. Afr. Mat. 27 (2016) 591–601. [CrossRef] [MathSciNet] [Google Scholar]
M. Achache and R. Khebchache, A full-Newton step feasible weighted primal-dual interior point algorithm for monotone LCP. Afr. Mat. 26 (2015) 139–151. [CrossRef] [MathSciNet] [Google Scholar]
M. Achache and N. Tabchouche, A full-Newton step feasible interior-point algorithm for monotone horizontal linear complementarity problems. Optimiz. Lett. 13 (2018) 1039–1057. [Google Scholar]
M. Achache and N. Tabchouche, Complexity analysis and numerical implementation of large-update interior-point methods for SDLCP based on a new parametric barrier kernel function, Optimization. J. Math. Prog. Oper. Res. 67 (2018) 1211–1230. [Google Scholar]
Y.Q. Bai, M. El Ghami and C. Roos, A new efficient large-update primal-dual interior-point method based on finite barrier. SIAM J. Optimiz. 13 (2002) 766–782. [CrossRef] [Google Scholar]
Y.Q. Bai, M. El Ghami and C. Roos, A comparative study of kernel function for primal-dual interior-points algorithms in linear optimization. SIAM J. Optimiz. 15 (2004) 101–128. [CrossRef] [Google Scholar]
R.W. Cottle, J.S. Pang and R.E. Stone, The Linear Complementarity Problem. Academic, San Diego (1992). [Google Scholar]
J. Czyzyk, S. Mehrotra, M. Wagner and S.J. Wright, PCx: an interior-point code for linear programming. Optim. Methods Softw. 11 (1999) 397–430. [CrossRef] [MathSciNet] [Google Scholar]
Z. Darvay, A new algorithm for solving self-dual linear optimization problems. Stud. Univ. Babes-Bolyai Inform. 47 (2002) 15–26. [MathSciNet] [Google Scholar]
Z. Darvay, New interior point algorithm in linear programming. Adv. Model. Optimiz. 5 (2003) 51–92. [Google Scholar]
Z. Darvay and P.R. Takács, New method for determining search directions for interior point algorithms in linear optimization. Optimiz. Lett. 12 (2018) 1099–1116. [CrossRef] [Google Scholar]
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 (2016) 27–42. [CrossRef] [Google Scholar]
Z. Darvay, T. Illés and C. Majoros, Interior-point algorithm for sufficient LCPs based on the technique of algebraically equivalent transformation. Optimiz. Lett. 15 (2021) 357–376. [CrossRef] [Google Scholar]
Z. Darvay, T. Illés, J. Povh and P.R. Rigó, Feasible corrector-predictor interior-point algorithm for P_*(κ)-linear complementarity problems based on a new search directions. SIAM J. Optimiz. 30 (2020) 2628–2658. [CrossRef] [Google Scholar]
A. Fischer, A special Newton-type optimization method. Optimization 24 (1992) 269–284. [Google Scholar]
A. Fischer, On the local superlinear convergence of a Newton-type method for LCP under weak conditions. Optimiz. Methods Softw. 6 (1995) 83–107. [CrossRef] [Google Scholar]
D. Gay, Electronic mail distribution of linear programming test problems. Math. Program. Soc. COAL News 13 (1985) 10–12. [Google Scholar]
W. Grimes, Path-following interior-point algorithm for monotone linear complementarity problems. Asian-Eur. J. Math. 15 (2022). [CrossRef] [Google Scholar]
W. Grimes and M. Achache, An infeasible interior-point algorithm for monotone linear complementarity problems. Int. J. Inf. Appl. Math. 04 (2021) 53–59. [Google Scholar]
M. Haddou, T. Migot and J. Omer, A generalized direction in interior point method for monotone linear complementarity problems. Optimiz. Lett. 13 (2019) 35–53. [CrossRef] [Google Scholar]
N.K. Karmarkar, A new polynomial-time algorithm for linear programming. Combinatorica 4 (1984) 373–395. [CrossRef] [MathSciNet] [Google Scholar]
B. Kheirfam, A predictor-corrector interior-point algorithm for P_*(κ)-horizontal linear complementarity problem. Numer. Algorithms 66 (2014) 349–361. [CrossRef] [MathSciNet] [Google Scholar]
B. Kheirfam, A new search direction for full-Newton step infeasible interior-point method in linear optimization. Preprint arXiv:2102.07223v1 (2021). [Google Scholar]
B. Kheirfam and M. Haghighi, A full-Newton step feasible interior-point algorithm for P_*(κ)-LCP based on a new search direction. Croat. Oper. Rev. 7 (2016) 277–290. [CrossRef] [MathSciNet] [Google Scholar]
B. Kheirfam and A. Nasrollahi, A full-Newton step interior-point method based on a class of specific algebra transformation. Fundam. Inf. 163 (2018) 325–337. [Google Scholar]
M. Kojima, N. Megiddo, T. Noma and A. Yoshise, A unified approach to interior point algorithms for linear complementarity problems, in Lecture Notes in Computer Science, vol. 538. Springer-Verlag, Berlin (1991). [CrossRef] [Google Scholar]
N. Moussaoui and M. Achache, A weighted-path following interior-point algorithm for convex quadratic optimization based on modified search directions. Stat. Optimiz. Inf. Comput. 10 (2022) 873–889. [CrossRef] [Google Scholar]
S. Pan, X. Li and S. He, An infeasible primal-dual interior point algorithm for linear programs based on logarithmic equivalent transformation. J. Math. Anal. Appl. 314 (2006) 644–660. [CrossRef] [MathSciNet] [Google Scholar]
J. Peng, C. Roos and T. Terlaky, Self-Regular Functions: A New Paradigm for primal-dual Interior-Point Methods. Princeton University Press, Princeton (2002). [Google Scholar]
C. Roos, T. Terlaky and J.P. Vial, Theory and algorithms for Linear Optimization. An Interior Point Approach, John-Wiley. Sons, Chichester, UK (1997). [Google Scholar]
G.Q. Wang and Y.Q. Bai, A new primal-dual path-following interior point algorithm for semidefinite programming. J. Math. Anal. Appl. 353 (2009) 339–349. [CrossRef] [MathSciNet] [Google Scholar]
G.Q. Wang and Y.Q. Bai, A primal-dual interior-point algorithm for second-order cone optimization with full-Nesterov-Todd step. Appl. Math. Comput. 215 (2009) 1047–1061. [MathSciNet] [Google Scholar]
G.Q. Wang, X.J. Fan, D.T. Zhu and D.Z. Wang, New complexity analysis of a full-Newton step feasible interior-point algorithm for P_*(κ)-LCP. Optimiz. Lett. 9 (2015) 1105–1119. [CrossRef] [Google Scholar]
Y. Ye, On homogeneous and self-dual algorithm for LCP. Math. Prog. 76 (1997) 211–222. [CrossRef] [Google Scholar]
Y. Ye, Interior Point Algorithm, Theory and Analysis, John Wiley and Sons, Chichester, UK (1997). [CrossRef] [Google Scholar]
Y. Ye, M.J. Todd and S. Mizuno, An -iteration homogeneous and self-dual linear programming algorithm. Math. Oper. Res. 19 (1994) 53–67. [CrossRef] [MathSciNet] [Google Scholar]
L. Zhang and Y. Xu, A full-Newton step primal dual interior-point algorithm for linear complementarity problem. J. Inf. Comput. Sci. 5 (2010) 305–313. [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.