Predictor-corrector interior-point algorithm for sufficient linear complementarity problems based on a new type of algebraic equivalent transformation technique

[1] M. Achache. Complexity analysis and numerical implementation of a short-step primal-dual
algorithm for linear complementarity problems. Appl. Math. Comput., 216(7):1889{1895,
2010.

[2] S. Asadi, N. Mahdavi-Amiri, Zs. Darvay, and P. R. Rigó. Full Nesterov-Todd step
feasible interior-point algorithm for symmetric cone horizontal linear complementarity
problem based on a positive-asymptotic barrier function. Optim. Methods Softw., 2020.
DOI:10.1080/10556788.2020.1734803.

[3] S. Asadi and H. Mansouri. A path-following algorithm for P_* (κ)-horizontal linear complementarity
problem based on Darvay's directions. In Proceeding of the 43rd Annual Iranian
Mathematics Conference, Tabriz University, Tabriz, Iran, pages 861{864, 2012.

[4] S. Asadi and H. Mansouri. Polynomial interior-point algorithm for P_* (κ) horizontal linear
complementarity problems. Numer. Algorithms, 63(2):385{398, 2013.

[5] Y.Q. Bai, M. El Ghami, and C. Roos. A comparative study of kernel functions for primaldual
interior-point algorithms in linear optimization. SIAM J. Optim., 15(1):101{128, 2004.

[6] C. Br�as, G. Eichfelder, and J. J�udice. Copositivity tests based on the linear complementarity
problem. Comput. Optim. Appl., 63(2):461{493, 2016.

[7] S.J. Chung. NP-completeness of the linear complementarity problem. J. Optim. Theory
Appl., 60(3):393{399, 1989.
[8] R.W. Cottle, J.S. Pang, and R.E. Stone. The Linear Complementarity Problem. Computer
Science and Scientific Computing. Academic Press, Boston, 1992.
[9] R.W. Cottle, J.S. Pang, and V. Venkateswaran. Sufficient matrices and the linear complementarity
problem. Linear Algebra Appl., 114:231{249, 1989.

[10] A. Csizmadia, Zs. Csizmadia, and T. Illés. Finiteness of the quadratic primal simplex
method when s-monotone index selection rules are applied. Cent. Eur. J. Oper. Res.,
26:535{550, 2018.

[11] Zs. Csizmadia and T. Illés. New criss-cross type algorithms for linear complementarity
problems with sufficient matrices. Optim. Methods Softw., 21(2):247{266, 2006.

[12] Zs. Csizmadia, T. Ill�es, and A. Nagy. The s-monotone index selection rule for criss-cross algorithms
of linear complementarity problems. Acta Univ. Sapientiae, Informatica, 5(1):103{
139, 2013.

[13] Zs. Darvay. A new algorithm for solving self-dual linear optimization problems. Studia
Univ. Babe�s-Bolyai, Ser. Informatica, 47(1):15{26, 2002.

[14] Zs. Darvay. New interior point algorithms in linear programming. Adv. Model. Optim.,
5(1):51{92, 2003.
[15] Zs. Darvay. A new predictor-corrector algorithm for linear programming (in Hungarian).
Alkalmazott Matematikai Lapok, 22:135{161, 2005.
22
[16] Zs. Darvay, T. Illés, B. Kheirfam, and P. R. Rig�o. A corrector-predictor interior-point
method with new search direction for linear optimization. Cent. Eur. J. Oper. Res., 28:1123{
1140, 2020.
[17] Zs. Darvay, T. Illés, and Cs. Majoros. Interior-point algorithm for sufficient LCPs based
on the technique of algebraically equivalent transformation. Optim. Lett., 2020. DOI:
10.1007/s11590-020-01612-0.

[18] Zs. Darvay, T. Illés, J. Povh, and P. R. Rigó. Predictor-corrector interior-point algorithm
for sufficient linear complementarity problems based on a new search direction. SIAM J.
Optim., 2020. Accepted for publication.

[19] Zs. 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):27{42, 2016.

[20] Zs. Darvay and P.-R. Tak�acs. New interior-point algorithm for symmetric optimization
based on a positive-asymptotic barrier function. Numer. Func. Anal. Opt., 39(15):1705{
1726, 2018.

[21] Zs. Darvay and P.-R. Takács. New method for determining search directions for interiorpoint
algorithms in linear optimization. Optim. Lett., 12(5):1099{1116, 2018.

[22] Zs. Darvay and I. Tak�o. Computational comparison of primal-dual algorithms based on a
new software, University of Babes-Bolyai, Cluj-Napoca. 2012. unpublished manuscript.

[23] E. de Klerk and M. E.-Nagy. On the complexitiy of computing the handicap of a sufficient
matrix. Math. Program., 129:383{402, 2011.

[24] D. den Hertog, C. Roos, and T. Terlaky. The linear complimentarity problem, sufficient
matrices, and the criss-cross method. Linear Algebra Appl., 187:1{14, 1993.

[25] M.C. Ferris and J.S. Pang. Engineering and economic applications of complementarity
problems. SIAM Review, 39(4):669{713, 1997.

[26] K. Fukuda, M. Namiki, and A. Tamura. EP theorems and linear complementarity problems.
Discrete Appl. Math., 84(1-3):107{119, 1998.

[27] K. Fukuda and T. Terlaky. Criss-cross methods: A fresh view on pivot algorithms. Math.
Program., 79:369{395, 1997.

[28] S.M. Guu and R.W. Cottle. On a subclass of P0. Linear Algebra Appl., 223/224:325{335,
1995.

[29] M. Haddou, T. Migot, and J. Omer. A generalized direction in interior point method for
monotone linear complementarity problems. Optim. Lett., 13(1):35{53, 2019.

[30] T. Illés and S. Morapitiye. Generating sufficient matrices. In F. Friedler, editor, 8th VO-
CAL Optimization Conference: Advanced Algorithms, pages 56{61. Pázmány P�eter Catholic
University, Budapest, Hungary, 2018.

[31] T. Illés and M. Nagy. A Mizuno-Todd-Ye type predictor-corrector algorithm for sufficient
linear complementarity problems. Eur. J. Oper. Res., 181(3):1097{1111, 2007.

[32] T. Illés, M. Nagy, and T. Terlaky. EP theorem for dual linear complementarity problems.
J. Optim. Theory Appl., 140(2):233{238, 2009.

[33] T. Illés, M. Nagy, and T. Terlaky. Polynomial interior point algorithms for general linear
complementarity problems. Alg. Oper. Res., 5(1):1{12, 2010.

[34] T. Illés, M. Nagy, and T. Terlaky. A polynomial path-following interior point algorithm for
general linear complementarity problems. J. Global. Optim., 47(3):329{342, 2010.

[35] B. Kheirfam. A predictor-corrector interior-point algorithm for P�(�)-horizontal linear
complementarity problem. Numer. Algorithms, 66(2):349{361, 2014.

[36] B. Kheirfam and M. Haghighi. A full-Newton step feasible interior-point algorithm for
P�(�)-LCP based on a new search direction. Croat. Oper. Res. Rev., 7(2), 2016.

[37] M. Kojima, N. Megiddo, T. Noma, and A. Yoshise. A Unified Approach to Interior Point
Algorithms for Linear Complementarity Problems, volume 538 of Lecture Notes in Computer
Science. Springer Verlag, Berlin, Germany, 1991.

[38] M. Kojima and R. Saigal. On the number of solutions to a class of linear complementarity
problems. Math. Program., 17:136{139, 1979.

[39] C.E. Lemke. On complementary pivot theory. In G.B. Dantzig and Jr. A.F. Veinott, editors,
Mathematics of Decision Sciences, Part 1, pages 95{114. American Mathematical Society,
Providence, Rhode Island, 1968.

[40] C.E. Lemke and J.T. Howson. Equilibrium points of bimatrix games. SIAM J. Appl. Math.,
12:413{423, 1964.

[41] G. Le�saja and C. Roos. Unified analysis of kernel-based interior-point methods for P�(�)-
linear complementarity problems. SIAM J. Optim., 20(6):3014{3039, 2010.
[42] X. Liu and F.A. Potra. Corrector-predictor methods for sufficient linear complementarity
problems in a wide neighborhood of the central path. SIAM J. Optim., 17(3):871{890, 2006.

[43] H. Mansouri and M. Pirhaji. A polynomial interior-point algorithm for monotone linear
complementarity problems. J. Optim. Theory Appl., 157(2):451{461, 2013.

[44] S. Mehrotra. On the implementation of a primal-dual interior point method. SIAM J.
Optim., 2(4):575{601, 1992.

[45] J. Miao. A quadratically convergent O((� + 1)
pnL) -iteration algorithm for the P�(�)-
matrix linear complementarity problem. Math. Program., 69(1):355{368, 1995.

[46] S. Mizuno, M.J. Todd, and Y. Ye. On adaptive-step primal-dual interior-point algorithms
for linear programming. Math. Oper. Res., 18:964{981, 1993.

[47] M. Nagy. Interior point algorithms for general linear complementarity problems. PhD thesis,
Eötvös Loránd University of Sciences, Institute of Mathematics, 2009.

[48] J. Peng, C. Roos, and T. Terlaky. Self-Regular Functions: a New Paradigm for Primal-Dual
Interior-Point Methods. Princeton University Press, 2002.

[49] F.A. Potra. Corrector-predictor methods for monotone linear complementarity problems in
a wide neighborhood of the central path. Math. Program., 111(1-2):243{272, 2008.

[50] F.A. Potra and X. Liu. Predictor-corrector methods for su�cient linear complementarity
problems in a wide neighborhood of the central path. Optim. Methods Softw., 20(1):145{168,
2005.

[51] F.A. Potra and R. Sheng. Predictor-corrector algorithm for solving P�(�)-matrix LCP from
arbitrary positive starting points. Math. Program., 76(1):223{244, 1996.

[52] F.A. Potra and R. Sheng. A large-step infeasible-interior-point method for the P�-Matrix
LCP. SIAM J. Optim., 7(2):318{335, 1997.

[53] P. R. Rigó and Zs. Darvay. Infeasible interior-point method for symmetric optimization
using a positive-asymptotic barrier. Comput. Optim. Appl., 71(2):483{508, 2018.

[54] P.R. Rigó. New trends in algebraic equivalent transformation of the central path and its
applications. PhD thesis, Budapest University of Technology and Economics, Institute of
Mathematics, Hungary, 2020.

[55] G. Le�saja and F. Potra. Adaptive full Newton-step infeasible interior-point method for
su�cient horizontal lcp. Optim. Methods Softw., 34:1014{1034, 2019.

[56] E. Sloan and O.N. Sloan. Quitting games and linear complementarity problems. Math. Op.
Res., 45(2):434{454, 2020.

[57] Gy. Sonnevend, J. Stoer, and G. Zhao. On the complexity of following the central path by
linear extrapolation II. Math. Program., 52(1):527{553, 1991.
[58] P.-R. Takács and Zs. Darvay. A primal-dual interior-point algorithm for symmetric optimization
based on a new method for finding search directions. Optimization, 81(3):889{905,
2018.
[59] P. Tseng. Co-NP-completeness of some matrix classification problems. Math. Program.,
88:183{192, 2000.

[60] H. Valiaho. Criteria for sufficient matrices. Linear Algebra Appl., 233:109{129, 1996.

[61] H. Valiaho. P�-matrices are just sufficient. Linear Algebra Appl., 239:103{108, 1996.

[62] H. V�aliaho. Determining the handicap of a su�cient matrices. Linear Algebra Appl.,
253:279{298, 1997.
[63] C. van de Panne. A complementary variant of Lemke's method for the linear complementary
problem. Math. Prog., 7:283{310, 1974.

[64] C. van de Panne and A. Whinston. Simplicial methods for quadratic programming. Naval
Research Logistics, 11:273{302, 1964.

[65] C. van de Panne and A. Whinston. The symmetric formulation of the simplex method for
quadratic programming. Econometrica, 37(3):507{527, 1969.

[66] M. Vieira. The accuracy of inteior-point methods based on kernel functions. J. Optim
Theory Appl., 155:637{649, 2012.
[67] P. Wolfe. The simplex method for quadratic programming. Econometrica, 27(3):382{398,
1959.

[68] Y. Ye. A path to the Arrow-Debreu competitive market equilibrium. Math. Program.,
111(1-2):315{348, 2008.

[69] L. Zhang and Y. Xu. A full-Newton step interior-point algorithm based on modified Newton
direction. Oper. Res. Lett., 39:318{322, 2011.

[70] M. Zhang, K. Huang, M. Li, and Y. Lv. A new full-Newton step interior-point method for
P�(�)-LCP based on a positive-asymptotic kernel function. J. Appl. Math. Comput., 2020.
DOI:10.1007/s12190-020-01356-1.