Generalized Conditional Gradient with Augmented Lagrangian for Composite Minimization

International audienceIn this paper we propose a splitting scheme which hybridizes generalized conditional gradient with a prox-imal step which we call CGALP algorithm, for minimizing the sum of three proper convex and lower-semicontinuous functions in real Hilbert spaces. The minimization is subject to an affine constraint, that allows in particular to deal with composite problems (sum of more than three functions) in a separate way by the usual product space technique. While classical conditional gradient methods require Lipschitz-continuity of the gradient of the differentiable part of the objective, CGALP needs only differentiability (on an appropriate subset), hence circumventing the intricate question of Lipschitz continuity of gradients. For the two remaining functions in the objective, we do not require any additional regularity assumption. The second function, possibly nonsmooth, is assumed simple, i.e., the associated proximal mapping is easily computable. For the third function, again nonsmooth, we just assume that its domain is weakly compact and that a linearly perturbed minimization oracle is accessible. In particular, this last function can be chosen to be the indicator of a nonempty bounded closed convex set, in order to deal with additional constraints. Finally, the affine constraint is addressed by the augmented Lagrangian approach. Our analysis is carried out for a wide choice of algorithm parameters satisfying so called "open loop" rules. As main results, under mild conditions, we show asymptotic feasibility with respect to the affine constraint, boundedness of the dual multipliers, and convergence of the Lagrangian values to the saddle-point optimal value. We also provide (subsequential) rates of convergence for both the feasibility gap and the Lagrangian values.Dans ce travail, nous proposons un schéma d’éclatement en optimisation non lisse, hybridant le gradient conditionnel avec une étapeproximale que nous appelons CGALP , pour minimiser la somme de fonctions propres fermées et convexes sur un compact de R n . La minimisationest de plus sujette à une contrainte affine, que nous prenons en compte par un Lagrangien augmenté, en qui permet en particulier de traiter desproblèmes composites à plusieurs fonctions par une technique d’espace produit. Certaines fonctions sont autorisées à être non lisses mais dontl’opérateur proximal est simple à calculer. Notre analyse et garanties de convergence sont assurées pour un large choix de paramètres "en boucleouverte". Comme résultats principaux, nous montrons la faisabilité asymptotique de la variable primale, la convergence de toute sous-suite versune solution du problème primal, la convergence de la variable duale à une solution du problème dual, et la convergence du Lagrangien. Des tauxde convergence sont aussi fournis. Les implications et illustrations de l’algorithme en traitement des données sont discutées