FINDING NORMAL SOLUTIONS IN PIECEWISE-LINEAR PROGRAMMING

Let f: R(n) --> (-infinity, infinity] be a convex polyhedral function. We show that if any standard active set method for quadratic programm ing (QP) finds x(t) = arg min(x)\x\(2)/2 + tf(x) for some t > 0, then its final working set defines a simple equality QP subproblem, whose L agrange multiplier can be used both for testing if t is large enough f or x(t) to coincide with the normal minimizer of f, and for increasing t otherwise. The QP subproblem may easily be solved via the matrix fa ctorizations used for finding x(t). This opens up the way for efficien t implementations. We also give finite methods for computing the whole trajectory {x(t)}(t greater than or equal to 0), minimizing f over an ellipsoid, and choosing penalty parameters in L(1)QP methods for stri ctly convex QP.