= Solution
Starting from $x_0\in\mathbb R^n$, <gradient descent> repeatedly computes the gradient and updates
$$
x_{k+1}=x_k-\eta\nabla f(x_k),
$$
stopping when the gradient norm, step, or objective decrease is sufficiently small.
The Hessian bounds say that $f$ is $\alpha$-<strongly convex function>[strongly convex] and has $\beta$-<Lipschitz gradient>[smooth gradient]. With $\eta=1/\beta$,
$$
f(x_k)-f(x_*)
\leq
\left(1-\frac{\alpha}{\beta}\right)^k
\bigl(f(x_0)-f(x_*)\bigr).
$$
Thus the iteration count is
$$
O\left(\frac{\beta}{\alpha}\log\frac1\varepsilon\right);
$$
convergence becomes slower linearly with the <condition number> $\kappa=\beta/\alpha$.
For
$$
f(x,y,z)=x^2+100y^2+10000z^2,
$$
the <Hessian matrix> is $\operatorname{diag}(2,200,20000)$, so
$$
\boxed{\kappa=10000}.
$$
Take
$$
\boxed{A=\operatorname{diag}(1,1/10,1/100)}.
$$
Then
$$
(f\circ A)(u,v,w)=u^2+v^2+w^2,
$$
whose Hessian is $2I$ and whose condition number is $1$.
Back to article page
