When LP is not a good idea - using structure in polyhedral optimization problems

Michael Osborne (mike.osbornemaths.anu.edu.au)

Abstract: 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.

Keywords: linear programming, l_1 estimation, rank regression, simplicial algorithm, line search, structure functional, active set method, homotopy method, the lasso, support vector regression

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 2: Applications -- Science and Engineering (Statistics )

Category 3: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Mathematical Science Institute, Australian National University, A.C.T 0200, Australia December, 2003

Download: [PDF]

Entry Submitted: 12/10/2003
Entry Accepted: 12/11/2003
Entry Last Modified: 12/10/2003

Modify/Update this entry