Solving Semi-Infinite Linear Programs Using Boosting-like Methods

Abstract

Linear optimization problems (LPs) with a very large or even infinite number of constraints frequently appear in many forms in machine learning. A linear program with m constraints can be written as $ \begin{array}{lll} \min\limits_{{\mathbf{x}}\in{\mathcal{P}}^n} && {\bf c}^\top {\mathbf{x}} \\ \mbox{with} && {\bf a}_j^\top {\mathbf{x}}\leq b_j \quad \forall i=1,\ldots, m,\end{array} $ where I assume for simplicity that the domain of x is the n dimensional probability simplex ${\mathcal{P}}^n$ . Optimization problems with an infinite number of constraints of the form ${\bf a}_j^\top {\mathbf{x}}\leq b_j$ , for all j ∈ J , are called semi-infinite , when the index set J has infinitely many elements, e.g. J =ℝ. In the finite case the constraints can be described by a matrix with m rows and n columns that can be used to directly solve the LP. In semi-infinite linear programs (SILPs) the constraints are often given in a functional form depending on j or implicitly defined, for instance by the outcome of another algorithm.