A Pivoting Algorithm for Linear Programming with Linear Complementarity Constraints

TitleA Pivoting Algorithm for Linear Programming with Linear Complementarity Constraints
Publication TypeJournal Article
Year of Publication2009
AuthorsFang, H, Leyffer, S, Munson, TS
JournalOptimization Methods Software
Date Published10/2009
Other NumbersANL/MCS-P1680-1009
Abstract

We present a pivoting algorithm for solving linear programs with linear complementarity constraints. Our method generalizes the simplex method for linear programming to deal with complementarity conditions. We develop an anticycling scheme that can verify Bouligand stationarity. We also give an optimization based technique to find an initial feasible vertex. Starting with a feasible vertex, our algorithm always finds a minimizer or an unbounded descent search direction in a finite number of pivoting steps.

URLhttp://www.optimization-online.org/DB_HTML/2009/11/2446.html
PDFhttp://www.mcs.anl.gov/papers/P1680.pdf