Polyhedral optimization

The homotopy algorithm of Osborne, Presnel and Turlach for minimizing a sum of squares subject to a constraint on the variables (the so called lasso - a particular case of a polyhedral constraint) has proved spectacularly successful in applications to a range of variable selection problems in which the aim is the selection of a minimum set of variables in linear models compatible with adequate model representation of the observed signal. In many cases it takes just k steps to select k variables.

Applications include compressed sensing where economical signal representation has realized bandwidth reductions of up to ten times. There is still work to be done on the original problem for objectives other than a sum of squares and for other forms of polyhedral constraints. A piecewise linear homotopy trajectory requires that the objective be locally at most quadratic. For maximum likelihood estimation in the case of linear models this requires piecewise linear or piecewise quadratic approximation of the log density terms as a function of their arguments. The piecewise nature means that homotopy slope discontinuities occur not only where the variable set changes (a selection step) but also where the local representation changes. There has been some work on the locally quadratic case. A new question is what is required for accuracy control of the local approximation of the objective in a variable selection exercise. Also, it should be possible to make at least some progress for some nonlinear models by using low order multivariate splines for example.