A lower bound on the iterative complexity of the Harker and Pang globalization technique of the Newton-min algorithm for solving the linear complementarity problem

Aganagić, 1984, Newton’s method for linear complementarity problems, Math Program, 28, 349, 10.1007/BF02612339

Armijo, 1966, Minimization of functions having Lipschitz continuous first partial derivatives, Pac J Math, 16, 1, 10.2140/pjm.1966.16.1

Ben Gharbia I (2012) Résolution de Problèmes de Complémentarité: application à un Écoulement Diphasique Dans un Milieu Poreux. Ph.D. Thesis, Université Paris-Dauphine

Ben Gharbia, 2012, Nonconvergence of the plain Newton-min algorithm for linear complementarity problems with a P-matrix, Math Program, 134, 349, 10.1007/s10107-010-0439-6

Ben Gharbia, 2013, An algorithmic characterization of P-matricity, SIAM J Matrix Anal Appl, 34, 904, 10.1137/120883025

Ben Gharbia, 2019, An algorithmic characterization of P-matricity II: adjustments, refinements, and validation, SIAM J Matrix Anal Appl, 40, 800, 10.1137/18M1168522

Bergounioux, 1999, Primal-dual strategy for constrained optimal control problems, SIAM J Control Optim, 37, 1176, 10.1137/S0363012997328609

Bergounioux, 2000, A comparison of a Moreau-Yosida-based active set strategy and interior point methods for constrained optimal control problems, SIAM J Optim, 11, 495, 10.1137/S1052623498343131

Bonnans, 2006

Burke, 1999, A polynomial time interior-point path-following algorithm for LCP based on Chen-Harker-Kanzow smoothing techniques, Math Program, 86, 91, 10.1007/s101070050081

Burke, 2002, Complexity of a noninterior path-following method for the linear complementarity problem, J Optim Theory Appl, 112, 53, 10.1023/A:1013040428127

Chandrasekaran, 1970, A special case of the complementary pivot problem, Opsearch, 7, 263

Chen, 1993, A non-interior continuation method for linear complementarity problems, SIAM J Matrix Anal Appl, 14, 1168, 10.1137/0614081

Chung, 1989, NP-completeness of the linear complementarity problem, J Optim Theor Appl, 60, 393, 10.1007/BF00940344

Conn AR, Gould NIM, Toint PhL (2000) Trust-region methods. MPS-SIAM series on optimization 1. SIAM and MPS, Philadelphia. https://doi.org/10.1137/1.9780898719857

Cottle, 2009

Curtis, 2015, A globally convergent primal-dual active-set framework for large-scale convex quadratic optimization, Comput Optim Appl, 60, 311, 10.1007/s10589-014-9681-9

Dennis, 1983

Dussault J-P, Frappier M, Gilbert JC (2018) Nmhp, version 1.0. https://who.rocq.inria.fr/Jean-Charles.Gilbert/codes/nmhp/nmhp.zip

Dussault J-P, Frappier M, Gilbert JC (2019) A globally convergent polyhedral Newton-min algorithm for solving a nonlinear complementarity problem. Technical report (to appear)

Fathi, 1979, Computational complexity of LCPs associated with positive definite symmetric matrices, Math Program, 17, 335, 10.1007/BF01588254

Fischer, 1996, On finite termination of an iterative method for linear complementarity problems, Math Program, 74, 279, 10.1007/BF02592200

Harker, 1990, A damped-Newton method for the linear complementarity problem

Hintermüller, 2003, The primal-dual active set strategy as a semismooth Newton method, SIAM J Optim, 13, 865, 10.1137/S1052623401383558

Hotta, 2000, A complexity analysis of a smoothing method using CHKS-functions for monotone linear complementarity problems, Comput Optim Appl, 17, 183, 10.1023/A:1026550331760

Izmailov, 2014, 10.1007/978-3-319-04247-3

Kanzow, 1996, Some noninterior methods for linear complementarity problems, SIAM J Matrix Anal Appl, 17, 851, 10.1137/S0895479894273134

Kanzow, 2004, Inexact semismooth Newton methods for large-scale complementarity problems, Optim Methods Softw, 19, 309, 10.1080/10556780310001636369

Kojima, 1986, Extension of Newton and quasi-Newton methods to systems of PC1 equations, J Oper Res Soc Jpn, 29, 352

Kojima, 1991

Kojima, 1991, A unified approach to interior point algorithms for linear complementarity problems: a summary, Oper Res Lett, 10, 247, 10.1016/0167-6377(91)90010-M

Kostreva MM (1976) Direct algorithms for complementarity problems. Ph.D. Thesis, Rensselaer Polytechnic Institute, Troy, New York

Mangasarian, 1977, Solution of symmetric linear complementarity problems by iterative methods, J Optim Theor Appl, 22, 465, 10.1007/BF01268170

Mizuno, 1989, Practical polynomial time algorithms for linear complmentarity problems, J Oper Res Soc Jpn, 32, 75

Murty, 1974, Note on a Bard-type scheme for solving the complementarity problem, Opsearch, 11, 123

Murty, 1978, Computational complexity of complementarity pivot methods, Math Program Stud, 7, 61, 10.1007/BFb0120782

Murty, 1988

Pang, 1990, Newton’s method for B-differentiable equations, Math Oper Res, 15, 311, 10.1287/moor.15.2.311

Pang, 1991, A B-differentiable equation-based, globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems, Math Program, 51, 101, 10.1007/BF01586928

Qi, 1993, A nonsmooth version of Newton’s method, Math Program, 58, 353, 10.1007/BF01581275

Samelson, 1958, A partition theorem for the Euclidean n-space, Proc Am Math Soc, 9, 805