We study an optimization program over nonnegative Borel measures that encourages sparsity in its solution. Efficient solvers for this program are in increasing demand, as it arises when learning from data generated by a continuum-of-subspaces' model, a recent trend with applications in signal processing, machine learning, and high-dimensional statistics. We prove that the conditional gradient method (CGM) applied to this infinite-dimensional program, as proposed recently in the literature, is equivalent to the exchange method (EM) applied to its Lagrangian dual, which is a semi-infinite program. In doing so, we formally connect such infinite-dimensional programs to the well-established field of semi-infinite programming. On the one hand, the equivalence established in this paper allows us to provide a rate of convergence for EM which is more general than those existing in the literature. On the other hand, this connection and the resulting geometric insights might in the future lead to the design of improved variants of CGM for infinite-dimensional programs, which has been an active research topic. CGM is also known as the Frank-Wolfe algorithm.
The conditional gradient method (CGM), also known as the Frank-Wolfe algorithm, is one of the earliest algorithms for constrained optimization @cite_12 . The version of the algorithm considered in this paper is the fully-corrective Frank-Wolfe algorithm, also known as the algorithm, in which the objective is optimized over the convex hull of all previous atoms @cite_49 @cite_8 . The algorithm was proposed for optimization over measures, the context considered in this paper, in @cite_3 .
@cite_3 @cite_49 @cite_12 @cite_8
2605512869 1963481290 2136885855 2023653074
We propose a variant of the classical conditional gradient method for sparse inverse problems with differentiable observation models. Such models arise in many practical problems including superresolution microscopy, time-series modeling, and matrix completion. Our algorithm combines nonconvex and convex optimization techniques: we propose global conditional gradient steps alternating with nonconvex local search exploiting the differentiable observation model. This hybridization gives the theoretical global optimality guarantees and stopping conditions of convex optimization along with the performance and modeling flexibility associated with nonconvex optimization. Our experiments demonstrate that our technique achieves state-of-the-art results in several applications. The Frank and Wolfe method of feasible directions is shown to be a case of the more general computational approach of inner linearization followed by restriction. An extension is proposed based on this observation. The extended procedure converges, and under certain conditions the asymptotic convergence rate is geometric. Limited computational experience comparing the two procedures is reported. We propose a unifying framework for polyhedral approximation in convex optimization. It subsumes classical methods, such as cutting plane and simplicial decomposition, but also includes new methods and new versions extensions of old methods, such as a simplicial decomposition method for nondifferentiable optimization and a new piecewise linear approximation method for convex single commodity network flow problems. Our framework is based on an extended form of monotropic programming, a broadly applicable model, which includes as special cases Fenchel duality and Rockafellar's monotropic programming, and is characterized by an elegant and symmetric duality theory. Our algorithm combines flexibly outer and inner linearization of the cost function. The linearization is progressively refined by using primal and dual differentiation, and the roles of outer and inner linearization are reversed in a mathematically equivalent dual algorithm. We provide convergence results for the general case where outer and inner linearization are combined in the same algorithm.