Linear Complementarity Problems: Applications, Formulations and Algorithms
The Linear Complementarity Problem (LCP) consists of finding two nonnegative vectors satisfying linear constraints and complementarity conditions between pairs of components of the same order. The LCP has found many applications in several areas of science, engineering, finance and economics. In this talk the LCP and some important extensions of this problem are first introduced together with some of their most relevant properties and applications. A number of formulations of optimization problems are shown to be formulated as an LCP or one of its extensions. These include Linear and Quadratic Programming, Affine Variational Inequalities, Bilevel Programming, Bilinear Programming, 0-1 Integer Programming, Fixed-Charge Problems, Absolute Value Programming, Copositive Programming, Fractional Quadratic Programming, Linear and Total Least-Squares Problems, Eigenvalue Complementarity Problems, Matrix Condition Number Estimation, Clique and Independent Numbers of a Graph and Mathematical Programming with Cardinality Constraints. The most relevant algorithms for solving LCP and its extensions are briefly reviewed. The benefits and drawbacks of solving these optimization problems by using complementarity algorithms applied to their formulations are discussed. Finally, some topics for future research are presented at the end of this talk.