A Globally Convergent Probability-One Homotopy for Linear Programs with Linear Complementarity Constraints


Layne T. Watson
ltw at cs dot vt dot edu
Mathematics and Computer Science
Virginia Tech

Stephen C. Billups
Stephen dot Billups at ucdenver dot edu
University of Colorado at Denver

John E. Mitchell
mitchj at rpi dot edu
Department of Mathematical Sciences,
Rensselaer Polytechnic Institute, Troy, New York 12180-3590, U.S.A

David R. Easterling
Computer Science
Virginia Tech

March 2011.


A solution of the standard formulation of a linear program with linear complementarity constraints (LPCC) does not satisfy a constraint qualification. A family of relaxations of an LPCC, associated with a probability-one homotopy map, proposed here is shown to have several desirable properties. The homotopy map is nonlinear, replacing all the constraints with nonlinear relaxations of NCP functions. Under mild existence and rank assumptions, (1) the LPCC relaxations RLPCC(lambda) have a solution for 0 <= lambda <= 1, (2) RLPCC(1) is equivalent to LPCC, (3) the Kuhn-Tucker constraint qualification is satisfied at every local or global solution of RLPCC(lambda) for almost all 0 <= lambda <= 1, (4) a point is a local solution of RLPCC(1) (and LPCC) if and only if it is a Kuhn-Tucker point for RLPCC(1), and (5) a homotopy algorithm can find a Kuhn-Tucker point for RLPCC(1). Since the homotopy map is a globally convergent probability-one homotopy, robust and efficient numerical algorithms exist to find solutions of RLPCC(1). Numerical results are included for some small problems.

Keywords: complementarity, constraint qualification, globally convergent, homotopy algorithm, linear program, probability-one homotopy

Journal submission.

Return to my list of papers.