Conditional gradient methods on unbounded feasible regions

Abstract

The conditional gradient method is attractive when linear minimization over the feasible region is substantially cheaper than projection. Its classical convergence theory, however, is formulated for compact feasible sets, whereas many natural convex feasible regions are closed and unbounded. This paper studies a simple compact-restriction principle for applying conditional gradient steps to unbounded feasible regions. The first scheme uses one compact convex set containing the initial objective sublevel set. The second scheme updates the restriction by intersecting compact convex sets generated along the iterations. In both cases the linear minimization oracle is solved only over compact subsets, but the resulting objective values converge to the global optimum of the original problem, provided the compact restrictions contain the corresponding objective sublevel sets. For smooth convex objectives we obtain the standard superlinear convergence rate of the objective. We also record constructive restrictions based on strong convexity, exact sublevel sets, and epigraph caps, and include a nonsmooth conditional subgradient extension with a sublinear convergence rate under a curvature assumption. Numerical experiments illustrate the behaviour of the fixed and dynamic restrictions on unbounded feasible regions.