  


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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  