Quadratic Minimization

We minimize a strictly convex quadratic \(f(\mathbf{x})=\tfrac12(\mathbf{x}-\mathbf{c})^{\mathsf T}Q(\mathbf{x}-\mathbf{c})\), where \(Q\) is symmetric positive definite. Its graph is an upward bowl; the level sets are nested ellipses centred at \(\mathbf{c}\). The default problem has an off-origin centre \(\mathbf{c}=(2,1)\) and a tilted bowl (\(Q=\left[\begin{smallmatrix}3&1\\1&2\end{smallmatrix}\right]\)), so the geometry is visible.

Unconstrained methods

• Gradient descent. \(\mathbf{x}_{k+1}=\mathbf{x}_k-\alpha\,\nabla f(\mathbf{x}_k)\), with \(\nabla f=Q(\mathbf{x}-\mathbf{c})\). The arrow points in the steepest-descent direction \(-\nabla f\); the step size \(\alpha\) controls how far you go. With a fixed \(\alpha\) the path zig-zags across the valley (steepest descent is locally greedy, not globally aimed at \(\mathbf{c}\)). With exact line search \(\alpha_k=\dfrac{\mathbf{g}_k^{\mathsf T}\mathbf{g}_k}{\mathbf{g}_k^{\mathsf T}Q\,\mathbf{g}_k}\) each step is as long as possible along that ray, giving exactly orthogonal successive steps.
• Newton's method. \(\mathbf{x}_{k+1}=\mathbf{x}_k-t\,Q^{-1}\nabla f(\mathbf{x}_k)\). Newton uses the curvature \(Q\) to aim straight at the minimiser. For a quadratic with full step \(t=1\) it lands on \(\mathbf{c}\) in one step — that is the meaning of second-order information.

Stopping criterion

Both methods iterate until the gradient is small: they stop as soon as \(\lVert\nabla f(\mathbf{x}_k)\rVert<\varepsilon\), where \(\varepsilon\) is the stopping tolerance you choose (default \(10^{-3}\)). A looser \(\varepsilon\) stops earlier with a coarser answer; a tighter \(\varepsilon\) runs longer for more accuracy. The dashed line on the convergence plot marks \(\varepsilon\), so you can see exactly when the gradient norm crosses it.

Reading the convergence plot

We plot the gradient norm \(\lVert\nabla f(\mathbf{x}_k)\rVert\) and the optimality gap \(f(\mathbf{x}_k)-f^\star\) on a log scale. A straight downward line means linear convergence; gradient descent's slope is governed by the condition number \(\kappa=\lambda_{\max}/\lambda_{\min}\) (rate \(\approx\big(\tfrac{\kappa-1}{\kappa+1}\big)^2\) per step). Newton drops to machine zero immediately (finite termination on a quadratic).