Mathematics Primer

This guide accompanies Real Analysis Review. It supplies the complete definitions, proofs and computations behind the shorter handout. Start with quadratic coordinates, sets and sequences, continuity and derivatives, convexity, or Taylor and finite differences. Linear algebra definitions and factorization diagnostics have their primary home in Linear Algebra Review and SciPy Basics.

Quadratic objectives in eigenvector coordinates¶

For a real symmetric $\mathbf B\in\mathbb R^{n\times n}$, consider

The symmetric spectral theorem gives $\mathbf B=\mathbf V\boldsymbol\Lambda\mathbf V^{\mathsf T}$, with $\mathbf V^{\mathsf T}\mathbf V=\mathbf I$ and $\boldsymbol\Lambda=\operatorname{diag}(\lambda_1,\ldots,\lambda_n)$. Define the coordinates $\mathbf z=\mathbf V^{\mathsf T}\mathbf x$ and the transformed function $q(\mathbf z)=f(\mathbf V\mathbf z)$. The function value is preserved; the coordinate vector changes. Write $\bar{\mathbf a}=\mathbf V^{\mathsf T}\mathbf a$. Then

Each column of $\mathbf V$ supplies a coordinate direction. Diagonal $\boldsymbol\Lambda$ removes cross terms. See Biegler (2010), §2.2.2, Eqs.(2.8)–(2.10), pp.22–23.

Stationary points and square completion¶

Stationarity requires $\bar a_j+\lambda_j z_j=0$ for every $j$. Let $J_0=\{j:\lambda_j=0\}$. A stationary point exists exactly when $\bar a_j=0$ for every $j\in J_0$. In that case

Setting the free coordinates to zero selects one representative; it does not establish uniqueness. If a null coordinate has $\bar a_j\ne0$, moving along that coordinate makes the affine term arbitrarily positive or negative.

For every $j\notin J_0$, the full square completion is

Consequently, with $\bar c=c-\sum_{j\notin J_0}\bar a_j^2/(2\lambda_j)$,

This formula also describes the case with no stationary point: the null-coordinate linear term remains. It avoids dividing by a zero eigenvalue.

Curvature and global classification¶

The exact eigenvalue signs give the following cases. For a singular matrix, the compatibility condition is $\bar a_j=0$ on $J_0$.

A stationary point is a saddle here when arbitrarily close points have both larger and smaller values. In a compatible singular case, its family has dimension $\dim\operatorname{Null}(\mathbf B)$. These conclusions follow directly from the square completion. See Biegler (2010), pp.23–25.

All four pictured objectives have $\mathbf a=\mathbf0$ and $c=0$; their eigenvectors are rotated by 30 degrees. They compare signs, while the separate conditioning picture compares positive eigenvalue magnitudes. For a positive-definite quadratic, contour semiaxes at a fixed positive objective increment are proportional to $1/\sqrt{\lambda_j}$.

Numerical analysis and plotting helper¶

The helper below requires an explicitly symmetric real matrix and uses the symmetric eigensolver. Its relative threshold identifies numerically small eigenvalues. It analyzes the thresholded model and prints the residual in the original stored system. Neither thresholding nor a small residual proves the exact rank of a nearly singular matrix. If the thresholded stationarity equations are incompatible, the code draws the surface about a plotting center and does not mark that center as a stationary point.

Example 2.8 in Biegler (2010)¶

Activity 1¶

Classify the stationary point for $f(\mathbf{x}) = x_1 + x_2$.

Activity 2¶

Classify the stationary point for $f(\mathbf{x}) = x_1^2 + x_2^2 - 2x_1 x_2 + 0 x_1 - 0 x_2 + 3$.

Hint: $\mathbf{B}$ needs to be symmetric.

Sets, sequences, regularity and convexity¶

The definitions below use finite-dimensional Euclidean spaces and the 2-norm unless another norm is specified. The full proofs support the handout activities.

Balls, neighborhoods, interior, boundary and closure¶

For $\bar{\mathbf x}\in\mathbb R^n$ and $r>0$, the open and closed balls are

A set $S$ is open if every $\mathbf x\in S$ has a ball $\mathcal B(\mathbf x,r)\subseteq S$. A neighborhood of a point is an open set containing that point. In particular, an open ball is a neighborhood; a neighborhood need not be a ball.

For $S\subseteq\mathbb R^n$:

• $\mathbf x$ is an interior point if some ball about it is contained in $S$; the interior is $\operatorname{int}S$.

• $\mathbf x$ is a boundary point if every ball about it meets both $S$ and its complement; the boundary is $\partial S$.

• $\mathbf x$ is in the closure $\operatorname{cl}S$ if every ball about it meets $S$.

Thus $\operatorname{cl}S=S\cup\partial S$. The interior is the largest open subset of $S$; the closure is the smallest closed set containing $S$. A boundary point need not belong to $S$: for $S=(0,1)$, the boundary is $\{0,1\}$ and the closure is $[0,1]$.

See Nocedal & Wright (2006), pp.620–621. The empty set and the whole space are both open and closed; these properties are not opposites.

Sequences, subsequences and closed sets¶

A sequence assigns a point $\mathbf x^k\in\mathbb R^n$ to each positive integer $k$. It converges to $\bar{\mathbf x}$ if

A subsequence has indices $k_1<k_2<\cdots$. A limit point of a sequence is the limit of one of its subsequences. A convergent sequence has exactly one limit point. The nonconvergent sequence $\mathbf x^k=((-1)^k,1/k)^{\mathsf T}$ has the two limit points $(1,0)^{\mathsf T}$ and $(-1,0)^{\mathsf T}$, obtained from the even and odd subsequences. See Nocedal & Wright (2006), pp.617–618.

A set is closed if its complement is open. Equivalently, it contains every limit of every convergent sequence of its points.

Proof that closed sets contain such limits. Suppose $\mathbf x^k\in S$, $\mathbf x^k\to\bar{\mathbf x}$, and $\bar{\mathbf x}\notin S$. The open complement contains a ball $\mathcal B(\bar{\mathbf x},r)$ disjoint from $S$. Convergence puts every sufficiently late iterate in the smaller ball of radius $r/2$, hence in both $S$ and its complement, a contradiction. Therefore $\bar{\mathbf x}\in S$.

Converse. If $\bar{\mathbf x}\in\operatorname{cl}S$, choose $\mathbf x^k\in S\cap\mathcal B(\bar{\mathbf x},1/k)$. This sequence converges to $\bar{\mathbf x}$. A set containing all such limits therefore contains its closure and is closed. This also proves the sequence characterization of closure. See Nocedal & Wright (2006), pp.620–621.

Bounded and compact sets¶

$S\subseteq\mathbb R^n$ is bounded if some $M>0$ satisfies $\lVert\mathbf x\rVert\le M$ for every $\mathbf x\in S$. It is compact if every sequence in $S$ has a subsequence converging to a point of $S$. In $\mathbb R^n$, compactness is equivalent to being closed and bounded. The finite-dimensional hypothesis matters. See Nocedal & Wright (2006), pp.620–621.

The four sets below are subsets of $\mathbb R^2$. Convexity means that the entire segment between any two member points remains in the set; its formal definition and proof examples appear below.

For the annulus, $(1,0)^{\mathsf T}$ and $(-1,0)^{\mathsf T}$ belong to the set, but their midpoint does not. For the open disk, $(1-1/k,0)^{\mathsf T}$ approaches a missing boundary point. In the quadrant, $(k,0)^{\mathsf T}$ has no convergent subsequence.

Weierstrass theorem and a minimizing sequence¶

A continuous real-valued function on a nonempty compact set $S\subseteq\mathbb R^n$ attains a minimum and a maximum. See Rapcsák, “Smooth Nonlinear Nonconvex Optimization,” in Encyclopedia of Optimization, 2nd ed. (2009), p.3623. The cited statement gives the minimum; applying it to the negative function gives the maximum.

Here is the complete sequential argument. Write $m=\inf_{\mathbf x\in S}\phi(\mathbf x)$.

1. If $m$ is finite, choose $\mathbf x^k\in S$ with $m\le\phi(\mathbf x^k)<m+1/k$. If $m=-\infty$, choose $\phi(\mathbf x^k)<-k$. These choices are permitted by the definition of infimum.

2. Compactness supplies a subsequence $\mathbf x^{k_i}\to\hat{\mathbf x}\in S$. Continuity implies $\phi(\mathbf x^{k_i})\to\phi(\hat{\mathbf x})$, a finite real number.

3. The $m=-\infty$ alternative contradicts that finite limit. Hence $m$ is finite, and the same subsequence has function values tending to $m$. Uniqueness of a real limit gives $\phi(\hat{\mathbf x})=m$.

The maximum follows from the minimum of $-\phi$. This is a compactness-plus-continuity proof, not a derivative test.

Without the hypotheses the conclusion can fail. The function $\phi(x)=x$ on $(0,1)$ has no minimum; $e^x$ on $\mathbb R$ has infimum zero but no minimizer. Compactness alone is insufficient: on $[0,1]$, define $\phi(0)=1$ and $\phi(x)=x$ for $x>0$. Its infimum is zero, is not attained, and the function is discontinuous at zero.

Limits and continuity on a domain¶

Let $\phi:D\subseteq\mathbb R^n\to\mathbb R$. At an accumulation point $\bar{\mathbf x}$ of $D$, the limit is $\ell$ if

The function is continuous at $\bar{\mathbf x}\in D$ if the same implication, with $\ell=\phi(\bar{\mathbf x})$, holds for all $\mathbf x\in D$ with $\|\mathbf x-\bar{\mathbf x}\|<\delta$. It is continuous on $D$ when it is continuous at every point of $D$. The domain is part of the definition. See Biegler (2010), Def.2.9, p.25; Nocedal & Wright (2006), Eq.(A.38), p.623.

The formula $1/x$ is continuous on $\mathbb R\setminus\{0\}$, and in particular on $(0,\infty)$. It is undefined at zero. Since $|1/x|$ is unbounded near zero, no assigned finite value at zero gives a continuous extension. This does not make the function discontinuous at a point outside its stated domain.

Lipschitz continuity and derivative bounds¶

$\phi:D\to\mathbb R$ is Lipschitz continuous on $N\subseteq D$ if one finite constant $L>0$ satisfies

The constant is selected before the pair of points. It may depend on the set $N$. Local Lipschitz continuity at an interior point means that such a neighborhood $N$ exists. This uses Nocedal & Wright (2006), Eq.(A.42), p.624; the quantifier order in Biegler’s Def.2.10, p.25, does not impose a single constant on the set.

The continuous function $\sqrt{x}$ is not Lipschitz on $[0,\infty)$. Setting $x=0$ and $y=a>0$ would require $\sqrt a\le La$, hence $L\ge1/\sqrt a$ for every $a>0$, which is impossible. On $[1,\infty)$,

Thus $L=1/2$ works there. The derivative $1/(2\sqrt{x})$ becomes unbounded toward zero, consistent with the first result.

More generally, a differentiable scalar function with $\|\nabla\phi\|\le L$ along every segment in a convex set is Lipschitz there, provided the function is continuous on each segment and differentiable in its interior. Apply the scalar mean value theorem along the segment and Cauchy–Schwarz. Conversely, where an $L$-Lipschitz function is differentiable, taking directional limits gives $|\nabla\phi^{\mathsf T}\mathbf p|\le L\|\mathbf p\|$. Lipschitz continuity does not require differentiability everywhere; $|x|$ is an example.

Derivatives, gradients, Hessians and level sets¶

For a scalar function, $\phi'(a)=\lim_{h\to0}[\phi(a+h)-\phi(a)]/h$ when the limit exists; the second derivative is the derivative of $\phi'$. For $\phi:D\subseteq\mathbb R^n\to\mathbb R$ at an interior point, the coordinate partial derivatives are

The gradient is the column of first partials and the Hessian collects second partials:

Differentiability at $\mathbf x$ means that the linear model has a remainder negligible relative to the step:

Existence of all coordinate partials alone does not imply this property. A function is $C^1$ if its first partials exist and are continuous, and $C^2$ if its second partials exist and are continuous. For a differentiable function, the two-sided directional derivative is

A real $C^2$ function has a symmetric Hessian. This permits real eigenvalues, an orthogonal eigenbasis and symmetric factorizations. Cholesky additionally requires positive definiteness; symmetry alone is insufficient. Symmetry also permits storing one triangle, containing $n(n+1)/2$ entries rather than $n^2$; the factor tends to one half as $n$ grows. See Biegler (2010), Defs.2.11–2.12, pp.25–27; Nocedal & Wright (2006), pp.626–628.

For $\alpha\in\mathbb R$, a level set is $\{\mathbf x\in D:\phi(\mathbf x)=\alpha\}$ and a sublevel set is $\{\mathbf x\in D:\phi(\mathbf x)\le\alpha\}$. At a regular point with nonzero gradient, differentiate $\phi(\mathbf x(t))=\alpha$ to obtain $\nabla\phi^{\mathsf T}\mathbf x'(t)=0$. This proves the normal-direction statement; a zero gradient does not specify a normal direction.

Mean value and implicit function theorems¶

If $\phi$ is continuous on $[a,b]$ and differentiable on $(a,b)$, with $a<b$, then

For a $C^1$ scalar-valued function on a neighborhood of a segment from $\mathbf x$ to $\mathbf x+\mathbf p$, apply this theorem to $g(t)=\phi(\mathbf x+t\mathbf p)$. Then $g'(t)=\nabla\phi(\mathbf x+t\mathbf p)^{\mathsf T}\mathbf p$. See Nocedal & Wright (2006), Eqs.(A.54)–(A.55), p.629.

There need not be one common mean-value point for a vector-valued function. For $\mathbf g(t)=(t^2,t^3)^{\mathsf T}$ on $[0,1]$, the two components would require $2\xi=1$ and $3\xi^2=1$, respectively. Those values of $\xi$ differ. The integral form used for gradients below avoids that claim.

Implicit function theorem. Let $\mathbf h:\mathbb R^n\times\mathbb R^m\to\mathbb R^n$ be $C^1$ near $(\mathbf z^*,\mathbf0)$, with $\mathbf h(\mathbf z^*,\mathbf0)=\mathbf0$ and nonsingular $\nabla_{\mathbf z}\mathbf h$ there. Then product neighborhoods exist on which the nearby roots are exactly the graph of a unique $C^1$ function $\mathbf z(\mathbf t)$ with $\mathbf z(\mathbf0)=\mathbf z^*$. Using the course’s derivative arrays, whose row indexes the input component,

The dimensions are $n\times n$, $m\times n$ and $m\times n$, respectively; evaluate the derivative arrays at $(\mathbf z(\mathbf t),\mathbf t)$. The formula follows by differentiating $\mathbf h(\mathbf z(\mathbf t),\mathbf t)=\mathbf0$. See Nocedal & Wright (2006), Thm.A.2, p.631.

For $h(z,t)=z^2+t-1$ near $(1,0)$, $h_z=2\ne0$, so the local branch is $z(t)=\sqrt{1-t}$ and $z'(0)=-h_t/h_z=-1/2$. There is another branch near $(-1,0)$; local uniqueness near $z=1$ does not assert a unique root globally. At $(0,1)$ the nonsingularity hypothesis fails.

Convex combinations, hulls, half-spaces and polyhedra¶

A convex combination of $\mathbf x_1,\ldots,\mathbf x_m$ is $\sum_i\theta_i\mathbf x_i$ with $\theta_i\ge0$ and $\sum_i\theta_i=1$. Their convex hull is the set of all these combinations. A set $S$ is convex if

The convex hull is convex: a convex combination of two combinations has nonnegative coefficients summing to one. Any convex set containing all the original points contains every finite convex combination, by induction. Hence the hull is the smallest convex set containing them. See Nocedal & Wright (2006), p.621; Nesterov (2018), pp.141–142.

For $\mathbf a\ne\mathbf0$, a hyperplane is $\{\mathbf x:\mathbf a^{\mathsf T}\mathbf x=b\}$. The two closed half-spaces use $\le b$ and $\ge b$. The normal $\mathbf a$ is perpendicular to the hyperplane. A polyhedron is an intersection of finitely many half-spaces and hyperplanes, equivalently $\{\mathbf x:\mathbf A\mathbf x\le\mathbf b\}$ after writing an equality as two inequalities. A polyhedron can be empty or unbounded.

Proof for a half-space. If $\mathbf a^{\mathsf T}\mathbf x_a\le b$ and $\mathbf a^{\mathsf T}\mathbf x_b\le b$, then

A hyperplane uses the same computation with equality. Applying the inequality row by row proves the polyhedron is convex. Lecture 2 is the primary handout home for the half-space and intersection convexity proofs. The existing Introduction to Constrained Nonlinear Optimization guide collects the general intersection proof and convex-program formulation checklist. See Nocedal & Wright (2006), p.8; Nesterov (2018), Def.3.1.4, p.159.

Rays and cones¶

Using the positive-scaling convention, the ray through $\mathbf d\ne\mathbf0$ is $\{\tau\mathbf d:\tau>0\}$. A cone $C$ satisfies

This convention does not require the origin. A convex cone is also a convex set. The generated set $\{\sum_i\tau_i\mathbf d_i:\tau_i\ge0\}$ contains the origin and is a convex cone: nonnegative scaling and convex combinations preserve nonnegative coefficients. The set $\{(x_1,x_2):x_1\ge0\text{ or }x_2\ge0\}$ is a cone but is not convex; the points $(1,-2)$ and $(-2,1)$ have a midpoint outside it. See Nocedal & Wright (2006), Eq.(A.36) and pp.621–622.

A convex half-space need not be a cone¶

Convex combinations keep a point in a half-space, but positive scaling can leave it. For

we have $\mathbf a^{\mathsf T}\mathbf x_b=3\le4$ for $\mathbf a=(1,2)^{\mathsf T}$, whereas $\mathbf a^{\mathsf T}(2\mathbf x_b)=6>4$. Thus $H$ is convex and is not a cone.

More generally, for $\mathbf a\ne\mathbf0$, the closed half-space $H_b=\{\mathbf x:\mathbf a^{\mathsf T}\mathbf x\le b\}$ is a cone under the positive-scaling definition exactly when $b=0$. If $b=0$, multiplying the inequality by any $\tau>0$ preserves it. If $b\ne0$, choose the boundary point $\mathbf x_b=b\mathbf a/\|\mathbf a\|_2^2$. For $b>0$, $2\mathbf x_b$ has functional value $2b>b$; for $b<0$, $\mathbf x_b/2$ has value $b/2>b$. Either case violates positive-scaling closure. This argument also applies under the convention that permits a cone to exclude the origin.

Convex functions and the first-order characterization¶

Let $D\subseteq\mathbb R^n$ be convex. A function $\phi:D\to\mathbb R$ is convex if for all $\mathbf x_a,\mathbf x_b\in D$ and $\theta\in(0,1)$,

It is strictly convex if the inequality is strict whenever $\mathbf x_a\ne\mathbf x_b$. On an open convex domain, a differentiable function is convex exactly when

Strict convexity is equivalent to the strict first-order inequality for distinct points. The excluded equal-point case matters: equality always holds at $\mathbf y=\mathbf x$. See Biegler (2010), Def.2.13, p.27, with the distinct-point qualification in Nocedal & Wright (2006), p.8; Nesterov (2018), Thm.2.1.2, pp.62–63.

First-order inequality implies the chord inequality¶

Set $\mathbf x_c=\theta\mathbf x_a+(1-\theta)\mathbf x_b$. Apply the first-order inequality twice, both times based at $\mathbf x_c$:

Multiply these inequalities by $\theta$ and $1-\theta$, both positive, and add. The gradient term is zero because

The remaining inequality is precisely the chord inequality. Strict first-order inequalities give the strict chord inequality for distinct endpoints.

Chord inequality implies the first-order inequality¶

Fix $\mathbf x,\mathbf y\in D$ and write $\mathbf p=\mathbf y-\mathbf x$.

1. Convexity gives $\phi(\mathbf x+\theta\mathbf p)\le(1-\theta)\phi(\mathbf x)+\theta\phi(\mathbf y)$.

2. Subtract $\phi(\mathbf x)$ and divide by the positive $\theta$:

3. Let $\theta\downarrow0$. Differentiability at $\mathbf x$ makes the left side tend to $\nabla\phi(\mathbf x)^{\mathsf T}\mathbf p$. A weak inequality survives the limit, giving the first-order inequality. Continuity of the gradient is not needed for this step.

A strict inequality does not automatically survive a limit. For the strict result, first obtain the weak supporting inequality just proved. At a distinct pair, strict convexity and that support bound imply

Subtract and divide by $\theta>0$ to get the strict first-order inequality. These arguments also explain why negating a first-order inequality at one pair of points does not justify applying the failure at two prescribed directions.

Hessians, strong convexity and quasi-convexity¶

For a $C^2$ function on an open convex domain, convexity is equivalent to $\nabla^2\phi(\mathbf x)\succeq0$ everywhere. Necessity follows by applying the supporting inequality to $\mathbf x\pm h\mathbf p$, adding, dividing by $h^2$ and taking $h\to0$. This gives $\mathbf p^{\mathsf T}\nabla^2\phi(\mathbf x)\mathbf p\ge0$ for every $\mathbf p$.

For sufficiency, the exact integral Taylor remainder is

A positive-semidefinite Hessian makes the integral nonnegative. Pointwise positive definiteness makes it positive for $\mathbf p\ne\mathbf0$, so it is sufficient for strict convexity. It is not necessary: $x^4$ is strictly convex but has second derivative zero at zero.

A differentiable function on a convex domain is m-strongly convex, $m>0$, if

for every segment in its domain. In the $C^2$ case this is equivalent to the uniform bound $\nabla^2\phi(\mathbf x)\succeq m\mathbf I$. A positive-definite Hessian at every point alone does not supply one uniform $m$. For example, $e^x$ has positive second derivative everywhere on $\mathbb R$, but the infimum of its second derivative is zero as $x\to-\infty$. See Nesterov (2018), Def.2.1.3 and Thm.2.1.11, pp.74–75; this corrects the pointwise-Hessian condition in Biegler’s Def.2.13.

For $\phi(x)=x^4$, $\phi'(x)=4x^3$, $\phi''(x)=12x^2$, and

A function is quasi-convex if each sublevel set is convex. Every convex function is quasi-convex: if $\phi(\mathbf x_a),\phi(\mathbf x_b)\le\alpha$, convexity yields

See Nesterov (2018), Lemma2.2.5, p.101. The converse fails. For $\phi(x)=1-e^{-x^2}$, the sublevel set for $0\le\alpha<1$ is

It is empty for $\alpha<0$ and all of $\mathbb R$ for $\alpha\ge1$. Every case is convex, but $\phi''(x)=(2-4x^2)e^{-x^2}<0$ when $|x|>1/\sqrt2$. In contrast, $x^4-2x^2$ is not quasi-convex: at level $-1/2$ its sublevel set is two disjoint intervals, with $|x|$ between $\sqrt{1-1/\sqrt2}$ and $\sqrt{1+1/\sqrt2}$.

On $\mathbb R$, $x^2$, $x^4$, $x$, and $1-e^{-x^2}$ distinguish the nested classes strongly convex, strictly convex, convex and quasi-convex, respectively.

Order notation and exact Taylor formulas¶

For sequences with $\nu_k\ne0$ eventually, $\eta_k=O(\nu_k)$ means that some finite $C$ bounds $|\eta_k|\le C|\nu_k|$ for every sufficiently large $k$. The notation $\eta_k=o(\nu_k)$ means $\eta_k/\nu_k\to0$. Analogously, as $h\to0$, $r(h)=O(h^p)$ means $|r(h)|\le C|h|^p$ for sufficiently small nonzero $h$; $r(h)=o(h^p)$ means $r(h)/h^p\to0$. For example, $h^2=o(h)$ and $h^2=O(h)$, but $h$ is not $o(h)$. See Nocedal & Wright (2006), pp.631–632.

The relevant limit is usually clear from context: an error $O(h^2)$ concerns $h\to0$, while an operation count $O(n^3)$ concerns $n\to\infty$. Constants and units remain relevant. Order one in $h$ alone does not guarantee three correct digits at $h=10^{-3}$. Convergence-rate definitions belong in the algorithm lectures that use them, rather than another rate table here.

Scalar expansion¶

If $f$ is $C^{r+1}$ near $a$, its finite expansion is

This statement does not assert convergence of an infinite Taylor series to $f$. See LeVeque (2007), §1.1, p.5 and §1.5, p.10.

Scalar-valued multivariate mean-value forms¶

Suppose the entire segment $\mathbf x+t\mathbf p$, $0\le t\le1$, lies in a neighborhood where $f$ is $C^1$. Then some $t_1\in(0,1)$ satisfies

If $f$ is $C^2$ there, some $t_2\in(0,1)$ satisfies

The two points need not be the same. Both statements are exact. To prove them, apply the corresponding one-dimensional theorem to $g(t)=f(\mathbf x+t\mathbf p)$, using $g'(t)=\nabla f^{\mathsf T}\mathbf p$ and $g''(t)=\mathbf p^{\mathsf T}\nabla^2f\,\mathbf p$. See Biegler (2010), Thm.2.14, pp.27–28 and its errata; the extraneous Hessian transpose in the printed formula is removed.

Integral forms¶

Componentwise fundamental theorem of calculus gives the exact vector identity

Integrating the scalar derivative twice also gives

For the first formula, differentiate each component of $\nabla f(\mathbf x+t\mathbf p)$ and integrate from zero to one. For the second, integrate the change in $g'(t)$, then interchange the order over the triangular region $0\le s\le t\le1$. Neither argument asserts a common vector mean-value point.

For the symmetric quadratic, $\nabla f=\mathbf a+\mathbf B\mathbf x$ and $\nabla^2f=\mathbf B$, so the second-order Taylor model is exact with no remainder. The integral of $1-t$ is $1/2$, recovering the quadratic term directly.

Finite differences, truncation and evaluation error¶

Assume $f$ is $C^3$ near $a$ and $h>0$. Forward, backward and central approximations are

Taylor expansion gives $D_+(h)-f'(a)=\tfrac12 f''(a)h+O(h^2)$ and $D_-(h)-f'(a)=-\tfrac12 f''(a)h+O(h^2)$. For central differences, write both expansions before subtracting:

The constant and second-order terms cancel. Thus $f(a+h)-f(a-h)=2f'(a)h+O(h^3)$ and $D_0(h)-f'(a)=O(h^2)$. With the $C^3$ expansion to the cubic term, the leading central error is $f^{(3)}(a)h^2/6+o(h^2)$. See Nocedal & Wright (2006), §8.1, pp.195–197.

Why a smaller step can give a worse derivative¶

If each function evaluation has absolute error bounded by $\eta$, the evaluation contribution is at most $2\eta/h$ for a one-sided formula and $\eta/h$ for central differences, before accounting for arithmetic and argument-rounding errors. Subtracting nearby computed function values can expose those errors. In particular, a floating-point sum $a+h$ can round back to $a$.

A useful scale model is

Differentiate the model to obtain $pC h^{p-1}-D\eta/h^2=0$. The orders are $h_*\sim\eta^{1/2}$ for one-sided differences and $h_*\sim\eta^{1/3}$ for central differences, with best modeled errors of orders $\eta^{1/2}$ and $\eta^{2/3}$. Constants depend on function/derivative scales. When the evaluation scale is order one and $\eta$ is of unit-roundoff size, these suggest steps around 10^-8 and 10^-5.3 in binary64. They are scale estimates, not universal optimal steps or exact measured minima.

For a full gradient in $n$ variables, a reused base value gives $n+1$ evaluations for forward differences; central differences use $2n$. This cost comparison concerns gradients built by finite differences, not every derivative-free algorithm.

Noisy functions and component scaling¶

If simulation or iterative-solve error dominates roundoff, use its evaluation-error scale in the model. Shrinking $h$ below that noise scale can make the derivative less useful. For forward differences, a practical component magnitude is $\sqrt{\eta_{\rm rel}}\max(|x_j|,\operatorname{typ}x_j)$, with a positive typical variable scale supplied by the modeler; the typical scale avoids a zero step at $x_j=0$. A signed perturbation or a different formula may be required at a bound or domain edge. See Dennis & Schnabel (1996), §5.4, Eqs.(5.4.8)–(5.4.10), pp.96–98. The corresponding central scaling has a cube-root dependence under its smooth error model.

Executed experiment¶

The cells below evaluate $f(x)=e^x$ at $a=1$ and $a=10$ with binary64 function calls and arithmetic. The derivative reference $e^a$ is evaluated at 100 decimal digits and checked at 160. Thus the reported error compares the actual stored derivative approximation with the analytic derivative, not with a rounded binary64 reference. The plot is built one curve at a time; the final figure and archived data are also used by the lecture notes.

The step grid is $h=10^{-16},10^{-15.75},\ldots,10^0$, four points per decade including both endpoints. Measured minima are restricted to this finite grid and can vary with the numerical library. The table prints every formula’s minimizing grid step and error for both evaluation points.

Forward Finite Difference¶

Backward Finite Difference¶

Central Finite Difference¶

Read and extend the experiment¶

1. Compare the actual minimizing steps and errors in the table with the order estimates. A grid minimum need not occur at the model’s exact optimum.

2. Read the right-hand slopes from the three curves and compare them with the computed regression slopes. On the left, cancellation and argument rounding produce a jagged branch, not an exact straight line.

3. Compare $a=1$ with $a=10$ in the table. The derivative and function scale grow by $e^9$, so absolute-error statements change even when the formulas have the same truncation orders.

Original test: exponential at 1¶

Use the three rows with a=1 in the executed table. They report the measured minima on this run’s grid. The central formula uses a larger best grid step and achieves a lower absolute error than the one-sided formulas in this example.

Variant: exponential at 10¶

The three a=10 rows are computed by the same function, grid and reference procedure. They replace historical hand-entered guesses. Library changes can alter the final digits and the location of a grid minimum; read the actual output.

Another test function¶

To study a different function, supply both its evaluation routine and its analytic derivative reference. Reusing exp(a) as the reference after changing the function would measure the wrong error. State the function, point, precision, domain and step grid with the results.

Discussion¶

Explain which change would alter the truncation constant, the function-evaluation noise, or the number of evaluations. Use those quantities to select a step range; a single best step is not valid for every function, variable scale or solver tolerance.