It has been known for almost 50 years that the discrete l_1 approximation problem can be solved effectively by linear programming. However, improved algorithms involve a step which can be interpreted as a line search, and which is not part of the standard LP solution procedures. l_1 provides the simplest example of a class of problems with a structure distinctly more complicated than that of the nondegenerate linear program. Here, the aim is to uncover this structure for these more general polyhedral functions and to show that this knowledge can be used to develop what are recognizably algorithms of simplicial type for minimizing them. A key component of this work is a compact local description of polyhedral convex functions. This can be applied also in the development of active set methods in polyhedral function constrained optimization problems. Applications include the development of new methods for problems in statistical estimation and data analysis.
Citation
Mathematical Science Institute, Australian National University, A.C.T 0200, Australia December, 2003