The Solution of SemiInfinite Linear Programs using Boostinglike methods
(invited lecture for ALT 2006)
Author: Gunnar Rätsch
Affiliation: Friedrich Miescher Labor der Max Planck Gesellschaft,
Tübingen, Germany
Abstract.
We consider methods for the solution of large linear optimization
problems, in particular socalled SemiInfinite Linear
Programs (SILPs) that have a finite number of variables but infinitely many
linear constraints. We illustrate that such optimization problems
frequently appear in machine learning and discuss several examples
including maximum margin boosting, multiple kernel learning and
structure learning.
In the second part we review methods for solving SILPs. Here, we are
particularly interested in methods related to boosting. We review
recent theoretical results concerning the convergence of these
algorithms and conclude this work with a discussion of empirical
results comparing these algorithms.
©Copyright 2006 Author
