A Globally Convergent Probability-One Homotopy
for Linear Programs with Linear Complementarity Constraints
Download the paper,
in pdf.
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
SIAM Journal on Optimization, 23(2), 1167-1188, 2013.
Download the paper,
in pdf.
Return to my list of papers.