Linear convergence of accelerated conditional gradient algorithms in spaces of measures

Konstantin Pieper, Daniel Walter

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

A class of generalized conditional gradient algorithms for the solution of optimization problem in spaces of Radon measures is presented. The method iteratively inserts additional Dirac-delta functions and optimizes the corresponding coefficients. Under general assumptions, a sub-linear rate in the objective functional is obtained, which is sharp in most cases. To improve efficiency, one can fully resolve the finite-dimensional subproblems occurring in each iteration of the method. We provide an analysis for the resulting procedure: under a structural assumption on the optimal solution, a linear convergence rate is obtained locally.

Original languageEnglish
Article number38
JournalESAIM - Control, Optimisation and Calculus of Variations
Volume27
DOIs
StatePublished - 2021

Funding

∗KP acknowledges funding by the US Air Force Office of Scientific Research grant FA9550-15-1-0001 and the Laboratory Directed Research and Development Program at Oak Ridge National Laboratory (ORNL), managed by UT-Battelle, LLC, under Contract No. DE-AC05-00OR22725 with the US Department of Energy (DOE). The US government retains and the publisher, by accepting the article for publication, acknowledges that the US government retains a nonexclusive, paid-up, irrevocable, worldwide license to publish or reproduce the published form of this manuscript, or allow others to do so, for US government purposes. DOE will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan (http://energy.gov/downloads/doe-public-access-plan). DW acknowledges support by the DFG through the International Research Training Group IGDK 1754 “Optimization and Numerical Analysis for Partial Differential Equations with Nonsmooth Structures”. Furthermore, support from the TopMath Graduate Center of TUM Graduate School at Technische Universität München, Germany and from the TopMath Program at the Elite Network of Bavaria is gratefully acknowledged.

Keywords

  • Generalized conditional gradient
  • Nonsmooth optimization
  • Sparsity
  • Vector-valued finite Radon measures

Fingerprint

Dive into the research topics of 'Linear convergence of accelerated conditional gradient algorithms in spaces of measures'. Together they form a unique fingerprint.

Cite this