Frank--Wolfe Methods with an Unbounded Feasible Region and Applications to Structured Learning
针对无界可行域（线性子空间与有界约束集的直和）的凸优化问题，提出两种新Frank-Wolfe方法，分别达到次线性与线性收敛率，在l1趋势过滤和核范数约束矩阵优化中优于现有求解器。
The Frank--Wolfe 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, the unbounded Frank--Wolfe method and the unbounded away-step Frank--Wolfe method, 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 an $O(1/k)$ sublinear convergence rate, and the 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.