= Gradient descent
{title2=$x_{k+1}=x_k-\eta\nabla f(x_k)$}
{wiki}
= Steepest descent method
{synonym}
<Gradient descent> is an <iterative method> for minimizing a <differentiable function> $f$: choose an initial <vector> $x_0$ and repeatedly move opposite its <gradient>.<Convex Optimization by Stephen Boyd and Lieven Vandenberghe>[§9.3, p. 466, Algorithm 9.3: negative-gradient direction and a separately chosen step size]{ref}
With a fixed positive <step size> $\eta$, the update is
$$
x_{k+1}=x_k-\eta\nabla f(x_k),\qquad k=0,1,2,\ldots.
$$
The direction and the <step size> play different roles: the <gradient> supplies local information about increase, while $\eta$ determines how far that information is trusted. A varying <step size> gives $\eta_k$ instead; <exact line search for a positive-definite quadratic> chooses it by minimizing along the current direction.
Why is this the steepest direction? For a unit <vector> $v$ in the <Euclidean norm>, the <directional derivative> is $\langle\nabla f(x),v\rangle$. The <Cauchy-Schwarz inequality> bounds it below by $-\|\nabla f(x)\|_2$, attained by $v=-\nabla f(x)/\|\nabla f(x)\|_2$ when the <gradient> is nonzero. This is steepest descent relative to the <Euclidean norm>; changing the <norm> can change the steepest direction. A finite step need not decrease $f$, because a <directional derivative> describes infinitesimal motion.
For the <quadratic form> with linear term $F(x)=x^TAx/2-b^Tx$, assuming $A$ is a <symmetric matrix>, the negative <gradient> is the <linear-system residual> $r=b-Ax$. Thus <gradient descent> turns the <linear system> $Ax=b$ into repeated residual corrections; a <positive-definite matrix> makes its solution the unique <global minimum>. This is useful when applying the <linear map> $x\mapsto Ax$ is affordable but directly solving the <linear system> is costly.
The attraction is that a <gradient> evaluation gives an entire update without solving a new <linear system>. The difficulty is choosing a <step size> that progresses along gently curved directions without overshooting steep ones. <Fixed-step gradient descent on a positive-definite quadratic> makes this tension exact: every <eigenvector> direction has its own multiplier, determined by its <eigenvalue>. The resulting <condition number> dependence explains why a narrow valley can slow even an inexpensive <iterative method>.
The simplicity of the <gradient> update and its sensitivity to the <condition number> of the <Hessian matrix> are central practical features.<Convex Optimization by Stephen Boyd and Lieven Vandenberghe>[§9.3.1, pp. 466–468, and §9.3.2, p. 475, Conclusions: convergence and conditioning]{ref}
Back to article page
