A Projected Variable Smoothing for Weakly Convex Optimization and Supremum Functions Sergio López-Rivera, Pedro Pérez-Aros and Emilio Vilches Abstract In this paper, we address two main topics. First, we study the problem of minimizing the sum of a smooth function and the composition of a weakly convex function with a linear operator on a closed vector subspace. For this problem, we propose a projected variable smoothing algorithm and establish a complexity bound of 𝒪 ⁡ ( ϵ − 3 ) \mathcal{O}(\epsilon^{-3}) to achieve an ϵ \epsilon -approximate solution. Second, we investigate the Moreau envelope and the proximity operator of functions defined as the supremum of weakly convex functions, and we compute the proximity operator in two important cases. In addition, we apply the proposed algorithm for solving a distributionally robust optimization problem, the LASSO with linear constraints, and the max dispersion problem. We illustrate numerical results for the max dispersion problem. ∎ MSC 90C26 49J52 65K05 1 Introduction In this paper, we consider the following problem \min_{x\in V}h(x)+g(Ax), (1) where V\subset\mathcal{H} is a closed vector subspace of a real Hilbert space \mathcal{H} , h\colon\mathcal{H}\rightarrow\mathbb{R} is a differentiable function with a Lipschitz gradient, g is weakly convex and lower semicontinuous, and A is a nonzero bounded linear operator from \mathcal{H} to a real Hilbert space \mathcal{G} . Whenever V=\mathcal{H} , the problem has been studied in bohm2021variable . When g is convex, it has been analyzed in MR4534446 . Additionally, if A=\operatorname{Id} , the problem can be solved using the algorithm proposed in briceno2015forward . If V=\mathcal{H} , we can also apply the method proposed in condat2013primal in the convex case. The class of weakly convex functions is a generalization of the class of convex functions and there are several classes of functions that are weakly convex. For example, every continuously differentiable piecewise quadratic function defined from \mathbb{R}^{n} to \mathbb{R} is weakly convex. Another example is the composition of a convex Lipschitz continuous function and a smooth function with Lipschitz gradient. We refer to MR4359983 for more details about this important class of functions. One of the problems of the form ( 1 ) is the constrained LASSO problem tibshirani2011solution that combines sparse minimization and least squares under linear constraints. Also, problem ( 1 ) appears in PDEs ( MR570823 , Section 3) , signal and image processing Aujol2006 ; MR1440119 , stochastic traffic theory MR3703499 , among other fields. In the previous applications, the vector subspace constraint models intrinsic properties of the solution as non-anticipativity in stochastic problems. We are interested in the case when the function g is a supremum function. The supremum function arises in several optimization problems MR4361979 ; sun2021robust ; MR4362585 . An important problem that involves the supremum function is the called Distributionally Robust Optimization (DRO) problem, which assumes that the true probability distribution belongs to a set of distributions called the ambiguity set . Optimization is then performed based on the worst-case scenario within this ambiguity set. The DRO model covers the Robust Optimization problem when the ambiguity set includes all possible distributions, and Stochastic Optimization when the ambiguity set consists of a single probability distribution. Another application which appears a weakly convex supremum function is the max dispersion problem (or max-min location problem) jeyakumar2018exact . The proposed algorithm for solving ( 1 ) is a generalization of the algorithm proposed in bohm2021variable and includes a projection onto the vector subspace. In the proposed method we need to compute the proximity operator of the function g . To do this, we generalize ( MR4279933 , Theorem 3.5) , which allows calculating the proximity operator of the supremum of convex functions. The remainder of the paper is organized as follows. In Sect. 2 , we introduce the notation and the basic definitions. Sections 3 and 4 describes the proposed algorithm and its convergence properties. As in bohm2021variable , the convergence of the algorithm is obtained under the hypothesis of that g is Lipschitz. We prove that if the sequence generated by the algorithm is bounded, then we can eliminate such hypothesis to obtain convergence. In Sect. 5 , we prove that, in the context of weakly convex functions, the Moreau envelope of a supremum function is the supremum of Moreau envelopes. As a consequence of this result, we investigate the proximity operator of the supremum of weakly convex functions, and we compute the proximity operator in two important cases. In Sect. 6 , we use the results proved in the previous sections for solving several applications including the DRO problem, the LASSO with linear constraints, and the max dispersion problem. We illustrate numerical results for the max dispersion problem in Section 7 . Finally, we mention some conclusions in Section 8 . 2 Preliminaries Let \mathcal{H} be a real Hilbert space with inner product \langle\cdot,\cdot\rangle and induced norm \|\cdot\| . We denote by \Gamma_{0}(\mathcal{H}) the set of extended valued functions oh \mathcal{H} that are proper, convex, and lower semicontinuous. Moreover, for \rho\geq 0 , we denote by \Gamma_{\rho}(\mathcal{H}) the set of functions g such that g+\frac{\rho}{2}\|\cdot\|^{2}\in\Gamma_{0}(\mathcal{H}) . We say that a function is weakly convex if the function belongs to \Gamma_{\rho}(\mathcal{H}) for some \rho\geq 0 . For \mu>0 , the Moreau envelope of an extended valued function f is defined by f_{\mu}(x):=\inf_{y\in\mathcal{H}}\,f(y)+\frac{1}{2\mu}\|x-y\|^{2}. If f\in\Gamma_{\rho}(\mathcal{H}) and \mu<1/\rho , the above infimum is attained at a unique point and defines the so-called proximity operator x\mapsto\operatorname{prox}_{\mu f}(x) (see, e.g., ( MR1230710 , Theorem 3.4) ). For a closed set \mathcal{Q}\subset\mathcal{H} , the distance function and the projection mapping are defined as follows: d(x,\mathcal{Q}):=\inf_{y\in\mathcal{Q}}\|x-y\|\textrm{ and }P_{\mathcal{Q}}(x)=\operatorname{argmin}_{y\in\mathcal{Q}}\|x-y\|. The subdifferential of a weakly convex function f (see, e.g., MR1230710 ) is defined by \partial f(x)=\partial(f+\frac{\rho}{2}\|\cdot\|^{2})(x)-\rho x\textrm{ for }x\in\mathcal{H}, where \rho\geq 0 is chosen such that f+\frac{\rho}{2}\in\Gamma_{0}(\mathcal{H}) , and the subdifferential on the right-hand side is understood in the sense of convex analysis. In this paper, we consider the problem \displaystyle\min_{x\in V}h(x)+g(Ax), (2) where V\subset\mathcal{H} is a closed vector subspace, h\colon\mathcal{H}\rightarrow\mathbb{R} is a differentiable function with a Lipschitz gradient of constant L_{\nabla h} , g\in\Gamma_{\rho}(\mathcal{H}) for some \rho\geq 0 , and A is a nonzero bounded linear operator from \mathcal{H} to a real Hilbert space \mathcal{G} . We say that x^{*}\in\mathcal{H} is a critical point of ( 2 ) if 0\in\nabla h(x^{*})+A^{*}\partial g(Ax^{*})+N_{V}(x^{*}). In the line of bohm2021variable , for every k\geq 1 , we consider the following regularized problem \displaystyle\min_{x\in V}F_{k}(x):=h(x)+g_{\mu_{k}}(Ax), (3) where \mu_{k}>0 and 2\rho\mu_{k}\leq 1 . By ( bohm2021variable , Lemma 3.1) , \nabla F_{k} is Lipschitz with constant \displaystyle L_{k}:=L_{\nabla h}+\dfrac{\|A\|^{2}}{\mu_{k}}, (4) where L_{\nabla h} is the Lipschitz constant of \nabla h . Note that x is a critical point of ( 3 ) if and only if \displaystyle 0\in\nabla F_{k}(x)+N_{V}(x)\,\Leftrightarrow\,x=P_{V}(x-\gamma\nabla F_{k}(x))\textrm{ for all }\gamma>0, which motivates us to use the algorithm: x_{k+1}=P_{V}(x_{k}-\gamma_{k}\nabla F_{k}(x_{k})) . 3 Algorithm Projected Variable Smoothing We propose the following algorithm. Algorithm 1 Projected Variable Smoothing x_{1}\in V , \alpha\in\left]0,1\right[ , and C>0 such that 2\rho C\leq 1 . for k=1,2,\ldots do Set \mu_{k}\leftarrow Ck^{-\alpha} , set L_{k} as in ( 4 ), set \gamma_{k}\leftarrow 1/L_{k} . x_{k+1}\leftarrow P_{V}(x_{k}-\gamma_{k}\nabla F_{k}(x_{k})) . end for In what follows, we assume that the sequence (F_{k}(x_{k})) is bounded from below by F^{*} . We have the following convergence result, which, for \alpha=1/3 , C=(2\rho)^{-1} , and V=\mathcal{H} recovers ( bohm2021variable , Theorem 4.1) . It is worth emphasizing that by controlling \alpha , we can balance the trade-off between satisfying the optimality condition and the convergence of the algorithm. Theorem 3.1 In the context of problem ( 2 ), assume that g is L_{g} -Lipschitz. Then, the sequence defined by Algorithm 1 satisfies \displaystyle\min_{1\leq j\leq k}d(-\nabla h(x_{j}),A^{*}\partial g(\operatorname{prox}_{\mu_{j}g}(Ax_{j}))+N_{V}(x_{j})) \displaystyle\leq k^{\frac{\alpha-1}{2}}\widetilde{C}\,\textrm{ for all }k\geq 1, \displaystyle\|Ax_{k}-\operatorname{prox}_{\mu_{k}g}(Ax_{k})\| \displaystyle\leq k^{-\alpha}CL_{g}\,\textrm{ for all }k\geq 1, where \widetilde{C}:=\dfrac{\sqrt{2}\sqrt{L_{\nabla h}+C^{-1}\|A\|^{2}}}{\sqrt{2^{1-\alpha}-1}}\sqrt{F_{1}(x_{1})-F^{*}+CL_{g}^{2}} . Proof By the descent lemma (see, e.g., ( MR3719240 , Lemma 5.7) ), for all k\geq 1 \displaystyle F_{k}(x_{k+1})\leq F_{k}(x_{k})+\langle\nabla F_{k}(x_{k}),x_{k+1}-x_{k}\rangle+\dfrac{1}{2\gamma_{k}}\|x_{k+1}-x_{k}\|^{2}. Using that P_{V} is linear, x_{k}\in V , and that \langle x,P_{V}y\rangle=\langle P_{V}x,P_{V}y\rangle , we have \langle\nabla F_{k}(x_{k}),x_{k+1}-x_{k}\rangle=\langle\nabla F_{k}(x_{k}),-P_{V}\gamma_{k}\nabla F_{k}(x_{k})\rangle=-\gamma_{k}\|P_{V}\nabla F_{k}(x_{k})\|^{2}. Thus, since \|x_{k+1}-x_{k}\|^{2}=\gamma_{k}^{2}\|P_{V}\nabla F_{k}(x_{k})\|^{2} , we get that \displaystyle F_{k}(x_{k+1})\leq F_{k}(x_{k})-\dfrac{\gamma_{k}}{2}\|P_{V}\nabla F_{k}(x_{k})\|^{2}. (5) By ( bohm2021variable , Lemma 4.1) , we have that \hskip-0.02843ptF_{k+1}(x_{k+1})\leq F_{k}(x_{k+1})+\dfrac{1}{2}(\mu_{k}-\mu_{k+1})\dfrac{\mu_{k}}{\mu_{k+1}}L_{g}^{2}\leq F_{k}(x_{k+1})+(\mu_{k}-\mu_{k+1})L_{g}^{2}, where we have used that \mu_{k}\leq 2^{\alpha}\mu_{k+1}\leq 2\mu_{k+1} . Hence, we obtain that F_{k+1}(x_{k+1})\leq F_{k}(x_{k})-\dfrac{\gamma_{k}}{2}\|P_{V}\nabla F_{k}(x_{k})\|^{2}+(\mu_{k}-\mu_{k+1})L_{g}^{2}. By summing these inequalities from k=1 to K , we obtain \displaystyle\sum_{k=1}^{K}\dfrac{\gamma_{k}}{2}\|P_{V}\nabla F_{k}(x_{k})\|^{2} \displaystyle\leq F_{1}(x_{1})-F_{K+1}(x_{K+1})+(\mu_{1}-\mu_{K+1})L_{g}^{2} (6) \displaystyle\leq F_{1}(x_{1})-F^{*}+\mu_{1}L_{g}^{2}. On the one hand, we observe that \displaystyle\gamma_{k}=\frac{\mu_{k}}{\mu_{k}L_{\nabla h}+\|A\|^{2}}\geq k^{-\alpha}\frac{C}{CL_{\nabla h}+\|A\|^{2}}=k^{-\alpha}\dfrac{1}{L_{\nabla h}+C^{-1}\|A\|^{2}}. (7) On the other hand, \displaystyle\sum_{k=1}^{K}k^{-\alpha}\geq\int_{1}^{K+1}x^{-\alpha}dx\geq(K+1)^{1-\alpha}-1\geq(2^{1-\alpha}-1)K^{1-\alpha}, where we have used Lemma 4 . Hence, \displaystyle\min_{1\leq j\leq K}\|P_{V}\nabla F_{j}(x_{j})\|^{2}\leq\dfrac{2(L_{\nabla h}+C^{-1}\|A\|^{2})}{(2^{1-\alpha}-1)K^{1-\alpha}}\left(F_{1}(x_{1})-F^{*}+CL_{g}^{2}\right). (8) Now, N_{V}(x)=V^{\perp} for all x\in V . Then, for all z\in\mathcal{H} and x\in V , we have that \displaystyle d(-z,N_{V}(x))=d(-z,V^{\perp})\leq\|-z-(-z+P_{V}z)\|=\|P_{V}z\|. (9) By ( bohm2021variable , Lemma 3.2) , we have that \nabla(g_{\mu_{j}}\circ A)(x_{j})=A^{*}\nabla g_{\mu_{j}}(Ax_{j})\in A^{*}\partial g(\operatorname{prox}_{\mu_{j}g}(Ax_{j})). Thus, taking z=\nabla F_{j}(x_{j})=\nabla h(x_{j})+\nabla(g_{\mu_{j}}\circ A)(x_{j}) in ( 9 ), we obtain that \displaystyle d(-\nabla h(x_{j}),A^{*}\partial g(\operatorname{prox}_{\mu_{j}g}(Ax_{j}))+N_{V}(x_{j}))\leq\|P_{V}\nabla F_{j}(x_{j})\|, (10) which, by virtue of ( 8 ), implies the first inequality. The second inequality follows from ( bohm2021variable , Lemma 3.3) . ∎ Remark 1 The proposed algorithm can be easily adapted to the case of a closed affine subspace. Indeed, if V is a closed affine subspace, that is, V=W+z_{0} , where W is a closed vector subspace and z_{0}\in\mathcal{H} , then problem ( 2 ) is equivalent to \min_{x\in W}h(x+z_{0})+g(y+Az_{0}) . The assumptions on the data hold, and \operatorname{prox}_{\mu g(\cdot+Az_{0})}(y)=\operatorname{prox}_{\mu g}(y+Az_{0})-Az_{0} . The hypothesis that the function g is Lipschitz in Theorem 3.1 may be too restrictive. For example, if g is of the form g(x)=-\|x\|^{2} , then such a hypothesis does not hold. In what follows, we prove that if the sequence generated by the Algorithm 1 is bounded and \mathcal{G}=\mathbb{R}^{m} , then a similar result to the Theorem 3.1 holds without requiring g to be Lipschitz. Theorem 3.2 In the context of problem ( 2 ), assume that \mathcal{G}=\mathbb{R}^{m} , and the sequence (x_{k}) generated by the Algorithm 1 is bounded. Then, there exist \ell\geq 0 and N\geq 1 such that \displaystyle\min_{N\leq j\leq k}d(-\nabla h(x_{j}),A^{*}\partial g(\operatorname{prox}_{\mu_{j}g}(Ax_{j}))+N_{V}(x_{j})) \displaystyle\leq k^{\frac{\alpha-1}{2}}\widetilde{C}\textrm{ for all }k\geq N, \displaystyle\|Ax_{k}-\operatorname{prox}_{\mu_{k}g}(Ax_{k})\| \displaystyle\leq k^{-\alpha}C\ell\textrm{ for all }k\geq N, where \widetilde{C}=\frac{\sqrt{2}\sqrt{L_{\nabla h}+C^{-1}\|A\|^{2}}}{\sqrt{\left(1+1/N\right)^{1-\alpha}-1}}\sqrt{F_{N}(x_{N})-F^{*}+\mu_{N}\ell^{2}} . Proof Since (x_{j}) is bounded, there exists m\geq 0 such that \|x_{j}\|\leq m for all j\geq 1 . Define S=\|A\|m\mathbb{B} . Then, by Proposition 5 , there exist \ell\geq 0 and \mu_{0}\in\left]0,1\right[ such that for all \mu\in\left]0,\mu_{0}\right[ and y\in S , \displaystyle\|\nabla g_{\mu}(y)\|=\dfrac{1}{\mu}\|y-\operatorname{prox}_{\mu g}(y)\|\leq\ell. (11) Let N\geq 1 such that \mu_{k}<\mu_{0} and \left(1+1/N\right)^{1-\alpha}-1<1/2 for all k\geq N . By ( bohm2021variable , Lemma 4.1) , the fact that \{Ax_{k}\}\subset S , and ( 11 ), we have that for all k\geq N \displaystyle F_{k+1}(x_{k+1}) \displaystyle\leq F_{k}(x_{k+1})+\dfrac{1}{2}(\mu_{k}-\mu_{k+1})\dfrac{\mu_{k}}{\mu_{k+1}}\|\nabla g_{\mu_{k}}(Ax_{k+1})\|^{2} \displaystyle\leq F_{k}(x_{k+1})+\dfrac{1}{2}(\mu_{k}-\mu_{k+1})\dfrac{\mu_{k}}{\mu_{k+1}}\ell^{2} \displaystyle\leq F_{k}(x_{k+1})+(\mu_{k}-\mu_{k+1})\ell^{2}, where we have used that \mu_{k}\leq 2^{\alpha}\mu_{k+1}\leq 2\mu_{k+1} . Thus, from ( 5 ), for all k\geq N , \displaystyle F_{k+1}(x_{k+1})\leq F_{k}(x_{k})-\dfrac{\gamma_{k}}{2}\|P_{V}\nabla F_{k}(x_{k})\|^{2}+(\mu_{k}-\mu_{k+1})\ell^{2}. By summing both sides of the last inequality from k=N to k=K , we obtain \displaystyle\sum_{k=N}^{K}\dfrac{\gamma_{k}}{2}\|P_{V}\nabla F_{k}(x_{k})\|^{2} \displaystyle\leq F_{N}(x_{N})-F_{K+1}(x_{K+1})+(\mu_{N}-\mu_{K+1})\ell^{2} (12) \displaystyle\leq F_{N}(x_{N})-F^{*}+\mu_{N}\ell^{2}. Now, note that \displaystyle\sum_{k=N}^{K}k^{-\alpha}\geq\int_{N}^{K+1}x^{-\alpha}dx\geq(K+1)^{1-\alpha}-N^{1-\alpha}. (13) Setting \theta:=\left(1+1/N\right)^{1-\alpha}-1 , from Lemma 5 , ( 7 ), ( 12 ), and ( 13 ), we get \displaystyle\min_{N\leq j\leq K}\|P_{V}\nabla F_{j}(x_{j})\|^{2}\leq\frac{1}{\theta K^{1-\alpha}}(2(L_{\nabla h}+C^{-1}\|A\|^{2})(F_{N}(x_{N})-F^{*}+\mu_{N}\ell^{2})), which implies the first inequality. The second inequality follows from ( 11 ). ∎ 4 Variable smoothing with epochs We observe that in Theorem 3.1 , the first bound states that during the first k=O(\epsilon^{-\frac{2}{1-\alpha}}) iterations, there exists an iteration j at which the optimality condition holds within a tolerance of \epsilon . Nevertheless, this bound could have been satisfied at an earlier iteration, that is, for some j\ll\epsilon^{-\frac{2}{1-\alpha}} . Consequently, the value of the second bound on \|Ax_{j}-\operatorname{prox}_{\mu_{j}g}(Ax_{j})\| may not be particularly small. This drawback is addressed by the following variant of Algorithm 1 ,inspired by bohm2021variable , where the steps are organized into a series of epochs, each of which is twice as long as the previous one. Algorithm 2 Projected variable smoothing with epochs x_{1}\in V , \alpha\in\left]0,1\right[ , C>0 such that 2\rho C\leq 1 , and tolerance \epsilon>0 . for l=0,1,\ldots do Set S_{l}\leftarrow\infty and j_{l}\leftarrow 2^{l} for k=2^{l},2^{l}+1,\ldots,2^{l+1}-1 do Set \mu_{k}\leftarrow Ck^{-\alpha} , set L_{k} as in ( 4 ), set \gamma_{k}\leftarrow 1/L_{k} . x_{k+1}\leftarrow P_{V}(x_{k}-\gamma_{k}\nabla F_{k}(x_{k})) if \|\nabla F_{k+1}(x_{k+1})\|\leq S_{l} then S_{l}\leftarrow\|\nabla F_{k+1}(x_{k+1})\| and j_{l}\leftarrow k+1 if S_{l}\leq\epsilon and \|Ax_{k+1}-\operatorname{prox}_{\mu_{k+1}g}(Ax_{k+1})\|\leq\epsilon^{\frac{2\alpha}{1-\alpha}} then STOP end if end if end for end for The next result recovers ( bohm2021variable , Theorem 4.2) for \alpha=1/3 , C=(2\rho)^{-1} , and V=\mathcal{H} . Theorem 4.1 In the context of problem ( 2 ), assume that g is L_{g} -Lipschitz. Then, given a tolerance \epsilon>0 , Algorithm 2 generates an iterate x_{j} for some j=O(\epsilon^{-\frac{2}{1-\alpha}}) such that \|Ax_{j}-\operatorname{prox}_{\mu_{j}g}(Ax_{j})\|\leq\epsilon^{\frac{2\alpha}{1-\alpha}} and d(-\nabla h(x_{j}),A^{*}\partial g(\operatorname{prox}_{\mu_{j}g}(Ax_{j}))+N_{V}(x_{j}))\leq\epsilon. Proof By ( 6 ), we deduce that \displaystyle\sum_{k=2^{l}}^{2^{l+1}-1}\frac{\gamma_{k}}{2}\|P_{V}\nabla F_{k}(x_{k})\|^{2}\leq F_{1}(x_{1})-F^{*}+CL_{g}^{2}. Now, note that \displaystyle\sum_{k=2^{l}}^{2^{l+1}-1}k^{-\alpha}\geq\int_{2^{l}}^{2^{l+1}}x^{-\alpha}dx=\frac{1}{1-\alpha}(2^{1-\alpha}-1)(2^{l})^{1-\alpha}. Then, from ( 7 ), we obtain that \displaystyle\min_{2^{l}\leq j\leq 2^{l+1}-1}\|P_{V}\nabla F_{j}(x_{j})\|\leq\widetilde{C}(2^{l})^{\frac{\alpha-1}{2}}, where \widetilde{C}=\sqrt{\frac{2(1-\alpha)}{2^{1-\alpha}-1}}\sqrt{L_{\nabla h}+C^{-1}\|A\|^{2}}\sqrt{F_{1}(x_{1})-F^{*}+CL_{g}^{2}} . Thus, by ( 10 ), we conclude that \displaystyle\min_{2^{l}\leq j\leq 2^{l+1}-1}d(-\nabla h(x_{j}),A^{*}\partial g(z_{j})+N_{V}(x_{j}))\leq\widetilde{C}(2^{l})^{\frac{\alpha-1}{2}}, (14) where z_{j}=\operatorname{prox}_{\mu_{j}g}(Ax_{j}) . Moreover, for 2^{l}\leq j\leq 2^{l+1}-1 , we have from ( bohm2021variable , Lemma 3.3) that \displaystyle\|Ax_{j}-z_{j}\|\leq\mu_{j}L_{g}=Cj^{-\alpha}L_{g}\leq C(2^{l})^{-\alpha}L_{g}. (15) From ( 14 ) and ( 15 ), it follows that Algorithm 2 must stop before the end of epoch l , that is, before 2^{l+1} iterations have been completed, where l is the first nonnegative number such that \widetilde{C}(2^{l})^{\frac{\alpha-1}{2}}\leq\epsilon and C(2^{l})^{-\alpha}L_{g}\leq\epsilon^{\frac{2\alpha}{1-\alpha}} , which are equivalent to \widetilde{C}^{\frac{2}{1-\alpha}}\epsilon^{-\frac{2}{1-\alpha}}\leq 2^{l} and C^{1/\alpha}L_{g}^{1/\alpha}\epsilon^{-\frac{2}{1-\alpha}}\leq 2^{l} . Hence, the algorithm terminates after at most 2\max\{\widetilde{C}^{\frac{2}{1-\alpha}},C^{1/\alpha}L_{g}^{1/\alpha}\}\epsilon^{-\frac{2}{1-\alpha}} iterations. ∎ 5 Supremum of weakly convex functions Supremum functions play a prominent role in optimization. They models several phenomena, ranging from stochastic optimization to equilibrium problems. However, they are usually nonsmooth; hence, their optimization presents significant challenges from both a theoretical and numerical perspective. In this section, we extend the analysis from MR4279933 . Hence, we study the Moreau envelope and the proximity operator of the supremum function: \displaystyle f(x)=\sup_{c\in\mathcal{C}}f_{c}(x)\quad\text{for all }x\in\mathcal{H}, (16) where \mathcal{H} is a real Hilbert space, \mathcal{C}\neq\emptyset is a convex subset of some topological vector space and f_{c}\in\Gamma_{\rho_{c}}(\mathcal{H}) with \rho_{c}\geq 0 for all c\in\mathcal{C} . Lemma 1 Let (f_{c})_{c\in\mathcal{C}} be a family of functions such that f_{c}\in\Gamma_{\rho_{c}}(\mathcal{H}) for all c\in\mathcal{C} . Assume that f:=\sup_{c\in\mathcal{C}}f_{c} is proper and that \bar{\rho}:=\sup_{c\in\mathcal{C}}\rho_{c}<+\infty . Then, f\in\Gamma_{\bar{\rho}}(\mathcal{H}) . More precisely, \displaystyle h:=f+\frac{\bar{\rho}}{2}\|\cdot\|^{2}\in\Gamma_{0}(\mathcal{H})\textrm{ and }r_{c}:=f_{c}+\frac{\bar{\rho}}{2}\|\cdot\|^{2}\in\Gamma_{0}(\mathcal{H})\textrm{ for all }c\in\mathcal{C}. (17) Proof It is clear that h_{c}:=f_{c}+\dfrac{\rho_{c}}{2}\|\cdot\|^{2}\in\Gamma_{0}(\mathcal{H}) for all c\in\mathcal{C} . Moreover, \displaystyle h:=f+\frac{\bar{\rho}}{2}\|\cdot\|^{2}=\sup_{c\in\mathcal{C}}f_{c}+\frac{\bar{\rho}}{2}\|\cdot\|^{2}=\sup_{c\in\mathcal{C}}(h_{c}+\frac{(\bar{\rho}-\rho_{c})}{2}\|\cdot\|^{2}). (18) Since h_{c} belong to \Gamma_{0}(\mathcal{H}) , and \bar{\rho}-\rho_{c}\geq 0 for all c\in\mathcal{C} , we obtain that r_{c}:=h_{c}+\frac{(\bar{\rho}-\rho_{c})}{2}\|\cdot\|^{2}=f_{c}+\frac{\bar{\rho}}{2}\|\cdot\|^{2} belongs to \Gamma_{0}(\mathcal{H}) for all c\in\mathcal{C} . Since \sup_{c\in\mathcal{C}}f_{c} is proper, we get that h=\sup_{c\in\mathcal{C}}r_{c}\in\Gamma_{0}(\mathcal{H}) . Hence, by ( 18 ), f\in\Gamma_{\bar{\rho}}(\mathcal{H}) . ∎ The next result provides a formula for the Moreau envelope of the supremum function in ( 16 ) as the supremum of the Moreau envelope of the data functions f_{c} . Whenever the data functions are convex, it recovers ( MR4279933 , Theorem 3.1) . Theorem 5.1 Let \mathcal{C}\neq\emptyset be a convex set and (f_{c})_{c\in\mathcal{C}} a family of functions such that f_{c}\in\Gamma_{\rho_{c}}(\mathcal{H}) for all c\in\mathcal{C} . Assume that f=\sup_{c\in\mathcal{C}}f_{c} is proper, \bar{\rho}:=\sup_{c\in\mathcal{C}}\rho_{c}<+\infty , and that c\mapsto f_{c}(x) is concave for all x\in\mathcal{H} . Then, for all \mu\in\left]0,1/\bar{\rho}\right[ , we have \displaystyle f_{\mu}(x)=\sup_{c\in\mathcal{C}}(f_{c})_{\mu}(x)\quad\text{for all }x\in\mathcal{H}. (19) Moreover, if \mathcal{C} is compact and the function c\mapsto f_{c}(x) is upper semicontinuous for all x\in\mathcal{H} , then the supremum in ( 19 ) is attained. Proof Let \mu\in]0,1/\bar{\rho}[ and x\in\mathcal{H} . By Lemma 1 , we have that f\in\Gamma_{\bar{\rho}}(\mathcal{H}) and h=\sup_{c\in\mathcal{C}}r_{c} , where h and the functions r_{c} are defined by ( 17 ). Thus, from ( 17 ), ( MR1230710 , Theorem 3.4(b)) , and ( MR4279933 , Theorem 3.1) , it follows that \displaystyle f_{\mu}(x) \displaystyle=-\frac{1}{2}\bar{\rho}(1-\mu\bar{\rho})^{-1}\|x\|^{2}+h_{\frac{\mu}{1-\mu\bar{\rho}}}((1-\mu\bar{\rho})^{-1}x) \displaystyle=\sup_{c\in\mathcal{C}}-\frac{1}{2}\bar{\rho}(1-\mu\bar{\rho})^{-1}\|x\|^{2}+(r_{c})_{\frac{\mu}{1-\mu\bar{\rho}}}((1-\mu\bar{\rho})^{-1}x) \displaystyle=\sup_{c\in\mathcal{C}}(f_{c})_{\mu}(x). Now, suppose that \mathcal{C} is compact and the function c\mapsto f_{c}(x) is upper semicontinuous for all x\in\mathcal{H} . Then for every x\in\mathcal{H} the function c\mapsto(f_{c})_{\mu}(x) is upper semicontinuous since it is the infimum of upper semicontinuous functions. Thus, the supremum in ( 19 ) is attained. ∎ The next result is a generalization of ( MR4279933 , Theorem 3.5) and provide a formula for the gradient of the Moreau envelope and the proximity operator of ( 16 ). Given \mu>0 , f=\sup_{c\in\mathcal{C}}f_{c} , and x\in\mathcal{H} , we define the following set \displaystyle\mathcal{C}_{\mu}^{f}(x):=\left\{c\in\mathcal{C}:f_{\mu}(x)=(f_{c})_{\mu}(x)\right\}. Theorem 5.2 Let \mathcal{C}\neq\emptyset be a compact convex set and (f_{c})_{c\in\mathcal{C}} be a family of functions such that f_{c}\in\Gamma_{\rho_{c}}(\mathcal{H}) for all c\in\mathcal{C} . Suppose that f=\sup_{c\in\mathcal{C}}f_{c} is proper, \bar{\rho}:=\sup_{c\in\mathcal{C}}\rho_{c}<+\infty , and that c\mapsto f_{c}(x) is concave and u.s.c. for all x\in\mathcal{H} . Then, for all \mu\in]0,1/\bar{\rho}[ and x\in\mathcal{H} , the set \mathcal{C}_{\mu}^{f}(x) is nonempty, \operatorname{prox}_{\mu f}(x)=\operatorname{prox}_{\mu f_{c}}(x),\textrm{ and }\nabla f_{\mu}(x)=\frac{x-\operatorname{prox}_{\mu f_{c}}(x)}{\mu}\quad\text{for all }c\in\mathcal{C}_{\mu}^{f}(x). Proof Let \mu\in]0,1/\bar{\rho}[ and x\in\mathcal{H} . First, by Theorem 5.1 , the set \mathcal{C}_{\mu}^{f}(x) is nonempty. Thus, by Lemma 1 and ( MR1230710 , Theorem 3.4(d)) , f_{\mu}\in C^{1,1} and \nabla f_{\mu}(x)=\frac{1}{\mu}(x-\operatorname{prox}_{(\frac{\mu}{1-\mu\bar{\rho}})h}((1-\mu\bar{\rho})^{-1}x))\text{ for all }x\in\mathcal{H}, where h is defined by ( 17 ). Now, since the function c\mapsto r_{c}(x) is concave and u.s.c. for all x\in\mathcal{H} , \mathcal{C} is compact, and h=\sup_{c\in\mathcal{C}}r_{c} , then from ( MR4279933 , Theorem 3.5) , it follows that for all c\in\mathcal{C}_{\frac{\mu}{1-\mu\bar{\rho}}}^{h}((1-\mu\bar{\rho})^{-1}x) \displaystyle\operatorname{prox}_{(\frac{\mu}{1-\mu\bar{\rho}})h}((1-\mu\bar{\rho})^{-1}x) \displaystyle=\operatorname{prox}_{(\frac{\mu}{1-\mu\bar{\rho}})r_{c}}((1-\mu\bar{\rho})^{-1}x), which yields from ( MR1230710 , Theorem 3.4(d)) and ( 17 ) that \displaystyle\nabla f_{\mu}(x)=\frac{1}{\mu}(x-\operatorname{prox}_{\mu f_{c}}(x))\quad\text{for all }c\in\mathcal{C}_{\frac{\mu}{1-\mu\bar{\rho}}}^{h}((1-\mu\bar{\rho})^{-1}x). Since r_{c}=f_{c}+\frac{\bar{\rho}}{2}\|\cdot\|^{2} and h=f+\frac{\bar{\rho}}{2}\|\cdot\|^{2} , we see from ( MR1230710 , Theorem 3.4(b)) that \mathcal{C}_{\frac{\mu}{1-\mu\bar{\rho}}}^{h}\left(\frac{x}{1-\mu\bar{\rho}}\right)=\mathcal{C}_{\mu}^{f}(x) . Finally, \nabla f_{\mu}(x)=\frac{1}{\lambda}(x-\operatorname{prox}_{\mu f}(x)) , whence \operatorname{prox}_{\mu f}(x)=\operatorname{prox}_{\mu f_{c}}(x) for all x\in\mathcal{H} and c\in\mathcal{C}_{\mu}^{f}(x) . ∎ In the following subsections, based on Theorem 5.2 , we compute the proximity of two particular supremum functions which are weakly convex. 5.1 Supremum functions of weakly convex with quadratic functions Consider the following function \displaystyle\mathbf{x}\in\mathcal{H}^{N}\mapsto f(\mathbf{x})=\sup_{p\in\Delta_{N}}-\sum_{i=1}^{N}p_{i}\|x_{i}-\xi_{i}\|^{2}=\max_{1\leq i\leq N}-\|x_{i}-\xi_{i}\|^{2}, (20) where \xi_{i}\in\mathcal{H} for all i\in\{1,\ldots,N\} . The function f in ( 20 ) appears in discrete versions of DRO problems where the ambiguity set is the the probability simplex \Delta_{N} , and the cost function is a weakly convex quadratic function. Proposition 1 Let \mathbf{x}\in\mathcal{H}^{N} and let \mu\in\left]0,1/2\right[ . Then, f is \rho -weakly convex with \rho=2 and \operatorname{prox}_{\mu f}(\mathbf{x})=\left(\dfrac{x_{i}-2\mu\bar{p}_{i}\xi_{i}}{1-2\mu\bar{p}_{i}}\right)_{i=1}^{N}, where \bar{p}\in\Delta_{N} is a solution to \displaystyle\max_{p\in\Delta_{N}}\phi(p):=\sum_{i=1}^{N}\left(\frac{p_{i}}{2\mu p_{i}-1}\right)\alpha_{i}\textrm{ and }\alpha_{i}=\|x_{i}-\xi_{i}\|^{2}\textrm{ for all }i\in\{1,\ldots,N\}. (21) Proof Define f_{i}(x):=-\|x-\xi_{i}\|^{2} for all i\in\{1,\ldots,N\} and \mathbf{x}\in\mathcal{H}^{N}\mapsto g_{p}(\mathbf{x})=\sum_{i=1}^{N}p_{i}f_{i}(x_{i}) for all p\in\Delta_{N} . We claim that g_{p} is weakly convex with parameter \rho=2 for all p\in\Delta_{N} . Note that \displaystyle\sum_{i=1}^{N}p_{i}f_{i}(x_{i})+\|\mathbf{x}\|^{2}=\sum_{i=1}^{N}p_{i}(f_{i}(x_{i})+\|x_{i}\|^{2})+\sum_{i=1}^{N}(1-p_{i})\|x_{i}\|^{2}. Then, since f_{i}+\|\cdot\|^{2} is convex and p_{i}\leq 1 for all i\in\{1,\ldots,N\} , g_{p}+\|\cdot\|^{2} is convex for all p\in\Delta_{N} . Thus, by Lemma 1 , f=\sup_{p\in\Delta_{N}}g_{p} is proper and \rho -weakly convex with \rho=2 . On the other hand, p\mapsto g_{p}(\mathbf{x}) is concave and u.s.c. for all \mathbf{x}\in\mathcal{H}^{N} . Thus, from Theorem 5.2 , for every \mu\in\left]0,1/2\right[ , \displaystyle\operatorname{prox}_{\mu f}(\mathbf{x})=\operatorname{prox}_{\mu g_{\bar{p}}}(\mathbf{x}),\quad\text{with }\bar{p}\in\operatorname{argmax}_{p\in\Delta_{N}}(g_{p})_{\mu}(\mathbf{x}). (22) Now, observe that for all i\in\{1,\ldots,N\} and x\in\mathcal{H} , y=\operatorname{prox}_{\mu(p_{i}f_{i})}(x) if and only if y=\frac{x-2\mu p_{i}\xi_{i}}{1-2\mu p_{i}} . Then, we have that \operatorname{prox}_{\mu g_{\bar{p}}}(\mathbf{x})=\left(\dfrac{x_{i}-2\mu\bar{p}_{i}\xi_{i}}{1-2\mu\bar{p}_{i}}\right)_{i=1}^{N}. Let us calculate (g_{p})_{\mu}(\mathbf{x}) . By the above formula, we obtain that (g_{p})_{\mu}(\mathbf{x})=g_{p}(\operatorname{prox}_{\mu g_{p}}(\mathbf{x}))+\frac{1}{2\mu}\|\mathbf{x}-\operatorname{prox}_{\mu g_{p}}(\mathbf{x})\|^{2}=\sum_{i=1}^{N}\left(\frac{p_{i}}{2\mu p_{i}-1}\right)\|x_{i}-\xi_{i}\|^{2}. Set \alpha_{i}=\|x_{i}-\xi_{i}\|^{2} for all i\in\{1,\ldots,N\} . Hence, in order to find \bar{p} in ( 22 ), we need to solve problem ( 21 ). Since \phi is continuous and \Delta_{N} is a nonempty compact set, problem ( 21 ) has solutions. ∎ In the context of problem ( 21 ), if \alpha_{i}=0 for some i\in\{1,\ldots,N\} , then a solution of problem ( 21 ) is p=e_{i} , where e_{i}\in\mathbb{R}^{N} is the canonical vector in \mathbb{R}^{N} . Then, we can assume that \alpha_{i}>0 for all i\in\{1,\ldots,N\} . We note that (\nabla^{2}\phi(p))_{ij}=\begin{cases}4\mu\alpha_{i}(2\mu p_{i}-1)^{-3}&\text{ if }i=j\\ 0&\text{ if }i\neq j\end{cases}\quad\text{for all }i,j\in\{1,\ldots,N\}. Then, \nabla^{2}(-\phi)(p) is a positive definite matrix for all p\in\Delta_{N} since \mu<1/2 . Thus -\phi is strictly convex on \Delta_{N} . In addition, \Delta_{N} is a compact convex set and -\phi is continuous. Therefore, the problem ( 21 ) has an unique solution. Now, we provide a solution of ( 21 ). The proof is given in Section A.3 . Proposition 2 In the context of ( 21 ), let \{\ell_{i}\}_{i=1}^{N} such that \alpha_{\ell_{1}}\geq\cdots\geq\alpha_{\ell_{N}} with \alpha_{i}>0 for all i\in\{1,\ldots,N\} and let I_{i}:=\{\ell_{1},\ldots,\ell_{i}\} for all i\in\{1,\ldots,N\} . Define \displaystyle k:=\min\{i\in\{0,\ldots,N-1\}:(N-i-2\mu)\sqrt{\alpha_{\ell_{i+1}}}<\sum_{j\notin I_{i}}\sqrt{\alpha_{j}}\}, (23) where I_{0}:=\emptyset . Then, \bar{p}\in\mathbb{R}^{N} defined by \displaystyle\bar{p}_{i}=\begin{cases}0&\text{if}\,\,i\in I_{k}\\ \dfrac{1}{2\mu}[1-\frac{(N-k-2\mu)\sqrt{\alpha_{i}}}{\sum_{j\notin I_{k}}\sqrt{\alpha_{j}}}]&\text{if}\,\,i\notin I_{k}\end{cases}\quad\text{ for all }i\in\{1,\ldots,N\} (24) is the solution to problem ( 21 ). 5.2 Supremum function weakly convex with affine functions Inspired in ( pmlr-v89-sun19b , Theorem 3) , we consider now the function \displaystyle x\in\mathbb{R}^{n}\mapsto f(x)=\sup_{c\in\mathcal{C}}\sum_{i=1}^{N}c_{i}(\langle a_{i},x\rangle+b_{i})-\sigma\|x\|^{2}, (25) where a_{i}\in\mathbb{R}^{n} , b_{i}\in\mathbb{R} , \sigma>0 , and \mathcal{C}\subset\Delta_{N} is a nonempty closed convex set. Clearly, f is \rho -weakly convex with \rho=2\sigma . Note that the function f appears in the discrete version of the DRO problem when the ambiguity set is the set \mathcal{C} and the cost function is weakly convex involving affine functions. The next result provides an algorithm for the proximity of the function f in ( 25 ). Proposition 3 Let x\in\mathbb{R}^{n} and \mu\in]0,\frac{1}{2\sigma}[ . Let A=\begin{bmatrix}a_{1}|\cdots|a_{N}\end{bmatrix}^{\top} , b=\begin{pmatrix}b_{1}\cdots b_{N}\end{pmatrix}^{\top} , and \gamma>0 such that \frac{\gamma\mu\|AA^{\top}\|}{1-2\sigma\mu}<1 . Let (\alpha_{k})\subset[0,1] such that \sum_{k\in\mathbb{N}}\alpha_{k}(1-\alpha_{k})=+\infty and let c^{0}\in\mathbb{R}^{N} . For every k\in\mathbb{N} , we consider y^{k}=\frac{1}{1-2\sigma\mu}(x-\mu A^{\top}c^{k}),z^{k}=c^{k}+\gamma(Ay^{k}+b),c^{k+1}=\alpha_{k}P_{\mathcal{C}}(z^{k})+(1-\alpha_{k})c^{k}. Then, y^{k}\rightarrow\operatorname{prox}_{\mu f}(x) . Proof For every c\in\mathcal{C} , consider f_{c}(x)=\sum_{i=1}^{N}c_{i}(\langle a_{i},x\rangle+b_{i})-\sigma\|x\|^{2} . It is clear that x\mapsto f_{c}(x) is weakly convex with parameter 2\sigma and that c\mapsto f_{c}(x) is concave and upper semicontinuous for all x\in\mathbb{R}^{n} . Moreover, it is clear that f=\sup_{c\in\mathcal{C}}f_{c} is proper. Thus, by Theorem 5.2 , we have that \displaystyle\operatorname{prox}_{\mu f}(x)=\operatorname{prox}_{\mu f_{\bar{c}}}(x)\quad\text{with }\bar{c}\in\operatorname{argmax}_{c\in\mathcal{C}}(f_{c})_{\mu}(x). (26) Moreover, for every c\in\mathcal{C} , y=\operatorname{prox}_{\mu f_{c}}(x) if and only if y=\frac{1}{1-2\sigma\mu}(x-\mu A^{\top}c) . In order to find \bar{c}\in\mathcal{C} in ( 26 ), we need to solve the following minimax problem \max_{c\in\mathcal{C}}(f_{c})_{\mu}(x)=\max_{c\in\mathcal{C}}\inf_{y\in\mathbb{R}^{n}}f_{c}(y)+\dfrac{1}{2\mu}\|y-x\|^{2}. The optimality condition of the above problem is Ay+b\in N_{\mathcal{C}}(c) and y=\operatorname{prox}_{\mu f_{c}}(x) . Hence, we need to find c\in\mathcal{C} such that c=P_{\mathcal{C}}(c+\gamma(Ay_{c}+b)) , where y_{c}=(1-2\sigma\mu)^{-1}(x-\mu A^{\top}c) . Then, by defining c\in\mathcal{C}\mapsto\mathcal{F}(c)=c+\gamma(Ay_{c}+b) , we conclude that \displaystyle c\in\operatorname{argmax}_{c\in\mathcal{C}}(f_{c})_{\mu}(x)\Leftrightarrow c=P_{\mathcal{C}}(\mathcal{F}(c)). (27) We claim that \mathcal{F} is nonexpansive. Indeed, let c_{1} and c_{2} in \mathcal{C} . Then \displaystyle\mathcal{F}(c_{1})-\mathcal{F}(c_{2}) \displaystyle=c_{1}-c_{2}-\dfrac{\gamma\mu AA^{\top}}{1-2\sigma\mu}(c_{1}-c_{2})=\left(I-\dfrac{\gamma\mu AA^{\top}}{1-2\sigma\mu}\right)(c_{1}-c_{2}). Let B:=\dfrac{\gamma\mu AA^{\top}}{1-2\sigma\mu} . It is easy to see that \|I-B\|_{2}\leq 1 . Define T=P_{\mathcal{C}}\circ\mathcal{F} . Then, since P_{\mathcal{C}} is nonexpansive, we obtain that T is nonexpansive. Hence, we deduce that c^{k+1}=\alpha_{k}Tc^{k}+(1-\alpha_{k})c^{k} . From ( MR3616647 , Theorem 5.15) , there exists \bar{c}\in\text{Fix}\,T such that c^{k}\rightarrow\bar{c} and y^{k}\rightarrow\operatorname{prox}_{\mu f_{\bar{c}}}(x) . Moreover, by ( 26 ) and ( 27 ), \operatorname{prox}_{\mu f_{\bar{c}}}(x)=\operatorname{prox}_{\mu f}(x) . Therefore, y^{k}\rightarrow\operatorname{prox}_{\mu f}(x) . ∎ 6 Applications 6.1 Distributionally Robust Optimization Let (\Omega,\mathcal{A}) be a measurable space, let \xi\colon\Omega\rightarrow\Xi\subset\mathbb{R}^{m} be a random vector with \Xi\subset\mathbb{R}^{m} being an uncertainty set, let \mathcal{P} be a nonempty closed convex subset of probability measures on (\Omega,\mathcal{A}) supported on \Xi (called ambiguity set ), let Q\subset\mathbb{R}^{n} be a compact convex set, and let F\colon\mathbb{R}^{n}\times\Xi\rightarrow\mathbb{R} be a measurable function. The problem \displaystyle\displaystyle\min_{x\in Q}\displaystyle\sup_{\mathbb{P}\in\mathcal{P}}\mathbb{E}_{\mathbb{P}}[F(x,\xi)]:=\int_{\Omega}F(x,\xi(\omega))d\mathbb{P}(\omega). (28) is called distributionally robust optimization (DRO) problem ( sun2021robust , eq 4.1.3) . The ambiguity set represents the information about the probability distributions. The problem ( 28 ) covers the stochastic optimization problem when the ambiguity set is a singleton, and the robust optimization problem when the ambiguity set includes all possible distributions. When \Xi is finite, that is, \Xi=\{\xi_{1},\ldots,\xi_{N}\} and denoting p_{i}=\mathbb{P}(\{\omega\in\Omega:\xi(\omega)=\xi_{i}\}) and f_{i}=F(\cdot,\xi_{i}) , for every \mathbb{P}\in\mathcal{P} and i\in\{1,\ldots,N\} , we have that the problem ( 28 ) reduces to \displaystyle\min_{x\in Q}\sup_{p\in\mathcal{P}}\sum_{i=1}^{N}p_{i}f_{i}(x), (29) where \mathcal{P}\subset\Delta_{N}:=\{p\in\mathbb{R}_{+}^{N}:\sum_{i=1}^{N}p_{i}=1\} . When Q=V\cap\mathcal{B} , where V is a closed vector subspace of \mathbb{R}^{n} and \mathcal{B} is a compact convex set, ( 29 ) reduces to \displaystyle\min_{x\in V\cap\mathcal{B}}\widetilde{g}(x), (30) where \widetilde{g}(x)=\sup_{p\in\mathcal{P}}\sum_{i=1}^{N}p_{i}f_{i}(x) . Note that if f_{i} is l.s.c. for all i\in\left\{1,\ldots,N\right\} , then \widetilde{g} is l.s.c.. Then, we can use the penalty method described in Section A.1 for solving ( 30 ). That is, we need to solve the penalized problem: \displaystyle\min_{x\in V}\lambda P(x)+\widetilde{g}(x), where \lambda>0 and P\colon\mathbb{R}^{n}\rightarrow\mathbb{R} is a l.s.c. function such that P(x)\geq 0 for all x\in\mathbb{R}^{n} and P(x)=0 if and only if x\in\mathcal{B} . When P(x)=\frac{1}{2}d^{2}(x,\mathcal{B}) , the penalized problem is equivalent to \displaystyle\min_{x\in V}h(x)+\widetilde{g}(x), (31) where h(x)=\frac{\lambda}{2}d^{2}(x,\mathcal{B}) . Then, \nabla h(x)=\lambda(x-P_{\mathcal{B}}(x)) and \nabla h is Lipschitz with constant \lambda . On the other hand, when f_{i}(x)=\langle a_{i},x\rangle+b_{i}-\sigma\|x\|^{2} , where a_{i}\in\mathbb{R}^{n} , b_{i}\in\mathbb{R} , and \sigma>0 , the proximity operator of \widetilde{g} can be calculated using the algorithm in Proposition 3 . Thus, ( 31 ) is a particular case of ( 2 ). When f_{i}(x)=\langle a_{i},x\rangle+b_{i}-\sigma\|x\|^{2} , it is straightforward to prove that the objective function in ( 31 ) is coercive if \lambda>2\sigma and hence, in this case, ( 31 ) has solutions for all \lambda>2\sigma . We consider now the following DRO model ( MR4361979 , Example 4) \min_{\mathbf{x}=(x_{1},\ldots,x_{N})\in\mathbb{R}^{nN}}\max_{p\in\mathcal{P}}\sum_{i=1}^{N}p_{i}f_{i}(x_{i})\quad\text{s.t.}\quad\mathbf{x}\in\mathcal{N}\cap\bigtimes_{i=1}^{N}Q_{i}, (32) where \mathcal{N}\subset\mathbb{R}^{nN} is the nonanticipative set (vector subspace), f_{i}\colon\mathbb{R}^{n}\rightarrow\mathbb{R} is the cost function in the scenario i , Q_{i} is a compact convex subset, and \mathcal{P}\subset\Delta_{N} is a nonempty closed convex ambiguity set. Note that ( 32 ) is equivalent to \displaystyle\min_{\mathbf{x}\in\mathcal{N}\cap\overline{Q}}g(\mathbf{x}), (33) where \overline{Q}=\bigtimes_{i=1}^{N}Q_{i} and g(\mathbf{x})=\sup_{p\in\mathcal{P}}\sum_{i=1}^{N}p_{i}f_{i}(x_{i}) . Observe that if f_{i} is lower semicontinuous for all i\in\{1,\ldots,N\} , then g also is lower semicontinuous. Similarly to ( 30 ), in order to solve ( 33 ), we can use the penalty method described in Section A.1 by solving the following problem \displaystyle\min_{\mathbf{x}\in\mathcal{N}}\frac{\lambda}{2}d(\mathbf{x},\overline{Q})^{2}+g(\mathbf{x}), (34) where \lambda>0 . In the case when f_{i}(x)=-\|x-\xi_{i}\|^{2} and \mathcal{P}=\Delta_{N} , where \xi_{i}\in\mathbb{R}^{n} , the proximity operator of g has a closed-form and is given in Proposition 1 and Proposition 2 . Moreover, in this case, we have that the objective function in ( 34 ) is coercive if \lambda>2 . Hence, in this case ( 34 ) has solutions for all \lambda>2 . Thus, ( 34 ) is a particular case of problem ( 2 ). 6.2 Constrained LASSO A constrained LASSO problem with linear constraints has the following form: \min_{x\in\mathbb{R}^{n},Rx=0}\|Bx-b\|^{2}+\|x\|_{1}, (35) where \|\cdot\|_{1} is the \ell^{1} norm which is a regularizer that induce sparsity in the solution vector x . The previous problem is convex and is a particular case of ( 2 ) when V=\ker R , A is the identity, and h(x)=\|Bx-b\|^{2} . Another class of problems where the regularization with the norm \|\cdot\|_{1} appears is in logistic regression shi2006lasso . To use the norm \|\cdot\|_{1} as a regularizer in ( 35 ) tends to reduce the number of nonzero elements of the solution generating a bias. Therefore, nonconvex regularizers are often used to reduces bias. These covers the \ell^{p} -norms (with p\in\left]0,1\right[ ) which are not weakly convex, as well as several weakly convex regularizers, which now we illustrate. In zhang2010nearly it is defined the minimax concave penalty (MCP) function: Given \lambda>0 and \theta>0 , the MCP is the function r_{\lambda,\theta}\colon\mathbb{R}\rightarrow\mathbb{R}_{+} defined by r_{\lambda,\theta}(x)=\begin{cases}\lambda|x|-\frac{x^{2}}{2\theta}&\text{if }\,\,|x|\leq\theta\lambda,\\ \frac{\theta\lambda^{2}}{2}&\text{otherwise }\end{cases} Observe that this function is \theta^{-1} -weakly convex. The proximity operator of r_{\lambda,\theta} (called firm threshold) has a closed form and is given, for every \gamma<\theta , by \operatorname{prox}_{\gamma r_{\lambda,\theta}}(x)=\begin{cases}0&\text{if }\,\,|x|<\gamma\lambda,\\ \frac{x-\lambda\gamma\operatorname{sgn}(x)}{1-\gamma/\theta}&\text{if }\,\,\gamma\lambda\leq|x|\leq\theta\lambda,\\ x&\text{if }\,\,|x|>\theta\lambda.\end{cases} Another weakly convex regularizer is the smoothly clipped absolute deviation (SCAD) MR1946581 , which is defined, for parameters \lambda>0 and \theta>2 , by r_{\lambda,\theta}(x)=\begin{cases}\lambda|x|&\text{if }\,\,|x|\leq\lambda,\\ \frac{-x^{2}+2\lambda\theta|x|-\lambda^{2}}{2(\theta-1)}&\text{if }\,\,\lambda<|x|\leq\theta\lambda,\\ \frac{(\theta+1)\lambda^{2}}{2}&\text{if }\,\,|x|>\theta\lambda.\end{cases} This function is (\theta-1)^{-1} -weakly convex. The problem we have seen so far has the structure of ( 2 ) when A is the identity. Let us consider the case A\neq\operatorname{Id} . We consider the Tukey biweight function beaton1974fitting , which is given by \displaystyle x\in\mathbb{R}^{n}\mapsto\sum_{i=1}^{m}\varphi(A_{i\bullet}x-b_{i}), where \varphi(\theta)=\frac{\theta^{2}}{1+\theta^{2}} , A\in\mathbb{R}^{m\times n} , and A_{i\bullet} denotes the i th row of A . Note that the above function can be written as g(Ax) with g(y)=\sum_{i=1}^{m}\varphi(y_{i}-b_{i}) for y\in\mathbb{R}^{m} . Moreover, the Tukey biweight function is \rho -weakly convex with \rho=6 . 6.3 Max Dispersion Problems Consider the following max dispersion problem (or max-min location problem): \displaystyle\max_{x\in S}\min_{1\leq i\leq N}\|x-u_{i}\|^{2}, (36) where S\subset\mathbb{R}^{n} is a compact subset and u_{i}\in\mathbb{R}^{n} for all i\in\{1,\ldots,N\} . The problem ( 36 ) consists in to find a point in S that is furthest from the given points u_{1},\ldots,u_{N} and has the geometric interpretation of finding the largest Euclidian ball with center in S and that does not enclose any given point. Note that x\mapsto\min_{1\leq i\leq N}\|x-u_{i}\|^{2} is continuous since is the minimum of finitely many continuous functions. Then, problem ( 36 ) has solutions. The problem ( 36 ) have been studied in jeyakumar2018exact when the constraint S is a polyhedral or a ball, and has applications in facility location, pattern recognition, among others dasarathy1980maxmin ; johnson1990minimax . In addition, it is shown in haines2013convex that the max dispersion problem over a box constraint is a NP-hard problem. Consider the case when S=V\cap\mathcal{B} , where V\subset\mathbb{R}^{n} is a vector subspace and \mathcal{B}\subset\mathbb{R}^{n} is a compact convex set. In this case, ( 36 ) is equivalent to \displaystyle\min_{x\in V\cap\mathcal{B}}\max_{1\leq i\leq N}-\|x-u_{i}\|^{2}. (37) In order to solve ( 37 ), we use the penalty method described in Section A.1 . That is, we solve the following penalized problem \displaystyle\min_{x\in V}\lambda P(x)+\max_{1\leq i\leq N}-\|x-u_{i}\|^{2}, (38) where P is the penalty function which is lower semicontinuous and satisfies that P(x)\geq 0 for all x\in\mathbb{R}^{n} and P(x)=0 if and only if x\in\mathcal{B} , while \lambda>0 is the penalty coefficient. Consider the penalty function P(x)=\frac{1}{2}d(x,\mathcal{B})^{2} . Then, the problem ( 38 ) is equivalent to \displaystyle\min_{x\in V}h(x)+\widetilde{g}(x), (39) where h(x)=\frac{\lambda}{2}d^{2}(x,\mathcal{B}) and \widetilde{g} is given by \displaystyle x\in\mathbb{R}^{n}\mapsto\widetilde{g}(x)=\sup_{p\in\Delta_{N}}\sum_{i=1}^{N}p_{i}(\langle x,2u_{i}\rangle-\|u_{i}\|^{2})-\|x\|^{2}. (40) The problem ( 39 ) is particular instance of ( 2 ) when A=\operatorname{Id} . Moreover, it is straightforward to prove that the objective function in ( 39 ) is coercive for all \lambda>2 , hence ( 39 ) has solutions for all \lambda>2 . Now, the function ( 40 ) is a particular case of ( 25 ) when a_{i}=2u_{i} , b_{i}=-\|u_{i}\|^{2} , \sigma=1 , and \mathcal{C}=\Delta_{N} . Thus, we can use the algorithm in Proposition 3 for computing the proximity operator of \widetilde{g} . Observe that the projection onto \mathcal{C}=\Delta_{N} has an explicit form given in duchi2008efficient . In addition, \nabla h(x)=\lambda(x-P_{\mathcal{B}}(x)) is Lipschitz with constant \lambda . On the other hand, since V\subset\mathbb{R}^{n} is a vector subspace, then by ( rockafellar1997convex , Theorem 1.4) , there exists R\in\mathbb{R}^{m\times n} such that V=\ker R . Thus, since \operatorname{ran}R is closed (since it is a vector subspace of finite dimension), then the projection onto V is given by P_{\ker R}=\operatorname{Id}-R^{\dagger}R , where R^{\dagger} is the generalized (or Moore-Penrose) inverse of R . Another equivalent formulation for the problem ( 39 ) is the following \displaystyle\min_{\mathbf{x}=(x_{1},\ldots,x_{N})\in\mathbb{R}^{nN}}H(\mathbf{x})+g(\mathbf{x})\quad\text{s.t.}\quad\mathbf{x}\in V^{N}\cap\mathcal{D}, (41) where H\colon\mathbb{R}^{nN}\rightarrow\mathbb{R} is defined by H(\mathbf{x})=h(x_{1})=\frac{\lambda}{2}d(x_{1},\mathcal{B})^{2} , \mathcal{D}=\{\mathbf{x}\in\mathbb{R}^{nN}:x_{1}=\cdots=x_{N}\} is the diagonal set, and g is given by \displaystyle\mathbf{x}\in\mathbb{R}^{nN}\mapsto g(\mathbf{x})=\max_{1\leq i\leq N}-\|x_{i}-u_{i}\|^{2}. (42) Note that \mathbf{x}=(x,\ldots,x) is solution to ( 41 ) if and only if x is solution to ( 39 ). The problem ( 41 ) is a particular case of ( 2 ) when A=\operatorname{Id} and the closed vector subspace is V^{N}\cap\mathcal{D} . As mentioned before, the objective function in ( 41 ) is coercive in \mathcal{D} for all \lambda>2 , hence ( 41 ) has solutions for all \lambda>2 . The proximity operator of ( 42 ) has a closed form and is given by Proposition 1 and Proposition 2 . The projection onto V^{N}\cap\mathcal{D} can be calculated using the Dykstra’s projection algorithm, which requires calculate the projection onto V^{N} and onto \mathcal{D} . Recall that V=\ker R . By ( MR3616647 , Proposition 29.3) , we have that P_{V^{N}}(\mathbf{x})=(P_{\ker R}(x_{i}))_{i=1}^{N} for all \mathbf{x}\in\mathbb{R}^{nN} . On the other hand, the projection onto \mathcal{D} is given by P_{\mathcal{D}}(\mathbf{x})=(\frac{1}{N}\sum_{j=1}^{N}x_{j})_{i=1}^{N} for all \mathbf{x}\in\mathbb{R}^{nN} . 7 Numerical experiments In this section, we use the Algorithm 1 for solving the equivalent problems ( 39 ) and ( 41 ) associated to the max dispersion problem. We consider \mathcal{B}=B(0,r) with r>0 and V=\ker R for some R\in\mathbb{R}^{m\times n} . Observe that the functions \widetilde{g} and g defined in ( 40 ) and ( 42 ) respectively, are \rho -weakly convex with \rho=2 . In the context of problem ( 39 ), we have that L_{\nabla h}=\lambda and A=\operatorname{Id} . Then, L_{k} defined in ( 4 ) is L_{k}=\lambda+\dfrac{1}{\mu_{k}}=\dfrac{1+\lambda\mu_{k}}{\mu_{k}} and \gamma_{k}=1/L_{k}=\dfrac{\mu_{k}}{1+\lambda\mu_{k}} . Hence, for all k\geq 1 (where F_{k} is defined in ( 3 )), we have \displaystyle x_{k}-\gamma_{k}\nabla F_{k}(x_{k})=\dfrac{1}{1+\lambda\mu_{k}}\left(\lambda\mu_{k}P_{\mathcal{B}}(x_{k})+\operatorname{prox}_{\mu_{k}\widetilde{g}}(x_{k})\right). Thus, the Algorithm 1 for solving problem ( 39 ) reduces to Algorithm 3 Projected variable smoothing for ( 39 ) x_{1}\in\ker R , \alpha\in\left]0,1\right[ , and C>0 such that 4C\leq 1 . for k=1,2,\ldots do \mu_{k}\leftarrow Ck^{-\alpha} and x_{k+1}\leftarrow P_{\ker R}\left(\dfrac{1}{1+\lambda\mu_{k}}(\lambda\mu_{k}P_{\mathcal{B}}(x_{k})+\operatorname{prox}_{\mu_{k}\widetilde{g}}(x_{k})\right)) . end for The proximity operator of \widetilde{g} in ( 40 ) can be calculated by using Proposition 3 , while the projection onto \mathcal{B}=B(0,r) is well-known. On the other hand, in the context of problem ( 41 ), \nabla H(\mathbf{x})=(\lambda(x_{1}-P_{\mathcal{B}}(x_{1})),0,\ldots,0) , which implies that \nabla H is Lipschitz with constant L_{\nabla H}=\lambda . Then, as in the case of problem ( 39 ), \gamma_{k}=\frac{\mu_{k}}{1+\lambda\mu_{k}} . Hence, for all k\geq 1 , \displaystyle\mathbf{x}^{k}-\gamma_{k}\nabla F_{k}(\mathbf{x}^{k})=\frac{1}{1+\lambda\mu_{k}}\left(\mu_{k}(\lambda\mathbf{x}^{k}-\nabla H(\mathbf{x}^{k}))+\operatorname{prox}_{\mu_{k}g}(\mathbf{x}^{k})\right). Therefore, the Algorithm 1 for solving problem ( 41 ) reduces to Algorithm 4 Projected variable smoothing for ( 41 ) \mathbf{x}^{1}\in V:=(\ker R)^{N}\cap\mathcal{D} , \alpha\in\left]0,1\right[ , and C>0 such that 4C\leq 1 . for k=1,2,\ldots do Set \mu_{k}\leftarrow Ck^{-\alpha} and \mathbf{z}^{k}\leftarrow(\lambda(x_{1}^{k}-P_{\mathcal{B}}(x_{1}^{k})),0,\ldots,0) \mathbf{x}^{k+1}\leftarrow P_{V}(\dfrac{1}{1+\lambda\mu_{k}}\left(\mu_{k}(\lambda\mathbf{x}^{k}-\mathbf{z}^{k})+\operatorname{prox}_{\mu_{k}g}(\mathbf{x}^{k})\right)) . end for The proximity operator of g in ( 42 ) has a closed-form and is given by Propositions 1 and 2 . For the numerical results, we consider n=3 , N=10 , \alpha=1/3 , C=1/4 , r=1 , and R=\begin{pmatrix}1&1&1\end{pmatrix} . That is, \ker R=\{(x,y,z)\in\mathbb{R}^{3}:x+y+z=0\} . We choose to stop every algorithm when the norm of the difference between two consecutive iterations is less than 10^{-5} . On the other hand, for every i\in\{1,\ldots,N\} , we consider vectors u_{i} of the form 2\texttt{rand}(n,1) , where \texttt{rand}(n,1) stands a random vector with components in \left[0,1\right] . Since \mathcal{B}=B(0,r) , then the objective function in ( 39 ) and ( 41 ) is F_{\lambda}(x)=\frac{\lambda}{2}(\max\{\|x\|-r,0\})^{2}+\max_{1\leq i\leq N}-\|x-u_{i}\|^{2}. In Figure 1 , we illustrate the value of the objective function F_{\lambda} with respect to the time (in seconds) for the algorithms 3 and 4 . Figure 1: Performance of algorithms 3 and 4 for \lambda=100 (left) and \lambda=200 (right). We observe that for both cases of \lambda , the Algorithm 4 converges in less time than Algorithm 3 . This is because Algorithm 3 requires computing the proximity operator of \widetilde{g} , which takes more time than calculating the proximity of g . However, the values of the objective function in the last iteration in algorithms 3 and 4 are -4.7043 and -4.6885 respectively for \lambda=100 , and of -4.6901 and -4.6763 respectively for \lambda=200 . Therefore, the Algorithm 3 provides a better approximation to the solution of the max dispersion problem. 8 Conclusions In this paper, we consider the problem of minimizing the sum of a smooth function and the composition of a weakly convex function with a bounded linear operator over a closed vector subspace, generalizing the framework studied in bohm2021variable , which considers the case where the vector subspace is the entire space. We propose a variable smoothing algorithm that includes projection onto the vector subspace and we prove a complexity of \mathcal{O}(\epsilon^{-3}) to achieve an \epsilon -approximate solution. In both the literature and the proposed algorithm, it is typically assumed that the weakly convex function is Lipschitz in order to obtain an approximate solution. However, we show that if the sequence generated by the proposed algorithm is bounded, this assumption is not necessary. The proposed algorithm requires computing the proximity operator of a weakly convex function. In this context, we compute the proximity operator of a supremum of weakly convex functions in two important cases. In one case, the proximity operator has a closed formula, and in the other, we provide an algorithm that converges to the proximity operator. The supremum function appears in the so-called distributionally robust optimization problem sun2021robust ; MR4361979 . Another problem where our algorithm can be applied, which also involves a supremum function, is the max-dispersion problem (or max-min location problem) over the intersection of a subspace and a compact convex set. Acknowledgements. The authors were supported by ANID Chile under grants Fondecyt Regular N ∘ 1240120 (P. Pérez-Aros and E. Vilches), Fondecyt Regular N ∘ 1220886 (P. Pérez-Aros and E. Vilches), Fondecyt Regular N ∘ 1240335 (P. Pérez-Aros), Proyecto de Exploración 13220097 (P. Pérez-Aros and E. Vilches), CMM BASAL funds for Center of Excellence FB210005 (P. Pérez-Aros and E. Vilches), Project ECOS230027 (P. Pérez-Aros and E. Vilches), MATH-AMSUD 23-MATH-17 (P. Pérez-Aros and E. Vilches). Beca de Doctorado Nacional 21210951 (S. López-Rivera). Appendix A Appendix A.1 Penalty Method This section is based in ( luenberger1984linear , Section 21.1) . Consider the following optimization problem \min_{x\in V\cap\mathcal{B}}f(x), (43) where f\colon\mathbb{R}^{n}\rightarrow\mathbb{R} is lower semicontinuous, V is a closed vector subspace of \mathbb{R}^{n} , and \mathcal{B} is a compact convex subset of \mathbb{R}^{n} . Note that ( 43 ) has solutions since f is lower semicontinuous and V\cap\mathcal{B} is compact. The idea of the penalty function method is replace problem ( 43 ) by a problem of the form \min_{x\in V}f(x)+\lambda P(x) , where \lambda>0 and P\colon\mathbb{R}^{n}\rightarrow\mathbb{R} is a lower semicontinuous function satisfying that P(x)\geq 0 for all x\in\mathbb{R}^{n} and P(x)=0 if and only if x\in\mathcal{B} . In order to solve problem ( 43 ) by the penalty function method, let \lambda_{k}\to+\infty be a sequence such that \lambda_{k}>0 and \lambda_{k+1}>\lambda_{k} for all k\in\mathbb{N} . Consider q(\lambda,x):=f(x)+\lambda P(x) and assume that for all k\in\mathbb{N} the problem \min_{x\in V}q(\lambda_{k},x) has a solution x_{k}\in V . Lemma 2 For every k\in\mathbb{N} , we have q(\lambda_{k},x_{k})\leq q(\lambda_{k+1},x_{k+1}),\,P(x_{k})\geq P(x_{k+1})\textrm{ and }f(x_{k})\leq f(x_{k+1}). Proof Since \lambda_{k} is increasing, we have \displaystyle q(\lambda_{k+1},x_{k+1})\geq f(x_{k+1})+\lambda_{k}P(x_{k+1})\geq f(x_{k})+\lambda_{k}P(x_{k})=q(\lambda_{k},x_{k}), thereby proving the first inequality. Next, observe that f(x_{k})+\lambda_{k}P(x_{k})\leq f(x_{k+1})+\lambda_{k}P(x_{k+1})\leq f(x_{k})+\lambda_{k+1}P(x_{k})+(\lambda_{k}-\lambda_{k+1})P(x_{k+1}), which implies the second inequality. Finally, by using the second inequality, we get that f(x_{k})+\lambda_{k}P(x_{k})\leq f(x_{k+1})+\lambda_{k}P(x_{k+1})\leq f(x_{k+1})+\lambda_{k}P(x_{k}), which implies the last inequality. ∎ Lemma 3 If x^{*} solves problem ( 43 ), then f(x^{*})\geq q(\lambda_{k},x_{k})\geq f(x_{k}) for all k\in\mathbb{N} . Proof f(x^{*})=f(x^{*})+\lambda_{k}P(x^{*})\geq f(x_{k})+\lambda_{k}P(x_{k})\geq f(x_{k}) . ∎ Theorem A.1 A cluster point of a sequence generated by the penalty method solves ( 43 ). Proof Let (x_{k}) generated by the penalty method and \bar{x} a cluster point. Let f^{*} the value of ( 43 ). From Lemmas 2 and 3 , it follows that (f(x_{k})) is increasing and bounded above by f^{*} . Hence, (f(x_{k})) converges and f(\overline{x})\leq\lim f(x_{k}) . Similarly, q^{*}:=\lim q(\lambda_{k},x_{k}) and \lim P(x_{k}) exist. Therefore, 0\leq\lim\lambda_{k}P(x_{k})=\lim q(\lambda_{k},x_{k})-\lim f(x_{k})\leq q^{*}-f(\overline{x}) , which, since \lambda_{k}\rightarrow\infty and P(x_{k})\geq 0 , implies that \lim P(x_{k})=0 . Moreover, 0\leq P(\bar{x})\leq\lim P(x_{k})=0 , thereby proving that \bar{x}\in\mathcal{B} . Finally, from Lemma 3 , we conclude that f(\overline{x})\leq\lim_{k\rightarrow\infty}f(x_{k})\leq f^{*} , which ends the proof. ∎ A.2 Key inequalities Lemma 4 Assume that \alpha\in]0,1[ . Then, for all K\in\mathbb{N} (K+1)^{1-\alpha}-1\geq(2^{1-\alpha}-1)K^{1-\alpha}. Proof Let us define \varphi(x)=(x+1)^{1-\alpha}-1-\theta x^{1-\alpha} for all x\geq 1 , where \theta=2^{1-\alpha}-1 . Since \alpha\in\left]0,1\right[ , 0<\theta<1 . Note that \varphi(1)=0 . Let x\geq 1 . Then, \varphi^{\prime}(x)=(1-\alpha)(x+1)^{-\alpha}-(1-\alpha)\theta x^{-\alpha} . We will see that \varphi^{\prime}(x)\geq 0 . Now, we observe that \theta<2^{-\alpha} if and only if \frac{\theta^{1/\alpha}}{1-\theta^{1/\alpha}}<1 . Therefore, x\geq 1>\frac{\theta^{1/\alpha}}{1-\theta^{1/\alpha}} . Now, we have that x\geq\frac{\theta^{1/\alpha}}{1-\theta^{1/\alpha}} if and only if (x+1)^{-\alpha}\geq\theta x^{-\alpha} . Whence \varphi^{\prime}(x)\geq 0 . It follows that \varphi(x)\geq\varphi(1)=0 for all x\geq 1 , which implies the result. ∎ Lemma 5 Let \alpha\in]0,1[ and N\in\mathbb{N} such that \theta:=(1+1/N)^{1-\alpha}-1<1/2 . Then, for all K\geq N (K+1)^{1-\alpha}-N^{1-\alpha}\geq\theta K^{1-\alpha}. Proof Define \varphi(x):=(x+1)^{1-\alpha}-N^{1-\alpha}-\theta x^{1-\alpha} . By definition of \theta , we deduce that \varphi(N)=0 . Let x\geq N . Then, \varphi^{\prime}(x)=(1-\alpha)(x+1)^{-\alpha}-(1-\alpha)\theta x^{-\alpha} . Since \alpha\in\left]0,1\right[ , we have that (2^{1/\alpha}-1)N>1 , which is equivalent to 1/2<(\frac{N}{N+1})^{\alpha} . Hence, \theta<1/2<(\frac{N}{N+1})^{\alpha} . Then, \theta^{1/\alpha}\leq\frac{N}{N+1} , which implies that x\geq N\geq\frac{\theta^{1/\alpha}}{1-\theta^{1/\alpha}} . Note that x\geq\frac{\theta^{1/\alpha}}{1-\theta^{1/\alpha}} if and only if (x+1)^{-\alpha}\geq\theta x^{-\alpha} . Hence \varphi^{\prime}(x)\geq 0 and \varphi(x)\geq\varphi(N)=0 for all x\geq N . ∎ Proposition 4 Let g\colon\mathcal{H}\rightarrow\mathbb{R}\cup\{+\infty\} be a proper, l.s.c., and \rho -weakly convex function. Then there exists \mu_{0}<\min\{1,\frac{1}{2\rho}\} such that for every \mu\in\left]0,\mu_{0}\right[ , x\in\mathcal{H} , and x_{0}\in\operatorname{dom}g we have \|\operatorname{prox}_{\mu g}(x)\|^{2}\leq 4(M+5\|x\|^{2}), where M=\max\{0,g(x_{0})\}+2\|x_{0}\|^{2}+1/2 . Proof We claim that there exists \theta>0 such that for all x\in\mathcal{H} , \displaystyle g(x)\geq-\dfrac{\theta}{2}(1+\|x\|^{2}). (44) Since g+\dfrac{\rho}{2}\|\cdot\|^{2} has an affine minorant, there exist x^{*}\in\mathcal{H} and \beta\in\mathbb{R} such that \displaystyle g(x)+\dfrac{\rho}{2}\|x\|^{2}\geq\langle x^{*},x\rangle+\beta\geq-\frac{\|x^{*}\|^{2}}{2}-\frac{\|x\|^{2}}{2}+\beta\textrm{ for all }x\in\mathcal{H}. Then, g(x)\geq-\frac{1}{2}(\|x^{*}\|^{2}-2\beta)-\frac{1}{2}(1+\rho)\|x\|^{2}\geq-\frac{1}{2}\max\{\|x^{*}\|^{2}-2\beta,1+\rho\}(1+\|x\|^{2}) . Therefore, g satisfies ( 44 ) with \theta=\max\{\|x^{*}\|^{2}-2\beta,1+\rho\}>0 . Let us define \mu_{0}=\min\{\frac{1}{2\theta},\frac{1}{1+\theta}\} . Let \mu\in]0,\mu_{0}[ , let x\in\mathcal{H} , let y=\operatorname{prox}_{\mu g}(x) , and x_{0}\in\operatorname{dom}g\neq\emptyset . By ( 44 ), we have that \displaystyle-\frac{\theta}{2}-\frac{\theta}{2}\|y\|^{2}+\frac{1}{2\mu}\|y-x\|^{2} \displaystyle\leq g(y)+\frac{1}{2\mu}\|y-x\|^{2}\leq g(x_{0})+\frac{1}{2\mu}\|x_{0}-x\|^{2}. Then, \displaystyle-\frac{\theta}{2}-\frac{\theta}{2}\|y\|^{2}+\frac{1}{2\mu}\|y\|^{2}-\frac{1}{\mu}\langle y,x\rangle\leq g(x_{0})+\frac{1}{2\mu}\|x_{0}\|^{2}-\frac{1}{\mu}\langle x_{0},x\rangle\leq g(x_{0})+\frac{1}{\mu}\|x_{0}\|^{2}+\frac{1}{2\mu}\|x\|^{2}. Now, from ab\leq\frac{\alpha}{2}a^{2}+\frac{1}{2\alpha}b^{2} with a=\|y\| , b=\|x\| and \alpha=\frac{1-\mu\theta}{2}>0 , we have that \displaystyle-\frac{\theta}{2}-\frac{\theta}{2}\|y\|^{2}+\frac{1}{2\mu}\|y\|^{2}\leq\frac{1}{2\mu}\left(\frac{1-\mu\theta}{2}\right)\|y\|^{2}+g(x_{0})+\frac{1}{\mu}\|x_{0}\|^{2}+\frac{1}{\mu(1-\mu\theta)}\|x\|^{2}+\frac{1}{2\mu}\|x\|^{2}. Rearranging, we obtain \displaystyle\frac{1}{4}\left(\frac{1-\mu\theta}{\mu}\right)\|y\|^{2}\leq g(x_{0})+\frac{1}{\mu}\|x_{0}\|^{2}+\left(\frac{1}{\mu(1-\mu\theta)}+\frac{1}{2\mu}\right)\|x\|^{2}+\frac{\theta}{2}, which implies that \displaystyle\|y\|^{2}\leq 4\left[\frac{\mu}{1-\mu\theta}g(x_{0})+\frac{1}{1-\mu\theta}\|x_{0}\|^{2}+\left(\frac{1}{(1-\mu\theta)^{2}}+\frac{1}{2(1-\mu\theta)}\right)\|x\|^{2}+\frac{\mu\theta}{2(1-\mu\theta)}\right]. Note that \frac{\mu}{1-\mu\theta}<1 (since \mu<\frac{1}{1+\theta} ), \frac{1}{1-\mu\theta}<2 , and \frac{\mu\theta}{2(1-\mu\theta)}<\frac{1}{2} (since \mu<\frac{1}{2\theta} ). Thus, \|y\|^{2}\leq 4(\max\{0,g(x_{0})\}+2\|x_{0}\|^{2}+5\|x\|^{2}+1/2) . ∎ Proposition 5 Let S be a nonempty closed convex and bounded subset of \mathbb{R}^{m} and let g\colon\mathbb{R}^{m}\rightarrow\mathbb{R} be a \rho -weakly convex and lower semicontinuous function. Then, there exist \ell\geq 0 and \mu_{0}\in\left]0,1\right[ (with \mu_{0} depending on \rho ) such that for all \mu\in\left]0,\mu_{0}\right[ and x\in S , \displaystyle\|\nabla g_{\mu}(x)\|=\dfrac{1}{\mu}\|x-\operatorname{prox}_{\mu g}(x)\|\leq\ell. Proof By Proposition 4 , there exist \widetilde{\mu}_{0}\in]0,1[ and M\geq 0 such that for all \mu\in\left]0,\widetilde{\mu}_{0}\right[ , \displaystyle\|\operatorname{prox}_{\mu g}(x)\|^{2}\leq 4(M+5\|x\|^{2})\textrm{ for all }x\in\mathbb{R}^{m}. Let us define \widetilde{S}:=\{x\in\mathbb{R}^{m}:d(x,S)\leq 1\} . Since \widetilde{S} is nonempty closed, convex, and bounded, there exists \widetilde{\ell}\geq 0 such that g+\frac{\rho}{2}\|\cdot\|^{2} is \widetilde{\ell} -Lipschitz on \widetilde{S} and there exists \widetilde{M}\geq 0 such that \|x\|\leq\widetilde{M} for all x\in\widetilde{S} . Let x,y\in\widetilde{S} . Then, \displaystyle|g(x)-g(y)| \displaystyle\leq|g(x)-g(y)+\dfrac{\rho}{2}\|x\|^{2}-\dfrac{\rho}{2}\|y\|^{2}|+\dfrac{\rho}{2}|\|x\|^{2}-\|y\|^{2}| \displaystyle\leq\widetilde{\ell}\|x-y\|+\dfrac{\rho}{2}|\|x\|+\|y\||\cdot|\|x\|-\|y\|| \displaystyle\leq\widetilde{\ell}\|x-y\|+\rho\widetilde{M}\|x-y\| \displaystyle=(\widetilde{\ell}+\rho\widetilde{M})\|x-y\|. Hence, g is Lipschitz on \widetilde{S} . Similarly, g is Lipschitz in S . Now, for all x\in S and \mu\in]0,\widetilde{\mu}_{0}[ , \displaystyle\dfrac{1}{2\mu}\|x-\operatorname{prox}_{\mu g}(x)\|^{2} \displaystyle\leq g(x)-g(\operatorname{prox}_{\mu g}(x)) \displaystyle\leq g(x)+\frac{\rho}{2}\|\operatorname{prox}_{\mu g}(x)\|^{2}-\langle x^{*},\operatorname{prox}_{\mu g}(x)\rangle-\beta \displaystyle\leq g(x)+2\rho(M+5\|x\|^{2})+\|x^{*}\|\|x-\operatorname{prox}_{\mu g}(x)\|+\|x^{*}\|\|x\|-\beta \displaystyle\leq g(x)+\mu\|x^{*}\|^{2}+\frac{1}{4\mu}\|x-\operatorname{prox}_{\mu g}(x)\|^{2}+2\rho(M+5\|x\|^{2})+\|x^{*}\|\|x\|-\beta, since ab\leq\frac{c^{2}}{2}a^{2}+\frac{1}{2c^{2}}b^{2} for c=\sqrt{2\mu} . Hence, for all x\in S and \mu\in\left]0,\widetilde{\mu}_{0}\right[ , we have \displaystyle\|x-\operatorname{prox}_{\mu g}(x)\|^{2}\leq 4\mu(g(x)+\mu\|x^{*}\|^{2}+2\rho(M+5\|x\|^{2})+\|x^{*}\|\|x\|-\beta). Since g is Lipschitz in S and S is bounded, the right-hand side of the latter inequality is uniformly bounded in S . Thus, we can to find \widetilde{m}>0 such that for all x\in S and \mu\in\left]0,\widetilde{\mu}_{0}\right[ \displaystyle\|x-\operatorname{prox}_{\mu g}(x)\|\leq\sqrt{\mu}\widetilde{m}. Set \mu_{0}=\min\{\widetilde{\mu}_{0},\frac{1}{\widetilde{m}^{2}}\}\in]0,1[ . Then, for all x\in S and \mu\in\left]0,\mu_{0}\right[ , \|x-\operatorname{prox}_{\mu g}(x)\|\leq 1 , whence \operatorname{prox}_{\mu g}(x)\in\widetilde{S} . Finally, the result follows from the formula \nabla g_{\mu}(x)\in\partial g(\operatorname{prox}_{\mu g}(x)) for all x\in\mathbb{R}^{m} and the \ell -Lipschitz continuity of g over in \widetilde{S} . ∎ A.3 Proof of Proposition 2 Proof of Proposition 2 : The set defined in ( 23 ) is nonempty since N-1 is in that set. Hence k is well defined. Note that \nabla\phi(p)=\left(\frac{-\alpha_{i}}{(2\mu p_{i}-1)^{2}}\right)_{i=1}^{N} for all p\in\mathbb{R}^{N} . Then, since -\phi is convex on \Delta_{N} , by the definition of \Delta_{N} and the KKT’s conditions, it follows that it is enough to prove that there exists \tau\in\mathbb{R} and (\eta_{i})_{i=1}^{N}\in\mathbb{R}_{+}^{N} such that \sum_{i=1}^{N}p_{i}=1 and \alpha_{i}(2\mu p_{i}-1)^{-2}+\tau-\eta_{i}=0,\eta_{i}p_{i}=0,p_{i}\geq 0\textrm{ for all }i\in\{1,\ldots,N\}, (45) where p\in\mathbb{R}^{N} is defined by ( 24 ). Consider \tau:=\frac{-1}{(N-k-2\mu)^{2}}(\sum_{j\notin I_{k}}\sqrt{\alpha_{j}})^{2}\in\mathbb{R} and (\eta_{i})_{i=1}^{N}\in\mathbb{R}^{N} defined by \eta_{i}=\tau+\alpha_{i} if i\in I_{k} and \eta_{i}=0 if i\notin I_{k} . Thus, we have the second condition in ( 45 ). Let us now prove the first condition in ( 45 ). Let i\in\{1,\ldots,N\} . If i\in I_{k} , then p_{i}=0 and \frac{\alpha_{i}}{(2\mu p_{i}-1)^{2}}+\tau-\eta_{i}=\alpha_{i}+\tau-\eta_{i}=0 . If i\notin I_{k} , then by ( 24 ), (1-2\mu p_{i})^{2}=(N-k-2\mu)^{2}\alpha_{i}(\sum_{j\notin I_{k}}\sqrt{\alpha_{j}})^{-2} and hence \displaystyle\alpha_{i}(1-2\mu p_{i})^{-2}+\tau-\eta_{i}=(N-k-2\mu)^{-2}(\sum_{j\notin I_{k}}\sqrt{\alpha_{j}})^{2}+\tau-\eta_{i}=-\eta_{i}=0, which proves the first condition in ( 45 ). We claim that \eta_{i}\geq 0 for all i\in I_{k} (note that if k=0 , the latter is direct since I_{0}=\emptyset , so in order to prove this claim we assume that k>0 ). Let i\in I_{k} . Then \alpha_{i}\geq\alpha_{\ell_{k}} . Now, by definition of k , we have that k-1 is not in the set in ( 23 ), that is, \displaystyle(N-k+1-2\mu)\sqrt{\alpha_{\ell_{k}}}\geq\sum_{j\notin I_{k-1}}\sqrt{\alpha_{j}}=\sqrt{\alpha_{\ell_{k}}}+\cdots+\sqrt{\alpha_{\ell_{N}}}, which yields that (N-k-2\mu)\sqrt{\alpha_{i}}\geq(N-k-2\mu)\sqrt{\alpha_{\ell_{k}}}\geq\sqrt{\alpha_{\ell_{k+1}}}+\cdots+\sqrt{\alpha_{\ell_{N}}}=\sum_{j\notin I_{k}}\sqrt{\alpha_{j}} . Hence, \eta_{i}=\tau+\alpha_{i}=\alpha_{i}-\frac{1}{(N-k-2\mu)^{2}}(\sum_{j\notin I_{k}}\sqrt{\alpha_{j}})^{2}\geq 0 . We claim now that p_{i}\geq 0 for all i\notin I_{k} . Let i\notin I_{k} . Then \alpha_{i}\leq\alpha_{\ell_{k+1}} and therefore \frac{(N-k-2\mu)\sqrt{\alpha_{i}}}{\sum_{j\notin I_{k}}\sqrt{\alpha_{j}}}\leq\frac{(N-k-2\mu)\sqrt{\alpha_{\ell_{k+1}}}}{\sum_{j\notin I_{k}}\sqrt{\alpha_{j}}}<1, where the last inequality is by the definition of k . Thus, from ( 24 ), we obtain that p_{i}\geq 0 . Finally, since |I_{k}^{c}|=N-k , we deduce from ( 24 ), that \sum_{i=1}^{N}p_{i}=1 . ∎