ITERATIVE SCHEMES FOR THE LEAST 2-NORM SOLUTION OF PIECEWISE-LINEAR PROGRAMS

Let f:R(n) --> (-infinity, infinity] be a convex polyhedral function. We show how to find the normal minimizer of f and the associated Lagra nge multipliers by computing x(epsilon) = arg min(x) f(x) + epsilon\X\ (2) /2 approximately for a sequence of epsilon down arrow O via any re laxation method applied to the corresponding dual problems. Our scheme s generalize those of Mangasarian and De Leone for solving very large sparse linear programs.