A Descent Algorithm for Minimizing Polyhedral Convex Functions
D. I. Clark, Michael Robert Osborne · SIAM Journal on Scientific and Statistical Computing · 1983
The idea of continuation applied to the proximal transform of a polyhedral convex function is used to develop a general procedure for the construction of descent algorithms which has the property that it specializes to variants of the projected gradient method when applied to such problems as $l_1 $ and $l_\infty $ curve fitting and linear programming. The novelty in this approach lies in the application of a generic form for the subdifferential of a polyhedral convex function which provides an explicit representation in terms of a small number of parameters. This is illustrated by applications to $l_\infty $ curve fitting and the minimization of piecewise linear functions, and these examples serve to establish the feasibility of a unified approach. The power of the method is demonstrated by deriving an effective algorithm for the rank regression problem (the existence of such an algorithm makes practical the application of nonparametric procedures based on rank in robust estimation). The new approach also opens up the possibility of common implementation strategies, and a tableau like scheme is decribed based on the use of orthogonal matrix factorizations.