  The Frank-Wolfe (FW) method is a popular algorithm for solving large-scale
convex optimization problems appearing in structured statistical learning.
However, the traditional Frank-Wolfe method can only be applied when the
feasible region is bounded, which limits its applicability in practice.
Motivated by two applications in statistical learning, the $\ell_1$ trend
filtering problem and matrix optimization problems with generalized nuclear
norm constraints, we study a family of convex optimization problems where the
unbounded feasible region is the direct sum of an unbounded linear subspace and
a bounded constraint set. We propose two new Frank-Wolfe methods: unbounded
Frank-Wolfe method (uFW) and unbounded Away-Step Frank-Wolfe method (uAFW), for
solving a family of convex optimization problems with this class of unbounded
feasible regions. We show that under proper regularity conditions, the
unbounded Frank-Wolfe method has a $O(1/k)$ sublinear convergence rate, and
unbounded Away-Step Frank-Wolfe method has a linear convergence rate, matching
the best-known results for the Frank-Wolfe method when the feasible region is
bounded. Furthermore, computational experiments indicate that our proposed
methods appear to outperform alternative solvers.
