Interior-Point Algorithms for Monotone Linear Complementarity Problem Based on Different Predictor Directions

References

• [1] Chung S (1989) NP-completeness of the linear complementarity problem. J. Optim. Theory Appl. 60(3):393–399.Crossref, Google Scholar
• [2] Cottle R, Pang J, Stone R (1992) The Linear Complementarity Problem, Computer Science and Scientific Computing (Academic Press, Boston).Google Scholar
• [3] E.-Nagy M, Illés T, Nesterov Y, Rigó PR (2025) Parabolic target space interior-point algorithms for weighted monotone linear complementarity problem. Math. Programming 219:553–582.Crossref, Google Scholar
• [4] E.-Nagy M, Illés T, Nesterov Y, Rigó PR (2026) New interior-point algorithm for linear optimization based on a universal tangent direction. SIAM J. Optim. 36(1):185–203.Crossref, Google Scholar
• [5] Illés T, Peng J, Roos C, Terlaky T (2000) A strongly polynomial rounding procedure yielding a maximally complementary solution for P*(κ) linear complementarity problems. SIAM J. Optim. 11(2):320–340.Crossref, Google Scholar
• [6] Jansen B, Roos C, Terlaky T, Vial JP (1996) Primal-dual target-following algorithms for linear programming. Ann. Oper. Res. 62:197–231.Crossref, Google Scholar
• [7] Kojima M, Mizuno S, Yoshise A (1989) A polynomial-time algorithm for a class of linear complementarity problems. Math. Programming 44(1–3):1–26.Crossref, Google Scholar
• [8] Kojima M, Megiddo N, Noma T, Yoshise A (1991) A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, Lecture Notes in Computer Science, vol. 538 (Springer, Berlin, Heidelberg).Crossref, Google Scholar
• [9] Nesterov Y (2008) Parabolic target space and primal–Dual interior-point methods. Discrete Appl. Math. 156(11):2079–2100.Crossref, Google Scholar
• [10] Potra F (2001) Q-superlinear convergence of the iterates in primal-dual interior-point methods. Math. Programming 91:99–115.Crossref, Google Scholar
• [11] Qi L, Sun D, Zhou G (2000) A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities. Math. Programming 87:1–35.Crossref, Google Scholar
• [12] Roos C, Terlaky T, Vial JP (1997) Theory and Algorithms for Linear Optimization. An Interior Approach (John Wiley & Sons, Chichester, UK).Google Scholar
• [13] Ye Y (1997) Interior Point Algorithms, Theory and Analysis (John Wiley & Sons, Chichester, UK).Crossref, Google Scholar
• [14] Ye Y, Anstreicher K (1993) On quadratic and O(nL) convergence of a predictor-corrector algorithm for LCP. Math. Programming 62:537–551.Crossref, Google Scholar
• [15] Yu N (2018) Lectures on Convex Optimization, Springer Optimization and Its Applications (Springer, Cham, Switzerland).Google Scholar
• [16] Yu N (2024) Local and global convergence of greedy parabolic target-following methods for linear programming. Preprint, submitted December 19, https://arxiv.org/abs/2412.14934.Google Scholar
• [17] Yu N, Nemirovskii A (1994) Interior Point Polynomial Methods in Convex Programming, SIAM Studies in Applied Mathematics, vol. 13 (SIAM Publications, Philadelphia).Google Scholar