ref_complementarity.bib

@article{scheelMathematicalProgramsComplementarity2000,
  title = {Mathematical {{Programs}} with {{Complementarity Constraints}}: {{Stationarity}}, {{Optimality}}, and {{Sensitivity}}},
  shorttitle = {Mathematical {{Programs}} with {{Complementarity Constraints}}},
  author = {Scheel, Holger and Scholtes, Stefan},
  year = {2000},
  month = feb,
  journal = {Mathematics of Operations Research},
  volume = {25},
  number = {1},
  pages = {1--22},
  issn = {0364-765X},
  abstract = {We study mathematical programs with complementarity constraints. Several stationarity concepts, based on a piecewise smooth formulation, are presented and compared. The concepts are related to stationarity conditions for certain smooth programs as well as to stationarity concepts for a nonsmooth exact penalty function. Further, we present Fiacco-McCormick type second order optimality conditions and an extension of the stability results of Robinson and Kojima to mathematical programs with complementarity constraints.}
}

@article{outrataMathematicalProgramsComplementarity2000,
  title = {On Mathematical Programs with Complementarity Constraints},
  author = {Outrata, Ji{\v r}{\'i} V.},
  year = {2000},
  month = jan,
  journal = {Optimization Methods and Software},
  volume = {14},
  number = {1-2},
  pages = {117--137},
  publisher = {Taylor \& Francis},
  issn = {1055-6788},
  doi = {10.1080/10556780008805796},
  url = {https://doi.org/10.1080/10556780008805796},
  urldate = {2022-03-21},
  abstract = {The paper deals with mathematical programs, where a complementarity problem arises among the constraints. The main attention is paid to optimality conditions and the respective constraint qualification. In addition, a simple numerical approach is proposed based on the exact penalization of the complementarity constraint.}
}

@misc{ConstraintsJuMP,
  title = {Constraints {$\cdot$} {{JuMP}}},
  url = {https://jump.dev/JuMP.jl/stable/manual/constraints/#Complementarity-constraints},
  urldate = {2022-03-21}
}

@misc{ComplementarityConstraintsArtelys,
  title = {Complementarity Constraints --- {{Artelys Knitro}} 13.0 {{User}}'s {{Manual}}},
  url = {https://www.artelys.com/docs/knitro/2_userGuide/complementarity.html},
  urldate = {2022-03-21}
}

@article{fletcherSolvingMathematicalPrograms2004,
  title = {Solving Mathematical Programs with Complementarity Constraints as Nonlinear Programs},
  author = {Fletcher, Roger and Leyffer, Sven},
  year = {2004},
  month = feb,
  journal = {Optimization Methods and Software},
  volume = {19},
  number = {1},
  pages = {15--40},
  publisher = {Taylor \& Francis},
  issn = {1055-6788},
  doi = {10.1080/10556780410001654241},
  url = {https://doi.org/10.1080/10556780410001654241},
  urldate = {2022-03-21},
  abstract = {We consider solving mathematical programs with complementarity constraints (MPCCs) as nonlinear programs (NLPs) using standard NLP solvers. This approach is appealing because it allows existing off-the-shelf NLP solvers to tackle large instances of MPCCs. Numerical experience on MacMPEC, a large collection of MPCC test problems is presented. Our experience indicates that sequential quadratic programming (SQP) methods are very well suited for solving MPCCs and at present outperform interior-point solvers both in terms of speed and reliability. All NLP solvers also compare very favorably to special MPCC solvers on tests published in the literature.}
}

@misc{ComplementarityProblemsNEOS,
  title = {Complementarity {{Problems}} {\textbar} {{NEOS}}},
  url = {https://neos-guide.org/content/complementarity-problems},
  urldate = {2022-03-22}
}

@article{ferrisEngineeringEconomicApplications1997,
  title = {Engineering and {{Economic Applications}} of {{Complementarity Problems}}},
  author = {Ferris, M. C. and Pang, J. S.},
  year = {1997},
  month = jan,
  journal = {SIAM Review},
  volume = {39},
  number = {4},
  pages = {669--713},
  publisher = {{Society for Industrial and Applied Mathematics}},
  issn = {0036-1445},
  doi = {10.1137/S0036144595285963},
  url = {https://epubs.siam.org/doi/abs/10.1137/S0036144595285963},
  urldate = {2022-03-22},
  abstract = {This paper gives an extensive documentation of applications of finite-dimensional nonlinear complementarity problems in engineering and equilibrium modeling. For most applications, we describe the problem briefly, state the defining equations of the model, and give functional expressions for the complementarity formulations. The goal of this documentation is threefold: (i) to summarize the essential applications of the nonlinear complementarity problem known to date, (ii) to provide a basis for the continued research on the nonlinear complementarity problem, and (iii) to supply a broad collection of realistic complementarity problems for use in algorithmic experimentation and other studies.}
}

@techreport{ferrisComplementarityRelatedProblems1998,
  title = {Complementarity and Related Problems: {{A}} Survey},
  author = {Ferris, Michael C and Kanzow, Christian},
  year = {1998},
  month = nov,
  pages = {24},
  abstract = {This survey gives an introduction to some of the recent developments in the eld of complementarity and related problems. After presenting two typical examples and the basic existence and uniqueness results, we focus on some new trends for solving nonlinear complementarity problems. Extensions to mixed complementarity problems, variational inequalities and mathematical programs with equilibrium constraints are also discussed.},
  langid = {english}
}

@book{cottleLinearComplementarityProblem2009,
  title = {The {{Linear Complementarity Problem}}},
  author = {Cottle, Richard W. and Pang, Jong-Shi and Stone, Richard E.},
  year = {2009},
  month = aug,
  series = {Classics in {{Applied Mathematics}}},
  publisher = {{Society for Industrial and Applied Mathematics}},
  address = {Philadelphia},
  url = {https://epubs.siam.org/doi/book/10.1137/1.9780898719000},
  isbn = {978-0-89871-686-3},
  langid = {english}
}

@article{deschutterExtendedLinearComplementarity1995,
  title = {The Extended Linear Complementarity Problem},
  author = {De Schutter, Bart and De Moor, Bart},
  year = {1995},
  month = dec,
  journal = {Mathematical Programming},
  volume = {71},
  number = {3},
  pages = {289--325},
  issn = {1436-4646},
  doi = {10.1007/BF01590958},
  url = {https://doi.org/10.1007/BF01590958},
  urldate = {2022-09-16},
  abstract = {In this paper we define the Extended Linear Complementarity Problem (ELCP), an extension of the well-known Linear Complementarity Problem (LCP). We show that the ELCP can be viewed as a kind of unifying framework for the LCP and its various generalizations. We study the general solution set of an ELCP and we develop an algorithm to find all its solutions. We also show that the general ELCP is an NP-hard problem.},
  langid = {english}
}

@book{murtyLinearComplementarityLinear1997,
  title = {Linear {{Complementarity}}, {{Linear}} and {{Non-linear Programming}}},
  author = {Murty, Katta G. and Yu, Vincent F.},
  year = {1997},
  edition = {Internet edition},
  address = {Berlin},
  url = {http://www-personal.umich.edu/~murty/books/linear_complementarity_webbook/},
  isbn = {978-3-88538-403-8}
}

@article{demoorGeneralizedLinearComplementarity1992,
  title = {The Generalized Linear Complementarity Problem and an Algorithm to Find All Its Solutions},
  author = {De Moor, Bart and Vandenberghe, Lieven and Vandewalle, Joos},
  year = {1992},
  month = may,
  journal = {Mathematical Programming},
  volume = {57},
  number = {1},
  pages = {415--426},
  issn = {1436-4646},
  doi = {10.1007/BF01581091},
  url = {https://doi.org/10.1007/BF01581091},
  urldate = {2022-11-27},
  abstract = {Motivated by a number of typical applications, a generalization of the classicallinear complementarity problem is presented together with an algorithm to determine the complete solution set. The algorithm is based on the double description method for solving linear inequalities and succeeds in describing continuous as well as unbounded solution sets.},
  langid = {english}
}

@article{deschutterEquivalenceLinearComplementarity2002,
  title = {On the Equivalence of Linear Complementarity Problems},
  author = {De Schutter, B. and Heemels, W. P. M. H. and Bemporad, A.},
  year = {2002},
  month = aug,
  journal = {Operations Research Letters},
  volume = {30},
  number = {4},
  pages = {211--222},
  issn = {0167-6377},
  doi = {10.1016/S0167-6377(02)00159-1},
  url = {https://www.sciencedirect.com/science/article/pii/S0167637702001591},
  urldate = {2022-11-29},
  abstract = {We show that the Extended Linear Complementarity Problem (ELCP) can be recast as a standard Linear Complementarity Problem (LCP) provided that the surplus variables or the feasible set of the ELCP are bounded. Since many extensions of the LCP are special cases of the ELCP, this implies that these extensions can be rewritten as an LCP as well. Our equivalence proof is constructive and leads to three possible numerical solution methods for a given ELCP: regular ELCP algorithms, mixed integer linear programming algorithms, and regular LCP algorithms.},
  langid = {english}
}

@misc{hallLCQPowSolverLinear2022,
  title = {{{LCQPow}} -- {{A Solver}} for {{Linear Complementarity Quadratic Programs}}},
  author = {Hall, Jonas and Nurkanovic, Armin and Messerer, Florian and Diehl, Moritz},
  year = {2022},
  month = nov,
  number = {arXiv:2211.16341},
  eprint = {2211.16341},
  primaryclass = {math},
  publisher = {arXiv},
  url = {http://arxiv.org/abs/2211.16341},
  urldate = {2022-12-03},
  abstract = {In this paper we introduce an open-source software package written in C++ for efficiently finding solutions to quadratic programming problems with linear complementarity constraints. These problems arise in a wide range of applications in engineering and economics, and they are challenging to solve due to their structural violation of standard constraint qualifications, and highly nonconvex, nonsmooth feasible sets. This work extends a previously presented algorithm based on a sequential convex programming approach applied to a standard penalty reformulation. We examine the behavior of local convergence and introduce new algorithmic features. Competitive performance profiles are presented in comparison to state-of-the-art solvers and solution variants in both existing and new benchmarks.},
  archiveprefix = {arXiv}
}

@article{hallSequentialConvexProgramming2022,
  title = {A {{Sequential Convex Programming Approach}} to {{Solving Quadratic Programs}} and {{Optimal Control Problems With Linear Complementarity Constraints}}},
  author = {Hall, Jonas and Nurkanovi{\'c}, Armin and Messerer, Florian and Diehl, Moritz},
  year = {2022},
  journal = {IEEE Control Systems Letters},
  volume = {6},
  pages = {536--541},
  issn = {2475-1456},
  doi = {10.1109/LCSYS.2021.3083467},
  abstract = {Mathematical programs with complementarity constraints are notoriously difficult to solve due to their nonconvexity and lack of constraint qualifications in every feasible point. This letter focuses on the subclass of quadratic programs with linear complementarity constraints. A novel approach to solving a penalty reformulation using sequential convex programming and a homotopy on the penalty parameter is introduced. Linearizing the necessarily nonconvex penalty function yields convex quadratic subproblems, which have a constant Hessian matrix throughout all iterates. This allows solution computation with a single KKT matrix factorization. Furthermore, a globalization scheme is introduced in which the underlying merit function is minimized analytically, and guarantee of descent is provided at each iterate. The algorithmic features and possible computational speedups are illustrated in a numerical experiment.}
}

@techreport{eavesEquivalenceLCPPLS1979,
  title = {Equivalence of {{LCP}} and {{PLS}}},
  author = {Eaves, B. C. and Lemke, C. E.},
  year = {1979},
  address = {Stanford, CA},
  institution = {Stanford University},
  url = {https://apps.dtic.mil/sti/pdfs/ADA080890.pdf},
  urldate = {2022-12-04}
}

@article{lootsmaUniquenessSolutionsLinear1999,
  title = {Uniqueness of Solutions of Linear Relay Systems},
  author = {Lootsma, Y. J. and {van der Schaft}, A. J. and {\c C}aml{\i}bel, M. K.},
  year = {1999},
  month = mar,
  journal = {Automatica},
  volume = {35},
  number = {3},
  pages = {467--478},
  issn = {0005-1098},
  doi = {10.1016/S0005-1098(98)90177-7},
  url = {https://www.sciencedirect.com/science/article/pii/S0005109898901777},
  urldate = {2022-12-04},
  abstract = {Conditions are given for uniqueness of solutions of linear time-invariant systems under relay feedback. From a hybrid dynamical point of view this entails the deterministic specification of the discrete transition rules. The results are based on the formulation of relay systems as complementarity systems, and use the constructive theory of the Linear Complementarity Problem.},
  langid = {english}
}

@article{fischerNewtontypeMethodPositivesemidefinite1995,
  title = {A {{Newton-type}} Method for Positive-Semidefinite Linear Complementarity Problems},
  author = {Fischer, A.},
  year = {1995},
  month = sep,
  journal = {Journal of Optimization Theory and Applications},
  volume = {86},
  number = {3},
  pages = {585--608},
  issn = {1573-2878},
  doi = {10.1007/BF02192160},
  url = {https://doi.org/10.1007/BF02192160},
  urldate = {2023-11-28},
  abstract = {The paper presents a damped and perturbed Newton-type method for solving linear complementarity problems with positive-semidefinite matricesM. In particular, the following properties hold: all occurring subproblems are linear equations; each subproblem is uniquely solvable without any assumption; every accumulation point generated by the method solves the linear complementarity problem. The additional property ofM to be an R0-matrix is sufficient, but not necessary, for the boundedness of the iterates. Provided thatM is positive definite on a certain subspace, the method converges Q-quadratically.},
  langid = {english}
}

@article{dirksePathSolverNommonotone1995,
  title = {The Path Solver: A Nommonotone Stabilization Scheme for Mixed Complementarity Problems},
  shorttitle = {The Path Solver},
  author = {Dirkse, Steven P. and Ferris, Michael C.},
  year = {1995},
  month = jan,
  journal = {Optimization Methods and Software},
  volume = {5},
  number = {2},
  pages = {123--156},
  publisher = {Taylor \& Francis},
  issn = {1055-6788},
  doi = {10.1080/10556789508805606},
  url = {https://doi.org/10.1080/10556789508805606},
  urldate = {2023-11-28},
  abstract = {The PATH solver is an implementation of a stabilized Newton method for the solution of the Mixed Complementarity Problem. The stabilization scheme employs a path-generation procedure which is used to construct a piecewise-linear path from the current point to the Newton point; a step length acceptance criterion and a non-monotone pathsearch are then used to choose the next iterate. The algorithm is shown to be globally convergent under assumptions which generalize those required to obtain similar results in the smooth case. Several imple{$\acute{\epsilon}$}entation issues are discussed, and extensive computational results obtained from problems commonly found in the literature are given}
}

@misc{TalkiitPdf,
  title = {Complementarity Problems and Complementarity Constraint},
  author = {Anitescu, Michai},
  url = {https://web.cels.anl.gov/~anitescu/Presentations/2006/talkiit.pdf},
  urldate = {2023-11-29}
}

@article{eavesLinearComplementarityProblem1971,
  title = {The {{Linear Complementarity Problem}}},
  author = {Eaves, B. Curtis},
  year = {1971},
  month = may,
  journal = {Management Science},
  volume = {17},
  number = {9},
  pages = {612--634},
  publisher = {INFORMS},
  issn = {0025-1909},
  doi = {10.1287/mnsc.17.9.612},
  url = {https://pubsonline.informs.org/doi/abs/10.1287/mnsc.17.9.612},
  urldate = {2023-11-29},
  abstract = {This study centers on the task of efficiently finding a solution of the linear complementarity problem: Ix - My = q, x {$\geq$} 0, y {$\geq$} 0, x {$\perp$} y. The main results are: (1) It is shown that Lemke's algorithm will solve (or show no solution exists) the problem for M {$\in$} L where L is a class of matrices, which properly includes (i) certain copositive matrices, (ii) certain matrices with nonnegative principal minors, (iii) matrices for bimatrix games. (2) If M {$\in$} L, if the system Ix - My = q, x {$\geq$} 0, y {$\geq$} 0 is feasible and nondegenerate, then the corresponding linear complementarity problem has an odd number of solutions. If M {$\in$} L and q {$>$} 0 then the solution is unique. (3) If for some M and every q {$\geq$} 0 the problem has a unique solution then M {$\in$} L and the problem has a solution for every q. (4) If M has nonnegative principal minors and if the linear complementarity with M and q has a nondegenerate complementary solution then the solution is unique. (5) If yTMy + yTq is bounded below on y {$\geq$} 0 then the linear complementarity problem with M and q has a solution and Lemke's algorithm can be used to find such a solution. If, in addition, the problem is nondegenerate, then it has an odd number of solutions. (6) A procedure based on Lemke's algorithm is developed which either computes stationary points for general quadratic programs or else shows that the program has no optimum. (7) If a quadratic program has an optimum and satisfies a nondegeneracy condition then there are an odd number of stationary points.}
}