= Quadratic minimization along a line
{title2=$\alpha_*=(p^T(b-Ax))/(p^TAp)$}
For a <symmetric positive-definite matrix> $A$ and a nonzero <vector> $p$, minimizing $f(x+\alpha p)$ over $\alpha\in\mathbb R$, where $f(x)=x^TAx/2-b^Tx$, gives the displayed optimizer. Put $r=b-Ax$. Expansion gives $f(x+\alpha p)=f(x)-\alpha p^Tr+\alpha^2p^TAp/2$, a strictly convex <quadratic function> of $\alpha$. At its minimum,
$$
f(x+\alpha_*p)-f(x)=-\frac{(p^Tr)^2}{2p^TAp}.
$$
Strict decrease is therefore equivalent to $p^Tr\ne0$. This is minimization over a full line, so the optimizer can be negative. For an <exact line search> restricted to a nonnegative <step size>, the optimizer is instead $\max(0,\alpha_*)$.
Back to article page
