Proximal gradient and accelerated composite optimization — Examples

The function $g$ is finite everywhere, hence proper. Its epigraph is the intersection of the two closed halfspaces $\lambda (u_2-u_1)\le s$ and $-\lambda (u_2-u_1)\le s$, so it is closed. The triangle inequality for absolute value gives convexity under [F5]. Write a candidate $u$ uniquely as $u=(a-b,a+b)$, so $a$ is its mean and $b$ its half-difference. Direct expansion gives $\mathrm{\parallel }u-v{\mathrm{\parallel }}_2^2=2(a-m{)}^2+2(b-d{)}^2$ and $g(u)=2\lambda \mathrm{\mid }b\mathrm{\mid }$. Hence the objective is $\frac{(a-m{)}^2}{t}+\frac{(b-d{)}^2}{t}+2\lambda \mathrm{\mid }b\mathrm{\mid }\mathrm{.}$ The first term is uniquely minimized at $a=m$; the remaining terms depend only on $b$.

The $b$-dependent objective is $2\lambda \mathrm{\mid }b\mathrm{\mid }+(b-d{)}^2\mathrm{/}t$, which under the scalar/one-coordinate identification is the proximal objective for the proper, closed, convex function $2\lambda \mathrm{\mid }\cdot \mathrm{\mid }$ with parameter $t\mathrm{/}2$. By [F2], its unique minimizer is $S_{(t\mathrm{/}2)(2\lambda )}(d)=S_{t\lambda }(d)$. This and $a=m$ give the displayed vector. The objective is strictly convex because of its positive quadratic term, consistent with uniqueness in [F3].

Under the scalar/one-coordinate identification [F2], $f(x)=x^2\mathrm{/}4$ is convex and continuously differentiable, since $f((1-\alpha )x+\alpha z)=(1-\alpha )f(x)+\alpha f(z)-\frac{\alpha (1-\alpha )}{4}(x-z{)}^2(0\le \alpha \le 1)\mathrm{.}$ Also $f^{\mathrm{\prime }}(x)=x\mathrm{/}2$, so its gradient is $1\mathrm{/}2$-Lipschitz and $L=1$ is valid. The zero function $g$ has nonempty domain, is convex, and has epigraph ${\mathbb{R}}^1\times [0,+\mathrm{\infty })$, which is closed; hence it is proper, closed and convex by [F3]. Its proximal map is the identity, so $T_1(y)=y-\mathrm{\nabla }f(y)=y\mathrm{/}2$. Starting from $t_1=1,y_1=x_0=1$, recurrence [F1] gives $x_1=1\mathrm{/}2$, $x_2=1\mathrm{/}4$, and $t_2=\frac{1+\sqrt{5}}{2},t_3=\frac{1+\sqrt{1+4t_2^2}}{2},t_4=\frac{1+\sqrt{1+4t_3^2}}{2},t_5=\frac{1+\sqrt{1+4t_4^2}}{2}\mathrm{.}$ The first interval follows from ${2.2360}^2<5<{2.2361}^2$. For the next three, substituting the already established intervals gives radicands $1+4t_2^2$, $1+4t_3^2$, and $1+4t_4^2$ in $(11.471696,11.472991)$, $(20.244014,20.249279)$, and $(31.228004,31.272004)$ respectively. The endpoint squares ${3.3868}^2<11.471696$, ${3.3874}^2>11.472991$, ${4.498}^2<20.244014$, ${4.502}^2>20.249279$, ${5.586}^2<31.228004$, and ${5.594}^2>31.272004$ then give $1.6180<t_2<1.6181$, $2.1934<t_3<2.1937$, $2.749<t_4<2.751$, and $3.293<t_5<3.297$.

The momentum coefficients satisfy $0.281<(t_2-1)\mathrm{/}{t}_3<0.283$, $0.433<(t_3-1)\mathrm{/}{t}_4<0.435$, and $0.529<(t_4-1)\mathrm{/}{t}_5<0.533$: for example, the bounding cross-products are $0.281(2.1937)=0.6164297<0.6180$, $0.283(2.1934)=0.6207322>0.6181$, $0.433(2.751)=1.191183<1.1934$, $0.435(2.749)=1.195815>1.1937$, $0.529(3.297)=1.744113<1.749$, and $0.533(3.293)=1.755169>1.751$. Substitution into $x_3=\frac{1}{8}(1-(t_2-1)\mathrm{/}{t}_3)$ gives $0.0896<x_3<0.0899$. Then $x_4=\frac{1}{2}[x_3+\frac{t_3-1}{t_4}(x_3-1\mathrm{/}4)]$ lies between $\frac{1}{2}[(1+0.435)(0.0896)-0.435\mathrm{/}4]=0.009913$ and $\frac{1}{2}[(1+0.433)(0.0899)-0.433\mathrm{/}4]=0.01028835$, so $0.0099<x_4<0.0103$. Finally $x_5=\frac{1}{2}[x_4+\frac{t_4-1}{t_5}(x_4-x_3)]$ and endpoint monotonicity gives $\frac{1}{2}[(1+0.533)(0.0099)-0.533(0.0899)]=-0.01637<x_5<\frac{1}{2}[(1+0.529)(0.0103)-0.529(0.0896)]=-\mathrm{0.01582485.}$ Thus $-0.0164<x_5<-0.0158$.

The intervals imply $\mathrm{\mid }{x}_5\mathrm{\mid }>0.0158>0.0103>\mathrm{\mid }{x}_4\mathrm{\mid }$. Since $f(x)=x^2\mathrm{/}4$ is strictly increasing as a function of $\mathrm{\mid }x\mathrm{\mid }$, $f(x_5)>f(x_4)$.

Here $f(\theta )=\frac{1}{2}\mathrm{\parallel }y-X\theta {\mathrm{\parallel }}_2^2$ is a convex continuously differentiable quadratic: for $0\le \alpha \le 1$, $f((1-\alpha )u+\alpha v)=(1-\alpha )f(u)+\alpha f(v)-\alpha (1-\alpha )\mathrm{\parallel }X(u-v){\mathrm{\parallel }}_2^2\mathrm{/}2.$ Its gradient is $\mathrm{\nabla }f(\theta )=H\theta -X^{T}y$ with $H=X^{T}X=\left(\begin{array}{cc}2& 1\\ 1& 1\end{array}\right)$. For $h=(a,b)$, $\mathrm{\parallel }Hh{\mathrm{\parallel }}_2^2=(2a+b{)}^2+(a+b{)}^2=5a^2+6ab+2b^2\le 8a^2+5b^2\le 8\mathrm{\parallel }h{\mathrm{\parallel }}_2^2,$ using $6ab\le 3(a^2+b^2)$. Thus $\mathrm{\nabla }f$ is $\sqrt{8}$-Lipschitz and $L=3$ is valid. The nonsmooth term $g=(1\mathrm{/}5)\mathrm{\parallel }\cdot {\mathrm{\parallel }}_1$ is proper, closed and convex by [F3]. Also $X^{T}y=(2,1)$, so $\mathrm{\nabla }f({\theta }_0)=(-2,-1)$ and ${\theta }_0-\mathrm{\nabla }f({\theta }_0)\mathrm{/}3=(2\mathrm{/}3,1\mathrm{/}3)$.

The nonsmooth term is $g=(1\mathrm{/}5)\mathrm{\parallel }\cdot {\mathrm{\parallel }}_1$, and the proximal parameter is $1\mathrm{/}3$, so its soft-threshold level is $(1\mathrm{/}3)(1\mathrm{/}5)=1\mathrm{/}15$. Applying [F3] to $(2\mathrm{/}3,1\mathrm{/}3)$ gives $(2\mathrm{/}3-1\mathrm{/}15,1\mathrm{/}3-1\mathrm{/}15)=(3\mathrm{/}5,4\mathrm{/}15)$.

The function is a continuously differentiable convex quadratic, with $f((1-\alpha )x+\alpha z)=(1-\alpha )f(x)+\alpha f(z)-\frac{\alpha (1-\alpha )}{2}\mathrm{\parallel }x-z{\mathrm{\parallel }}_2^2(0\le \alpha \le 1)\mathrm{.}$ Its gradient is $\mathrm{\nabla }f(x)=(x_1+2,x_2)$, whose Lipschitz constant is $1$, hence $L=2$ is valid. At $x_0$, the unprojected point is $x_0-\mathrm{\nabla }f(x_0)\mathrm{/}2=(-1,0)$; coordinatewise projection onto $C$ gives $x_1=(0,0)$. Repeating the same computation shows the iterate remains there.

For every $z\in C$, $⟨(-2,0),z-(0,0)⟩=-2z_1\le 0$, hence $(-2,0)\in N_C(0)$ by the outward-cone definition. Equivalently, write $C$ as $-x_i\le 0$ with $G=-I,d=0$; at $x_{\ast }=0$, $\lambda =(2,0)\ge 0$ has zero complementarity and $\mathrm{\nabla }f(0)+G^T\lambda =(2,0)-(2,0)=0$. By [F3], this KKT tuple certifies global minimality and the projected-gradient fixed point.