On Linear Programs with Linear Complementarity Constraints
Accepted for publication in the
Journal of Global Optimization,
53(1), pages 29-51,
2012.
Download the paper,
in pdf.
Authors:
Jing Hu
Market Analytics, Inc., 500 Davis Street, Suite 1001, Evanston, Illinois 60201.
John E. Mitchell
mitchj at rpi dot edu
Department of
Mathematical Sciences, Rensselaer Polytechnic
Institute, Troy,
New York 12180-3590, U.S.A
Jong-Shi
Pang
jspang at illinois dot edu
Industrial and Enterprise Systems
Engineering,
University of Illinois at Urbana-Champaign,
117 Transportation Bldg., 104 S. Mathews Ave., Urbana, IL 61801.
Bin Yu
yub at rpi dot edu
Department of
Decision Sciences and Engineering Systems,
Rensselaer Polytechnic
Institute, Troy,
New York 12180-3590, U.S.A
Abstract:
The paper is a manifestation of the fundamental importance
of the linear program with linear complementarity constraints (LPCC)
in disjunctive and hierarchical programming as well as in some novel
paradigms of mathematical programming. In addition to providing
a unified framework for bilevel and inverse linear optimization,
nonconvex piecewise linear programming, indefinite quadratic programs,
quantile minimization, and zero-norm minimization, the LPCC provides
a gateway to a mathematical program with equilibrium constraints,
which itself is an important class of constrained optimization problems
that has broad applications. We describe several approaches for
the global resolution of the LPCC, including
a logical Benders approach that can be applied to problems that may be
infeasible or unbounded.
Keywords:
linear programs with linear complementarity constraints;
LPECs;
inverse programming;
hierarchical programming;
piecewise linear;
quantile minimization;
cross-validated support vector regression
Download the paper,
in pdf.
Return to my list of papers.