A new Ai-Zhang type interior point algorithm for sufficient linear complementarity problems

Ai, W., Zhang, S.: An O(√nL) iteration primal-dual path-following method, based on wide neighborhoods and large
updates, for monotone LCP. SIAM J. Optim. 16(2), 400–417 (2005). doi:https://doi.org/10.1137/040604492

Asadi, S., Mansouri, H.: Polynomial interior-point algorithm for P∗(κ) horizontal linear complementarity problems.
Numer. Algorithm. 63(2), 385–398 (2013). doi:https://doi.org/10.1007/s11075-012-9628-0

Asadi, S., Mansouri, H., Darvay, Z., 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). doi:https://doi.org/10.1007/s10957-018-1402-6

Asadi, S., Mansouri, H., Lesaja, G., Zangiabadi, M.: A long-step interior-point algorithm for symmetric cone Cartesian
P∗(κ)-HLCP. Optimization 67(11), 2031–2060 (2018). doi:https://doi.org/10.1080/02331934.2018.1512604

Bai, Y., Lesaja, G., Roos, C., Wang, G., El Ghami, M.: A class of large-update and small-update primaldual
interior-point algorithms for linear optimization. J. Optim. Theory. Appl. 138(3), 341–359 (2008).
doi:https://doi.org/10.1007/s10957-008-9389-z

Chung, S.J.: NP-completeness of the linear complementarity problem. J. Optim. Theor. Appl. 60(3), 393–399 (1989).
doi:https://doi.org/10.1007/BF00940344

Cottle, R., Pang, J.S., Venkateswaran, V.: Sufficient matrices and the linear complementarity problem. Lin. Algebra
Appl. 114, 231–249 (1989). doi:https://doi.org/10.1016/0024-3795(89)90463-1

Darvay, Zs.: New interior point algorithms in linear programming. Adv. Model. Optim. 5(1), 51–92 (2003)

Darvay, Zs., Illés, T., Kheirfam, B., Rigó, P.R.: A corrector–predictor interior-point method with new search direction for linear optimization. Cent. Eur. J. Oper. Res. 28(3), 1123–1140 (2020). doi: https://doi.org/10.1007/s10100-019-
00622-3

Darvay, Zs., Illés, T., Majoros, Cs.: Interior-point algorithm for sufficient LCPs based on the technique of algebraically equivalent transformation. Optim. Lett. 15(2), 357–376 (2021). doi:https://doi.org/10.1007/s11590-020-01612-0

Darvay, Zs., Illés, T., Povh, J., Rigó, P.R.: Feasible corrector-predictor interior-point algorithm for P∗(κ)-
linear complementarity problems based on a new search direction. SIAM J. Optim. 30(3), 2628–2658 (2020).
doi:https://doi.org/10.1137/19M1248972

Darvay, Zs., Illés, T., Rigó, P.R.: Predictor-corrector interior-point algorithm for P∗(κ)-linear complementarity
problems based on a new type of algebraic equivalent transformation technique. Eur. J. Oper. Res. (2021).
doi:https://doi.org/10.1016/j.ejor.2021.08.039

Darvay, Zs., Papp, I.M., Takács, P.R.: Complexity analysis of a full-Newton step interior-point method for linear
optimization. Period. Math. Hung. 73(1), 27–42 (2016). doi:https://doi.org/10.1007/s10998-016-0119-2

Darvay, Zs., Tak´acs, P.R.: Large-step interior-point algorithm for linear optimization based on a new wide neighbourhood. Cent. Eur. J. Oper. Res. 26(3), 551–563 (2018). doi: https://doi.org/10.1007/s10100-018-0524-0

Darvay, Zs., Takács, P.R.: New method for determining search directions for interior-point algorithms in linear optimization. Optim. Lett. 12(5), 1099–1116 (2018). doi: https://doi.org/10.1007/s11590-017-1171-4

E.-Nagy, M.: Sufficient matrices. https://sites.google.com/view/menagy/research/sufficient-matrices. Accessed:
2022-01-04

E.-Nagy, M., Ill´es, T., Povh, J., Varga, A., ˇZerovnik, J.: Testing sufficient matrices (2021). Manuscript in preparation.

E.-Nagy, M., Varga, A.: A new long-step interior point algorithm for linear programming based on the algebraic
equivalent transformation. Corvinus Econ. Work. Paper. (6) (2021)

Feng, Z., Fang, L.: A new O(nL)-iteration predictor–corrector algorithm with wide neighborhood for semidefinite
programming. J. Comput. Appl. Math. 256, 65–76 (2014). doi:https://doi.org/10.1016/j.cam.2013.07.011

Ferris, M.C., Pang, J.S.: Engineering and economic applications of complementarity problems. SIAM Rev. 39(4),
669–713 (1997). doi:https://doi.org/10.1137/S0036144595285963
A new Ai-Zhang type IPA for sufficient LCPs 17

Gurtuna, F., Petra, C., Potra, F.A., Shevchenko, O., Vancea, A.: Corrector-predictor methods for sufficient linear
complementarity problems. Comput. Optim. Appl. 48(3), 453–485 (2011). doi:https://doi.org/10.1007/s10589-009-
9263-4

Guu, S.M., Cottle, R.W.: On a subclass of P(0). Lin. Algebra. Appl. 223, 325–335 (1995).
doi:https://doi.org/10.1016/0024-3795(93)00271-Z

Illés, T., Morapitiye, S.: Generating sufficient matrices. In: Short papers of the 8th VOCAL optimization conference:
advanced algorithms, published by P´azm´any P´eter Catholic University, Budapest, p. 56 (2018)

Illés, T., Rigó, P.R., Török, R.: Predictor-corrector interior-point algorithm based on a new search direction working in a wide neighbourhood of the central path. Corvinus Econ. Work. Paper. (2) (2021)

Illés, T., Roos, C., Terlaky, T.: Simple approach for the interior point theory of linear complementarity problems with P∗-matrices (1998). Unpublished manuscript.

Kheirfam, B., Haghighi, M.: A full-Newton step feasible interior-point algorithm for P∗(κ)-LCP based on a new search
direction. Croat. Oper. Res. Rev. pp. 277–290 (2016). doi: https://doi.org/10.17535/crorr.2016.0019

de Klerk, E., E.-Nagy, M.: On the complexity of computing the handicap of a sufficient matrix. Math. Program. 129(2),
383–402 (2011). doi:
https://doi.org/10.1007/s10107-011-0465-z

Kojima, M., Megiddo, N., Noma, T., Yoshise, A.: A unified approach to interior point algorithms for linear complementarity
problems. Lect. Notes Comput. Sci. (1991). doi: https://doi.org/10.1007/3-540-54509-3

Kojima, M., Mizuno, S., Yoshise, A.: A primal-dual interior point algorithm for linear programming. In: Progress in
mathematical programming, pp. 29–47. Springer (1989). doi:https://doi.org/10.1007/978-1-4613-9617-8 2

Lemke, C.E., Howson Jr, J.T.: Equilibrium points of bimatrix games. J. Soc. Ind. Appl. Math. 12(2), 413–423 (1964).
doi:https://doi.org/10.1137/0112033

Li, Y., Terlaky, T.: A new class of large neighborhood path-following interior point algorithms for semidefinite
optimization with O
�
n log Tr(X0S0)
ε
�
iteration complexity. SIAM. J. Optim. 20(6), 2853–2875 (2010).
doi: https://doi.org/10.1137/080729311

Liu, C., Liu, H., Cong, W.: An O(
√nL) iteration primal-dual second-order corrector algorithm for linear programming.
Optim. Lett. 5(4), 729–743 (2011). doi:https://doi.org/10.1007/s11590-010-0242-6

Nagy, M.: Interior point algorithms for general linear complementarity problems. Ph.D. thesis, Eötvös Loránd University
(2009)

Peng, J., Roos, C., Terlaky, T.: Self-regularity: A New Paradigm for Primal-dual Interior-point Algorithms. Princeton
Series in Applied Mathematics. Princeton University Press (2002). doi: https://doi.org/10.2307/j.ctt7sf0f

Pirhaji, M., Mansouri, H., Zangiabadi, M.: An O
????√nL
�wide neighborhood interior-point algorithm for semidefinite
optimization. Comput. Appl. Math. 36(1), 145–157 (2017). doi:https://doi.org/10.1007/s40314-015-0220-9

Potra, F.A.: A superlinearly convergent predictor-corrector method for degenerate LCP in a wide neighborhood
of the central path with O(√nL) iteration complexity. Math. Program. 100(2), 317–337 (2004).
doi:https://doi.org/10.1007/s10107-003-0472-9

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). doi: https://doi.org/10.1137/120884341

Väliaho, H.: P∗-matrices are just sufficient. Lin. Algebra. Appl. 239, 103–108 (1996).
doi: https://doi.org/10.1016/S0024-3795(96)90005-1

Väliaho, H.: Determining the handicap of a sufficient matrix. Lin. Algebra Appl. 253(1-3), 279–298 (1997).
doi: https://doi.org/10.1016/0024-3795(95)00703-2

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). doi: https://doi.org/10.1007/s12190-015-0900-z

Ye, Y.: Exchange market equilibria with Leontief’s utility: Freedom of pricing leads to rationality. Theor. Comput. Sci. 378(2), 134–142 (2007). doi: https://doi.org/10.1016/j.tcs.2007.02.016