A Mathematical Program with Linear Complementarity Constraints (MPLCC) is an optimization problem where a continuously differentiable function is minimized on a set defined by linear constraints and complementarity conditions on pairs of complementary variables. This problem finds many applications in several areas of science, engineering, finance and economics and is also an important tool for solving some NP-hard global problems.
The problems of finding a feasible solution, a stationary point and a global minimum for the MPLCC are addressed in this talk. Local algorithms can be used to compute a feasible solution of the MPLCC in some special cases. In general, finding such a solution is an NP-hard problem and enumerative algorithms for quadratic or 0-1 linear integer formulations of this problem are required for such a task.
A complementarity active-set method is recommended to find a stationary point for an MPLCC. The algorithm requires a feasible solution to start with and reduces to a basis restricted simplex method when the objective function is linear.
Branch-and-bound algorithms are the most traditional approaches for computing a global minimum to an MPLCC. RLT and SDP techniques are used to speed up the convergence to such a point. A sequential algorithm computing stationary points of the MPLCC with strictly reducing objective function values is also discussed. Finally, the MPLCC can be solved by using a special purpose 0-1 integer programming. Some comments about the performance of these approaches and a few topics for future research are also presented in this talk.
Homepage of Joaquim João Júdice