A branch and cut approach to linear programs with linear complementarity constraints.

摘要

In this thesis, the primary problem of interest is the Linear Program with Linear Complementarity Constraints (LPCC), consisting of minimizing a linear objective function over a set of linear constraints with a set of linear complementarity constraints. The LPCC provides a unified framework for various optimization models, such as hierarchical optimization, inverse convex quadratic programs, indefinite quadratic programs, piecewise linear optimization and quantile minimization, as well as optimization problems with equilibrium constraints. However due to the fact that complementarity constraints are non-convex in nature, meaning the LPCC is NP-hard, finding the global resolution of the LPCC is a big challenge.;Different from traditional approaches for accommodating such complementarity constraints which introduce additional binary variables and a conceptually very large scalar theta and solve the resulting mixed-integer programming problem, we exploit the disjunctive structure of LPCC directly. We discuss various methods to tighten the linear relaxation of LPCC. Different types of linear constraints and second order cone constraints which are valid for LPCC are both being studied. Computational results are included to compare the benefit of the various constraints on the value of the relaxation. Then we propose a branch and cut algorithm to globally solve the LPCC problem, where branching is imposed directly on complementarity constraints. The algorithm is able to characterize infeasible and unbounded LPCC problems as well as solve problems with finite optimal value. We test our algorithm on randomly generated problems, and compare the results by using different cutting planes and branching strategies.;Finally a data mining application of LPCC, the cross-validated support vector regression problem, is fully explored. In this application, we present a bilevel programming formulation for a cross-validated support vector regression problem with (C, epsilon) as the design variables, and then convert it into an instance of an LPCC by writing out the KKT condition of the inner quadratic program which is strictly convex. By taking advantage of the properties of this LPCC formulation and its original bilevel formulation, we use our proposed algorithm with the customized preprocessing routine to attack this challenging problem. The computational result shows that our approach has the capability to solve this type of problem with small size dataset.