A long-step interior point framework and a related function class for linear optimization

I. Adler, N. Karmarkar, M. G. Resende, and G. Veiga, Data structures and programming techniques for the
implementation of Karmarkar’s algorithm, ORSA J Comput, 1 (1989), pp. 84–106, https://doi.org/10.1287/ijoc.1.2.84

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

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

S. Asadi, H. Mansouri, Z. Darvay, M. Zangiabadi, and N. Mahdavi-Amiri, Large-neighborhood infeasible predictor–
corrector algorithm for horizontal linear complementarity problems over Cartesian product of symmetric cones, J. Optim. Theory Appl., 180 (2019), pp. 811–829, https://doi.org/10.1007/s10957-018-1402-6

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

Y.-Q. Bai, M. El Ghami, and C. Roos, A new efficient large-update primal-dual interior-point method based on a
finite barrier, SIAM Journal on Optimization, 13 (2002), pp. 766–782, https://doi.org/10.1137/S1052623401398132.

Zs. Darvay, A weighted-path-following method for linear optimization, Studia Universitatis Babes-Bolyai, Series Informatica, 47 (2002), pp. 3–12.

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

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

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

Zs. 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 direction, SIAM J. Optim., 30 (2020), pp. 2628–2658, https:
//doi.org/10.1137/19M1248972

Zs. Darvay, T. Illés, and P. R. Rigó, 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), https:
//doi.org/10.1016/j.ejor.2021.08.039

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 (2016), pp. 27–42, https://doi.org/10.1007/s10998-016-0119-2

Zs. Darvay and P. R. Rigó, New interior-point algorithm for symmetric optimization based on a positive-asymptotic
barrier function, Numerical Functional Analysis and Optimization, 39 (2018), pp. 1705–1726, https://doi.org/10.
1080/01630563.2018.1492938.

Zs. Darvay and P. R. Rigó, Interior-point algorithm for symmetric cone horizontal linear complementarity problems
based on a new class of algebraically equivalent transformations, Optim. Lett., 18 (2024), pp. 615–634, https://doi.org/10.1007/s11590-023-02020-w

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

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

M. E.-Nagy and A. Varga, A numerical comparison of long-step interior point algorithms for linear optimization,
SOR ’21 Proceedings - The 16th International Symposium on Operational Research in Slovenia, (2021), pp. 75–80.

M. E.-Nagy and A. Varga, A new Ai–Zhang type interior point algorithm for sufficient linear complementarity problems,
J. Optim. Theor. Appl., (2022), https://doi.org/10.1007/s10957-022-02121-z

M. E.-Nagy and A. Varga, A new long-step interior point algorithm for linear programming based on the algebraic
equivalent transformation, Cent. Eur. J. Oper. Res., (2022), https://doi.org/10.1007/s10100-022-00812-6

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

D. M. Gay, Electronic mail distribution of linear programming test problems, Math Program Soc COAL Newsl, 13 (1985), pp. 10–12.

M. Haddou, T. Migot, and J. Omer, A generalized direction in interior point method for monotone linear complementarity
problems, Optimization Letters, 13 (2019), pp. 35–53.

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

T. Illés, P. R. Rigó, and R. Török, Unified approach of primal-dual interior-point algorithms for a new class of
AET functions, Corvinus Econ. Work. Paper., (2022).

B. Jansen, C. Roos, and T. Terlaky, The theory of linear programming: skew symmetric self-dual problems and the
central path, Optim, 29 (1994), pp. 225–233, https://doi.org/10.1080/02331939408843952

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., (2016), pp. 277–290, https://doi.org/10.17535/crorr.2016.0019

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

M. Kojima and S. Shindo, Extension of Newton and quasi-Newton methods to systems of PC1 equations, Journal of
the Operations Research Society of Japan, 29 (1986), pp. 352–375, https://doi.org/10.15807/jorsj.29.352

G. Lesaja and C. Roos, Unified analysis of kernel-based interior-point methods for P∗(κ)-linear complementarity
problems, SIAM Journal on Optimization, 20 (2010), pp. 3014–3039, https://doi.org/10.1137/090766735

Y. Li and T. Terlaky, 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 (2010), pp. 2853–2875, https://doi.
org/10.1137/080729311

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

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

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

N. Ploskas and N. Samaras, Linear Programming Using MATLAB®, vol. 127, Springer, 2017, https://doi.org/10.
1007/978-3-319-65919-0

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 (2014), pp. 1–28, https://doi.org/10.1137/120884341

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

G. Sonnevend, An "analytical centre" for polyhedrons and new classes of global algorithms for linear (smooth, convex)
programming, in System modelling and optimization, Springer, 1986, pp. 866–875.

X. Yang, Y. Zhang, and H. Liu, A wide neighborhood infeasible-interior-point method with arc-search for linear
programming, J. Appl. Math. Comput., 51 (2016), pp. 209–225, https://doi.org/10.1007/s12190-015-0900-z

Y. Ye, M. J. Todd, and S. Mizuno, An O √nL-iteration homogeneous and self-dual linear programming algorithm,
Math Oper Res, 19 (1994), pp. 53–67, https://doi.org/10.1287/moor.19.1.53