Comprehensive Analysis of Kernel-Based Interior-Point Methods for P_* (κ) - LCP

W. Ai and S. Zhang, A 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.

E. Andersen and Y. Ye, On a homogeneous algorithm for the monotone complementarity
problem, Math. Program., 84 (1999), pp. 375–399.

M. Anitescu, G. Lesaja, and F. A. Potra, Equivalence between different formulations of
the linear complementarity problem, Optim. Methods Softw., 7 (1997), pp. 265–290.

Y. Bai, M. El Ghami, and C. Roos, A new efficient large-update primal-dual interior-point
methods based on a finite barrier, SIAM J. Optim., 13 (2003), pp. 766–782.

Y. Bai, M. El Ghami, and C. Roos, A comparative study of kernel functions for primal-dual
interior-point algorithms in linear optimization, SIAM J. Optim., 15 (2004), pp. 101–128.

Y. Bai, G. Lesaja, C. Roos, G. Wang, and M. El Ghami, A class of large- and smallupdate
primal-dual interior-point algorithms for linear optimization, J. Optim. Theory Appl., 138 (2008), pp. 341–359.

G.-M. Cho and M.-K. Kim, A new large-update interior point algorithm for P∗(κ)-LCPs
based on kernel functions, Appl. Math. Comput., 182 (2006), pp. 1169–1183.

S. Chung, A note on the complexity of LCP. the LCP is strongly NP-complete, Technical Report
792, Department of Industrial and Operations Engineering, The University of Michigan,(1979).

R. W. Cottle, J.-S. Pang, and R. E. Stone, The Linear Complementarity Problem,
Academic Press, Boston, MA, 1992.

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

Zs. Darvay, T. Illés, J. Povh, and P. 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.

Zs. Darvay, I. Papp, and P. Takács, Complexity analysis of a full-Newton step interiorpoint
method for linear optimization, Period. Math. Hung., 73 (2016), pp. 27–42.

Zs. Darvay and P. Rigó, New interior-point algorithm for symmetric optimization based on
a positive-asymptotic barrier function, Numer. Funct. Anal. Optim., 39 (2018), pp. 1705–1726.

Zs. Darvay and P. Takács, New method for determining search directions for interior-point
algorithms in linear optimization, Optim. Lett., 12 (2018), pp. 1099–1116.

L. Derbal and Z. Kebbiche, Theoretical and numerical result for linear optimization problem
based on a new kernel function, J. Sib. Fed. Univ. Math. Phys., 12 (2019), pp. 160–172.

M. E-Nagy, T. Illés, J. Povh, A. Varga, and J. Zerovnik, Sufficient matrices: properties,
generating and testing, J. Optim. Theory Appl., 202 (2024), pp. 204–236.

M. E-Nagy and A. Varga, A new Ai-Zhang type interior point algorithm for sufficient linear
complementarity problems, J. Optim. Theory Appl., 202 (2024), pp. 76–107.

F. Facchinei and J.-S. Pang, Finite-Dimens. Var. Inequal. Complement. Probl., Springer,
New York, 2003.

T. Illés, P. Rigó, and R. Török, Unified approach of interior-point algorithms for P∗(κ)-
LCPs using a new class of algebraically equivalent transformations, J. Optim. Theory
Appl., 202 (2024), pp. 27–49.

M. Kojima, N. Megiddo, T. Noma, and A. Yoshise, A Unified Approach to Interior Point
Algorithms for Linear Complementarity problems, vol. 538, Springer-Verlag, New York,
1991.

G. Lesaja and C. Roos, Unified analysis of kernel-based interior-point methods for P∗(κ)-
LCP, SIAM J. Optim., 20 (2010), pp. 3014–3039.

G. Lesaja, G. Q. Wang, and 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 (2012), pp. 827–843.

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 (2006), pp. 871–890.

R. Monteiro and S. Wright, A superlinear infeasible-interior-point affine scaling algorithm
for LCP, SIAM J. Optim., 6 (1996), pp. 1–20.

J. Peng, C. Roos, and T. Terlaky, Self-Regularity: A New Paradigm for Primal-Dual
Interior-Point Algorithms, Princeton University Press, 2002.

F. Potra, A superlinearly convergent predictor-corrector method for degenerate LCP in a
wide neighborhood of the central path with O(√nL)-iteration complexity, Math. Program., Ser. A, 100 (2004), pp. 317–337.

F. Potra and X. Liu, Predictor-corrector methods for sufficient linear complementarity problems
in a wide neighborhood of the central path, Optim. Methods Softw., 20 (2005), pp. 145–168.

J. Renegar, A Mathematical View of Interior-Point Methods in Convex Optimization,
MPS/SIAM Ser. Optim., SIAM, Philadelphia, 2001.

C. Roos, T. Terlaky, and J. P. Vial, Theory and Algorithms for Linear Optimization.
An Interior-Point Approach, Springer Science, 2005.

L. Tuncel and M. Todd, On the interplay among entropy, variable metrics and potential
functions in interior-point algorithms, Comput. Optim. Appl., 8 (1997), pp. 5–19.

H. Väliaho, P∗-matrices are just sufficient, Linear Algebra Appl., 239 (1996), pp. 103–108.

G. Wang, M. El Ghami, and T. Steighaug, A new parametric kernel function with trigonometric
barrier term for convex quadratic symmetric cone optimization, Appl. Anal. Optim., 1 (2017), pp. 19–44.

Y. Ye, On homogeneous and self-dual algorithms for LCP, Math. Program., 76 (1997), pp. 211–221.