ANZIAM J. 46(E) ppC196--C209, 2005.

Polyhedral function constrained optimization problems

M. R. Osborne
(Received 25 October 2004, revised 1 March 2005)

Abstract

Recently polyhedral functions have proved distinctly useful in expressing selection criteria in various model building techniques. Here they play the role of a constraint on an estimation problem. Whereas they can always be replaced by an appropriate family of linear constraints, the resulting set can be a very large. Compact representations are available and their use is illustrated by developing both active set and homotopy algorithms for the general polyhedral constrained problem. These are illustrated using some well known data sets.

Download to your computer

Authors

M. R. Osborne
Mathematical Sciences Institute, Australian National University, ACT 0200, Australia. mailto:Mike.Osborne@maths.anu.edu.au

Published April 22, 2005. ISSN 1446-8735

References

  1. S. S. Chen, D. L. Donoho, and M. A. Saunders, Atomic decomposition by basis pursuit, SIAM J. Sci. Comput. 20 (1998), no. 1, 33--61. http://www.siam.org/journals/sissc/20-1/30401.html
  2. Trevor Hastie, Saharon Rosset, Rob Tibshirani, and Ji Zhu, The entire regularization path for the support vector machine, Statistics Department Technical Report, Stanford University, 2003. http://jmlr.csail.mit.edu/papers/volume5/hastie04a/hastie04a.pdf.
  3. M. R. Osborne, Simplicial algorithms for minimizing polyhedral functions, Cambridge University Press, 2001.
  4. M. R. Osborne, Brett Presnell, and B. A. Turlach, A new approach to variable selection in least squares problems, IMA J. Numerical Analysis 20 (2000), 389--403. http://imanum.oupjournals.org/cgi/content/abstract/20/3/389.
  5. Saharon Rosset, and Ji Zhu, Piecewise linear regularised solution paths, Statistics Department Technical Report, Stanford University, 2003. http://www-stat.stanford/%7Esaharon/papers/piecewise.ps.
  6. R. Tibshirani, Regression shrinkage and selection via the lasso, J. R. S. S. B 58 (1996), no. 1, 267--288. http://citeseer.ist.psu.edu/tibshirani94regression.html.
  7. V. Vapnik, S. E. Golowich, and A. Smola, Support vector method for function approximation, regression estimation, and signal processing, Advances in Neural Information Processing Systems (M. C. Mozer, M. I. Jordan, and T. Petsche, eds.), MIT Press, 1997. http://citeseer.ist.psu.edu/vapnik96support.html
  8. Ji Zhu, Saharon Rosset,Trevor Hastie, and Rob Tibshirani, 1-norm support vector machines, Advances in Neural Information Processing Systems 16, MIT Press, 2004. http://www-stat.stanford/%7Esaharon/papers/svmL1.ps
Copyright Austral. Mathematical Soc.; prepared April 22, 2005, from Osbo.tex with anziamje.sty (v2.3c)