Linear convergence of accelerated conditional gradient algorithms in\n spaces of measures

2019/04/19 by Konstantin Pieper, Pieper, Konstantin, Daniel Walter +1 · 4 citations
Engineering · Mathematics · Medicine · #46E27 #49M05 #65J22 #65K05 #90C25 #FOS: Mathematics #Medical Imaging Techniques and Applications #Numerical methods in inverse problems #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1904.09218

openalex publication_date 2019/04/19 · openalex created_date 2022/07/29 · openalex updated_date 2026/07/28

Abstract

A class of generalized conditional gradient algorithms for the solution of\noptimization problem in spaces of Radon measures is presented. The method\niteratively inserts additional Dirac-delta functions and optimizes the\ncorresponding coefficients. Under general assumptions, a sub-linear\n\O(1/k) rate in the objective functional is obtained, which is sharp\nin most cases. To improve efficiency, one can fully resolve the\nfinite-dimensional subproblems occurring in each iteration of the method. We\nprovide an analysis for the resulting procedure: under a structural assumption\non the optimal solution, a linear \O(\ζ^k) convergence rate is\nobtained locally.\n

Cited by

• Sparse Source Identification in Transient Advection-Diffusion Problems with a Primal-Dual-Active-Point Strategy
• Lazifying point insertion algorithms in spaces of measures
• Goal-oriented optimal sensor placement for PDE-constrained inverse problems in crisis management
• Optimal control of the Poisson equation with transport regularization: Properties of optimal transport plans and transport map

Related

• Generalized conditional gradient: analysis of convergence and applications
• Accelerated gradient descent method for functionals of probability measures by new convexity and smoothness based on transport maps
• Locally Accelerated Conditional Gradients
• Adaptive Conditional Gradient Descent
• Conditional Gradient Methods