Proximal gradient and accelerated composite optimization

Put $d=y-x$. If $d=0$ the inequality is equality. Otherwise define $\varphi (s)=f(x+sd)$ on $[0,1]$. By [F2] and continuity of $\mathrm{\nabla }f$, $\varphi$ is continuous on $[0,1]$, differentiable on $(0,1)$, and ${\varphi }^{\mathrm{\prime }}(s)=⟨\mathrm{\nabla }f(x+sd),d⟩$.

For an arbitrary natural $N\ge 1$, partition $[0,1]$ at $j\mathrm{/}N$. Applying [F1] on each subinterval gives ${\xi }_j\in (j\mathrm{/}N,(j+1)\mathrm{/}N)$ with $\varphi ((j+1)\mathrm{/}N)-\varphi (j\mathrm{/}N)={\varphi }^{\mathrm{\prime }}({\xi }_j)\mathrm{/}N$. Telescoping and subtracting ${\varphi }^{\mathrm{\prime }}(0)$ yields $f(y)-f(x)-⟨\mathrm{\nabla }f(x),d⟩=\frac{1}{N}{\sum }_{j=0}^{N-1}({\varphi }^{\mathrm{\prime }}({\xi }_j)-{\varphi }^{\mathrm{\prime }}(0))\le \frac{L\mathrm{\parallel }d{\mathrm{\parallel }}_2^2}{N^2}{\sum }_{j=0}^{N-1}(j+1)=\frac{L}{2}(1+1\mathrm{/}N)\mathrm{\parallel }d{\mathrm{\parallel }}_2^2,$ because [F3] and [F4] give $\mathrm{\mid }{\varphi }^{\mathrm{\prime }}(s)-{\varphi }^{\mathrm{\prime }}(0)\mathrm{\mid }\le Ls\mathrm{\parallel }d{\mathrm{\parallel }}_2^2$ and ${\xi }_j<(j+1)\mathrm{/}N$. To evaluate the finite sum for every natural $N$, its value is $N(N+1)\mathrm{/}2$: at $N=0$ both sides are zero, and the recursion [F6] adds $N+1$ when $N$ is increased by one, giving $(N+1)(N+2)\mathrm{/}2$. [F7] proves this identity by induction. Only finitely many mean-value points are used for each fixed $N$.

The left side of the bound in step 1.2 is independent of $N$. Suppose it exceeded $L\mathrm{\parallel }d{\mathrm{\parallel }}_2^2\mathrm{/}2$ by $\delta >0$. For $L\mathrm{\parallel }d{\mathrm{\parallel }}_2^2>0$, [F5] lets us choose $N$ with $1\mathrm{/}N<2\delta \mathrm{/}(L\mathrm{\parallel }d{\mathrm{\parallel }}_2^2)$, making the right side in step 1.2 strictly smaller than the left side, a contradiction. If $L\mathrm{\parallel }d{\mathrm{\parallel }}_2^2=0$, step 1.2 already gives the desired bound.

Let $d$ be the dimension of the direction space of $\mathrm{aff}D$. If $d=0$, then $D$ is a singleton $\{x_0\}$ and the constant affine function $g(x_0)$ is a minorant. If $d>0$, choose affinely independent points $a_0,\dots ,a_d\in D$ spanning $\mathrm{aff}D$ and let $x_0$ be their barycenter. Iterating the two-point convexity condition shows their simplex lies in $D$. In affine barycentric coordinates, this simplex is defined by ${\lambda }_i\ge 0$ and ${\sum }_{i=0}^d{\lambda }_i=1$; at $x_0$ every ${\lambda }_i=1\mathrm{/}(d+1)$. These affine coordinate functions on the finite-dimensional space $\mathrm{aff}D$ are continuous, so they remain positive on a relative neighborhood of $x_0$, which therefore lies in the simplex and in $D$. Thus $x_0$ is a relative-interior point of $D$.

Put $p=(x_0,g(x_0))\in E_g$ and $q_j=(x_0,g(x_0)-1\mathrm{/}j)$ for integers $j\ge 1$. Each $q_j$ lies outside $E_g$ and tends to $p$. Let $p_j$ be its unique nearest point in $E_g$, supplied by [F1]. Since $p\in E_g$, $\mathrm{\parallel }{q}_j-p_j{\mathrm{\parallel }}_2\le 1\mathrm{/}j$. For each coordinate $\mathrm{\ell }<n+1$, $\mathrm{\mid }(q_j-p_j{)}_{\mathrm{\ell }}\mathrm{\mid }\le \mathrm{\parallel }{q}_j-p_j{\mathrm{\parallel }}_2\le 1\mathrm{/}j$, because each squared coordinate is a term of the sum defining the squared Euclidean norm. As $q_j\to p$ coordinatewise, this gives $p_j\to p$ coordinatewise and hence in Euclidean norm, since there are finitely many coordinates.

Normalize $u_j=(q_j-p_j)\mathrm{/}\mathrm{\parallel }{q}_j-p_j{\mathrm{\parallel }}_2$, which is defined because $q_j\mathrm{\notin }{E}_g$ and $E_g$ is closed. The vectors $u_j$ have norm one, so their range lies in the Euclidean ball $B(0,2)$. By [F3], choose a subsequence $(u_{j_{\mathrm{\ell }}})$ converging in ${\mathbb{R}}^{n+1}$ to $u=(a,c)$. Since each coordinate difference is bounded by the Euclidean norm, this convergence gives coordinate convergence; the finite-sum formula for the squared norm then gives $\mathrm{\parallel }u{\mathrm{\parallel }}_2^2={\lim }_{\mathrm{\ell }\to \mathrm{\infty }}\mathrm{\parallel }{u}_{j_{\mathrm{\ell }}}{\mathrm{\parallel }}_2^2=1$. Both $q_j$ and $p_j$ have horizontal coordinate in $\mathrm{aff}D$, so each horizontal component of $u_j$ lies in the direction space $V$ of $\mathrm{aff}D$. This finite-dimensional subspace is closed: after extending a basis of $V$ to one of ${\mathbb{R}}^n$, it is the common zero set of the remaining continuous coordinate functionals. Hence $a\in V$. For each fixed $z\in E_g$, [F2] gives $⟨u_j,z-p_j⟩\le 0$. Along the chosen subsequence, coordinate convergence and the finite-sum formula for the inner product show $⟨u_{j_{\mathrm{\ell }}},z-p_{j_{\mathrm{\ell }}}⟩\to ⟨u,z-p⟩$, so $⟨u,z-p⟩\le 0$.

The upward vertical ray $p+(0,s)$ lies in $E_g$ for all $s\ge 0$, so step 2.1 forces $c\le 0$. If $c=0$, the relative neighborhood from step 1.1 lets each direction $h\in V$ be tested at $x_0+\epsilon h$ and $x_0-\epsilon h$ for sufficiently small $\epsilon >0$. Applying step 2.1 to the corresponding epigraph points gives both $\epsilon ⟨a,h⟩\le 0$ and $-\epsilon ⟨a,h⟩\le 0$, so $⟨a,h⟩=0$ for every $h\in V$. Taking $h=a\in V$ gives $\mathrm{\parallel }a{\mathrm{\parallel }}_2^2=0$, hence $a=0$, contradicting $\mathrm{\parallel }u{\mathrm{\parallel }}_2=1$. Thus $c<0$.

For any $x\in D$, apply step 2.1 to $(x,g(x))\in E_g$ to get $⟨a,x-x_0⟩+c(g(x)-g(x_0))\le 0$. Dividing by $c<0$ reverses the inequality and yields $g(x)\ge g(x_0)+⟨-a\mathrm{/}c,x-x_0⟩$. Set $a_0=-a\mathrm{/}c$ and $b_0=g(x_0)-⟨a_0,x_0⟩$. This is the desired affine bound on $D$, and outside $D$ the value is $+\mathrm{\infty }$, so the bound holds on all of ${\mathbb{R}}^n$.

Since $\mathrm{dom}g\mathrm{\ne }\mathrm{\varnothing }$, choose $x_0$ with $g(x_0)<+\mathrm{\infty }$. The value $f(x_0)$ is real, so $F(x_0)<+\mathrm{\infty }$ and $F$ is proper.

For $x,y$ with finite $F$ and $0\le \theta \le 1$, both $g(x),g(y)$ are finite. Applying convexity separately to $f$ and $g$ and adding gives $F((1-\theta )x+\theta y)\le (1-\theta )F(x)+\theta F(y)$; if either value of $F$ is $+\mathrm{\infty }$, the extended-real convexity inequality is automatic. Thus $F$ is convex.

For $r\in \mathbb{R}$, let $\mathrm{\Phi }(x,s)=(x,s-f(x))$. It is continuous: the first coordinates are unchanged, while continuity of $f$ makes the last coordinate $s-f(x)$ continuous. The identity $\mathrm{epi}F={\mathrm{\Phi }}^{-1}(\mathrm{epi}g)$ follows by rearranging $f(x)+g(x)\le s$, including points where $g(x)=+\mathrm{\infty }$. If a point lies outside $\mathrm{epi}F$, its image lies outside the closed set $\mathrm{epi}g$, so an open ball about that image misses $\mathrm{epi}g$; continuity of $\mathrm{\Phi }$ supplies a neighborhood of the original point mapped into that ball. Hence the complement of $\mathrm{epi}F$ is open and $F$ is closed.

Since $C$ is nonempty, some $x\in C$ has ${\iota }_C(x)=0<+\mathrm{\infty }$, so the indicator is proper. If $x,y\in C$, convexity of $C$ puts every convex combination in $C$, where the indicator is zero; if either endpoint is outside $C$, the convexity inequality is automatic for an interior coefficient, and at endpoints it is equality. Thus ${\iota }_C$ is convex.

Its epigraph is exactly $C\times [0,+\mathrm{\infty })$: for $x\in C$ the inequality $0\le s$ is required, and for $x\mathrm{\notin }C$ no real $s$ satisfies $+\mathrm{\infty }\le s$. This product is closed because both factors are closed, so ${\iota }_C$ is closed.

If $n=0$, then ${\mathbb{R}}^0=\{0\}$ by [F6], and nonempty $C\subseteq {\mathbb{R}}^0$ is $\{0\}$. The proximal objective has this sole point as its unique minimizer, and it is also the unique nearest point in $C$ to $v=0$. Hence the claim holds for $n=0$.

Now assume $n\ge 1$. The proximal objective is finite exactly on $C$, where it equals $\mathrm{\parallel }u-v{\mathrm{\parallel }}_2^2\mathrm{/}(2t)$. Since $2t>0$, minimizing it over all ${\mathbb{R}}^n$ is equivalent to minimizing distance from $v$ over $C$. By [F4] the latter has a unique minimizer, which is therefore exactly the singleton in [F5].

If $n=0$, [F10] gives ${\mathbb{R}}^0=\{0\}$. Properness [F1] forces $g(0)$ to be finite. Every input $v$, candidate $u$, competitor $z$ and subgradient vector $p$ is $0$. The objective in [F8] has only the candidate $0$, so ${\mathrm{prox}}_{tg}(0)=\{0\}$. The inequality in [F7] is $g(0)\ge g(0)+0$, so $\mathrm{\partial }g(0)=\{0\}$ and $(v-u)\mathrm{/}t=0\in \mathrm{\partial }g(0)$; both directions of the resolvent equivalence hold. Firm nonexpansiveness and nonexpansiveness both reduce to $0\le 0$. This proves every conclusion for $n=0$ without compactness or an affine-minorant argument. For the remainder assume $n\ge 1$.

Define $H(x)=g(x)+\mathrm{\parallel }x-v{\mathrm{\parallel }}_2^2\mathrm{/}(2t)$. The quadratic is finite and continuous, and the identity $\mathrm{\parallel }(1-\theta )x+\theta y-v{\mathrm{\parallel }}_2^2=(1-\theta )\mathrm{\parallel }x-v{\mathrm{\parallel }}_2^2+\theta \mathrm{\parallel }y-v{\mathrm{\parallel }}_2^2-\theta (1-\theta )\mathrm{\parallel }x-y{\mathrm{\parallel }}_2^2$ shows it is convex. Thus [F3] makes $H$ proper, closed and convex. Choose $x_0\in \mathrm{dom}g$ and put $c=H(x_0)$. Then $S=\{x:H(x)\le c\}$ is nonempty and closed: it is the inverse image of $\mathrm{epi}H$ under the continuous map $x\mapsto (x,c)$.

By [F2], completing the square gives $H(x)\ge b+⟨a,x⟩+\frac{\mathrm{\parallel }x-v{\mathrm{\parallel }}_2^2}{2t}=b+⟨a,v⟩-\frac{t}{2}\mathrm{\parallel }a{\mathrm{\parallel }}_2^2+\frac{1}{2t}\mathrm{\parallel }x-(v-ta){\mathrm{\parallel }}_2^2\mathrm{.}$ Thus $H(x)\le c$ forces $x$ into a fixed-radius ball, so $S$ is bounded and hence compact by [F4]. The restriction $H{\mathrm{\mid }}_S$ is real-valued; each weak sublevel set is the intersection of $S$ with the inverse image of $\mathrm{epi}H$ under $x\mapsto (x,r)$ for its level $r$, hence closed in $S$. By [F6] it is lower semicontinuous, so [F5] gives a minimizer on $S$. Every point outside $S$ has value greater than $c$, while the minimum on $S$ is at most $c$, so this minimizer is global.

The quadratic satisfies $\mathrm{\parallel }\frac{x+y}{2}-v{\mathrm{\parallel }}_2^2=\frac{1}{2}\mathrm{\parallel }x-v{\mathrm{\parallel }}_2^2+\frac{1}{2}\mathrm{\parallel }y-v{\mathrm{\parallel }}_2^2-\frac{1}{4}\mathrm{\parallel }x-y{\mathrm{\parallel }}_2^2$. If two distinct points minimized $H$, convexity of $g$ and this identity would make their midpoint have strictly smaller value, a contradiction. Hence the global minimizer is unique, proving the singleton claim.

Suppose $u$ minimizes $H$ and fix $z\in \mathrm{dom}g$. For $0<\alpha <1$, convexity gives $g(u+\alpha (z-u))\le (1-\alpha )g(u)+\alpha g(z)$. Minimality and expansion of the quadratic therefore imply $0\le H(u+\alpha (z-u))-H(u)\le \alpha (g(z)-g(u)+\frac{⟨u-v,z-u⟩}{t})+\frac{{\alpha }^2}{2t}\mathrm{\parallel }z-u{\mathrm{\parallel }}_2^2\mathrm{.}$ Divide by $\alpha$ and let $\alpha \downarrow 0$; the parenthesized term is nonnegative. The same subgradient inequality is automatic for $z\mathrm{\notin }\mathrm{dom}g$, so $(v-u)\mathrm{/}t\in \mathrm{\partial }g(u)$.

Conversely, if $(v-u)\mathrm{/}t\in \mathrm{\partial }g(u)$, then for every finite-valued $g(z)$ the subgradient inequality and $\mathrm{\parallel }z-v{\mathrm{\parallel }}_2^2-\mathrm{\parallel }u-v{\mathrm{\parallel }}_2^2=\mathrm{\parallel }z-u{\mathrm{\parallel }}_2^2+2⟨u-v,z-u⟩$ give $H(z)-H(u)\ge \mathrm{\parallel }z-u{\mathrm{\parallel }}_2^2\mathrm{/}(2t)\ge 0$. Infinite-valued competitors cannot lower $H$, so $u$ is the unique minimizer from step 2.2. This proves the reverse implication.

Let $u_i={\mathrm{prox}}_{tg}(v_i)$ and $p_i=(v_i-u_i)\mathrm{/}t$. From step 3.1, $p_i\in \mathrm{\partial }g(u_i)$. Applying the two subgradient inequalities with $(u_1,u_2)$ and $(u_2,u_1)$ and adding yields $⟨p_1-p_2,u_1-u_2⟩\ge 0$. Substitution and multiplication by $t>0$ give $\mathrm{\parallel }{u}_1-u_2{\mathrm{\parallel }}_2^2\le ⟨u_1-u_2,v_1-v_2⟩$. By [F9] the right side is at most $\mathrm{\parallel }{u}_1-u_2{\mathrm{\parallel }}_2\mathrm{\parallel }{v}_1-v_2{\mathrm{\parallel }}_2$; if $u_1=u_2$ nonexpansiveness is immediate, and otherwise division gives it.

Set $h(u)=\lambda \mathrm{\parallel }u{\mathrm{\parallel }}_1$. It is finite everywhere and $h(0)=0$, so its effective domain is nonempty. By [F4] and $\lambda >0$, the norm triangle and homogeneity inequalities give $h((1-\theta )u+\theta w)\le (1-\theta )h(u)+\theta h(w)(0\le \theta \le 1),$ so $h$ is convex. It is continuous by [F5]. To see its epigraph is closed, take any $(u,s)$ with $s<h(u)$, set $\epsilon =(h(u)-s)\mathrm{/}3$, and choose ${\delta }_0>0$ so $\mathrm{\parallel }{u}^{\mathrm{\prime }}-u{\mathrm{\parallel }}_2<{\delta }_0$ implies $\mathrm{\mid }h(u^{\mathrm{\prime }})-h(u)\mathrm{\mid }<\epsilon$. If $\mathrm{\parallel }(u^{\mathrm{\prime }}-u,s^{\mathrm{\prime }}-s){\mathrm{\parallel }}_2<\min \{{\delta }_0,\epsilon \}$ in ${\mathbb{R}}^{n+1}$, then $s^{\mathrm{\prime }}<s+\epsilon <h(u)-\epsilon <h(u^{\mathrm{\prime }})$, so this neighborhood misses the epigraph. Thus the complement is open and the epigraph is closed. By [F6], $h$ is proper, closed and convex, as required by the proximal definition.

Fix a scalar $s=v_k$. On $u\ge 0$, completing the square shows the minimum is at $u=\max \{s-t\lambda ,0\}$; on $u\le 0$ it is at $u=\min \{s+t\lambda ,0\}$. If $s>t\lambda$, the first candidate is $s-t\lambda >0$ and has value strictly below the common boundary value at $0$, while the second candidate is $0$. If $s<-t\lambda$, the symmetric argument gives the unique minimizer $s+t\lambda <0$. If $-t\lambda \le s\le t\lambda$, both half-line minima are $0$. Thus the unique scalar minimizer is $S_{t\lambda }(s)$ in all three cases.

By [F1], the objective in [F2] is the finite sum ${\sum }_{k<n}{\varphi }_k(u_k)$, where ${\varphi }_k(u_k)=\lambda \mathrm{\mid }{u}_k\mathrm{\mid }+(u_k-v_k{)}^2\mathrm{/}(2t)$. It is enough to find the unique minimizer of each scalar function: the sum is minimized exactly when every coordinate is at its scalar minimum, and the positive quadratic term makes each scalar function strictly convex.

Applying step 1.2 to each of the finitely many coordinates $k<n$ gives the unique vector minimizer $(S_{t\lambda }(v_k){)}_{k<n}$, which is the proximal point by [F2].

By [F1] and [F3], $L(y-x^{+})-\mathrm{\nabla }f(y)\in \mathrm{\partial }g(x^{+})$. For finite $g(z)$, [F2] gives $g(z)-g(x^{+})\ge ⟨L(y-x^{+})-\mathrm{\nabla }f(y),z-x^{+}⟩\mathrm{.}$ Add $⟨\mathrm{\nabla }f(y),z-x^{+}⟩$ and $\frac{L}{2}(\mathrm{\parallel }z-y{\mathrm{\parallel }}_2^2-\mathrm{\parallel }{x}^{+}-y{\mathrm{\parallel }}_2^2)$ to both sides. Using $\mathrm{\parallel }z-y{\mathrm{\parallel }}_2^2-\mathrm{\parallel }{x}^{+}-y{\mathrm{\parallel }}_2^2=\mathrm{\parallel }z-x^{+}{\mathrm{\parallel }}_2^2+2⟨z-x^{+},x^{+}-y⟩$ and $y-x^{+}=-(x^{+}-y)$ cancels the cross terms and leaves $L\mathrm{\parallel }z-x^{+}{\mathrm{\parallel }}_2^2\mathrm{/}2$. Rearranging is the claimed inequality.

If $g(z)=+\mathrm{\infty }$, the right side is $+\mathrm{\infty }$ and the inequality holds automatically, so the finite-$g(z)$ calculation proves the statement for every $z$.