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.
Accepté le :
Première publication :
Publié le :
Keywords: Vector-valued finite Radon measures, generalized conditional gradient, sparsity, nonsmooth optimization
@article{COCV_2021__27_1_A40_0,
author = {Pieper, Konstantin and Walter, Daniel},
title = {Linear convergence of accelerated conditional gradient algorithms in spaces of measures},
journal = {ESAIM: Control, Optimisation and Calculus of Variations},
year = {2021},
publisher = {EDP-Sciences},
volume = {27},
doi = {10.1051/cocv/2021042},
language = {en},
url = {https://www.numdam.org/articles/10.1051/cocv/2021042/}
}
TY - JOUR AU - Pieper, Konstantin AU - Walter, Daniel TI - Linear convergence of accelerated conditional gradient algorithms in spaces of measures JO - ESAIM: Control, Optimisation and Calculus of Variations PY - 2021 VL - 27 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/cocv/2021042/ DO - 10.1051/cocv/2021042 LA - en ID - COCV_2021__27_1_A40_0 ER -
%0 Journal Article %A Pieper, Konstantin %A Walter, Daniel %T Linear convergence of accelerated conditional gradient algorithms in spaces of measures %J ESAIM: Control, Optimisation and Calculus of Variations %D 2021 %V 27 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/cocv/2021042/ %R 10.1051/cocv/2021042 %G en %F COCV_2021__27_1_A40_0
Pieper, Konstantin; Walter, Daniel. Linear convergence of accelerated conditional gradient algorithms in spaces of measures. ESAIM: Control, Optimisation and Calculus of Variations, Tome 27 (2021), article no. 38. doi: 10.1051/cocv/2021042
[1] , and , Linear convergence of a modified Frank-Wolfe algorithm for computing minimum-volume enclosing ellipsoids. Optim. Methods Softw. 23 (2008) 5–19.
[2] and , Infinite dimensional analysis. A hitchhiker’s guide. Springer, Berlin, third ed. (2006).
[3] , and , Spike detection from inaccurate samplings. Appl. Comput. Harmon. Anal. 38 (2015) 177–195.
[4] and , A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imag. Sci. 2 (2009) 183–202.
[5] , Vols. I, II of Measure theory. Springer-Verlag, Berlin (2007).
[6] , and , The alternating descent conditional gradient method for sparse inverse problems. SIAM J. Optim. 27 (2017) 616–639.
[7] , , , and , Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3 (2011) 1–122.
[8] and , Sparsity of solutions for variational inverse problems with finite-dimensional data. Calc. Var. 59 (2020).
[9] and , Inverse problems in spaces of measures. ESAIM: COCV 19 (2013) 190–218.
[10] and , Towards a mathematical theory of super-resolution. Commun. Pure Appl. Math. 67 (2014) 906–956.
[11] and , A tight upper bound on the rate of convergence of Frank-Wolfe algorithm. SIAM J. Control 6 (1968) 509–516.
[12] , and , Approximation of elliptic control problems in measure spaces with sparse solutions. SIAM J. Control Optim. 50 (2012) 1735–1752.
[13] and , Spike controls for elliptic and parabolic PDEs. Systems Control Lett. 62 (2013) 311–318.
[14] and , A duality-based approach to elliptic control problems in non-reflexive Banach spaces. ESAIM: COCV 17 (2011) 243–266.
[15] and , A measure space approach to optimal source placement. Comput. Optim. Appl. 53 (2012) 155–171.
[16] An introduction to Γ-convergence. Vol. 8 of Progress in Nonlinear Differential Equations and their Applications. Birkhäuser Boston, Inc., Boston, MA (1993).
[17] and , Approximate methods in optimization problems, Translated from the Russian by Scripta Technica, Inc. Translation edited by George M. Kranc. Modern Analytic and Computational Methods in Science and Mathematics, No. 32, American Elsevier Publishing Co., Inc., New York (1970).
[18] , , and , The sliding Frank–Wolfe algorithm and its application to super-resolution microscopy. Inverse Problems 36 (2019) 014001.
[19] and , A unifying Radon-Nikodym theorem for vector measures. J. Multivariate Anal. 3 (1973) 184–203.
[20] , Rates of convergence for conditional gradient algorithms near singular and nonsingular extremals. SIAM J. Control Optim. 17 (1979) 187–211.
[21] , Convergence rates for conditional gradient sequences generated by implicit step length rules. SIAM J. Control Optim. 18 (1980) 473–487.
[22] and , Conditional gradient algorithms with open loop step size rules. J. Math. Anal. Appl. 62 (1978) 432–444.
[23] , A characterization of the Non-Degenerate Source Condition in Super-Resolution. ArXiv e-prints (2017).
[24] and , Exact support recovery for sparse spikes deconvolution. Found. Comput. Math. 15 (2015) 1315–1355.
[25] and , Sparse inverse problems over measures: equivalence of the conditional gradient and exchange methods. SIAM J. Optim. 29 (2019) 1329–1349.
[26] , Theory of optimal experiments, Probability and Mathematical Statistics, No. 12. Translated from the Russian and edited by and . Academic Press, New York-London (1972).
[27] and , Model-oriented design of experiments. Vol. 125 of Lecture Notes in Statistics. Springer-Verlag, New York (1997).
[28] , and , On the linear convergence rates of exchange and continuous methods for total variation minimization. Math. Program. (2020).
[29] and , An algorithm for quadratic programming. Naval Res. Logist. Quart. 3 (1956) 95–110.
[30] , and , Frequency-sparse optimal quantum control. Math. Control Related Fields 8 (2018) 155.
[31] and , On choosing and bounding probability metrics. Int. Stat. Rev./Revue Internationale de Statistique 70 (2002) 419–435.
[32] , A simple proof of Singer’s representation theorem. Proc. Amer. Math. Soc. 124 (1996) 3211–3212.
[33] , and , Directional sparsity in optimal control of partial differential equations. SIAM J. Control Optim. 50 (2012) 943–963.
[34] and , Semi-infinite programming: theory, methods, and applications. SIAM Rev. 35 (1993) 380–429.
[35] , and , The primal-dual active set strategy as a semismooth Newton method. SIAM J. Optim. 13 (2002) 865–888 (2003).
[36] , and , The length of the primal-dual path in Moreau-Yosida-based path-following methods for state constrained optimal control. SIAM J. Optim. 24 (2014) 108–126.
[37] , An extension of the Frank and Wolfe method of feasible directions. Math. Program. 6 (1974) 14–27.
[38] and , Optimum designs in regression problems. Ann. Math. Statist. 30 (1959) 271–294.
[39] , and , Measure valued directional sparsity for parabolic optimal control problems. SIAM J. Control Optim. 52 (2014) 3078–3108.
[40] , and , Optimal control of the undamped linear wave equation with measure valued controls. SIAM J. Control Optim. 54 (2016) 1212–1244.
[41] and , On the global linear convergence of Frank-Wolfe optimization variants, in Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 1. NIPS’15. MIT Press, Cambridge, MA, USA (2015) 496–504.
[42] , Real analysis. Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, second ed. (1983).
[43] , Real and functional analysis. Vol. 142 of Graduate Texts in Mathematics. Springer-Verlag, New York, third ed. (1993).
[44] and , Constrained minimization methods. USSR Computational Mathematics and Mathematical Physics 6 (1966) 1–50.
[45] , and , Numerical analysis of sparse initial data identification for parabolic problems. ESAIM: M2AN 54 (2020) 1139–1180.
[46] , and , On linear-quadratic elliptic control problems of semi-infinite type. Appl. Anal. 90 (2011) 1047–1074.
[47] , Numerical methods for a class of nonsmooth optimization problems and generalized variational inequalties, dissertation, Technische Universität München, München (2016).
[48] and , A semismooth Newton method with multidimensional filter globalization for l1 -optimization. SIAM J. Optim. 24 (2014) 298–333.
[49] and , Steepest descent algorithms in a space of measures. Stat. Comput. 12 (2002) 115–123.
[50] , , and , A sparse control approach to optimal sensor placement in PDE-constrained parameter estimation problems. Num. Math. 143 (2019) 943–984.
[51] , Finite element discretization and efficient numerical solution of elliptic and parabolic sparse control problems. PhD Dissertation, Technische Universität München (2015). http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:91-diss-20150420-1241413-1-4.
[52] , , and , Inverse point source location with the helmholtz equation on a bounded domain. Comput. Optim. Appl. 77 (2020) 213–249.
[53] and , Design of experiments in nonlinear models: asymptotic normality, optimality criteria and small-sample properties. Lecture notes in statistics. Springer, New York, NY (2013).
[54] , Second-order derivatives of extremal-value functions and optimality conditions for semi-infinite programs. Math. Oper. Res. 10 (1985) 207–219.
[55] , Elliptic optimal control problems with L1-control cost and applications for the placement of control devices. Comput. Optim. Appl. 44 (2009) 159–181.
[56] , Optimal measurement methods for distributed parameter system identification. Systems and Control Series, CRC Press, Boca Raton, FL (2005).
[57] , Semismooth Newton methods for operator equations in function spaces. SIAM J. Optim. 13 (2002) 805–842 (2003).
[58] , On sparse sensor placement for parameter identification problems with partial differential equations. Ph.D. thesis, Technische Universität München, (2019). http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:91-diss-20190604-1456274-1-8.
[59] , Convergence theory in nonlinear programming. North-Holland, Amsterdam (1970).
[60] , Some algorithmic aspects of the theory of optimal designs. Ann. Stat. (1978) 1286–1301.
[61] , Some iterative procedures for generating nonsingular optimal designs. Commun. Stat. Theory Methods 7 (1978) 1399–1412.
[62] , The sequential generation of D-optimum experimental designs. Ann. Math. Statist. 41 (1970) 1655–1664.
[63] , D-optimal designs via a cocktail algorithm. Stat. Comput. 21 (2011) 475–481.
Cité par Sources :
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.
