Predictor-corrector interior-point algorithm based on a new search direction working in a wide neighbourhood of the central path

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

[2] S. Asadi, N. Mahdavi-Amiri, Zs. Darvay, 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, H. Mansouri, Zs. Darvay, M. Zangiabadi, On the P*(κ) horizontal linear complementarity
problems over Cartesian product of symmetric cones. Optim. Methods Sofw.,
31(2), (2016), 233–257.

[4] S. Asadi, H. Mansouri, G. Lesaja, M. Zangiabadi, A long-step interior-point algorithm for
symmetric cone Cartesian P*(κ)-HLCP. Optimization, 67(11), (2018), 2031–2060.

[5] C. Brás, G. Eichfelder, J. Júdice, Copositivity tests based on the linear complementarity
problem. Comput. Optim. Appl., 63(2), (2016), 461–493.

[6] S.J. Chung, NP-completeness of the linear complementarity problem. J. Optim. Theory
Appl., 60(3), (1989), 393–399.

[7] R.W. Cottle, J.S. Pang, R.E. Stone, The Linear Complementarity Problem. Computer
Science and Scientific Computing. Academic Press, Boston, 1992.

[8] R.W. Cottle, J.S. Pang, V. Venkateswaran, Sufficient matrices and the linear complementarity
problem. Linear Algebra Appl., 114 (1989), 231–249.

[9] Zs. Darvay, A new algorithm for solving self-dual linear optimization problems. Studia
Univ. Babes-Bolyai, Ser. Informatica, 47(1), (2002), 15–26.
[10] Zs. Darvay, New interior point algorithms in linear programming. Adv. Model. Optim.,
5(1), (2003), 51–92.
[11] Zs. Darvay, A new predictor-corrector algorithm for linear programming. Alkalmazott
Matematikai Lapok, 22:135–161, 2005. in Hungarian.
[12] Zs. Darvay, A predictor-corrector algorithm for linearly constrained convex optimization.
Studia Univ. Babes-Bolyai, Ser. Informatica, 54(2), (2009), 121–138.
[13] Zs. Darvay, T. Illés, B. Kheirfam, P. R. Rigó, A corrector-predictor interior-point method
with new search direction for linear optimization. Cent. Eur. J. Oper. Res., 28 (2020),
1123–1140.
[14] Zs. Darvay, T. Illés, J. Povh, P. R. Rigó, Feasible corrector-predictor interior-point algorithm
for P*(κ)-linear complementarity problems based on a new search direction. Siam J.
Optim., 30(3), (2020), 2628–2658.
20
[15] Zs. Darvay, I.-M. Papp, P.-R. Takács, Complexity analysis of a full-Newton step interiorpoint
method for linear optimization. Period. Math. Hung., 73(1), (2016), 27–42.
[16] M. E.-Nagy, Sufficient Matrices. https://sites.google.com/view/menagy/research/sufficientmatrices
, Accessed: 2021-03-04.
[17] M. E.-Nagy, T. Illés, G. Lovics, Market exchange models and geometric programming.
Cent. Eur. J. Oper. Res., 27 (2019), 415-435.
[18] E. de Klerk, M. E.-Nagy, On the complexitiy of computing the handicap of a sufficient
matrix. Math. Program., 129 (2011), 383–402.
[19] E. de Klerk, C. Roos, T. Terlaky, Polynomial primal-dual affine scaling algorithms in
semidefinite programming. J. Comb. Optim., 2(1), (1998), 51–69.
[20] M.C. Ferris, J.S. Pang, Engineering and economic applications of complementarity problems.
SIAM Review, 39(4), (1997), 669–713.
[21] M. Fiedler and V. Pták, On matrices with non-positive off-diagonal elements and positive
principal minors. Czechoslovak Mathematical Journal, 12:382–400, 1962.
[22] M. Fiedler and V. Pták, Some generalizations of positive definiteness and monotonicity.
Numerische Mathematik, 9:163–172, 1966.
[23] S.M. Guu, R.W. Cottle, On a subclass of P0. Linear Algebra Appl., 223/224 (1995), 325-335.
[24] F. Gurtuna, C. Petra, F.A. Potra, O. Shevchenko, A. Vancea, Corrector-predictor methods
for sufficient linear complementarity problems. Comput. Optim. Appl., 48(3), (2011), 453–
485.
[25] M. Haddou, T. Migot, J. Omer, A generalized direction in interior point method for
monotone linear complementarity problems. Optim. Lett., 13(1), (2019), 35–53.
[26] T. Illés, S. Morapitiye, Generating sufficient matrices. In F. Friedler, editor, 8th VOCAL
Optimization Conference: Advanced Algorithms, pages 56–61. Pázmány Péter Catholic University,
Budapest, Hungary, 2018.
[27] T. Illés, M. Nagy, A Mizuno-Todd-Ye type predictor-corrector algorithm for sufficient linear
complementarity problems. Eur. J. Oper. Res., 181(3), (2007), 1097–1111..
[28] T. Illés, M. Nagy, T. Terlaky, EP theorem for dual linear complementarity problems. J.
Optim. Theory Appl., 140(2), (2009), 233–238.
[29] T. Illés, M. Nagy, T. Terlaky, Polynomial interior point algorithms for general linear complementarity
problems. Alg. Oper. Res., 5(1), (2010), 1–12.
[30] T. Illés, M. Nagy, T. Terlaky, A polynomial path-following interior point algorithm for
general linear complementarity problems. J. Global. Optim., 47(3), (2010), 329–342.
[31] T. Illés, J. Peng, C. Roos, T. Terlaky, A strongly polynomial rounding procedure yielding
a maximally complementary solution for P*(κ) linear complementarity problems. SIAM J.
Optim., 11(2), (2000), 320–340.
[32] B. Kheirfam, A new infeasible interior-point method based on Darvay’s technique for
symmetric optimization. Ann. Oper. Res., 211(1), (2013), 209–224.
[33] B. Kheirfam, A predictor-corrector interior-point algorithm for P*(κ)-horizontal linear
complementarity problem. Numer. Algorithms, 66(2), (2014), 349–361.
[34] B. Kheirfam, 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, 277-290.
[35] E. De Klerk, Aspects of Semidefinite Programming: Interior Point Algorithms and Selected
Applications. Kluwer Academic Pubishers, 2002.
[36] M. Kojima, N. Megiddo, T. Noma, 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.
[37] M. Kojima, S. Mizuno, A. Yoshise, A polynomial-time algorithm for a class of linear complementarity
problems. Math. Program. ,44 (1989), 1–26.
[38] G. Lešaja, C. Roos, Unified analysis of kernel-based interior-point methods for P*(κ)-linear
complementarity problems. SIAM J. Optim., 20(6), (2010), 3014–3039.
21
[39] X. Liu, F.A. Potra. Corrector-predictor methods for sufficient linear complementarity problems
in a wide neighborhood of the central path. SIAM J. Optim., 17(3), (2006), 871–890.
[40] Z. Luo, N. Xiu, Path-following interior point algorithms for the Cartesian P*(κ)-LCP over
symmetric cones. Science in China Series A: Mathematics, 52(8), (2009), 1769–1784.
[41] S. Mizuno, M.J. Todd, Y. Ye, On adaptive-step primal-dual interior-point algorithms for
linear programming. Math. Oper. Res., 18 (1993), 964–981.
[42] Y.E. Nesterov and A.S. Nemirovskii, Interior point polynomial methods in convex programming:
Theory and applications. SIAM Publications, Philadelphia, USA, 1994.
[43] J. Peng, C. Roos, T. Terlaky, Self-Regular Functions: a New Paradigm for Primal-Dual
Interior-Point Methods. Princeton University Press, 2002.
[44] F.A. Potra, A superlinearly convergent predictor-corrector method for degenerate LCP in a
wide neighborhood of the central path with O(p
nL) iteration complexity. Math. Program.,
100(2), (2004), 317–337.
[45] F.A. Potra, 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), (2014),
1–28.
[46] F.A. Potra, X. Liu, Predictor-corrector methods for sufficient linear complementarity problems
in a wide neighborhood of the central path. Optim. Methods Softw., 20(1), (2005),
145–168.

[47] F.A. Potra, R. Sheng, Predictor-corrector algorithm for solving P*(κ)-matrix LCP from
arbitrary positive starting points. Math. Program., 76(1), (1996), 223–244.

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

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

[50] 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.

[51] C. Roos, T. Terlaky, J.-Ph. Vial, Theory and Algorithms for Linear Optimization. An
Interior Approach. John Wiley & Sons, Chichester, UK, 1997.

[52] G. Lešaja, G.Q. Wang, D.T. Zhu, Interior-point methods for Cartesian P*(κ)-linear complementarity
problems over symmetric cones based on the eligible kernel functions. Optim.
Methods Softw., 27(4-5), (2012), 827–843.

[53] S.H. Schmieta, F. Alizadeh, Extension of primal-dual interior point algorithms to symmetric
cones. Math. Program., Ser. A, 96(3), (2003), 409–438.

[54] E. Sloan, O.N. Sloan, Quitting Games and Linear Complementarity Problems. Math. Op.
Res., 45(2), (2020), 434–454.

[55] Gy. Sonnevend, J. Stoer, G. Zhao, On the complexity of following the central path by linear
extrapolation ii. Math. Program., 52(1), (1991), 527–553.

[56] P.-R. Takács, Zs. Darvay, A primal-dual interior-point algorithm for symmetric optimization
based on a new method for finding search directions. Optimization, 81(3), (2018), 889–905.
[57] H. Väliaho, P�-matrices are just sufficient. Linear Algebra Appl., 239, (1996), 103–108.
[58] M.V.C. Vieira, Jordan algebraic approach to symmetric optimization. PhD thesis, Electrical
Engineering, Mathematics and Computer Science, Delft University of Technology, The
Netherlands, 2007.

[59] G.Q. Wang, Y.Q. Bai, A new primal-dual path-following interior-point algorithm for semidefinite
optimization. J. Math. Anal. Appl., 353(1), (2009), 339–349.

[60] G.Q. Wang, C.J. Yu, 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.

[61] S.J. Wright, Primal-Dual Interior-Point Methods. SIAM, Philadelphia, USA, 1997.

[62] Y. Ye, Interior Point Algorithms, Theory and Analysis. John Wiley & Sons, Chichester,
UK, 1997.

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