Applied Mathematics and Optimization, Vol.32, No.3, 235-254, 1995
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 programming (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 Lagrange multiplier can be used both for testing if t is large enough for 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 factorizations used for finding x(t). This opens up the way for efficient 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 strictly convex QP.