= Solution
{c}
The <subgradient inequality> for the <differentiable> <convex function> $f$ gives
$$
\phi(u)=f(u)-f(y)-\nabla f(y)^T(u-y)\geq0\qquad\text{for every }u.
$$
Thus $y$ is a <global minimizer> of $\phi$ with value zero. Subtracting an <affine function> preserves <convexity>.
We must also justify using part (a) for $\phi$, since its <partial derivative> can differ from that of $f$. First show that condition (6) for a singleton block implies the full coordinate <Lipschitz continuity> estimate
$$
|\partial_i f(z+te_i)-\partial_i f(z)|\leq L_i|t|,\qquad z\in\mathbb R^n,\ t\in\mathbb R.
$$
If $\partial_i f(z)\ne0$, choose $\alpha=-t/\partial_i f(z)$ in (6). If it is zero but $\partial_i f(z+te_i)\ne0$, apply the same argument starting at $z+te_i$ and reverse the displacement. If both <partial derivatives> are zero, the estimate is immediate. The availability of all real $\alpha$ in (6) justifies these choices.
Now $\partial_i\phi(z)=\partial_i f(z)-\partial_i f(y)$, so differences of this <partial derivative> along coordinate lines are unchanged. Hence $\phi$ has the same <coordinate Lipschitz continuity> constant $L_i$ and satisfies the singleton version of (6). Apply part (a) to $\phi$ with <step size> $1/L_i$:
$$
\phi\left(x-\frac{\partial_i\phi(x)}{L_i}e_i\right)
\leq\phi(x)-\frac{[\partial_i\phi(x)]^2}{2L_i}.
$$
Combining with its already established nonnegativity proves
$$
\boxed{0\leq\phi\left(x-\frac{\partial_i\phi(x)}{L_i}e_i\right)\leq\phi(x)-\frac{[\partial_i\phi(x)]^2}{2L_i}.}
$$
\b[The coordinate estimate survives subtraction of the supporting <affine function>.] This is the step that allows the arbitrary comparison point $y$ to be exploited in part (c).
Back to article page
