A new branch and bound algorithm for solving quadratic programs with linear complementarity constraints

摘要

In order to find a global solution for a quadratic program with linear complementarity constraints (QPLCC) more quickly than some existing methods, we consider to embed a local search method into a global search method. To say more specifically, in a branch-and-bound algorithm for solving QPLCC, when we find a new feasible solution to the problem, we utilize an extreme point algorithm to obtain a locally optimal solution which can provide a better bound and help us to trim more branches. So, the global algorithm can be accelerated. A preliminary numerical experiment was conducted which supports the new algorithm.