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

### Authors:

**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

Mathematics

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.

### Abstract:

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.