Motivated principally by the low-rank matrix completion problem, we present an extension of the Frank--Wolfe method that is designed to induce near-optimal solutions on low-dimensional faces of the feasible region. This is accomplished by a new approach to generating “in-face” directions at each iteration, as well as through new choice rules for selecting between in-face and “regular” Frank--Wolfe steps. Our framework for generating in-face directions generalizes the notion of away steps introduced by Wolfe. In particular, the in-face directions always keep the next iterate within the minimal face containing the current iterate. We present computational guarantees for the new method that trade off efficiency in computing near-optimal solutions with upper bounds on the dimension of minimal faces of iterates. We apply the new method to the matrix completion problem, where low-dimensional faces correspond to low-rank matrices. We present computational results that demonstrate the effectiveness of our methodo...
['Robert M. Freund', 'Paul Grigas', 'Rahul Mazumder']
An Extended Frank-Wolfe Method with "In-Face" Directions, and its Application to Low-Rank Matrix Completion