Regularized Linear Programs with Equilibrium Constraints

Abstract

We consider an arbitrary linear program with equilibrium constrains (LPEC) that may possibly be infeasible or have an unbounded objective function. We regularize the LPEC by perturbing it in a minimal way so that the regularized problem is solvable. We show that such regularization leads to a problem that is guaranteed to have a solution which is an exact solution to the original LPEC if that problem is solvable, otherwise it is a residual-minimizing approximate solution to the original LPEC. We propose a finite successive linearization algorithm for the regularized problem that terminates at point satisfying the minimum principle necessary optimality condition for the problem.