Antonio Silveti-Falls

Cesare Molinari
email: ce-cio.molinari@gmail.com

Jalal Fadili
email: jalal.fadili@ensicaen.fr.

Generalized Conditional Gradient with Augmented Lagrangian for Composite Minimization

Keywords: Conditional gradient, Augmented Lagrangian, Composite minimization, Proximal mapping, Moreau envelope AMS subject classifications. 49J52, 65K05, 65K10

In this paper we propose a splitting scheme which hybridizes generalized conditional gradient with a proximal 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.

Introduction

Problem Statement

In this work, we consider the composite optimization problem, min x∈Hp {f (x) + g(T x) + h(x) : Ax = b} , (P)

where H p , H d , H v are real Hilbert spaces (the subindices p, d and v denoting the "primal", the "dual" and an auxiliary space -respectively), endowed with the associated scalar products and norms (to be understood from the context), A : H p → H d and T : H p → H v are bounded linear operators, b ∈ H d and f , g, h are proper, convex, and lower semi-continuous functions with C def = dom (h) being a weakly compact subset of H p . We allow for some asymmetry in regularity between the functions involved in the objective. While g is assumed to be prox-friendly, for h we assume that it is easy to compute a linearly-perturbed oracle (see (1.2)). On the other hand, f is assumed to be differentiable and satisfies a condition that generalizes Lipschitz-continuity of the gradient (see Definition 2.6).

Problem (P) can be seen as a generalization of the classical Frank-Wolfe problem in [START_REF] Franke | An algorithm for quadratic programming[END_REF] of minimizing a Lipschitz-smooth function f on a convex closed bounded subset C ⊂ H p ,

min x∈Hp {f (x) : x ∈ C} (1.1)
In fact, if A ≡ 0, b ≡ 0, g ≡ 0, and h ≡ ι C is the indicator function of C then we recover exactly (1.1) from (P).

Contribution

We develop and analyze a novel algorithm to solve (P) which combines penalization for the nonsmooth function g with the augmented Lagrangian method for the affine constraint Ax = b. In turn, this achieves full splitting of all the parts in the composite problem (P) by using the proximal mapping of g (assumed prox-friendly) and a linear oracle for h of the form (1.2). Our analysis shows that the sequence of iterates is asymptotically feasible for the affine constraint, that the sequence of dual variables converges weakly to a solution of the dual problem, that the associated Lagrangian converges to optimality, and establishes convergence rates for a family of sequences of step sizes and sequences of smoothing/penalization parameters which satisfy so-called "open loop" rules in the sense of [START_REF] Polak | An historical survey of computational methods in optimal control[END_REF] and [START_REF] Dunn | Conditional gradient algorithms with open loop step size rules[END_REF]. This means that the allowable sequences of parameters do not depend on the iterates, in contrast to a "closed loop" rule, e.g. line search or other adaptive step sizes. Our analysis also shows, in the case where (P) admits a unique minimizer, weak convergence of the whole sequence of primal iterates to the solution.

The structure of (P) generalizes (1.1) in several ways. First, we allow for a possibly nonsmooth term g. Second, we consider h beyond the case of an indicator function where the linear oracle of the form

min s∈H h (s) + x, s (1.2)
can be easily solved. Observe that (1.2) has a solution over dom(h) since the latter is weakly compact. This oracle is reminiscent of that in the generalized conditional gradient method [START_REF] Bredies | Iterated hard shrinkage for minimization problems with sparsity constraints[END_REF][START_REF] Bredies | A generalized conditional gradient method and its connection to an iterative shrinkage method[END_REF][START_REF] Beck | The cyclic block conditional gradient method for convex optimization problems[END_REF][START_REF] Bach | Duality between subgradient and conditional gradient methods[END_REF]. Third, the regularity assumptions on f are also greatly weakened to go far beyond the standard Lipschitz gradient case. Finally, handling an affine constraint in our problem means that our framework can be applied to the splitting of a wide range of composite optimization problems, through a product space technique, including those involving finitely many functions h i and g i , and, in particular, intersection of finitely many nonempty bounded closed convex sets; see Section 5.

Relation to prior work

In the 1950's Frank and Wolfe developed the so-called Frank-Wolfe algorithm in [START_REF] Franke | An algorithm for quadratic programming[END_REF], also commonly referred to as the conditional gradient algorithm [START_REF] Levitin | Constrained minimization methods[END_REF][START_REF] Dem | The minimization of a smooth convex functional on a convex set[END_REF][START_REF] Dunn | Conditional gradient algorithms with open loop step size rules[END_REF], for solving problems of the form (1.1). The main idea is to replace the objective function f with a linear model at each iteration and solve the resulting linear optimization problem; the solution to the linear model is used as a step direction and the next iterate is computed as a convex combination of the current iterate and the step direction. We generalize this setting to include composite optimization problems involving both smooth and nonsmooth terms, intersection of multiple constraint sets, and also affine constraints.

Frank-Wolfe algorithms have received a lot of attention in the modern era due to their effectiveness in fields with high-dimensional problems like machine learning and signal processing (without being exhaustive, see, e.g., [START_REF] Jaggi | Revisiting Frank-Wolfe: Projection-free sparse convex optimization[END_REF][START_REF] Beck | A conditional gradient method with linear rate of convergence for solving convex linear systems[END_REF][START_REF] Lacoste-Julien | On the global linear convergence of frank-wolfe optimization variants[END_REF][START_REF] Harchaoui | Conditional gradient algorithms for norm-regularized smooth convex optimization[END_REF][START_REF] Zhang | Accelerated training for matrix-norm regularization: A boosting approach[END_REF][START_REF] Narasimhan | Learning with complex loss functions and constraints[END_REF][START_REF] Catala | A low-rank approach to off-the-grid sparse deconvolution[END_REF]). In the past, composite, constrained problems like (P) have been approached using proximal splitting methods, e.g. generalized forward-backward as developed in [START_REF] Raguet | Generalized forward-backward splitting[END_REF] or forward-douglas-rachford [START_REF] Molinari | Convergence rates of Forward-Douglas-Rachford splitting method[END_REF]. Such approaches require one to compute the proximal mapping associated to the function h. Alternatively, when the objective function satisfies some regularity conditions and when the constraint set is well behaved, one can forgo computing a proximal mapping, instead computing a linear minimization oracle. The computation of the proximal step can be prohibitively expensive; for example, when h is the indicator function of the nuclear norm ball, computing the proximal operator of h requires a full singular value decomposition while the linear minimization oracle over the nuclear norm ball requires only the leading singular vector to be computed ( [START_REF] Jaggi | A simple algorithm for nuclear norm regularized problems[END_REF], [START_REF] Yurtsever | Sketchy decisions: Convex low-rank matrix optimization with optimal storage[END_REF]). Unfortunately, the regularity assumptions required by classical Frank-Wolfe style algorithms are too restrictive to apply to general problems like (P).

While finalizing this work, we became aware of the recent work of [START_REF] Yurtsever | A conditional gradient framework for composite convex minimization with applications to semidefinite programming[END_REF], who independently developed a conditional gradient-based framework which allows one to solve composite optimization problems involving a Lipschitz-smooth function f and a nonsmooth function g, min x∈C {f (x) + g (T x)} .

(

The main idea is to replace g with its Moreau envelope of index β k at each iteration k, with the index parameter β k going to 0. This is equivalent to partial minimization with a quadratic penalization term, as in our algorithm. Like our algorithm, that of [START_REF] Yurtsever | A conditional gradient framework for composite convex minimization with applications to semidefinite programming[END_REF] is able to handle problems involving both smooth and nonsmooth terms, intersection of multiple constraint sets and affine constraints, however their algorithms employ different methods for these situations. Our algorithm uses an augmented Lagrangian to handle the affine constraint while the conditional gradient framework treats the affine constraint as a nonsmooth term g and uses penalization to smooth the indicator function corresponding to the affine constraint. In particular circumstances, outlined in more detail in Section 6, our algorithms agree completely.

Another recent and parallel work to ours is that of [START_REF] Pedregosa | Frank-wolfe splitting via augmented lagrangian method[END_REF], where the Frank-Wolfe via Augmented Lagrangian (FW-AL) is developed to approach the problem of minimizing a Lipschitz-smooth function over a convex, compact set with a linear constraint, min x∈C {f (x) : Ax = 0} .

(1.4)

The main idea of FW-AL is to use the augmented Lagrangian to handle the linear constraint and then apply the classical augmented Lagrangian algorithm, except that the marginal minimization on the primal variable that is usually performed is replaced by an inner loop of Frank-Wolfe. It turns out that the problem they consider is a particular case of (P), discussed in Section 6.

Organization of the paper

In Section 2 we introduce the notation and review some necessary material from convex and real analysis. In Section 3 we present the Conditional Gradient with Augmented Lagrangian and Proximal-step (CGALP ) algorithm and the underlying assumptions. In Section 4, we first state our main convergence results and then turn to their proof. The latter is divided in three main parts. First we show the asymptotic feasibility, then the boundedness of the dual multiplier in the augmented Lagrangian and finally the optimality guarantees, i.e. weak convergence of the sequence (µ k ) k∈N to a solution of the dual problem, weak subsequential convergence of the sequence (x k ) k∈N to a solution of the primal problem, and convergence of the Lagrangian values, and with convergence rates. In Section 5 we describe how our framework can be instantiated to solve a variety of composite optimization problems. In Section 6 we provide a more detailed discussion comparing CGALP to prior work. Some numerical results are reported in Section 7.

For readers who are primarily interested in the practical perspective, we suggest skipping directly to Section 3 for the algorithms and its assumptions or Section 4 for the main convergence results.

Notation and Preliminaries

We first recall some important definitions and results from convex analysis. For a more comprehensive coverage we refer the interested reader to [START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF][START_REF] Peypouquet | Convex optimization in normed spaces: theory, methods and examples[END_REF] and [START_REF] Rockafellar | Convex analysis[END_REF] in the finite dimensional case. Throughout, we let H denote an arbitrary real Hilbert space and g an arbitrary function from H to the real extended line, namely g : H → R ∪ {+∞}. The function g is said to belong to Γ 0 (H) if it is proper, convex, and lower semicontinuous. The domain of g is defined to be dom (g)

def = {x ∈ H : g (x) < +∞}. The Legendre-Fenchel conjugate of g is the function g * : H → R ∪ {+∞} such that, for every u ∈ H, g * (u) def = sup x∈H { u, x -g (x)} . Notice that g 1 ≤ g 2 =⇒ g * 2 ≤ g * 1 .
(2.1)

Moreau proximal mapping and envelope

The proximal operator for the function g is defined to be

prox g (x) def = argmin y∈H g(y) + 1 2 x -y 2
and its Moreau envelope with parameter β as

g β (x) def = inf y∈H g(y) + 1 2β x -y 2 . ( 2.2)
Denoting x + = prox g (x), we have the following classical inequality (see, for instance, [30, Chapter 6.2.1]): for every y ∈ H,

2 g(x + ) -g(y) + x + -y 2 -x -y 2 + x + -x 2 ≤ 0. (2.3)
We recall that the subdifferential of the function g is defined as the set-valued operator ∂g : H → 2 H such that, for every x in H,

∂g(x) = u ∈ H : g(y) ≥ g(x) + u, y -x ∀y ∈ H . (2.4)
We denote dom(∂g) def = x ∈ H : ∂g(x) = ∅ . When g belongs to Γ 0 (H), it is well-known that the subdifferential is a maximal monotone operator. If, moreover, the function is Gâteaux differentiable at x ∈ H, then ∂g(x) = {∇g(x)}. For x ∈ dom(∂g), the minimal norm selection of ∂g(x) is defined to be the unique element

[∂g (x)] 0 def = Argmin y∈∂g(x)
y . Then we have the following fundamental result about Moreau envelopes.

Proposition 2.1. Given a function g ∈ Γ 0 (H), we have the following: (i) The Moreau envelope is convex, real-valued, and continuous.

(ii) Lax-Hopf formula: the Moreau envelope is the viscosity solution to the following Hamilton Jacobi equation:

∂ ∂β g β (x) = -1 2 ∇ x g β (x) 2 (x, β) ∈ H × (0, +∞) g 0 (x) = g (x)
x ∈ H.

(2.5)

(iii) The gradient of the Moreau envelope is1 β -Lipschitz continuous and is given by the expression

∇ x g β (x) = x -prox βg (x) β . (iv) ∀x ∈ dom(∂g), ∇g β (x) ր [∂g (x)] 0 as β ց 0. (v) ∀x ∈ H, g β (x) ր g(x)
as β ց 0. In addition, given two positive real numbers β ′ < β, for all x ∈ H we have

0 ≤ g β ′ (x) -g β (x) ≤ β -β ′ 2 ∇ x g β ′ (x) 2 ; 0 ≤ g (x) -g β (x) ≤ β 2 [∂g (x)] 0 2 .
Proof. (i): see [START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF]Proposition 12.15]. The proof for (ii) can be found in [2, Lemma 3.27 and Remark 3.32] (see also [START_REF] Imbert | Convex analysis techniques for hopf-lax formulae in hamilton-jacobi equations[END_REF] or [1, Section 3.1]). The proof for claim (iii) can be found in [START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF]Proposition 12.29] and the proof for claim (iv) can be found in [START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF]Corollary 23.46]. For the first part in (v), see [START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF]Proposition 12.32(i)].

To show the first inequality in (v), combine (ii) and convexity of the function β → g β (x) for every x ∈ H. The second inequality follows from the first one and (iv), taking the limit as β ′ → 0.

Remark 2.2.

(i) While the regularity claim in Proposition 2.1(iii) of the Moreau envelope g β (x) w.r.t. x is well-known, a less known result is the C 1 -regularity w.r.t. β for any x ∈ H (Proposition 2.1(ii)). To our knowledge, the proof goes back, at least, to the book of [START_REF] Attouch | Variational convergence for functions and operators[END_REF]. Though it has been rediscovered in the recent literature in less general settings. (ii) For given functions H : H → R and g 0 : H → R, a natural generalization of the Hamilton-Jacobi equation in (2.5) is

∂ ∂β g (x, β) + H (∇ x g (x, β)) = 0 (x, β) ∈ H × (0, +∞) g (x, 0) = g (x) x ∈ H.
Supposing that H is convex and that lim p →+∞ H(p)/ p = +∞, the solution of the above system is given by the Lax-Hopf formula (see [14, Theorem 5, Section 3.3.2] 1 ):

g (x, t) def = inf y∈H g 0 (y) + tH * y -x t .
If H(p) = 1 2 p 2 , then H * (p) = 1 2 p 2 and we recover the result in Proposition 2.1.

Regularity of differentiable functions

In what follows, we introduce some definitions related with regularity of differentiable functions. They will provide useful upper-bounds and descent properties. Notice that the the notions and results of this part are independent from convexity.

Definition 2.3. (ω-smoothness) Consider a function ω : R + → R + such that ω(0) = 0 and

ξ (s) def = 1 0 ω (st) dt (2.6)
is non-decreasing. A differentiable function g : H → R is said to belong to C 1,ω (H) or to be ω-smooth if the following inequality is satisfied for every x, y ∈ H:

∇g (x) -∇g (y) ≤ ω ( x -y ) .
Lemma 2.4. (ω-smooth Descent Lemma) Given a function g ∈ C 1,ω (H) we have the following inequality: for every x and y in H,

g (y) -g (x) ≤ ∇g (x) , y -x + y -x ξ ( y -x ) ,
where ξ is defined in (2.6).

Proof. We recall here the simple proof for completeness:

g (y) -g (x) = 1 0 d dt g (x + t (y -x)) dt = 1 0 ∇g (x) , y -x dt + 1 0 ∇g (x + t (y -x)) -∇g (x) , y -x dt ≤ ∇g (x) , y -x + y -x 1 0 ∇g (x + t (y -x)) -∇g (x) dt ≤ ∇g (x) , y -x + y -x 1 0 ω (t y -x ) dt,
where in the first inequality we used Cauchy-Schwartz and in the second Definition 2.3. We conclude using the definition of ξ.

For L > 0 and ω (t) = Lt ν , ν ∈]0, 1], C 1,ω (H) is the space of differentiable functions with Hölder continuous gradients, in which case ξ (s) = Ls ν /(1 + ν) and the Descent Lemma reads

g (y) -g (x) ≤ ∇g (x) , y -x + L 1 + ν y -x 1+ν , (2.7)
see e.g., [START_REF] Nesterov | Universal gradient methods for convex optimization problems[END_REF][START_REF] Yu | Complexity bounds for primal-dual methods minimizing the model of objective function[END_REF]. When ν = 1, we have that C 1,ω (H) is the class of differentiable functions with L-Lipschitz continuous gradient, and one recovers the classical Descent Lemma. Now, following [START_REF] Bolte | A descent lemma beyond lipschitz gradient continuity: first-order methods revisited and applications[END_REF], we introduce some notions that allow one to further generalize (2.7). Given a function

G : H → R ∪ {+∞}, differentiable on the open set C 0 ⊂ int (dom (G)), define the Bregman divergence of G as the function D G : dom (G) × C 0 → R, D G (x, y) = G(x) -G(y) -∇G(y), x -y .
(2.8)

Then we have the following result.

Lemma 2.5. (Generalized Descent Lemma, [START_REF] Bolte | A descent lemma beyond lipschitz gradient continuity: first-order methods revisited and applications[END_REF]Lemma 1]) Let G and g be differentiable on C 0 , where C 0 is an open subset of int (dom (G)). Assume that Gg is convex on C 0 . Then, for every x and y in C 0 , g(y) ≤ g(x) + ∇g(x), yx + D G (y, x).

Proof. For our purpose, we intentionally weakened the hypothesis needed in the original result of [18, Lemma 1]. We repeat their argument but show the result is still valid under our weaker assumption. Let x and y be in C 0 , where, by hypothesis, C 0 is open and contained in int (dom (G)). As Gg is convex and differentiable on C 0 , from the gradient inequality (2.4) we have, for all y ∈ C 0 ,

(G -g) (y) ≥ (G -g) (x) + ∇ (G -g) (x), y -x .
Rearranging the terms and using the definition of D G in (2.8), we obtain the claim.

The previous lemma suggests the introduction of the following definition, which extends Definition 2.

; (ii) G -g is convex on C 0 ; (iii) it holds K (G,ζ,C) def = sup x,s∈C; γ∈]0,1] z=x+γ(s-x) D G (z, x) ζ (γ) < +∞. (2.9)
K (G,ζ,C
) is a far-reaching generalization of the standard curvature constant widely used in the literature of conditional gradient.

Remark 2.7. Assume that (g, C) is (G, ζ)-smooth. Using first Lemma 2.5 and then the definition in (2.9), we have the following descent property: for every x, s ∈ C and for every γ ∈]0, 1],

g (x + γ (s -x)) ≤ g(x) + γ ∇g(x), s -x + D G (x + γ (s -x) , x) ≤ g(x) + γ ∇g(x), s -x + K (G,ζ,C) ζ (γ) .
Notice that, as in the previous definition, we do not require C to be convex. So, in general, the point z = x + γ (sx) may not lie in C. Proof. With G = g and g being ω-smooth on C 0 , both G and g are differentiable on C 0 and Gg ≡ 0 is convex on C 0 . Thus, all conditions required in Definition 2.6 hold true. It then remains to show (2.9) with the bound K (g,ζ,C) ≤ d C . First notice that, for every x, s ∈ C and for every γ ∈]0, 1], the point z = x + γ (sx) belongs to C 0 . Indeed, C ⊂ C 0 and C 0 is convex by hypothesis. In particular, as g is ω-smooth on C 0 , the Descent Lemma 2.4 holds between the points x and z. Then

K (g,ζ,C) = sup x,s∈C; γ∈]0,1] z=x+γ(s-x) D g (z, x) ζ (γ) = sup x,s∈C; γ∈]0,1] z=x+γ(s-x) g(z) -g(x) -∇g(x), z -x ξ(d C γ) ≤ sup x,s∈C; γ∈]0,1] z=x+γ(s-x) z -x ξ ( z -x ) ξ(d C γ) = sup x,s∈C; γ∈]0,1] γ s -x ξ (γ s -x ) ξ(d C γ) ≤ sup γ∈]0,1] γd C ξ (d C γ) ξ(d C γ) = d C .
In the first inequality we used Lemma 2.4, while in the second we used that sx ≤ d C (both x and s belong to C, that is bounded by hypothesis) and the monotonicity of the function ξ (see Definition 2.3).

Indicator and support functions Given a subset C ⊂ H, we define its indicator function as ι C (x) = 0 if x belongs to C and ι C (x) = +∞ otherwise. Recall that, if C is nonempty, closed, and convex, then ι C belongs to Γ 0 (H). Remember also the definition of the support function of C, σ

C def = ι * C . Equivalently, σ C (x) def = sup { z, x : z ∈ C}.
We denote by ri (C) the relative interior of the set C (in finite dimension, it is the interior for the topology relative to its affine full). We denote par(C) as the subspace parallel to C which, in finite dimension, takes the form R(C -C).

We have the following characterization of the support function from the relative interior in finite dimension.

Proposition 2.9. ([35, Lemma 1]) Let H be finite-dimensional and C ⊂ H a nonempty, closed bounded and convex subset. If 0 ∈ ri(C), then σ C ∈ Γ 0 (R n ) is sublinear, non-negative and finite-valued, and

σ C (x) = 0 ⇐⇒ x ∈ (par(C)) ⊥ .
Coercivity We recall that a function g is coercive if lim x →+∞ g (x) = +∞ and that coercivity is equivalent to the boundedness of the sublevel-sets [START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF]Proposition 11.11]. We have the following result, that relates coercivity to properties of the Fenchel conjugate. Proposition 2.10. ([4, Theorem 14.17]) Given g in Γ 0 (H), g * is coercive if and only if 0 ∈ int (dom(g)).

The recession function (sometimes referred to as the horizon function) of g at a given point d ∈ R n is defined to be g d,∞ : R n → R ∪ {+∞} such that, for every x ∈ R n ,

g d,∞ (x) def = lim α→∞ g (d + αx) -g (d)
α .

Recall that, if g is convex, the recession function is independent from the selection of the point d ∈ R n and can be then simply denoted as g ∞ . In finite dimension, the following result relates coercivity to properties of the recession function.

Proposition 2.11. Let g ∈ Γ 0 (R n ) and A : R m → R n be a linear operator. Then, (i)

g coercive ⇐⇒ g ∞ (x) > 0 ∀x = 0. (ii) g ∞ ≡ σ dom(g * ) . (iii) (g • A) ∞ ≡ g ∞ • A.
In particular, we deduce that g • A is coercive if and only if σ dom(g * ) (Ax) > 0 for every x = 0.

Proof. The proofs can be found in [START_REF] Rockafellar | Variational analysis[END_REF]Theorem 3.26], [START_REF] Rockafellar | Variational analysis[END_REF]Theorem 11.5] and [23, Corollary 3.2] respectively.

Real sequences

We close this section with some definitions and lemmas for real sequences that will be used to prove the convergence properties of the algorithm. We denote ℓ + as the set of all sequences in

[0, +∞[. Given p ∈ [1, +∞[, ℓ p is the space of real sequences (r k ) k∈N such that ∞ k=1 |r k | p 1/p < +∞.
For p = +∞, we denote by ℓ ∞ the space of bounded sequences. Furthermore, we will use the notation

ℓ p + def = ℓ p ∩ ℓ + .
) k∈N ∈ ℓ + . Suppose that (z k ) k∈N ∈ ℓ 1 + , (p k ) k∈N / ∈ ℓ 1
, and that, for some α > 0, the following inequalities are satisfied for every k ∈ N:

r k+1 ≤ r k -p k w k + z k ; w k -w k+1 ≤ αp k .
(2.10)

Then, (i) (r k ) k∈N is convergent and (p k w k ) k∈N ∈ ℓ 1 + . (ii) lim k w k = 0.
(iii) For every k ∈ N, inf 1≤i≤k w i ≤ (r 0 + E)/P k , where, again, P n = n k=1 p k and E = +∞ k=1 z k . (iv) There exists a subsequence w k j j∈N such that, for all j ∈ N, w k j ≤ P -1 k j .

Proof.

(i) See Lemma 2.12.

(ii) Claim (ii) follows by combining (i) and Lemma 2.13(ii).

(iii) Sum (2.10) using a telescoping property and summability of (z k ) k∈N .

(iv) Claim (iv) follows by combining (i) and Lemma 2.13(i).

Notice that the conclusions of Lemma 2.14 remain true if non-negativity of the sequence (r k ) k∈N is replaced with the assumption that it is bounded from below by a trivial translation argument. Observe also that Lemma 2.14 guarantees the convergence of the whole sequence to zero, but it gives a convergence rate only on a subsequence.

Algorithm and assumptions

Algorithm

As described in the introduction, we combine penalization with the augmented Lagrangian approach to form the following functional

J k (x, y, µ) = f (x) + g (y) + h (x) + µ, Ax -b + ρ k 2 Ax -b 2 + 1 2β k y -T x 2 , (3.1)
where µ is the dual multiplier, and ρ k and β k are non-negative parameters. The steps of our scheme, then, are summarized in Algorithm 1.

Algorithm 1: Conditional Gradient with Augmented Lagrangian and Proximal-step (CGALP ) Input:

x 0 ∈ C = dom (h); µ 0 ∈ ran(A); (γ k ) k∈N , (β k ) k∈N , (θ k ) k∈N , (ρ k ) k∈N ∈ ℓ + . k = 0 repeat y k = prox β k g (T x k ) z k = ∇f (x k ) + T * (T x k -y k ) /β k + A * µ k + ρ k A * (Ax k -b) s k ∈ Argmin s∈Hp {h (s) + z k , s } x k+1 = x k -γ k (x k -s k ) µ k+1 = µ k + θ k (Ax k+1 -b) k ← k + 1 until convergence; Output: x k+1 .
For the interpretation of the algorithm, notice that the first step is equivalent to

{y k } = Argmin y∈Hv J k (x k , y, µ k ) . Now define the functional E k (x, µ) def = f (x) + g β k (T x) + µ, Ax -b + ρ k 2 Ax -b 2
. By convexity of the set C and the definition of x k+1 as a convex combination of x k and s k , the sequence (x k ) k∈N remains in C for all k, although the affine constraint Ax k = b might only be satisfied asymptotically. It is an augmented Lagrangian, where we do not consider the non-differentiable function h and we replace g by its Moreau envelope. Notice that

∇ x E k (x, µ k ) = ∇f (x) + T * [∇g β k ](T x) + A * µ k + ρ k A * (Ax -b) = ∇f (x) + 1 β k T * T x -prox β k g (T x) + A * µ k + ρ k A * (Ax -b) . (3.2)
where in the second equality we used 2.1(iii). Then z k is just ∇ x E k (x k , µ k ) and the first three steps of the algorithm can be condensed in

s k ∈ Argmin s∈Hp {h (s) + ∇ x E k (x k , µ k ) , s } . (3.3)
Thus the primal variable update of each step of our algorithm boils down to conditional gradient applied to the function

E k (•, µ k ),
where the next iterate is a convex combination between the previous one and the new direction s k . A standard update of the Lagrange multiplier µ k follows.

Assumptions

Assumptions on the functions

In order to help the reading, we recall in a compact form the following notation that we will use to refer to various functionals throughout the paper:

Φ (x) def = f (x) + g (T x) + h (x) ; Φ k (x) def = f (x) + g β k (T x) + h (x) + ρ k 2 Ax -b 2 ; Φ (x) def = Φ (x) + (ρ/2) Ax -b 2 ; φ(µ) def = Φ * (-A * µ) + b, µ ; L (x, µ) def = f (x) + g (T x) + h (x) + µ, Ax -b ; L k (x, µ) def = f (x) + g β k (T x) + h (x) + µ, Ax -b + ρ k 2 Ax -b 2 ; E k (x, µ) def = f (x) + g β k (T x) + µ, Ax -b + ρ k 2 Ax -b 2 , (3.4)
where ρ is defined in Assumption (P.4) to be ρ = sup

k ρ k .
In the list (3.4), we can recognize Φ as the objective, Φ k as the smoothed objective augmented with a quadratic penalization of the constraint, and L k as a smoothed augmented Lagrangian. L denotes the classical Lagrangian. Recall that

(x ⋆ , µ ⋆ ) ∈ H p × H d is a saddle-point for the Lagrangian L if for every (x, µ) ∈ H p × H d , L (x ⋆ , µ) ≤ L (x ⋆ , µ ⋆ ) ≤ L (x, µ ⋆ ) . (3.5)
It is well-known from standard Lagrange duality, see e.g. [START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF]Proposition 19.19] or [START_REF] Peypouquet | Convex optimization in normed spaces: theory, methods and examples[END_REF]Theorem 3.68], that the existence of a saddle point (x ⋆ , µ ⋆ ) ensures strong duality, that x ⋆ solves (P) and µ ⋆ solves the dual problem, min

µ∈H d (f + g • T + h) * (-A * µ) + µ, b . (D)
The following assumptions on the problem will be used throughout the convergence analysis (for some results only a subset of these assumptions will be needed):

(A.1) f, g • T , and h belong to Γ 0 (H p ). (A.2) The pair (f, C) is (F, ζ)-smooth (see Definition 2.6), where we recall C def = dom (h). (A.3) C is weakly compact (and thus contained in a ball of radius R > 0). (A.4) T C ⊂ dom(∂g) and sup x∈C [∂g (T x)] 0 < ∞. (A.5) h is Lipschitz continuous relative to its domain C with constant L h ≥ 0, i.e., ∀(x, z) ∈ C 2 , |h(x) - h(z)| ≤ L h x -z . (A.6) There exists a saddle-point (x ⋆ , µ ⋆ ) ∈ H p × H d for the Lagrangian L. (A.7) ran(A) is closed. (A.8) One of the following holds: (a) A -1 (b) ∩ int (dom (g • T )) ∩ int (C) = ∅, where A -1 (b) is the pre-image of b under A. (b) H p and H d are finite dimensional and      A -1 (b) ∩ ri (dom (g • T )) ∩ ri (C) = ∅ and ran (A * ) ∩ par (dom (g • T ) ∩ C) ⊥ = {0} . (3.6)
At this stage, a few remarks are in order.

Remark 3.1.

(i) By Assumption (A.1), C is also closed and convex. This together with Assumption (A.3) entail, upon using [4, Lemma 3.29 and Theorem 3.32], that C is weakly compact. (ii) Since the sequence of iterates (x k ) k∈N generated by Algorithm 1 is guaranteed to belong to C under (P.1), we have from (A.4)

sup k [∂g (T x k )] 0 ≤ M. (3.7)
where M is a positive constant. (iii) Assumption (A.5) will only be needed in the proof of convergence to optimality (Theorem 4.2). It is not needed to show asymptotic feasibility (Theorem 4. The uniform boundedness of the minimal norm selection on C, as required in Assumption (A.4), is important when we will invoke Proposition 2.1(v) in our proofs to get meaningful estimates. The following result gives some sufficient conditions under which (A.4) holds (in fact an even stronger claim). Lemma 3.2. Let C be a nonempty bounded subset of H p , g ∈ Γ 0 (H v ) and T : H p → H v be a bounded linear operator. Suppose that T C ⊂ int (dom (g)). Then the assumption (A.4) holds.

1). (iv) Assume that

A -1 (b) ∩ dom(g • T ) ∩ C = ∅,
Proof. Since g ∈ Γ 0 (H p ), it follows from [4, Proposition 16.21] that

T C ⊂ int (dom (g)) ⊂ dom(∂g).
Moreover, by [4, Corollary 8.30(ii) and Proposition 16.14], we have that ∂g is locally weakly compact on int (dom (g)). In particular, as we assume that C is bounded, so is T C, and since T C ⊂ int (dom (g)), it means that for each z ∈ T C there exists an open neighborhood of z, denoted by U z , such that ∂g (U z ) is bounded. Since (U z ) z∈C is an open cover of T C and T C is bounded, there exists a finite subcover

(U z k ) n k=1 . Then, x∈C ∂g (T x) ⊂ n k=1 ∂g (U z k ) .
Since the right-hand-side is bounded (as it is a finite union of bounded sets),

sup x∈C, u∈∂g(T x) u < +∞,
whence the desired conclusion trivially follows.

Assumptions on the parameters

We also use the following assumptions on the parameters of Algorithm 1 (recall the function ζ in Definition 2.6):

(P.1) (γ k ) k∈N ⊂]0, 1] and the sequences (ζ (γ k )) k∈N , γ 2 k /β k k∈N and (γ k β k ) k∈N belong to ℓ 1 + . (P.2) (γ k ) k∈N / ∈ ℓ 1 . (P.3) (β k ) k∈N ∈ ℓ + is non-increasing and converges to 0. (P.4) (ρ k ) k∈N ∈ ℓ + is non-decreasing with 0 < ρ = inf k ρ k ≤ sup k ρ k = ρ < +∞. (P.5) For some positive constants M and M , M ≤ inf k (γ k /γ k+1 ) ≤ sup k (γ k /γ k+1 ) ≤ M . (P.6) (θ k ) k∈N satisfies θ k = γ k c for all k ∈ N for some c > 0 such that M c - ρ 2 < 0. (P.7) (γ k ) k∈N and (ρ k ) k∈N satisfy ρ k+1 -ρ k -γ k+1 ρ k+1 + 2 c γ k - γ 2 k
c ≤ γ k+1 for all k ∈ N and for c in (P.6).

Remark 3.3.

(i) One can recognize that the update of the dual multiplier µ k in Algorithm 1 has a flavour of gradient ascent applied to the augmented dual with step-size θ k . However, unlike the standard method of multipliers with the augmented Lagrangian, Assumption (P.6) requires θ k to vanish in our setting. The underlying reason is that our update can be seen as an inexact dual ascent (i.e., exactness stems from the conditional gradient-based update on x k which is not a minimization of over x of the augmented Lagrangian L k ). Thus θ k must annihilate this error asymptotically. (ii) A sufficient condition for (P.7) to hold consists of taking ρ k ≡ ρ > 0 and γ k+1 ≥ 2 c(1+ρ) γ k . In particular, if (γ k ) k∈N satisfies (P.5), then, for (P.7) to hold, it is sufficient to take ρ k ≡ ρ > 2M /c as supposed in (P.6). (iii) The relevance of having ρ k vary is that it allows for more general and less stringent choice of the step-size γ k . It is, however, possible (and easier in practice), to simply pick ρ k ≡ ρ for all k ∈ N as described above.

There is a large class of sequences that fulfill the requirements (P.1)-(P.7). A typical one is as follows.

Example 3.4. Take2 , for k ∈ N,

ρ k ≡ ρ > 0, γ k = (log(k + 2)) a (k + 1) 1-b , β k = 1 (k + 1) 1-δ , with a ≥ 0, 0 ≤ 2b < δ < 1, δ < 1 -b, ρ > 2 2-b /c, c > 0.
In this case, one can take the crude bounds M = (log(2)/ log(3)) a and M = 2 1-b , and choose ρ > 2M /c as devised in Remark 3.3(ii). In turn, (P.4)-(P.7) hold. In addition, suppose that f has a ν-Hölder continuous gradient (see (2.7)). Thus for (P.1)-(P.2) to hold, simple algebra shows that the allowable choice of b is in 0, min 1/3, ν 1+ν .

Convergence analysis 4.1 Main results

We state here our main results.

inf 0≤i≤k Ax i -b = O 1 √ Γ k and ∃ a subsequence x k j j∈N s.t. for all j ∈ N, Ax k j -b ≤ 1 Γ k j , (4.1)
where, for all k ∈ N,

Γ k def = k i=0 γ i . (iii) Ergodic rate: for each k ∈ N, let xk def = k i=0 γ i x i /Γ k . Then Ax k -b = O 1 √ Γ k . (4.2)
Theorem 4.1 will be proved in Section 4.3.

Theorem 4.2 (Convergence to optimality). Suppose that assumptions (A.1)-(A.8) and (P.1)-(P.7) hold, with

M ≥ 1. Let (x k ) k∈N be the sequence of primal iterates generated by Algorithm 1 and (x ⋆ , µ ⋆ ) a saddle-point pair for the Lagrangian. Then, in addition to the results of Theorem 4.1, the following holds (i) Convergence of the Lagrangian:

lim k→∞ L (x k , µ ⋆ ) = L (x ⋆ , µ ⋆ ) . (4.3)
(ii) Every weak cluster point x of (x k ) k∈N is a solution of the primal problem (P), and (µ k ) k∈N converges weakly to μ a solution of the dual problem (D), i.e., (x, μ) is a saddle point of L.

(iii) Pointwise rate:

inf 0≤i≤k L (x i , µ ⋆ ) -L (x ⋆ , µ ⋆ ) = O 1 Γ k and ∃ a subsequence x k j j∈N s.t. for each j ∈ N,L x k j +1 , µ ⋆ -L (x ⋆ , µ ⋆ ) ≤ 1 Γ k j . (4.4) (iv) Ergodic rate: for each k ∈ N, let xk def = k i=0 γ i x i+1 /Γ k . Then L (x k , µ ⋆ ) -L (x ⋆ , µ ⋆ ) = O 1 Γ k . (4.5)
An important observation is that Theorem 4.2, which will be proved in Section 4.5, actually shows that

lim k→∞ L (x k , µ ⋆ ) -L (x ⋆ , µ ⋆ ) + ρ k 2 Ax k -b 2 = 0,
and subsequentially, for each j ∈ N,

L x k j , µ ⋆ -L (x ⋆ , µ ⋆ ) + ρ k j 2 Ax k j -b 2 ≤ 1 Γ k j . ( 4
: t ∈ R + → (log(t + 2)) a /(t + 1) 1-b . We obviously have σ(k) = γ k for k ∈ N.
Moreover, it is easy to see that ∃k ′ ≥ 0 (depending on a and b), such that σ is decreasing for t ≥ k ′ . Thus, ∀k ≥ k ′ , we have

Γ k ≥ k i=k ′ γ i ≥ k+1 k ′ σ(t)dt ≥ k+2 k ′ +1 (log(t)) a t b-1 dt = log(k+2) log(k ′ +1)
t a e bt dt.

It is easy to show, using integration by parts for the first case, that

Γ -1 k =          o 1 (k+2) b a = 1, b > 0, O 1 (k+2) b a = 0, b > 0, O 1 log(k+2) a = 0, b = 0.
This result reveals that picking a and b as large as possible results in a faster convergence rate, with the proviso that b satisfy some conditions for (P.1)-(P.7) to hold, see the discussion in Example 3.4 for the largest possible choice of b.

Preparatory results

The next result is a direct application of the Descent Lemma 2.7 and the generalized one in Lemma 2.5 to the specific case of Algorithm 1. It allows to obtain a descent property for the function E k (•, µ k ) between the previous iterate x k and next one x k+1 . Lemma 4.5. Suppose Assumptions (A.1), (A.2) and (P.1) hold. For each k ∈ N, define the quantity

L k def = T 2 β k + A 2 ρ k . (4.7)
Then, for each k ∈ N, we have the following inequality:

E k (x k+1 , µ k ) ≤ E k (x k , µ k ) + ∇ x E k (x k , µ k ) , x k+1 -x k + K (F,ζ,C) ζ (γ k ) + L k 2 x k+1 -x k 2 .
Proof. Define for each k ∈ N,

Ẽk (x, µ) def = g β k (T x) + µ, Ax -b + ρ k 2 Ax -b 2 , so that E k (x, µ) = f (x) + Ẽk (x, µ). Compute ∇ x Ẽk (x, µ) = T * ∇g β k (T x) + A * µ + ρ k A * (Ax -b) ,
which is Lipschitz-continuous with constant L k = T 2 β k + A 2 ρ k by virtue of (A.1) and Proposition 2.1(iii). Then we can use the Descent Lemma (2.7) with ν = 1 on Ẽk (•, µ k ) between the points x k and x k+1 , to obtain, for each k ∈ N,

Ẽk (x k+1 , µ k ) ≤ Ẽk (x k , µ k ) + ∇ Ẽk (x k , µ k ) , x k+1 -x k + L k 2 x k+1 -x k 2 . ( 4.8)
From Assumption (A.2), Lemma 2.5 and Remark 2.7, we have, for each k ∈ N,

f (x k+1 ) ≤ f (x k ) + ∇f (x k ), x k+1 -x k + D F (x k+1 , x k ) ≤ f (x k ) + ∇f (x k ), x k+1 -x k + K (F,ζ,C) ζ (γ k ) ,
where we used that both x k and s k lie in C, that γ k belongs to ]0, 1] by (P.1) and thus

x k+1 = x k + γ k (s k -x k ) ∈ C. Summing (4.8
) with the latter and recalling that E k (x, µ k ) = f (x) + Ẽk (x, µ k ), we obtain the claim.

Again for the function E k (•, µ k ), we also have a lower-bound, presented in the next lemma.

Lemma 4.6. Suppose Assumptions (A.1) and (A.2) hold. Then, for all k ∈ N, for all x, x ′ ∈ H p and for all µ ∈ H d ,

E k (x, µ) ≥ E k x ′ , µ + ∇ x E k x ′ , µ , x -x ′ + ρ k 2 A(x -x ′ ) 2 .
Proof. First, split the function

E k (•, µ) as E k (x, µ) = E 0 k (x, µ) + ρ k 2 Ax -b 2 for an opportune definition of E 0 k (•, µ).
For the first term, simply by convexity, we have

E 0 k (x, µ) ≥ E 0 k x ′ , µ + ∇ x E 0 k x ′ , µ , x -x ′ . (4.9)
Now use the strong convexity of the term (ρ k /2) • -b 2 between points Ax and Ax ′ , to affirm that

ρ k 2 Ax -b 2 ≥ ρ k 2 Ax ′ -b 2 + ∇ ρ k 2 • -b 2 Ax ′ , Ax -Ax ′ + ρ k 2 A(x -x ′ ) 2 . (4.10) Compute ∇ ρ k 2 • -b 2 Ax ′ , Ax -Ax ′ = ρ k A * Ax ′ -b , x -x ′ = ∇ ρ k 2 A • -b 2 x ′ , x -x ′ .
Summing (4.9) and (4.10) and invoking the gradient computation above, we obtain the claim.

L (x k , µ ⋆ ) -L (x k+1 , µ ⋆ ) ≤ γ k d C (M T + D + L h + A µ ⋆ ) Proof. First define u k def = [∂g(T x k )
] 0 and recall that, by (A.4) and its consequence in (3.7), u k ≤ M for every k ∈ N. Then,

L (x k , µ ⋆ ) -L (x k+1 , µ ⋆ ) = Φ(x k ) -Φ(x k+1 ) + µ ⋆ , A (x k -x k+1 ) ≤ u k , T (x k -x k+1 ) + ∇f (x k ), x k -x k+1 + L h x k -x k+1 + µ ⋆ A x k -x k+1 ,
where we used the subdifferential inequality (2.4) on g, the gradient inequality on f , the L h -Lipschitz continuity of h relative to C (see (A.5)), and the Cauchy-Schwartz inequality on the scalar product. Since

x k+1 = x k + γ k (x k -s k ), we obtain L (x k , µ ⋆ ) -L (x k+1 , µ ⋆ ) ≤ γ k u k , T (x k -s k ) + ∇f (x k ), x k -s k + L h x k -s k + µ ⋆ A x k -s k ≤ γ k d C (M T + D + L h + µ ⋆ A ) ,
ρ k 2 Ax k -b 2 - ρ k+1 2 Ax k+1 -b 2 ≤ ρd C A ( A R + b ) γ k ,
where R is the radius of the ball containing C and ρ = sup k ρ k .

Proof. By (P.4) and convexity of the function

ρ k+1 2 A • -b 2 , we have ρ k 2 Ax k -b 2 - ρ k+1 2 Ax k+1 -b 2 ≤ ρ k+1 2 Ax k -b 2 - ρ k+1 2 Ax k+1 -b 2 ≤ ∇ ρ k+1 2 A • -b 2 (x k ), x k -x k+1 .
Now compute the gradient and use the definition of x k+1 , to obtain

ρ k 2 Ax k -b 2 - ρ k+1 2 Ax k+1 -b 2 ≤ ρ k+1 γ k Ax k -b, A (x k -s k ) ≤ ρd C A ( A R + b ) γ k .
In the last inequality, we used Cauchy-Schwartz inequality, triangle inequality, the fact that x ks k ≤ d C , and assumptions (A.3) and (P.4) (respectively, sup x∈C x ≤ R and ρ k+1 ≤ ρ).

Asymptotic feasibility

We begin with an intermediary lemma establishing the main feasibility estimation and some summability results that will also be used in the proof of optimality.

∆ p k def = L k (x k+1 , µ k ) -Lk (µ k ) , ∆ d k def = L -Lk (µ k ) ,
where we have denoted Lk (µ k )

def = min x L k (x, µ k ) and L def = L (x ⋆ , µ ⋆ ). Denote the sum ∆ k def = ∆ p k + ∆ d k .
Then we have the following estimation,

∆ k+1 ≤ ∆ k -γ k+1 M c Ax k+1 -b 2 + δ A (x k+1 -xk+1 ) 2 + L k+1 2 γ 2 k+1 d 2 C +K (F,ζ,C) ζ (γ k+1 ) + β k -β k+1 2 M + ρ k+1 -ρ k 2 Ax k+1 -b 2 ,
and, moreover,

γ k Ax k -b 2 k∈N ∈ ℓ 1 + , γ k A (x k -xk ) 2 k∈N ∈ ℓ 1 + , and γ k Ax k -b 2 k∈N ∈ ℓ 1 + .
Proof. First notice that the quantity ∆ p k ≥ 0 and can be seen as a primal gap at iteration k while ∆ d k may be negative but is bounded from below by our assumptions. Indeed, in view of (A.1), (A.6) and Remark 3.1(iv), Lk (µ k ) is bounded from above since

Lk (µ k ) ≤ L k (x ⋆ , µ k ) = f (x ⋆ ) + g β k (T x ⋆ ) + h (x ⋆ ) + µ k , Ax ⋆ -b + ρ k 2 Ax ⋆ -b 2 = f (x ⋆ ) + g β k (T x ⋆ ) + h (x ⋆ ) ≤ f (x ⋆ ) + g (T x ⋆ ) + h (x ⋆ ) < +∞,
where we used Proposition 2.1(v) in the last inequality.

We denote a minimizer of L k (x, µ k ) by xk ∈ Argmin x∈Hp L k (x, µ k ), which exists and belongs to C by (A.1)-(A.3). Then, we have

∆ d k+1 -∆ d k = L k (x k , µ k ) -L k+1 (x k+1 , µ k+1 ) . (4.11) Since xk is a minimizer of L k (x, µ k ) we have that L k (x k , µ k ) ≤ L k (x k+1 , µ k ) which leads to, L k (x k+1 , µ k ) = L k+1 (x k+1 , µ k ) + g β k (T xk+1 ) -g β k+1 (T xk+1 ) + ρ k -ρ k+1 2 Ax k+1 -b 2 ≤ L k+1 (x k+1 , µ k ) ,
where the last inequality comes from Proposition 2.1(v) and the assumptions (P.3) and (P.4). Combining this with (4.11),

∆ d k+1 -∆ d k ≤ L k+1 (x k+1 , µ k ) -L k+1 (x k+1 , µ k+1 ) = µ k -µ k+1 , Ax k+1 -b = -θ k Ax k+1 -b, Ax k+1 -b , (4.12)
where in the last equality we used the definition of µ k+1 . Meanwhile, for the primal gap we have

∆ p k+1 -∆ p k = (L k+1 (x k+2 , µ k+1 ) -L k (x k+1 , µ k )) + (L k (x k , µ k ) -L k+1 (x k+1 , µ k+1 )) . Note that L k (x k+1 , µ k ) = L k (x k+1 , µ k+1 ) -θ k Ax k+1 -b 2
and estimate L k (x k , µ k ) -L k+1 (x k+1 , µ k+1 ) as in (4.12), to get

∆ p k+1 -∆ p k ≤ L k+1 (x k+2 , µ k+1 ) -L k (x k+1 , µ k+1 ) + θ k Ax k+1 -b 2 -θ k Ax k+1 -b, Ax k+1 -b . (4.13)
Using (4.12) and (4.13), we then have

∆ k+1 -∆ k ≤ L k+1 (x k+2 , µ k+1 ) -L k (x k+1 , µ k+1 ) + θ k Ax k+1 -b 2 -2θ k Ax k+1 -b, Ax k+1 -b .
Note that

L k (x k+1 , µ k+1 ) = L k+1 (x k+1 , µ k+1 ) -g β k+1 -g β k (T x k+1 ) - ρ k+1 -ρ k 2 Ax k+1 -b 2 . Then ∆ k+1 -∆ k ≤ L k+1 (x k+2 , µ k+1 ) -L k+1 (x k+1 , µ k+1 ) + g β k+1 (T x k+1 ) -g β k (T x k+1 ) + ρ k+1 -ρ k 2 Ax k+1 -b 2 + θ k Ax k+1 -b 2 -2θ k Ax k+1 -b, Ax k+1 -b .
We denote by T1 = L k+1 (x k+2 , µ k+1 ) -L k+1 (x k+1 , µ k+1 ) and the remaining part of the right-hand side by T2. For the moment, we focus our attention on T1. Recall that L k (x, µ k ) = E k (x, µ k ) + h (x) and apply Lemma 4.5 between points x k+2 and x k+1 , to get

T1 ≤ h (x k+2 ) -h (x k+1 ) + ∇ x E k+1 (x k+1 , µ k+1 ) , x k+2 -x k+1 + K (F,ζ,C) ζ (γ k+1 ) + L k+1 2 x k+2 -x k+1 2 .
By (A.1) we have that h is convex and thus, since x k+2 is a convex combination of x k+1 and s k+1 , we get

T1 ≤ -γ k+1 (h (x k+1 ) -h (s k+1 ) + ∇ x E k+1 (x k+1 , µ k+1 ) , x k+1 -s k+1 ) + L k+1 2 x k+2 -x k+1 2 + K (F,ζ,C) ζ (γ k+1 ) .
Applying the definition of s k as the minimizer of the linear minimization oracle and Lemma 4.6 at the points xk+1 , x k+1 , and µ k+1 gives,

T1 ≤ -γ k+1 (h (x k+1 ) -h (x k+1 ) + ∇ x E k+1 (x k+1 , µ k+1 ) , x k+1 -xk+1 ) + L k+1 2 x k+2 -x k+1 2 + K (F,ζ,C) ζ (γ k+1 ) ≤ -γ k+1 h (x k+1 ) -h (x k+1 ) + E k+1 (x k+1 , µ k+1 ) -E k+1 (x k+1 , µ k+1 ) + ρ k+1 2 A (x k+1 -xk+1 ) 2 + L k+1 2 x k+2 -x k+1 2 + K (F,ζ,C) ζ (γ k+1 ) = -γ k+1 L k+1 (x k+1 , µ k+1 ) -L k+1 (x k+1 , µ k+1 ) + ρ k+1 2 A (x k+1 -xk+1 ) 2 + L k+1 2 x k+2 -x k+1 2 + K (F,ζ,C) ζ (γ k+1 ) ≤ - γ k+1 ρ k+1 2 A (x k+1 -xk+1 ) 2 + L k+1 2 x k+2 -x k+1 2 + K (F,ζ,C) ζ (γ k+1 ) ,
where we used that xk+1 is a minimizer of L k+1 (•, µ k+1 ) in the last inequality. Now, combining T1 and T2 and using the Pythagoras identity we have

∆ k+1 -∆ k ≤ -θ k Ax k+1 -b 2 + θ k -γ k+1 ρ k+1 2 A (x k+1 -xk+1 ) 2 + L k+1 2 x k+2 -x k+1 2 + K (F,ζ,C) ζ (γ k+1 ) + g β k+1 -g β k (T x k+1 ) + ρ k+1 -ρ k 2 Ax k+1 -b 2 . (4.14)
Under (P.6) we have

θ k = γ k c for some c > 0 such that ∃δ > 0, M c - ρ 2 = -δ < 0,
where M is the constant such that γ k ≤ M γ k+1 (see Assumption (P.5)). Then, using (P.5) and the above inequality,

θ k -γ k+1 ρ k+1 2 ≤ M c - ρ k+1 2 γ k+1 ≤ M c - ρ 2 γ k+1 = -δγ k+1 and θ k ≥ M γ k+1 c . (4.15)
Now use the fact that x k+2 = x k+1 + γ k+1 (s k+1x k+1 ) to estimate

x k+2 -x k+1 2 ≤ γ 2 k+1 d 2 C . (4.16)
Moreover, by the two assumptions (P.3), (A.4) and Proposition 2.1(v), (3.7) holds with a constant M > 0 , and thus with Proposition 2.1(iv) we obtain

g β k+1 -g β k (T x k+1 ) ≤ β k -β k+1 2 ∂g (T x k+1 ) 0 2 ≤ β k -β k+1 2 M. ( 4
∆ k+1 -∆ k ≤ - M c γ k+1 Ax k+1 -b 2 -δγ k+1 A (x k+1 -xk+1 ) 2 + L k+1 2 γ 2 k+1 d 2 C + K (F,ζ,C) ζ (γ k+1 ) + β k -β k+1 2 M + ρ k+1 -ρ k 2 Ax k+1 -b 2 . (4.18)
Because of the assumptions (P.1) and (P.4), and in view of the definition of L k in (4.7), we have the following,

L k 2 γ 2 k d 2 C = 1 2 T 2 β k + A 2 ρ k γ 2 k d 2 C ∈ ℓ 1 + .
For the telescopic terms from the right hand side of (4.18) we have

β k -β k+1 2 ∈ ℓ 1 + and ρ k+1 -ρ k 2 Ax k+1 -b 2 ≤ (ρ k+1 -ρ k ) A 2 R 2 + b 2 ∈ ℓ 1 + ,
where R is the constant arising from (A.3). Under (P.1) we also have that

K (F,ζ,C) ζ (γ k+1 ) ∈ ℓ 1 + .
Using the notation of Lemma 2.14, we set

r k = ∆ k , p k = γ k+1 , w k = M c Ax k+1 -b 2 + δ A (x k+1 -xk+1 ) 2 , z k = L k+1 2 γ 2 k+1 d 2 C + K (F,ζ,C) ζ (γ k+1 ) + β k -β k+1 2 M + ρ k+1 -ρ k 2 Ax k+1 -b 2 .
We have shown above that

r k+1 ≤ r k -p k w k + z k ,
where (z k ) k∈N ∈ ℓ 1 + , and r k is bounded from below. We then deduce using Lemma 2.14(i) that (r k ) k∈N is convergent and

γ k Ax k -b 2 k∈N ∈ ℓ 1 + , γ k A (x k -xk ) 2 k∈N ∈ ℓ 1 + . (4.19)
Consequently,

γ k Ax k -b 2 k∈N ∈ ℓ 1 + , (4.20)
since, by Jensen's inequality,

∞ k=1 γ k Ax k -b 2 ≤ 2 ∞ k=1 γ k A (x k -xk ) 2 + Ax k -b 2 < +∞.
We are now ready to prove Theorem 4.1, i.e., to show that the sequence of iterates (x k ) k∈N is asymptotically feasible.

Proof.

(i) By Lemma 4.8 with ρ k ≡ ρ k+1 ≡ 2, we have

Ax k -b 2 -Ax k+1 -b 2 ≤ 2γ k d C A ( A R + b ) .
Using this together with Lemma 4.9 and Assumption (P.2), we are in position to apply Lemma 2.14(ii) to conclude that lim k→∞ Ax kb = 0. (ii) The rates in (4.1) follow respectively from Lemma 2.14(iii) and Lemma 2.14(iv). (iii) We have, by Jensen's inequality and Lemma 4.9, that

Ax k -b 2 ≤ 1 Γ k k i=0 γ i Ax i -b 2 ≤ 1 Γ k +∞ i=0 γ i Ax i -b 2 = O 1 Γ k .

Dual multiplier boundedness

In this part we provide a lemma that shows the sequence of dual variables (µ k ) k∈N generated by Algorithm 1 is bounded. We start by studying coercivity of φ.

Lemma 4.10. Suppose that Assumptions (A.1)-(A.3) and (A.6)-(A.8) hold. Then φ is coercive on ran (A).

Proof. From (3.4), we have, for any c ∈ A -1 (b), that

φ(µ) = Φ * + -c, • (-A * µ) .
Moreover, Assumptions (A.1) and (A.7) entail that Φ ∈ Γ 0 (H p ). We now consider separately the two assumptions.

(a) Case of (A.8)(a): If follows from the Fenchel-Moreau theorem ([4, Theorem 13.32]) that

Φ * -c, • * = Φ * * (• + c) = Φ (• + c) .
Using this, together with Proposition 2.10 and (A.2), we can assert that Φ *c, • is coercive if and only if

0 ∈ int dom Φ (• + c) = int (dom (Φ)) -c = int (dom (g • T ) ∩ C) -c = int (dom (g • T )) ∩ int (C) -c.
But this is precisely what (A.8)(a) guarantees. In turn, using [4, Proposition 14.15], (A.8)(a) is equivalent to

∃(a > 0, β ∈ R), Φ * -c, • ≥ a • + β.
Using standard results on linear operators in Hilbert spaces [4, Facts 2.18 and 2.19], we have

(A.7) ⇐⇒ (∃α > 0), (∀µ ∈ ran(A)), A * µ ≥ α µ .
Combining the last two inequalities, we deduce that under (A.8)(a),

∃(a > 0, α > 0, β ∈ R), (∀µ ∈ ran(A)), φ(µ) ≥ a A * µ + β ≥ aα µ + β,
φ∞ (u) = Φ * + -c, • • (-A * ) ∞ (u) (Proposition 2.11(iii)) = Φ * + -c, • ∞ (-A * u) (Proposition 2.11(ii)) = σ dom( Φ * + -c,• ) * (-A * u) = σ dom( Φ(•+c)) (-A * u) = σ dom( Φ)-c (-A * u) (by (A.2)) = σ dom(g•T )∩C-c (-A * u) .
Notice that, by Assumption (A.4), we have dom (g • T ) ∩ C = C. Thus, using Proposition 2.11(i), we have the following chain of equivalences

φ is coercive on ran (A) ⇐⇒ φ∞ (u) > 0, ∀u ∈ ran (A) \ {0} ⇐⇒ σ C-c (-A * u) > 0, ∀u ∈ ran (A) \ {0} .
For this to hold, and since ran (A) = ker (A * ) ⊥ , a sufficient condition is that Proof. Using the notation in (3.4), the primal problem:

σ C-c (x) > 0, ∀x ∈ ran (A * ) \ {0} . ( 4
min x∈Hp {Φ(x) : Ax = b} = min x∈Hp sup µ∈H d L (x, µ) ,
is obviously equivalent to

min x∈Hp Φ(x) + ρ k 2 Ax -b 2 : Ax = b = min x∈Hp sup µ∈H d L (x, µ) + ρ k 2 Ax -b 2 .
We associate to the previous the following regularized primal problem:

min x∈Hp {Φ k (x) : Ax = b} = min x∈Hp sup µ∈H d L k (x, µ)
and its Lagrangian dual, namely:

sup µ∈H d inf x∈Hp L k (x, µ) = -inf µ∈H d sup x∈Hp -L k (x, µ) .

Now consider the dual function in the latter, namely ϕ

k (µ) def = -inf x∈Hp L k (x, µ).
Observe that the minimum is actually attained owing to (A.1) and (A.3). Now we claim that ϕ k is continuously differentiable with L ∇ϕ k -Lipschitz gradient, and 1/ρ (see (P.4)) is an upper-bound for (L ∇ϕ k ) k∈N . In order to show it, introduce the notation

F k (x) def = f (x) + g β k (T x) + h(x); G k (v) def = ρ k 2 v -b 2 .
By definition, we have

ϕ k (µ) = -min x∈Hp f (x) + g β k (T x) + h(x) + µ, Ax -b + ρ k 2 Ax -b 2 = -min x∈Hp {F k (x) + A * µ, x + G k (Ax)} + µ, b . (4.22)
Using Fenchel-Rockafellar duality and strong duality, which holds by (P.4) and continuity of G k (see, for instance, [30, Theorem 3.51]), we have the following equality,

min x∈Hp {F k (x) + A * µ, x + G k (Ax)} = -min v∈H d {(F k (•) + A * µ, • ) * (-A * v) + G * k (v)} = -min v∈H d {F * k (-A * v -A * µ) + G * k (v)}
where we have used the fact that the conjugate of a linear perturbation is the translation of the conjugate in the last line. Substituting the above into (4.22) we find

ϕ k (µ) = min v∈H d F * k (-A * (v + µ)) + 1 2ρ k v 2 + v, b + µ, b = min v∈H d F * k (-A * (v + µ)) + 1 2ρ k v + ρ k b 2 + µ, b - ρ k 2 b 2
Moreover, from the primal-dual extremality relationships [30, Theorem 3.51(i)], we have

-ṽ = ∇G k (Ax) = ρ k (Ax -b) , (4.23)
where x is a minimizer (which exists and belongs to C) of the primal objective L k (•, µ) and ṽ is the unique minimizer to the associated dual objective. Now, using the change of variable u = v + µ, we get

ϕ k (µ) = inf u∈H d F * k (-A * u) + 1 2ρ k u -µ + ρ k b 2 + µ, b - ρ k 2 b 2 = [F * k • (-A * )] ρ k (µ -ρ k b) + µ, b - ρ k 2 b 2 ,
where the notation [•] ρ k denotes the Moreau envelope with parameter ρ k as defined in (2.2). It follows from Proposition 2.1(i) and (iii), that ϕ k is convex, real-valued and its gradient, given by

∇ϕ k (µ) = ρ -1 k (µ -ρ k b -ũ) + b = ρ -1 k (µ -ũ) , where ũ = prox ρ k F * k •(-A * ) (µ -ρ k b), (4.24)
is 1/ρ k -Lipschitz continuous since the gradient of a Moreau envelope with parameter ρ k is 1/ρ k -Lipschitz continuous (see Proposition 2.1(iii)). As ρ k is non-decreasing, 1/ρ k ≤ 1/ρ and the sequence of functions (∇ϕ k ) k∈N is uniformly Lipschitz-continuous with constant 1/ρ. In addition, combining (4.23) and (4.24), and recalling the change of variable ũ = ṽ + µ, we get that

∇ϕ k (µ) = ρ -1 k (µ -ũ) = -ρ -1 k ṽ = Ax -b. (4.25)
As in Lemma 4.9, we are going to denote xk a minimizer of L k (x, µ k ). Then, from the Descent Lemma (see Proposition 2.4 and inequality (2.7)), we have

ϕ k (µ k+1 ) ≤ ϕ k (µ k ) + ∇ϕ k (µ k ), µ k+1 -µ k + 1 2ρ µ k+1 -µ k 2 .
Now substitute in the right-hand-side the expression ∇ϕ k (µ k ) = Ax kb in (4.25) and the update

µ k+1 = µ k + θ k (Ax k+1 -b) from the algorithm, to obtain ϕ k (µ k+1 ) ≤ ϕ k (µ k ) + θ k Ax k -b, Ax k+1 -b + θ 2 k 2ρ Ax k+1 -b 2 ≤ ϕ k (µ k ) + θ k 2 Ax k -b 2 + θ k 2 θ k ρ + 1 Ax k+1 -b 2 , (4.26)
where we estimated the scalar product by Cauchy-Schwartz and Young inequality. Moreover, by definition,

ϕ k+1 (µ k+1 ) = -inf x∈Hp f (x) + g β k+1 (T x) + h(x) + µ k+1 , Ax -b + ρ k+1 2 Ax -b 2 = sup x∈Hp -L k (x, µ k+1 ) + g β k -g β k+1 (T x) + 1 2 (ρ k -ρ k+1 ) Ax -b 2 .
(4.27)

Now recall assumptions (P.3) and (P.4): for β k non-increasing, g β kg β k+1 (T x) ≤ 0 for every x ∈ H p by Proposition 2.1(v) and, for ρ k non-decreasing, ρ kρ k+1 ≤ 0. Then we can estimate the right-hand-side of (4.27) to obtain

ϕ k+1 (µ k+1 ) ≤ sup x∈Hp -L k (x, µ k+1 ) = ϕ k (µ k+1 ).
Sum (4.26) with the latter, to obtain

ϕ k+1 (µ k+1 ) -ϕ k (µ k ) ≤ θ k 2 Ax k -b 2 + θ k 2 θ k ρ + 1 Ax k+1 -b 2 .
By Assumption (P.6), θ k = γ k /c where γ k ≤ 1. Moreover, by assumption (P.5), γ k ≤ M γ k+1 . Then,

ϕ k+1 (µ k+1 ) -ϕ k (µ k ) ≤ γ k 2c Ax k -b 2 + M 2c 1 ρc + 1 γ k+1 Ax k+1 -b 2 . (4.28)
Notice that the right-hand-side is in

ℓ 1 + , because both γ k Ax k -b 2 k∈N and γ k Ax k -b 2 k∈N
are in ℓ 1 + by Lemma 4.9. Additionally, (ϕ k (µ k )) k∈N is bounded from below. Indeed, by virtue of (A.6) and Remark 3.1(iv), we have

ϕ k (µ k ) ≥ -L k (x ⋆ , µ k ) ≥ -[f (x ⋆ ) + g(T x ⋆ ) + h(x ⋆ )] > -∞.
Then we can use Lemma 2.14(i) on inequality (4.28) to conclude that (ϕ k (µ k )) k∈N is convergent and, in particular, bounded. Now recall Φ k , Φ and φ from (3.4). Notice that

ϕ k (µ) = sup x∈Hp { µ, b -Ax -Φ k (x)} = sup x∈Hp { -A * µ, x -Φ k (x)} + b, µ = Φ * k (-A * µ) + b, µ .
It then follows that

g β k ≤ g =⇒ Φ k ≤ Φ ⇐⇒ Φ * ≤ Φ * k =⇒ φ ≤ ϕ k , (4.29)
where we used Proposition 2.1(v) and the fact in (2.1). We are now in position to invoke Lemma 4.10 which shows that φ is coercive on ran(A), and thus, by (4.29), (ϕ k ) k∈N is coercive uniformly in k on ran(A). In turn, since ran(A) is closed and (µ k ) k∈N ⊂ ran(A) = ker(A * ) ⊥ , we have from (4.29) and the proof of Lemma 4.10 that

∃(a > 0, α > 0, β ∈ R), (∀k ∈ N), ϕ k (µ k ) ≥ φ(µ k ) ≥ a A * µ k + β ≥ aα µ k + β,
which shows that (µ k ) k∈N is indeed bounded by boundedness of (ϕ k (µ k )) k∈N .

Optimality

In this section we prove Theorem 4.2 by establishing convergence of the Lagrangian values to the optimum (i.e., the value at the saddle-point).

We start by showing some boundedness claims that will be important in our proof.

Lemma 4.12. Under assumptions (A.1)-(A.8) and (P.1)-(P.6), the objective Φ is bounded on C, and thus

M def = sup x∈C |Φ(x)| + sup k∈N µ k ( A R + b ) < +∞, (4.30)
where we recall the radius R from assumption (A.3).

Proof.

By assumption (A.4), g is subdifferentiable at T x for any x ∈ C. Thus convexity of g implies that for any x ∈ C

g(T x) ≤ g(T x ⋆ ) + [∂g (T x)] 0 , T x -T x ⋆ ≤ g(T x ⋆ ) + [∂g (T x)] 0 T d C g(T x) ≥ g(T x ⋆ ) + [∂g (T x ⋆ )] 0 , T x -T x ⋆ ≥ g(T x ⋆ ) -[∂g (T x ⋆ )] 0 T d C . ( 4
In turn, convexity entails that for any x ∈ C

f (x) ≤ f (x ⋆ ) + ∇f (x) , x -x ⋆ ≤ f (x ⋆ ) + ∇f (x) d C , f (x) ≥ f (x ⋆ ) + ∇f (x ⋆ ) , x -x ⋆ ≥ f (x ⋆ ) -∇f (x ⋆ ) d C . (4.33)
From assumption (A.5), we also have for any

x ∈ C h(x ⋆ ) -L h d C ≤ h(x) ≤ h(x ⋆ ) + L h d C . (4.34)
Summing (4.31), (4.33) and (4.34), using (4.32) and assumption (A.4), we get

|Φ(x)| ≤ |Φ(x ⋆ )| + L h + T sup x∈C [∂g (T x)] 0 + sup x∈C ∇f (x) .
From Lemma 4.11, we know that the sequence of dual variables (µ k ) k∈N is bounded which concludes the proof.

Define C k def = L k 2 d 2 C + d C (D + M T + L h + A µ ⋆ )
, where L k is given in (4.7) and the constants D, M , and L h are as in Lemma 4.7. We then have the following lemma, in which we state the main energy estimation. Lemma 4.13. Suppose that assumptions (A.1)-(A.8) and (P.1)-(P.6) hold, with M ≥ 1. Consider the sequence of primal-dual iterates ((x k , µ k )) k∈N generated by Algorithm 1 and (x ⋆ , µ ⋆ ) a saddle-point point of the Lagrangian as in (3.5). Let

r k def = (1 -γ k )L k (x k , µ k ) + c 2 µ k -µ ⋆ 2 + β k 2 M 2 + γ k M . (4.35)
Then, we have the following energy estimate

r k+1 -r k + γ k L (x k , µ ⋆ ) -L (x ⋆ , µ ⋆ ) + ρ k 2 Ax k -b 2 ≤ 1 2 ρ k+1 -ρ k -γ k+1 ρ k+1 + 2 c γ k - γ 2 k c Ax k+1 -b 2 + γ k β k 2 M 2 + K (F,ζ,C) ζ (γ k ) + C k γ 2 k . (4.36)
Proof. Notice that the dual update µ k+1 = µ k + θ k (Ax k+1b) can be re-written as

{µ k+1 } = Argmin µ∈H d -L k (x k+1 , µ) + 1 2θ k µ -µ k 2 .
Then, from firm nonexpansiveness of the proximal mapping (see (2.3)),

0 ≥ θ k [L k (x k+1 , µ ⋆ ) -L k (x k+1 , µ k+1 )] + 1 2 µ k+1 -µ ⋆ 2 -µ k -µ ⋆ 2 + µ k+1 -µ k 2 = θ k [L k (x k+1 , µ ⋆ ) -L k (x k+1 , µ k+1 )] + 1 2 µ k+1 -µ ⋆ 2 -µ k -µ ⋆ 2 + θ 2 k 2 Ax k+1 -b 2 . (4.37)
Notice that

L k (x k+1 , µ k ) -L k (x k , µ k ) = [E k (x k+1 , µ k ) + h(x k+1 )] -[E k (x k , µ k ) + h(x k )]
and that, by the definition of x k+1 in the algorithm and by convexity of function h,

h(x k+1 ) -h(x k ) = h((1 -γ k ) x k + γ k s k ) -h(x k ) ≤ γ k (h(s k ) -h(x k )) .
Then,

L k (x k+1 , µ k ) -L k (x k , µ k ) ≤ E k (x k+1 , µ k ) -E k (x k , µ k ) + γ k (h(s k ) -h(x k )) . (4.38)
Now apply Lemma 4.6 at the points x ⋆ , x k , and µ k to affirm that

E k (x ⋆ , µ k ) ≥ E k (x k , µ k ) + ∇ x E k (x k , µ k ) , x ⋆ -x k + ρ k 2 A(x ⋆ -x k ) 2 .
From the latter, by the alternative definition of s k in the algorithm (see (3.3)), we obtain

E k (x ⋆ , µ k ) ≥ E k (x k , µ k ) -h(x ⋆ ) + h(s k ) + ∇ x E k (x k , µ k ) , s k -x k + ρ k 2 Ax k -b 2 . (4.39)
From Lemma 4.5, we have also that

E k (x k+1 , µ k ) ≤ E k (x k , µ k ) + ∇ x E k (x k , µ k ) , x k+1 -x k + K (F,ζ,C) ζ (γ k ) + L k 2 x k+1 -x k 2 .
Recall that, from the algorithm,

x k+1 = x k + γ k (s k -x k ). Then, E k (x k+1 , µ k ) ≤ E k (x k , µ k ) + γ k ∇ x E k (x k , µ k ) , s k -x k + K (F,ζ,C) ζ (γ k ) + L k γ 2 k 2 s k -x k 2 ≤ E k (x k , µ k ) + γ k E k (x ⋆ , µ k ) + h(x ⋆ ) -E k (x k , µ k ) -h(s k ) - ρ k 2 Ax k -b 2 + K (F,ζ,C) ζ (γ k ) + L k 2 d 2 C γ 2 k ,
where in the last inequality we used (4.39). Using the latter in (4.38), we obtain

L k (x k+1 , µ k ) -L k (x k , µ k ) ≤γ k L k (x ⋆ , µ k ) -L k (x k , µ k ) - ρ k 2 Ax k -b 2 + K (F,ζ,C) ζ (γ k ) + L k 2 d 2 C γ 2 k . (4.40)
Notice also that, from the definitions of L k (x k+1 , •) and µ k+1 as

µ k+1 = µ k + θ k (Ax k+1 -b), L k (x k+1 , µ k+1 ) -L k (x k+1 , µ k ) = µ k+1 -µ k , Ax k+1 -b = θ k Ax k+1 -b 2 .
So, from the latter and (4.40),

L k (x k+1 , µ k+1 ) -L k (x k , µ k ) ≤ θ k Ax k+1 -b 2 + γ k [L k (x ⋆ , µ k ) -L k (x k , µ k )] - ρ k γ k 2 Ax k -b 2 + K (F,ζ,C) ζ (γ k ) + L k 2 d 2 C γ 2 k .
Now recall that, by assumption (P.6), θ k = γ k /c. Multiply (4.37) by c and sum with the latter, to obtain

(1 -cθ k )L k (x k+1 , µ k+1 ) -(1 -cθ k )L k (x k , µ k ) + c 2 µ k+1 -µ ⋆ 2 -µ k -µ ⋆ 2 ≤ θ k - cθ 2 k 2 Ax k+1 -b 2 + γ k [L k (x ⋆ , µ k ) -L k (x k , µ k )] -cθ k [L k (x k+1 , µ ⋆ ) -L k (x k , µ k )] -ρ k γ k 2 Ax k -b 2 + K (F,ζ,C) ζ (γ k ) + L k 2 d 2 C γ 2 k .
The previous inequality can be re-written, by trivial manipulations, as

(1 -cθ k+1 )L k+1 (x k+1 , µ k+1 ) -(1 -cθ k )L k (x k , µ k ) + c 2 µ k+1 -µ ⋆ 2 -µ k -µ ⋆ 2 ≤ (1 -cθ k+1 )L k+1 (x k+1 , µ k+1 ) -(1 -cθ k )L k (x k+1 , µ k+1 ) + θ k - cθ 2 k 2 Ax k+1 -b 2 + γ k [L k (x ⋆ , µ k ) -L k (x k , µ k )] -cθ k [L k (x k+1 , µ ⋆ ) -L k (x k , µ k )] - ρ k γ k 2 Ax k -b 2 + K (F,ζ,C) ζ (γ k ) + L k 2 d 2 C γ 2 k = c (θ k -θ k+1 ) [f + h + µ k+1 , A • -b ] (x k+1 ) + (1 -cθ k+1 ) g β k+1 -(1 -cθ k ) g β k (T x k+1 ) + 1 2 (1 -cθ k+1 ) ρ k+1 -(1 -cθ k ) ρ k + 2θ k -cθ 2 k Ax k+1 -b 2 + γ k [L k (x ⋆ , µ k ) -L k (x k , µ k )] -cθ k [L k (x k+1 , µ ⋆ ) -L k (x k , µ k )] - ρ k γ k 2 Ax k -b 2 + K (F,ζ,C) ζ (γ k ) + L k 2 d 2 C γ 2 k . (4.41)
By (P.5) and (P.6), and the assumption that M ≥ 1, we have θ k+1 ≤ M -1 θ k ≤ θ k . In view of (P.3), we also have β k+1 ≤ β k by (P.3). In particular, g β k ≤ g β k+1 ≤ g. Now, by Proposition 2.1(iv) and the definition of the constant M in (3.7), we are able to estimate the quantity

(1 -cθ k+1 ) g β k+1 -(1 -cθ k ) g β k (T x k+1 ) = g β k+1 -g β k (T x k+1 ) + c θ k g β k -θ k+1 g β k+1 (T x k+1 ) ≤ 1 2 (β k -β k+1 ) [∂g(T x k+1 )] 0 2 + c θ k g β k -θ k+1 g β k (T x k+1 ) ≤ 1 2 (β k -β k+1 ) M 2 + c (θ k -θ k+1 ) g(T x k+1 ).
Then,

c (θ k -θ k+1 ) [f + h + µ k+1 , A • -b ] (x k+1 ) + (1 -cθ k+1 ) g β k+1 -(1 -cθ k ) g β k (T x k+1 ) ≤ c (θ k -θ k+1 ) L (x k+1 , µ k+1 ) + 1 2 (β k -β k+1 ) M 2 . (4.42)
Recall that, by assumption (A.3), C is convex and bounded and that, by the update x k+1 = x k +γ k (s kx k ) with s k ∈ C and γ k ∈]0, 1] by (P.1), x k always belongs to C. From the assumptions, the functions f, h and g • T are bounded on C and, from the algorithm and convexity, (x k ) k∈N ⊂ C. By Lemma 4.11, also the sequence (µ k ) k∈N is bounded. Then, recalling M from Lemma 4.12, we can use the Cauchy-Schwartz and the triangular inequality to affirm that

L (x k , µ k ) = Φ(x k ) + µ k , Ax k -b ≤ M . (4.43)
Recall the definition of r k in (4.35). Coming back to (4.41) and using both (4.42) and (4.43), we obtain

r k+1 -r k ≤ 1 2 (1 -γ k+1 ) ρ k+1 -(1 -γ k ) ρ k + 2 c γ k - γ 2 k c Ax k+1 -b 2 + γ k [L k (x ⋆ , µ k ) -L k (x k+1 , µ ⋆ )] - ρ k γ k 2 Ax k -b 2 + K (F,ζ,C) ζ (γ k ) + L k 2 d 2 C γ 2 k . (4.44)
Recall that, by feasibility of

x ⋆ , L (x ⋆ , µ k ) = L (x ⋆ , µ ⋆ ). Now compute L k (x ⋆ , µ k ) -L k (x k+1 , µ ⋆ ) = L (x ⋆ , µ k ) -L (x k+1 , µ ⋆ ) + g β k -g (T x ⋆ ) + g -g β k (T x k+1 ) - ρ k 2 Ax k+1 -b 2 ≤ L (x ⋆ , µ ⋆ ) -L (x k+1 , µ ⋆ ) + β k 2 M 2 - ρ k 2 Ax k+1 -b 2 ,
where in the inequality we used the facts that g β k ≤ g and that, by Proposition 2.1(v) and (3.7),

g -g β k (T x k+1 ) ≤ β k 2 [∂g(T x k+1 )] 0 2 ≤ β k 2 M 2 .
Then, using the latter in (4.44), we obtain

r k+1 -r k ≤ 1 2 ρ k+1 -ρ k -γ k+1 ρ k+1 + 2 c γ k - γ 2 k c Ax k+1 -b 2 + γ k [L (x ⋆ , µ ⋆ ) -L (x k+1 , µ ⋆ )] + γ k β k 2 M 2 - ρ k γ k 2 Ax k -b 2 + K (F,ζ,C) ζ (γ k ) + L k 2 d 2 C γ 2 k .
We replace the term

[L (x ⋆ , µ ⋆ ) -L (x k+1 , µ ⋆ )] with [L (x ⋆ , µ ⋆ ) -L (x k , µ ⋆ )]+[L (x k , µ ⋆ ) -L (x k+1 , µ ⋆ )]
and estimate using Lemma 4.7 to get the following,

r k+1 -r k ≤ 1 2 ρ k+1 -ρ k -γ k+1 ρ k+1 + 2 c γ k - γ 2 k c Ax k+1 -b 2 + γ k [L (x ⋆ , µ ⋆ ) -L (x k , µ ⋆ )] + γ k β k 2 M 2 - ρ k γ k 2 Ax k -b 2 + K (F,ζ,C) ζ (γ k ) + C k γ 2 k .
We conclude by trivial manipulations.

We are now ready to prove Theorem 4.2.

Proof. Our starting point is the main energy estimate (4.36). Let us focus on its right-hand-side. Under assumption (P.7),

1 2 ρ k+1 -ρ k -γ k+1 ρ k+1 + 2 c γ k - γ 2 k c Ax k+1 -b 2 ≤ γ k+1 Ax k+1 -b 2 ,
where the right hand side is in ℓ 1 + by Lemma 4.9. Now remember that

C k = L k 2 d 2 C +d C (D + M T + L h + A µ ⋆ ), where L k = T 2 /β k + A 2 ρ k . Then we have γ k β k M 2 /2+K (F,ζ,C) ζ (γ k )+C k γ 2 k = γ k β k M 2 /2+K (F,ζ,C) ζ (γ k )+ T 2 γ 2 k d C / (2β k )+ A 2 ρ k γ 2 k d C /2 + d C (D + M T + L h + A µ ⋆ ) γ 2 k ∈ ℓ 1 + .
Indeed, under assumption (P.1), the sequences (γ k β k ) k∈N , (ζ (γ k )) k∈N , and γ 2 k /β k k∈N belong to ℓ 1 + . Moreover, we have by assumptions (P.3) and (P.4) that ργ 2 k ≤ ρ k γ 2 k ≤ β 0 ργ 2 k /β k , whence we get that ρ k γ 2 k k∈N ∈ ℓ 1 + and γ 2 k k∈N ∈ ℓ 1 + after invoking assumption (P.1). Thus all terms on the right hand side are summable. Let

w k def = [L (x k , µ ⋆ ) -L (x ⋆ , µ ⋆ )] + ρ k 2 Ax k -b 2 z k def = γ k+1 Ax k+1 -b 2 + γ k β k M 2 /2 + K (F,ζ,C) ζ (γ k ) + C k γ 2 k .
So far, we have shown that

r k+1 ≤ r k -γ k w k + z k , (4.45)
where r k is bounded from below, and (z k ) k∈N ∈ ℓ 1 + . The rest of the proof consists of invoking properly Lemma 2.14.

(i) In order to use Lemma 2.14(ii), we need to show that for some positive constant α,

w k -w k+1 ≤ αγ k .
Notice that the term L (x k , µ ⋆ ) -L (x ⋆ , µ ⋆ ) is proportional to γ k by Lemma 4.7. For the second term of w k , we have by Lemma 4.8 that

ρ k 2 Ax k -b 2 - ρ k+1 2
Ax k+1b 2 is proportional to γ k . The desired claim then follows from Lemma 2.14(ii). (ii) By [4, Lemma 2.37], we can assert that (x k ) k∈N possesses a weakly convergent subsequence, say

x k j j∈N , with cluster point x ∈ C. Since A • -b ∈ Γ 0 (H p ) and in view of [START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF]Theorem 9.1], we have

Ax -b ≤ lim inf j Ax k j -b = lim k Ax k -b = 0,
where we used lower semicontinuity of the norm and Theorem 4.2. Thus Ax = 0, meaning that x is a feasible point of (P). In turn, L (x, µ ⋆ ) = Φ(x). The function L (•, µ ⋆ ) is lower semicontinuous by (A.1) and (A.6). Thus, using [4, Theorem 9.1] and by virtue of claim (i), we have

Φ(x) = L (x, µ ⋆ ) ≤ lim inf j L x k j , µ ⋆ = lim k L (x k , µ ⋆ ) = L (x ⋆ , µ ⋆ ) ≤ L (x, µ ⋆ )
for all x ∈ H p , and in particular for all x ∈ A -1 (b). Thus, for every x ∈ A -1 (b), we deduce that

Φ(x) ≤ L (x, µ ⋆ ) = Φ(x),
meaning that x is a solution for problem (P).

Meanwhile, as the sequence (µ k ) k∈N is bounded by Lemma 4.11, we can again invoke [START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF]Lemma 2.37] to extract a weakly convergent subsequence µ k j j∈N with cluster point μ. By Fermat's rule ([4, Theorem 16.2]), the weak sequential cluster point μ is a solution to (D) if and only if

0 ∈ ∂ (Φ * • (-A * )) (μ) + b.
Since the proximal operator is the resolvent of the subdifferential, it follows that (4.24) is equivalent to

∇ϕ k j µ k j -b ∈ ∂ Φ * k j • (-A * ) µ k j -ρ k j ∇ϕ k j µ k j . ( 4
* k j • -(A * ) Mosco-converges to (f + g • T + h) * • (-A * ) = Φ * • (-A * ). This implies, via [2, Theorem 3.66], that ∂Φ * k j • (-A * ) graph-converges to ∂Φ * • (-A * )
, and [2, Proposition 3.59] shows that ∂Φ k j • (-A * ) j∈N is sequentially closed for graph-convergence in the weak-strong topology on H d , i.e., for any sequence (v k j , η k j ) in the graph of ∂Φ * k j • (-A * ) such that v k j converges weakly to v and η k j converges strongly to η, we have η ∈ ∂Φ * • (-A * )(v). Taking v k j = ∇ϕ k j µ k jb and η k j = µ k jρ k j ∇ϕ k j µ k j , we conclude that

0 ∈ ∂ (Φ * • (-A * )) (μ) + b,
i.e., μ is a solution of the dual problem (D). Recall r k from (4.35) which verifies (4.45). From Lemma 2.14(i), (r k ) k∈N is convergent. By (P.1) and (P.3), γ k and β k both converge to 0. We also have that

-L k (x k , µ k ) = (L(x k , µ ⋆ ) -L k (x k , µ k )) -L(x k , µ ⋆ ) = g(T x k ) -g β k (T x k ) + µ ⋆ -µ k , Ax k -b - ρ k 2 Ax k -b 2 -L(x k , µ ⋆ ).
We have from Theorem 4. (Lemma 4.11). We also have L(x k , µ ⋆ ) → L(x ⋆ , µ ⋆ ) by claim (i) above. By Proposition 2.1(v) and (3.7), we get that

1(i) that ρ k 2 Ax k -b 2 → 0. In turn, µ ⋆ -µ k , Ax k -b → 0 since (µ k ) k∈N is bounded
0 ≤ g(T x k ) -g β k (T x k ) ≤ β k 2 M 2 .
Passing to the limit and in view of (P.3), we conclude that g(T x k )g β k (T x k ) → 0. Altogether, this shows that L k (x k , µ k ) → L(x ⋆ , µ ⋆ ). In turn, we conclude that the limit

lim k→∞ µ k -µ ⋆ 2 = 2/c lim k→∞ r k -L(x ⋆ , µ ⋆ )
exists. Since µ ⋆ was an arbitray optimal dual point, and we have shown above that each subsequence of (µ k ) k∈N converges weakly to an optimal dual point, we are in position to invoke Opial's lemma [START_REF]Weak convergence of the sequence of successive approximations for nonexpansive mappings[END_REF] to conclude that the whole dual multiplier sequence weakly converges to a solution of the dual problem. (iii) Recalling that (γ k ) k∈N ∈ ℓ 1 + (see assumption (P.2)), the rates in (4.4) follow by applying Lemma 2.14(iii)-(iv) to (4.45). Notice that both terms in w k are positive and that ρ k ≥ ρ > 0 (see again assumption (P.4)). Therefore we have that, for the same subsequence x k j j∈N , (4.6) holds.

(iv) The ergodic rate (4.2) follows by applying the Jensen's inequality to the convex function L (•, µ ⋆ ).

Applications

Sum of several nonsmooth functions

In this section we explore the applications of Algorithm 1 to splitting in composite optimization problems, where we allow the presence of more than one nonsmooth function g or h in the objective:

min x∈Hp f (x) + n i=1 g i (T i x) + n i=1 h i (x) . (5.1)
First, we denote the product space by H p def = H n p endowed with the scalar product x, y = 1 n n i=1 x (i) , y (i) , where x and y are vectors in H p with x def = x (1) , . . . , x (n) ⊤ . We define also V as the diagonal subspace of H p , i.e. V def = {x ∈ H p : x (1) = . . . = x (n) }, V ⊥ the orthogonal subspace to V, and Π V , Π V ⊥ the orthogonal projections onto V, V ⊥ -respectively. We finally introduce the (diagonal) linear operator T :

H p → H p defined by [T (x)] (i) = T i x (i)
and the functions

F (x) def = 1 n n i=1 f x (i) ; G (T x) def = n i=1 g i T i x (i) ; H (x) def = n i=1 h i x (i) .
Then problem (5.1) is obviously equivalent to

min x∈Hp {F (x) + G(T x) + H (x) : Π V ⊥ x = 0} , (5.2)
which fits in the setting of our main problem (P). In order to make more clear the presentation, we separate the two cases of multiple g and multiple h, that can be trivially combined. Moreover, we focus on the main case h i = ι C i .

Sum of several simple functions over a compact set

Consider the following composite minimization problem,

min x∈C f (x) + n i=1 g i (T i x) . (5.3)
We can reformulate the problem in the product space H p using the above notation to get,

min x∈C n ∩V {F (x) + G (T x)} .
Applying Algorithm 1 to this problem gives a completely separable scheme; we first compute the direction,

s k ∈ Argmin s∈C n ∩V ∇ F (x k ) + G β k (T x k ) , s ,
which reduces to the following computation since

s k =    s k . . . s k    has identical components, s k ∈ Argmin s∈C n i=1 1 n ∇f x (i) k + ∇g β k i T i x (i) k , s .
The term ∇g β k i has a closed form given in Proposition 2.1 which can be used to get the following formula for the direction,

s k ∈ Argmin s∈C n i=1 1 n ∇f x (i) k + 1 β k T * i T i x (i) k -prox βg T i x (i) k
, s .

Minimizing over intersection of compact sets

A classical problem found in machine learning is to minimize a Lipschitz-smooth function f over the intersection of convex, compact sets C i in some real Hilbert space H,

min x∈ n i=1 C i f (x) = min x∈H f (x) + n i=1 h i (x) ,
where h i ≡ ι C i . Reformulating the problem in the product space H p gives,

min x∈Hp Π V ⊥ x=0 {F (x) + H (x)} .
Then, we can apply Algorithm 1 and compute the step direction

s k ∈ Argmin s∈C 1 ×...×Cn s, ∇ F (x) + µ k , Π V ⊥ x k + ρ k 2 Π V ⊥ x k 2
which gives a separable scheme for each component of

s k =    s (1) k . . . s (n) k   , s (i) k ∈ Argmin s∈C i s, 1 n ∇f x (i) k + (Π V ⊥ µ k ) (i) + ρ k (Π V ⊥ x k ) (i) = Argmin s∈C i s, 1 n ∇f x (i) k + µ (i) k - 1 n n j=1 µ (j) k + ρ k   x (i) k - 1 n n j=1 x (j) k   .
(5.4)

Comparison

Conditional Gradient Framework

In [START_REF] Yurtsever | A conditional gradient framework for composite convex minimization with applications to semidefinite programming[END_REF] the following problem was analyzed in the finite-dimensional setting, ) with an arbitrary real Hilbert space H p (possibly infinite dimensional). Furthermore, the analysis in [START_REF] Yurtsever | A conditional gradient framework for composite convex minimization with applications to semidefinite programming[END_REF] is restricted to the parameter choices γ k = 2 k+1 and β k = β 0 √ k+1 exclusively, although they do include a section in which they consider two variants of an inexact linear minimization oracle: one with additive noise and one with multiplicative noise. In contrast, the results we present in Section 3 show optimality and feasibility for a wider choice for both the sequence of stepsizes (γ k ) k∈N and the sequence of smoothing parameters (β k ) k∈N , although we only consider exact linear perturbation oracles of the form Argmin s∈Hp {h (s) + x, s }. Finally, for solving (6.1) with an exact linear minimization oracle, our algorithm encompasses the algorithm in [START_REF] Yurtsever | A conditional gradient framework for composite convex minimization with applications to semidefinite programming[END_REF] by choosing h (x) = ι C (x), A ≡ 0, and restricting f to be in C 1,1 (H) with H = R n .

min x∈C {f (x) + g (T x)} (6.1) where f ∈ C 1,1 (R n ) ∩ Γ 0 (R n ), T ∈ R d×n is a linear operator, g • T ∈ Γ 0 (R n ),
In [START_REF] Yurtsever | A conditional gradient framework for composite convex minimization with applications to semidefinite programming[END_REF]Section 5] there is a discussion on splitting and affine constraints using the conditonal gradient framework presented. In this setting, i.e. assuming exact oracles, the primary difference between CGALP and the conditional gradient framework is the approach each algorithm takes to handle affine constraints. In CGALP , the augmented Lagrangian formulation is used to account for the affine constraints, introducing a dual variable µ and both a linear and quadratic term for the constraint Axb = 0. In contrast, in [START_REF] Yurtsever | A conditional gradient framework for composite convex minimization with applications to semidefinite programming[END_REF] the affine constraint is treated the same as the nonsmooth term g • T and thus handled by quadratic penalization/smoothing alone. The consequence of smoothing for the affine constraint Ax = b comes from calculating the gradient of the squared-distance to the constraint. This will involve solving a least squares problem at each iteration which can be computationally expensive. Our algorithm does not need to solve such a linear system.

The difference in the approaches is highlighted when both methods are applied to problem presented in Section 5.3 with n = 2 since this problem necessitates an affine constraint Π V ⊥ x = 0 for splitting. According to [37, Section 5], we reformulate the problem to be min (2) .

x (1) ∈C 1 x (2) ∈C 2 1 2 f x (1) + f x (2) + ι {x (1) } x
Note that the inclusion of the function ι {x (1) } x (2) in the objective is equivalent to the affine constraint

Π V ⊥ x = 0 in the n = 2 case.
Apply the conditional gradient framework on the variable x (1) , x (2) to get

s k ∈ Argmin s (1) ∈C 1 s (2) ∈C 2        s (1) s (2) ,     ∇ x (1) 1 2 f x (1) k + ι β k x (2) k x (1) k ∇ x (2) 1 2 f x (2) k + ι β k x (1) k x (2) k           
, which leads to a separable scheme that can be computed component-wise, s

k ∈ Argmin s∈C 1 s, 1 2 ∇f x (1) k + x (1) k -x (2) k β k s (2) k ∈ Argmin s∈C 2 s, 1 2 ∇f x (2) k + x (2) k -x (1) k β k . (6.2) (1)
Compare the direction obtained in (6.2) to the one obtained in (5.4), the components of which we rewrite below for n = 2, s

k ∈ Argmin Due to affine constraint, the computation of the direction in (6.2) necessitates smoothing and, as a consequence, the parameter β k , which is necessarily going to 0. In CGALP , the introduction of the dual variable µ k in place of smoothing the affine constraint avoids the parameter β k . Instead, we have the parameter ρ k but ρ k can be picked to be constant without issue.

FW-AL Algorithm

In [START_REF] Pedregosa | Frank-wolfe splitting via augmented lagrangian method[END_REF] the following problem was analyzed,

min x∈ n i=1 C i Ax=0 f (x)
using a combination of the Frank-Wolfe algorithm with the augmented Lagrangian to account for the constraint Ax = 0. The function f is assumed to be Lipschitz-smooth, in contrast to our approach. The perspective used in their paper is to modify the classic ADMM algorithm, replacing the marginal minimization with respect to the primal variable by a Frank-Wolfe step instead, although their analysis is not restricted only to Frank-Wolfe steps. Indeed, in all the scenarios where one can apply FW-AL using a Frank-Wolfe step our algorithm encompasses FW-AL as a special case, discussed in Section 5.3. The primary differences between CGALP and FW-AL are in the convergence results and the generality of CGALP . The results in [START_REF] Pedregosa | Frank-wolfe splitting via augmented lagrangian method[END_REF] prove convergence of the objective in the case where the sets C i are polytopes and convergence of the iterates in the case where the sets C i are polytopes and f is strongly convex, but they do not prove convergence of the objective, weak convergence of the dual variable, or asymptotic feasibility of the iterates in the general case where each C i is a compact, convex set. Instead, they prove two theorems which imply subsequential convergence of the objective and subsequential asymptotic feasibility in the general case and subsequential convergence of the iterates to the optimum in the strongly convex case in [START_REF] Pedregosa | Frank-wolfe splitting via augmented lagrangian method[END_REF]Theorem 2] and [START_REF] Pedregosa | Frank-wolfe splitting via augmented lagrangian method[END_REF]Corollary 2] respectively. Unfortunately, each of these results is obtained separately and so the subsequences that produce each result are not guaranteed to coincide with one another. Interestingly, the results they obtain are not unique to Frank-Wolfe style algorithms as their analysis is from the perspective of a modified ADMM algorithm; they only require that the algorithm used to replace the marginal minimization on the primal variable in ADMM produces sublinear decrease in the objective. Finally, they do not provide conditions for the dual multiplier sequence, µ k in our notation, to be bounded as they discuss in their analysis of issues with similar proofs, e.g. in GDMM. This is a crucial issue as the constants in their bounds depend on the norm of these dual multipliers.

Numerical Experiments

In this section we present some numerical experiments comparing the performance of Algorithm 1 and a proximal algorithm applied to splitting in composite optimization problems.

Projection problem

First, we consider a simple projection problem,

min x∈R 2 1 2
xy 2 2 : x 1 ≤ 1, Ax = 0 , (

where y ∈ R 2 is the vector to be projected and A : R 2 → R 2 is a rank-one matrix. To exclude trivial projections, we choose randomly y / ∈ B 1 1 ∩ ker(A), where B 1 1 is the unit ℓ 1 ball centered at the origin. Then Problem (7.1) is nothing but Problem (P) with f (x) = 1 2 xy 2 2 , g ≡ 0, h ≡ ι B 1 1 and C = B 1 1 . The assumptions mentioned previously, i.e. (A.1)-(A.8), all hold in this finite-dimensional case as f , g, and h are all in Γ 0 R 2 , f is Lipschitz-smooth, h is the indicator function for a compact convex set, g has full domain and 0 ∈ ker(A) ∩ int(C). Regarding the parameters and the associated assumptions, we choose γ k according to Example 3.4 with (a, b) ∈ {(0, 0), (0, 1/3 -0.01), (1, 1/3 -0.01)}, θ k = γ k , and ρ = 2 2-b + 1. The ergodic convergence profiles of the Lagrangian are displayed in Figure 1 along with the theoretical rates (see Theorem 4.2 and Example 4.4). The observed rates agree with the predicted ones of O

Matrix completion problem

We also consider the following, more complicated matrix completion problem, min

X∈R N×N ΩX -y 1 : X * ≤ δ 1 , X 1 ≤ δ 2 , (7.2)
which fits the framework to apply the GFB algorithm proposed in [START_REF] Raguet | Generalized forward-backward splitting[END_REF] (in fact Douglas-Rachford since the smooth part vanishes). The algorithm has three steps, each of which is separable in the components. We choose the step sizes λ k = γ = 1 in the GFB to get,

                             U k+1 =      2W (1) k -Z (1) k + Ω * y -Ω 2W (1) k -Z (1) k + prox • 1 Ω 2W (1) k -Z (1) k -y Π B δ 1 • * 2W (2) k -Z (2) k Π B δ 2 • 1 2W (3) k -Z (3) k      Z k+1 = Z k + U k+1 -W k W k+1 =    3 i=1 Z (i) k+1 /3 3 i=1 Z (i) k+1 /3 3 i=1 Z (i) k+1 /3    (7.6)
We know from [START_REF] Raguet | Generalized forward-backward splitting[END_REF] that Z k converges to Z ⋆ , and W k and U k both converge to W ⋆ = Π V (Z ⋆ ) = (X ⋆ , X ⋆ , X ⋆ ), where X ⋆ is a minimizer of (7.2).

Results

We compare the performance of CGALP with GFB for varying dimension, N , using their respective ergodic convergence criteria. For CGALP this is the quantity L Xk , µ * -L (X ⋆ , µ ⋆ ) where Xk = k i=0 γ i X i /Γ k .

Meanwhile, for GFB, we know from [START_REF] Molinari | Convergence rates of Forward-Douglas-Rachford splitting method[END_REF] that the Bregman divergence

D v ⋆ Q Ū k = Q( Ū k ) -Q(W ⋆ ) - v ⋆ , Ū k -W ⋆ , with Ū k = k i=0
U i /(k + 1) and v ⋆ = (W ⋆ -Z ⋆ )/γ, converges at the rate O(1/(k + 1)).

To compute the convergence criteria, we first run each algorithm for 10 5 iterations to approximate the optimal variables (X ⋆ and µ ⋆ for CGALP , and Z ⋆ and W ⋆ for GFB). Then, we run each algorithm again for 10 5 iterations, this time recording the convergence criteria at each iteration. The results are displayed in Figure 2. It can be observed that our theoretically predicted rate (which is O (1/ log(k + 2)) for CGALP according to Theorem 4.2 and Example 4.4) is in close agreement with the observed one. On the other hand, as is very well-known, employing a proximal step for the nuclear ball constraint will necessitate to compute an SVD which is much more time consuming than computing the linear minimization oracle for large N . For this reason, even though the rates of convergence guaranteed for CGALP are slower than for GFB, one can expect CGALP to be a more time computationally efficient algorithm for large N .

Lemma 2 . 8 .

 28 Suppose that the set C is bounded and denote by d C def = sup x,y∈C xy its diameter. Moreover, assume that the function g is ω-smooth on some open and convex subset C 0 containing C. Set ζ(γ) def = ξ(d C γ), where ξ is given in (2.6). Then the pair (g, C) is (g, ζ)-smooth with K (g,ζ,C) ≤ d C .

  which entails that the set of minimizers of (P) is a non-empty convex closed bounded set under (A.1)-(A.3). Then there are various domain qualification conditions, e.g., one of the conditions in[START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF] Proposition 15.24 and Fact 15.25], that ensure the existence of a saddle-point for the Lagrangian L (see[4, Theorem 19.1 and Proposition 9.19(v)]). (v) Observe that under the inclusion assumption of Lemma 3.2, (A.8)(a) is equivalent to A -1 (b)∩int (C) = ∅. (vi) Assumption (A.8) will be crucial to show that φ is coercive on ker(A * ) ⊥ = ran(A) (the last equality follows from (A.7)), and hence boundedness of the dual multiplier sequence (µ k ) k∈N provided by Algorithm 1 (see Lemma 4.10 and Lemma 4.11).

Lemma 4 . 7 .

 47 Suppose that assumptions (A.1)-(A.8) and (P.1)-(P.7) hold, with M ≥ 1. Let (x k ) k∈N be the sequence of primal iterates generated by Algorithm 1 and µ ⋆ a solution of the dual problem (D). Then we have the following estimate,

  where we have denoted by D the constant D def = sup x∈C ∇f (x) < +∞ (see (4.32)).

Lemma 4 . 8 .

 48 Suppose that assumptions (A.3) and (P.4) hold. Let (x k ) k∈N be the sequence of primal iterates generated by Algorithm 1. Then we have the following estimate,

Lemma 4 . 9 .

 49 Suppose that Assumptions (A.1)-(A.4) and (A.6) hold. Consider the sequence of iterates (x k ) k∈N from Algorithm 1 with parameters satisfying Assumptions (P.1)-(P.6). Define the two quantities ∆ p k and ∆ d k in the following way,

  which in turn is equivalent to coercivity of φ on ran(A) by [4, Proposition 14.15]. (b) Case of (A.8)(b): Since H d is finite dimensional, We have, ∀u ∈ H d ,

. 21 )Lemma 4 . 11 .

 21411 It remains to check that the latter condition holds under (A.8)(b). First, observe that C is a nonempty bounded convex set thanks to (A.1) and (A.3). The first condition in (A.8)(b) is equivalent to 0 ∈ ri(Cc) for some c ∈ A -1 (b). It then follows from Proposition 2.9 that σ C-c (x) > 0, ∀x ∈ par(Cc) ⊥ = par(C) ⊥ , which then implies (4.21) thanks to the second condition in (A.8)(b). Suppose that assumptions (A.1)-(A.3) and (A.6)-(A.8) and (P.1)-(P.6) hold. Then the sequence of dual iterates (µ k ) k∈N generated by Algorithm 1 is bounded.

  and C is a compact, convex subset of R n . They develop an algorithm which avoids projecting onto the set C, instead utilizing a linear minimization oracle lmo C (v) = Argmin x∈C x, v , and replaces the function g • T with the smooth function g β k • T . They consider only functions f which are Lipschitz-smooth and finite dimensional spaces, i.e. R n , compared to CGALP which weakens the assumptions on f to be differentiable and (F, ζ)-smooth (see Definition 2.6

b and o 1 (

 1 k+2) b for the respective choices of (a, b).

Figure 2 :

 2 Figure 2: Convergence profiles for CGALP (left) and GFB (right) for N = 32, N = 64, and N = 128.

  3.

	Definition 2.6. ((G, ζ)-smoothness) Let G : H → R ∪ {+∞} and ζ :]0, 1] → R + . The pair (g, C), where g : H → R ∪ {+∞} and C ⊂ dom(g), is said to be (G, ζ)-smooth if there exists an open set C 0 such that C ⊂ C 0 ⊂ int (dom (G)) and (i) G and g are differentiable on C 0

Lemma 2.12. (

  In the next, we recall some key results about real sequences.[START_REF] Combettes | Quasi-fejérian analysis of some optimization algorithms[END_REF] Lemma 3.1]) Consider three sequences (r k ) k∈N ∈ ℓ + , (a k ) k∈N ∈ ℓ + , and(z k ) k∈N ∈ ℓ 1 + , such that r k+1 ≤ r ka k + z k , ∀k ∈ N. Then (r k ) k∈N is convergent and (a k ) k∈N ∈ ℓ 1 + . Consider two sequences (p k ) k∈N ∈ ℓ + and (w k ) k∈N ∈ ℓ + such that (p k w k ) k∈N ∈ ℓ 1 + and (p k ) k∈N / ∈ ℓ 1 .Then the following holds: (i) there exists a subsequence w k j j∈N such that

	Lemma 2.13. ([36, Theorem 2] and [36, Proposition 2(ii)]) w k j ≤ P -1 k j ,
	where P n = n k=1 p k . In particular, lim inf k (ii) If moreover there exists a constant α > 0 such that w k -w k+1 ≤ αp k for every k ∈ N, then w k = 0.
	lim k	w k = 0.

Lemma 2.14. Consider the sequences

  (r k ) k∈N ∈ ℓ + , (p k ) k∈N ∈ ℓ + , (w k ) k∈N ∈ ℓ + ,and (z k

  .46) By Lemma 4.9 it follows that Ax k converges strongly to b and, combined with (4.25), thus ∇ϕ k j µ k j converges strongly to 0. On the other hand, µ k jρ k j ∇ϕ k j µ k j converges weakly to μ. We now argue that we can pass to the limit in (4.46) by showing sequential closedness. When g ≡ 0, we have, for all j ∈ N, Φ k j ≡ f + h and the rest of the argument relies on sequential closedness of the graph of the subdifferential of Φ * • (-A * ) ∈ Γ 0 (H d ) in the weak-strong topology. For the general case, our argument will rely on the fundamental concept of Mosco convergence of functions, which is epigraphical convergence for both the weak and strong topology (see[START_REF] Brezis | Convergence and approximation of semigroups of nonlinear operators in banach spaces[END_REF] and [2, Definition 3.7]). By Proposition 2.1(v) and assumptions (A.1)-(A.2), Φ k j j∈N is an increasing sequence of functions inΓ 0 (H d ). It follows from [2, Theorem 3.20(i)] that Φ k j Mosco-converges to sup j∈N Φ k j = sup j∈N f + g β k j •T +h = f +g •T +h = Φ since β k j → 0 by (P.3). Bicontinuity of the Legendre-Fenchel conjugation for the Mosco convergence (see[START_REF] Attouch | Variational convergence for functions and operators[END_REF] Theorem 3.18]) entails that Φ

The proof in[START_REF] Evans | Partial differential equations[END_REF] is given in the finite-dimensional case but it extends readily to any real Hilbert space.

Of course, one can add a scaling factor in the choice of the parameters which would allow for more practical flexibility. But this does not change anything to our discussion nor to the bahviour of the CGALP algorithm for k large enough.

Acknowledgements

ASF was supported by the ERC Consolidated grant NORIA. JF was partly supported by Institut Universitaire de France. CM was supported by Project MONOMADS funded by Conseil Régional de Normandie. We would like to warmly thank Gabriel Peyré for his support and very fruitful and inspiring discussions.

where δ 1 and δ 2 are positive constants, Ω : R N ×N → R p is a masking operator, y ∈ R p is a vector of observations, and • * and • 1 are respectively the nuclear and ℓ 1 norms. The mask operator Ω is generated randomly by specifying a sampling density, in our case 0.8. We generate the vector y randomly in the following way. We first generate a sparse vector ỹ ∈ R N with N/5 non-zero entries independently uniformly distributed in [-1, 1]. We take the exterior product ỹ ỹ⊤ = X 0 to get a rank-1 sparse matrix which we then mask to get ΩX 0 . The radii of the contraints in (7.2) are chosen according to the nuclear norm and ℓ 1 norm of X 0 , δ 1 = X 0 * 2 and δ 2 = X 0 1 2 .

CGALP

2) is a special instance of (5.1) with n = 2, f ≡ 0,

, where B δ 1 * and B δ 2 1 are the nuclear and ℓ 1 balls of radii δ 1 and δ 2 . We then follow the same steps as in Section 5.1. Let

which is a special case of (5.2) with F ≡ 0. It is immediate to check that our assumptions (A.1)-(A.8) hold. Indeed, all functions are in Γ 0 (H p ) and F ≡ 0, and thus (A.1) and (A.2) are verified.

1 which is a non-mepty convex compact set. We also have ΩC ⊂ dom(∂G) = R p × R p , and for any

∞ and thus (A.4) is verified. (A.5) also holds with L h = 0. V is closed as we are in finite dimension, and thus (A.7) is fulfilled. We also have, since dom(G

), which shows that (A.8) is verified. The latter is nothing but the condition in [START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF]Fact 15.25(i)]. It then follows from the discussion in Remark 3.1(iv) that (A.6) holds true.

We use Algorithm 1 by choosing the sequence of parameters

, and ρ k ≡ 15, which verify all our assumptions (P.1)-(P.7) in view of Example 3.4. Our choice of γ k is the most common in the literature, and it can be improved according to our discussion in the previous section.

Finding the direction S k by solving the linear minimization oracle is a separable problem, and thus each component is given by, S

, S (1) , S

k ∈ Argmin

k -X

, S (2) .

Because of the structure of the sets B δ 1

, finding the first component of S k reduces to computing the leading right and left singular vectors of

k -X

(2) k while finding the second component reduces to computing the largest entry of

over all the entries (i, j). The dual variable update is given by,

k+1 -X

(1) k+1

GFB

  ∈ H p , Q (W ) = ΩW (1) y 1 + ι B δ 1 3) . Then we reformulate problem (7.2) as