[proofplan]
We find the minimizer of $\alpha \mapsto F(x + \alphad)$ by expanding this one-variable quadratic function of $\alpha$, differentiating, and setting the derivative to zero. The expansion uses the identity $\nabla F(x) = Ax - b = -r$, and the resulting first-order condition gives $\alpha = \langle r, d \rangle / \langle d, Ad \rangle$.
[/proofplan]
[step:Expand $F(x + \alphad)$ as a quadratic polynomial in $\alpha$]
Substituting $x + \alphad$ into $F(y) = \frac{1}{2}\langle y, Ay \rangle - \langle b, y \rangle$:
\begin{align*}
F(x + \alphad) &= \frac{1}{2}\langle x + \alphad, A(x + \alphad) \rangle - \langle b, x + \alphad \rangle \\
&= \frac{1}{2}\langle x, Ax \rangle + \alpha\langle d, Ax \rangle + \frac{\alpha^2}{2}\langle d, Ad \rangle - \langle b, x \rangle - \alpha\langle b, d \rangle,
\end{align*}
where the cross term uses the symmetry of $A$: $\frac{1}{2}\langle x, A(\alphad) \rangle + \frac{1}{2}\langle \alphad, Ax \rangle = \alpha\langle d, Ax \rangle$. Grouping:
\begin{align*}
F(x + \alphad) = F(x) + \alpha\langle Ax - b, d \rangle + \frac{\alpha^2}{2}\langle d, Ad \rangle = F(x) - \alpha\langle r, d \rangle + \frac{\alpha^2}{2}\langle d, Ad \rangle,
\end{align*}
using $r = b - Ax$.
[/step]
[step:Minimize over $\alpha$ by setting the derivative to zero]
The function $\alpha \mapsto F(x + \alphad)$ is a quadratic polynomial in $\alpha$ with positive leading coefficient $\frac{1}{2}\langle d, Ad \rangle > 0$ (since $A$ is positive definite and $d \neq 0$). Differentiating with respect to $\alpha$ and setting the result to zero:
\begin{align*}
\frac{d}{d\alpha} F(x + \alphad) = -\langle r, d \rangle + \alpha\langle d, Ad \rangle = 0.
\end{align*}
Solving for $\alpha$:
\begin{align*}
\alpha = \frac{\langle r, d \rangle}{\langle d, Ad \rangle}.
\end{align*}
Since the quadratic has a positive leading coefficient, this critical point is a global minimum. The denominator $\langle d, Ad \rangle > 0$ by positive definiteness of $A$ and the assumption $d \neq 0$.
[guided]
The function $\varphi(\alpha) := F(x + \alphad)$ is a one-dimensional quadratic:
\begin{align*}
\varphi(\alpha) = \underbrace{F(x)}_{\text{constant}} - \underbrace{\langle r, d \rangle}_{\text{linear coefficient}}\,\alpha + \underbrace{\frac{1}{2}\langle d, Ad \rangle}_{\text{positive quadratic coefficient}}\,\alpha^2.
\end{align*}
This is a parabola opening upward (since $\langle d, Ad \rangle > 0$ by positive definiteness of $A$ and $d \neq 0$), so it has exactly one minimizer. Setting $\varphi'(\alpha) = 0$:
\begin{align*}
-\langle r, d \rangle + \alpha\langle d, Ad \rangle = 0 \implies \alpha = \frac{\langle r, d \rangle}{\langle d, Ad \rangle}.
\end{align*}
Geometrically, this "exact line search" finds the point along the ray $x + \alphad$ where the quadratic surface $F$ achieves its minimum. The formula has a natural interpretation: the numerator $\langle r, d \rangle$ measures how much the residual points along the search direction (the directional derivative of $-F$), and the denominator $\langle d, Ad \rangle$ measures the curvature of $F$ along that direction. A larger curvature means a smaller step.
[/guided]
[/step]
