Appendix: Mathematics Background

This appendix briefly reviews various mathematical concepts used throughout the book.

A.1 Taylor Series Expansion¶

Series expansions are representations of a given function in terms of a series of other (usually simpler) functions. One common series expansion is the Taylor series, which is expressed as a polynomial whose coefficients are based on the derivatives of the original function at a fixed point.

The Taylor series is a general tool that can be applied whenever the function has derivatives. We can use this series to estimate the value of the function near the given point, which is useful when the function is difficult to evaluate directly. The Taylor series is used to derive algorithms for finding the zeros of functions and algorithms for minimizing functions in Chapter 4 and Chapter 5.

To derive the Taylor series, we start with an infinite polynomial series about an arbitrary point, $x$, to approximate the value of a function at $x + \Delta x$ using

We can make this approximation exact at $\Delta x=0$ by setting the first coefficient to $f(x)$. To find the appropriate value for $a_1$, we take the first derivative to get

which means that we need $a_1 = f^\prime(x)$ to obtain an exact derivative at $x$. To derive the other coefficients, we systematically take the derivative of both sides and the appropriate value of the first nonzero term (which is always constant). Identifying the pattern yields the general formula for the $n$th-order coefficient:

Substituting this into the polynomial in Equation A.1 yields the Taylor series

The series is typically truncated to use terms up to order $m$,

which yields an approximation with a truncation error of order ${\cal O}(\Delta x^{m+1})$. In optimization, it is common to use the first three terms (up to $m = 2$) to get a quadratic approximation.

The Taylor series in multiple dimensions is similar to the single-variable case but more complicated. The first derivative of the function becomes a gradient vector, and the second derivatives become a Hessian matrix. Also, we need to define a direction along which we want to approximate the function because that information is not inherent like it is in a one-dimensional function. The Taylor series expansion in $n$ dimensions along a direction $p$ can be written as

where $\alpha$ is a scalar that determines how far to go in the direction $p$.

In matrix form, we can write

where $H$ is the Hessian matrix.

A.2 Chain Rule, Total Derivatives, and Differentials¶

The single-variable chain rule is needed for differentiating composite functions. Given a composite function, $f(g(x))$, the derivative with respect to the variable $x$ is

If a function depends on more than one variable, then we need to distinguish between partial and total derivatives. For example, if $f(g(x),h(x))$, then $f$ is a function of two variables: $g$ and $h$. The application of the chain rule for this function is

where $\partial / \partial x$ indicates a partial derivative, and $\mathrm{d} / \mathrm{d} x$ is a total derivative. When taking a partial derivative, we take the derivative with respect to only that variable, treating all other variables as constants. More generally,

The differential of a function represents the linear change in that function with respect to changes in the independent variable. We introduce them here because they are helpful for finding total derivatives of multivariable equations that are implicit.

If function $y=f(x)$ is differentiable, the differential $\mathrm{d} y$ is

where $\mathrm{d} x$ is a nonzero real number (considered small) and $\mathrm{d} y$ is an approximation of the change (due to the linear term in the Taylor series). We can solve for $f^\prime(x)$ to get $f^\prime(x) = \mathrm{d} y / \mathrm{d} x$. This states that the derivative of $f$ with respect to $x$ is the differential of $y$ divided by the differential of $x$. Strictly speaking, $\mathrm{d} y / \mathrm{d} x$ here is not the derivative, although it is written in the same way. The derivative is a symbol, not a fraction. However, for our purposes, we will use these representations interchangeably and treat differentials algebraically. We also write the differentials of functions as

In Example 5, there is no clear advantage in using differentials. However, differentials are more straightforward for finding total derivatives of multivariable implicit equations because there is no need to identify the independent variables. Given an equation, we just need to (1) find the differential of the equation and (2) solve for the derivative of interest. When we want quantities to remain constant, we can set the corresponding differential to zero. Differentials can be applied to vectors (say a vector $x$ of size $n$), yielding a vector of differentials with the same size ($\mathrm{d} x$ of size $n$). We use this technique to derive the unified derivatives equation (UDE) in Section 6.9.

A.3 Matrix Multiplication¶

Consider a matrix $A$ of size $(m \times n)$^[1]and a matrix $B$ of size $(n \times p)$. The two matrices can be multiplied together $(C = A B)$ as follows:

where $C$ is an $(m \times p)$ matrix. This multiplication is illustrated in Figure A.3. Two matrices can be multiplied only if their inner dimensions are equal ($n$ in this case). The remaining products discussed in this section are just special cases of matrix multiplication, but they are common enough that we discuss them separately.

A.3.1 Vector-Vector Products¶

In this book, a vector $u$ is a column vector; thus, the row vector is represented as $u^\intercal$. The product of two vectors can be performed in two ways. The more common is called an inner product (also known as a dot product or scalar product). The inner product is a functional, meaning that it is an operator that acts on vectors and produces a scalar. This product is illustrated in Figure A.4. In the real vector space of $n$ dimensions, the inner product of two vectors, $u$ and $v$, whose dimensions are equal, is defined algebraically as

The order of multiplication is irrelevant, and therefore,

In Euclidean space, where vectors have magnitude and direction, the inner product is defined as

where $\|\cdot\|$ represents the 2-norm (Equation A.25), and $\theta$ is the angle between the two vectors.

The outer product takes the two vectors and multiplies them element-wise to produce a matrix, as illustrated in Figure A.5. Unlike the inner product, the outer product does not require the vectors to be of the same length. The matrix form is as follows:

The index form is as follows:

Outer products generate rank 1 matrices. They are used in quasi-Newton methods (Section 4.4.4 and ).

A.3.2 Matrix-Vector Products¶

Consider multiplying a matrix $A$ of size $(m \times n)$ by vector $u$ of size $n$. The result is a vector of size $m$:

This multiplication is illustrated in Figure A.6.

The entries in $v$ are dot products between the rows of $A$ and $u$:

where $A_{i \ast}$ is the $i$th row of the matrix $A$. Thus, a matrix-vector product transforms a vector in $n$-dimensional space ($\mathbb{R}^n$) to a vector in $m$-dimensional space ($\mathbb{R}^m$).

A matrix-vector product can be thought of as a linear combination of the columns of $A$, where the $u_j$ values are the weights:

and $A_{\ast j}$ are the columns of $A$.

We can also multiply by a vector on the left, instead of on the right:

In this case, a row vector is multiplied with a matrix, producing a row vector.

A.3.3 Quadratic Form (Vector-Matrix-Vector Product)¶

Another common product is a quadratic form. A quadratic form consists of a row vector, times a matrix, times a column vector, producing a scalar:

The index form is as follows:

In general, a vector-matrix-vector product can have a nonsquare $A$ matrix, and the vectors would be two different sizes, but for a quadratic form, the two vectors $u$ are identical, and thus $A$ is square. Also, in a quadratic form, we assume that $A$ is symmetric (even if it is not, only the symmetric part of $A$ contributes, so effectively, it acts like a symmetric matrix).

A.4 Four Fundamental Subspaces in Linear Algebra¶

This section reviews how the dimensions of a matrix in a linear system relate to dimensional spaces.^[2] These concepts are especially helpful for understanding constrained optimization (Chapter 5) and build on the review in Section 5.2n-Dimensional Space.

A vector space is the set of all points that can be obtained by linear combinations of a given set of vectors. The vectors are said to span the vector space. A basis is a set of linearly independent vectors that generates all points in a vector space. A subspace is a space of lower dimension than the space that contains it (e.g., a line is a subspace of a plane).

Two vectors are orthogonal if the angle between them is 90 degrees. Then, their dot product is zero. A subspace $S_1$ is orthogonal to another subspace $S_2$ if every vector in $S_1$ is orthogonal to every vector in $S_2$.

Consider an $(m \times n)$ matrix $A$. The rank ($r$) of a matrix $A$ is the maximum number of linearly independent row vectors of $A$ or, equivalently, the maximum number of linearly independent column vectors. The rank can also be defined as the dimensionality of the vector space spanned by the rows or columns of $A$. For an $(m \times n)$ matrix, $r \le \min(m,n)$.

Through a matrix-vector multiplication $Ax=b$, this matrix maps an $n$-vector $x$ into an $m$-vector $b$.

Figure A.7 shows this mapping and illustrates the four fundamental subspaces that we now explain.

The column space of a matrix $A$ is the vector space spanned by the vectors in the columns of $A$. The dimensionality of this space is given by $r$, where $r \le n$, so the column space is a subspace of $n$-dimensional space. The row space of a matrix $A$ is the vector space spanned by the vectors in the rows of $A$ (or equivalently, it is the column space of $A^\intercal$). The dimensionality of this space is given by $r$, where $r \le m$, so the row space is a subspace of $n$-dimensional space.

The nullspace of a matrix $A$ is the vector space consisting of all the vectors that are orthogonal to the rows of $A$. Equivalently, the nullspace of $A$ is the vector space of all vectors $x_n$ such that $A x_n =0$. Therefore, the nullspace is orthogonal to the row space of $A$. The dimension of the nullspace of $A$ is $n-r$.

Combining the nullspace and row space of $A$ adds up to the whole $n$-dimensional space, that is, $x = x_r + x_n$, where $x_r$ is in the row space of $A$ and $x_n$ is in the nullspace of $A$.

The left nullspace of a matrix $A$ is the vector space of all $x$ such that $A^\intercal x=0$. Therefore, the left nullspace is orthogonal to the column space of $A$. The dimension of the left nullspace of $A$ is $m-r$. Combining the left nullspace and column space of $A$ adds up to the whole $m$-dimensional space.

A.5 Vector and Matrix Norms¶

Norms give an idea of the magnitude of the entries in vectors and matrices. They are a generalization of the absolute value for real numbers. A norm $\|\cdot\|$ is a real-valued function with the following properties:

• $\|x\| \ge 0$ for all $x$.

• $\|x\| = 0$ if an only if $x=0$.

• $\|\alpha x\| = |\alpha| \|x\|$ for all real numbers $\alpha$.

• $\|x+y\| \le \|x\| + \|y\|$ for all $x$ and $y$.

Most common matrix norms also have the property that $\|xy\| \le \|x\| \|y\|$, although this is not required in general.

We start by defining vector norms, where the vector is $x=[x_1,\ldots,x_n]$. The most familiar norm for vectors is the 2-norm, also known as the Euclidean norm, which corresponds to the Euclidean length of the vector:

Because this norm is used so often, we often omit the subscript and just write $\|x\|$. In this book, we sometimes use the square of the 2-norm, which can be written as the dot product,

More generally, we can refer to a class of norms called $p$-norms:

where $1\le p < \infty$. Of all the $p$-norms, three are most commonly used: the 2-norm (Equation A.25), the 1-norm, and the $\infty$-norm. From the previous definition, we see that the 1-norm is the sum of the absolute values of all the entries in $x$:

The application of $\infty$ in the $p$-norm definition is perhaps less obvious, but as $p\rightarrow\infty$, the largest term in that sum dominates all of the others. Raising that quantity to the power of $1/p$ causes the exponents to cancel, leaving only the largest-magnitude component of $x$. Thus, the infinity norm is

The infinity norm is commonly used in optimization convergence criteria.

The vector norms are visualized in Figure A.8 for $n=2$. If $x = [1,\ldots,1]$, then

It is also possible to assign different weights to each vector component to form a weighted norm:

Several norms for matrices exist. There are matrix norms similar to the vector norms that we defined previously. Namely,

where $\lambda_{\max} \left( A^\intercal A \right)$ is the largest eigenvalue of $A^\intercal A$. When $A$ is a square symmetric matrix, then

Another matrix norm that is useful but not related to any vector norm is the Frobenius norm, which is defined as the square root of the absolute squares of its elements, that is,

The Frobenius norm can be weighted by a matrix $W$ as follows:

This norm is used in the formal derivation of the Broyden–Fletcher–Goldfarb–Shanno (BFGS) update formula (see ).

A.6 Matrix Types¶

There are several common types of matrices that appear regularly throughout this book. We review some terminology here.

A diagonal matrix is a matrix where all off-diagonal terms are zero. In other words, $A$ is diagonal if:

The identity matrix $I$ is a special diagonal matrix where all diagonal components are 1.

The transpose of a matrix is defined as follows:

Note that

A symmetric matrix is one where the matrix is equal to its transpose:

The inverse of a matrix, $A^{-1}$, satisfies

Not all matrices are invertible. Some common properties for inverses are as follows:

A symmetric matrix $A$ is positive definite if and only if

for all nonzero vectors $x$. One property of positive-definite matrices is that their inverse is also positive definite.

The positive-definite condition (Equation A.42) can be challenging to verify. Still, we can use equivalent definitions that are more practical.

For example, by choosing appropriate $x$s, we can derive the necessary conditions for positive definiteness:

These are necessary but not sufficient conditions. Thus, if any diagonal element is less than or equal to zero, we know that the matrix is not positive definite.

An equivalent condition to Equation A.42 is that all the eigenvalues of $A$ are positive. This is a sufficient condition.

Another practical condition equivalent to Equation A.42 is that all the leading principal minors of $A$ are positive. A leading principal minor is the determinant of a leading principal submatrix. A leading principal submatrix of order $k$, $A_k$ of an $(n \times n)$ matrix $A$ is obtained by removing the last $n-k$ rows and columns of $A$, as shown in Figure A.9. Thus, to verify if $A$ is positive definite, we start with $k=1$, check that $A_{1}>0$ (only one element), then check that $\det(A_2)>0$, and so on, until $\det(A_n)>0$. Suppose any of the determinants in this sequence is not positive. In that case, we can stop the process and conclude that $A$ is not positive definite.

A positive-semidefinite matrix satisfies

for all nonzero vectors $x$. In this case, the eigenvalues are nonnegative, and there is at least one that is zero. A negative-definite matrix satisfies

for all nonzero vectors $x$. In this case, all the eigenvalues are negative. An indefinite matrix is one that is neither positive definite nor negative definite. Then, there are at least two nonzero vectors $x$ and $y$ such that

A.7 Matrix Derivatives¶

Let us consider the derivatives of a few common cases: linear and quadratic functions. Combining the concept of partial derivatives and matrix forms of equations allows us to find the gradients of matrix functions. First, let us consider a linear function, $f$, defined as

where $a$, $x$, and $b$ are vectors of length $n$, and $a_i, ~x_i, ~\text{and } b_i$ are the $i$th elements of $a,~x,\text{ and } b$, respectively. If we take the partial derivative of each element with respect to an arbitrary element of $x$, namely, $x_k$, we get

Thus,

Recall the quadratic form presented in Section A.3.3; we can combine that with a linear term to form a general quadratic function:

where $x, b$, and $c$ are still vectors of length $n$, and $A$ is an $n$-by-$n$ symmetric matrix. In index notation, $f$ is as follows:

For convenience, we separate the diagonal terms from the off-diagonal terms, leaving us with

Now we take the partial derivatives with respect to $x_k$ as before, yielding

We now move the diagonal terms back into the sums to get

which we can put back into matrix form as follows:

If $A$ is symmetric, then $A^\intercal = A$, and thus

A.8 Eigenvalues and Eigenvectors¶

Given an $(n \times n)$ matrix, if there is a scalar $\lambda$ and a nonzero vector $v$ that satisfy

then $\lambda$ is an eigenvalue of the matrix $A$, and $v$ is an eigenvector.

The left-hand side of Equation A.57 is a matrix-vector product that represents a linear transformation applied to $v$. The right-hand side of Equation A.57 is a scalar-vector product that represents a vector aligned with $v$. Therefore, the eigenvalue problem (Equation A.57) answers the question: Which vectors, when transformed by $A$, remain in the same direction, and how much do their corresponding lengths change in that transformation?

The solutions of the eigenvalue problem (Equation A.57) are given by the solutions of the scalar equation,

This equation yields a polynomial of degree $n$ called the characteristic equation, whose roots are the eigenvalues of $A$.

If $A$ is symmetric, it has $n$ real eigenvalues $(\lambda_1, \ldots, \lambda_n)$ and $n$ linearly independent eigenvectors $(v_1, \ldots, v_n)$ corresponding to those eigenvalues. It is possible to choose the eigenvectors to be orthogonal to each other (i.e., $v_i^\intercal v_j=0$ for $i \neq j$) and to normalize them (so that $v_i^\intercal v_i=1$).

We use the eigenvalue problem in Section 4.1.2, where the eigenvectors are the directions of principal curvature, and the eigenvalues quantify the curvature. Eigenvalues are also helpful in determining if a matrix is positive definite.

A.9 Random Variables¶

Imagine measuring the axial strength of a rod by performing a tensile test with many rods, each designed to be identical. Even with “identical” rods, every time you perform the test, you get a different result (hopefully with relatively small differences). This variation has many potential sources, including variation in the manufactured size and shape, in the composition of the material, and in the contact between the rod and testing fixture. In this example, we would call the axial strength a random variable, and the result from one test would be a random sample. The random variable, axial strength, is a function of several other random variables, such as bar length, bar diameter, and material Young’s modulus.

One measurement does not tell us anything about how variable the axial strength is, but if we perform the test many times, we can learn a lot about its distribution. From this information, we can infer various statistical quantities, such as the mean value of the axial strength. The mean of some variable $x$ that is measured $n$ times is estimated as follows:

This is actually a sample mean, which would differ from the population mean (the true mean if you could measure every bar). With enough samples, the sample mean approaches the population mean. In this brief review, we do not distinguish between sample and population statistics.

Another important quantity is the variance or standard deviation. This is a measure of spread, or how far away our samples are from the mean. The unbiased^[3]estimate of the variance is

and the standard deviation is just the square root of the variance. A small variance implies that measurements are clustered tightly around the mean, whereas a large variance means that measurements are spread out far from the mean. The variance can also be written in the following mathematically equivalent but more computationally-friendly format:

More generally, we might want to know what the probability is of getting a bar with a specific axial strength. In our testing, we could tabulate the frequency of each measurement in a histogram. If done enough times, it would define a smooth curve, as shown in Figure A.10. This curve is called the probability density function (PDF), $p(x)$, and it tells us the relative probability of a certain value occurring.

More specifically, a PDF gives the probability of getting a value with a certain range:

The total integral of the PDF must be 1 because it contains all possible outcomes (100 percent):

From the PDF, we can also measure various statistics, such as the mean value:

This quantity is also referred to as the expected value of $x$ ($\mathbb{E}[x]$). The expected value of a function of a random variable, $f(x)$, is given by:^[4]

We can also compute the variance, which is the expected value of the squared difference from the mean:

or in a mathematically equivalent format:

The mean and variance are the first and second moments of the distribution. In general, a distribution may require an infinite number of moments to describe it fully. Higher-order moments are generally mean centered and are normalized by the standard deviation so that the $n$th normalized moment is computed as follows:

The third moment is called skewness, and the fourth is called kurtosis, although these higher-order moments are less commonly used.

The cumulative distribution function (CDF) is related to the PDF, which is the cumulative integral of the PDF and is defined as follows:

The capital $P$ denotes the CDF, and the lowercase $p$ denotes the PDF. As an example, the PDF and corresponding CDF for the axial strength are shown in Figure A.10. The CDF always approaches 1 as $x \rightarrow \infty$.

We often fit a named distribution to the PDF of empirical data. One of the most popular distributions is the normal distribution, also known as the Gaussian distribution. Its PDF is as follows:

For a normal distribution, the mean and variance are visible in the function, but these quantities are defined for any distribution. Figure A.11 shows two normal distributions with different means and standard deviations to illustrate the effect of those parameters.

Several other popular distributions are shown in Figure A.12: uniform distribution, Weibull distribution, lognormal distribution, and exponential distribution. These are only a few of many other possible probability distributions.

An extension of variance is the covariance, which measures the variability between two random variables:

From this definition, we see that the variance is related to covariance by the following:

Covariance is often expressed as a matrix, in which case the variance of each variable appears on the diagonal. The correlation is the covariance divided by the standard deviations: