Optimization in Practice with MATLAB for Engineering Students and Professionals (2015)

PART 1

HELPFUL PRELIMINARIES

2

Mathematical Preliminaries

2.1 Overview

This chapter presents some of the basic mathematics needed for learning and using optimization. Specifically, this chapter reviews the basics of linear algebra (e.g., vectors, matrices and eigenvalues) and calculus. A review of the material presented in this chapter may be helpful. For most, it will be well known material; for others, it will be a great opportunity for a quick review. For others still, it will be an opportunity to learn the minimally required mathematics for the material presented in this book.

2.2 Vectors and Geometry

A scalar is a quantity that is determined by its magnitude and sign. For example, length, temperature, and speed are scalars. A vector is a quantity that is determined by both its magnitude and its direction. It is a directed line segment. For example, velocity and force are examples of vectors.

A vector can be expressed in terms of its components in a Cartesian Coordinate system as a = a₁i + a₂ j + a₃k, where i, j, and k denote the unit vectors along the X, Y and Z axes. The magnitude of this vector is given as ||a|| = .

The length of a vector x is also called the norm (or Euclidean norm) of the vector, denoted by |x|. The position vector of a given point A : {x,y,z} is the vector from the origin of the axes to the point A.

2.2.1 Dot Product

The dot product or Inner product of two vectors yields a scalar. Mathematically, the dot product of two vectors a and b, denoted a⋅b, is the product of their lengths times the cosine of the angle θ between them.

In terms of vector components, the dot product of two vectors a = a₁i + a₂ j + a₃k and b = b₁i + b₂j + b₃k is given as

Two vectors are said to be orthogonal when their dot product is equal to zero (θ = 90^o).

2.2.2 Equation of a Line

The slope-intercept form of the equation of a line that has a slope of m and y-intercept c is

The point-slope form of the equation of a line that passes through a point P : (x₁,y₁) with a slope m is

The two-point form of the equation of a line that passes through two points P₁ : (x₁,y₁) and P₂ : (x₂,y₂) is

The two-intercept form of a line with x intercept a and y intercept b is given as

2.2.3 Equation of a Plane

The equation of a plane with a normal vector n = [a,b,c]^T passing through the point (x ₀,y₀,z₀) is given as

where x = (x,y,z) is any generic point on the plane. Substituting the value of x in Eq. 2.7, the general form of the equation of a plane is

where d = −ax₀ −by₀ −cz₀. The plane specified in this form has its X, Y , and Z intercepts at p = , q = , and r = .

Figure 2.1. Equation of a Plane

In the intercept form, a plane passing through the points (a, 0, 0), (0,b, 0), and (0, 0,c) can be given as

The plane passing through the two points (x₁,y₁,z₁) and (x₂,y₂,z₂), and parallel to the direction [a,b,c]^T is given by the following equation.

The plane that passes through the three points (x₁,y₁,z₁), (x₂,y₂,z₂), and (x₃,y₃,z₃) is given by,

In the above two equations, we used the notation = det(A), for any given matrix A.

2.3 Basic Linear Algebra

Linear algebra can be defined as the study of the theory and application of linear systems of equations and linear transformations. Linear algebra uses matrices and their properties in a systematic way, often to solve physically meaningful problems (Ref. [1]).

2.3.1 Preliminary Definitions

A matrix is a rectangular array of numbers, symbols, or functions, which are called the elements of the matrix. The following matrices are presented to help discuss some basic matrix definitions.

The first example provided in Eq. 2.12 has two rows (horizontal lines) and three columns (vertical lines). The order of this matrix is 2 × 3 since it has two rows and three columns. Matrices where the number of rows is not equal to the number of columns are called Rectangular matrices. The second example provided in Eq. 2.13 has two rows and two columns. Matrices where the number of rows is equal to the number of columns are called Square matrices. The third example found in Eq. 2.14 has only one column. These are called Column matrices. The fourth example in Eq. 2.15 has only one row. These are called Row matrices. A general notation for a matrix is given by

Any element in a matrix can be represented using the double subscript notation as a_ij, where i denotes the row and j the column in which the element is located. When m = n, the matrix is said to be square. The diagonal containing the elements a₁₁, a₂₂,...a_nn is called the principal diagonal of the matrix. The matrix given by Eq. 2.17, where all the elements in the principal diagonal are ones, and the rest of the elements are zeros, is called theIdentity Matrix. The matrix in the form shown in Eq. 2.18, where all the elements below the principal diagonal are zeros, is called an Upper Triangular matrix. A Lower triangular form is provided in Eq. 2.19, where all the elements above the principal diagonal are zeros.

2.3.2 Matrix Operations

Addition

The addition of two matrices is possible only if they are of the same order. If two matrices A and B have the same order, then A + B can be obtained by adding the corresponding elements of A and B. Consider the following example.

Example 1:

and

then,

Subtraction

Similar to the addition operation, two matrices can be subtracted only if they have the same order. For the two matrices A and B given by Eqs. 2.20 and 2.21, A − B can be obtained by subtracting the corresponding elements as,

Example 2:

Scalar Multiplication

The product of any matrix with a scalar can be obtained by multiplying each element of that matrix with that scalar. For example, for matrix A in Eq. 2.20, 4A can be obtained by simply multiplying each element of A by 4.

Example 3:

Matrix Multiplication

Unlike matrix addition, matrix multiplication is not obtained by multiplying the corresponding elements of two matrices. Consider two matrices C and D. These two matrices can be multiplied to yield CD only if the number of columns in C is equal to the number of rows in D. If C is an m × n matrix and D is an n × p matrix, then the product of C and D has an order of m × p. For example, consider the following:

Example 4:

and

then

In addition, consider

Note that CD ≠ DC. The following are some important properties of matrix multiplication.

1. AB ≠ BA

2. AI = IA = A

3. AB = 0 does not necessarily imply A = 0 or B = 0

4. k(AB)=(kA)B=A(kB), where k is a scalar

5. A(BC)=(AB)C

6. (A + B)C=AC + BC

7. A(B + C)=AB + AC

Transpose

The transpose of a matrix is obtained by interchanging its rows and columns. Consider the following example.

Example 5:

Some important properties of the transpose of a matrix follow:

1. If A^T = A, then A is called a Symmetric Matrix. If A^T = −A, then A is called a Skew Symmetric Matrix.

2. (A^T)^T = A

3. (A + B)^T = A^T + B^T

4. (AB)^T = B^TA^T

2.3.3 Determinants

The general form of a determinant of a matrix is given as

where j represents any row in A, C_ij is called the Cofactor of A, and M_ij is the corresponding minor. The minor determinant M_ij is the determinant of the sub-matrix obtained by deleting the ith row and the jth column of the matrix. A cofactor is a signed minor determinant. Specifically, C_ij = M_ij when i + j is even and C_ij = −M_ij when i + j is odd. For example, let us compute the determinant of a 2 × 2 matrix.

Example 6:

The following example demonstrates computation of the determinant of a 3 × 3 matrix.

Example 7:

The following are some important properties of determinants of (square) matrices.

1. det(A^T) = det(A)

2. det(I) = 1

3. If two rows or columns of a matrix are identical, then det(A) = 0.

4. If all entries of a row or column are all zeros, then det(A) = 0.

5. If B is obtained by interchanging any two rows or columns of A, then det(B) = −det(A)

6. If a row or column of a matrix is a linear combination of two or more rows or columns, respectively, then det(A) = 0.

7. det(AB) = det(A)det(B)

8. det(cA) = cⁿdet(A), where c is a scalar.

9. If the determinant of a matrix is zero, the matrix is said to be singular. Otherwise, the matrix is said to be non-singular.

10.If a matrix is upper triangular or lower triangular, the determinant of that matrix is simply equal to the product of the elements in the principal diagonal.

2.3.4 Inverse

For a square matrix A, if there exists a matrix B, such that, AB = BA = I, then B is the inverse of A. A general definition of inverse is given as

where Adjoint(A) = C^T, and C is the matrix of the co-factors of A. For a 2 × 2 matrix, the above equation reduces to the following simple formula.

It follows from Eq. 2.23 that the inverse of a matrix exists if and only if the determinant is nonzero (i.e., the matrix is non-singular). The inverse of a matrix can also be computed using the Gauss Jordan method. The following example illustrates how to compute the inverse of a 2 × 2 matrix using its determinant.

Example 8:

The following properties of matrix inversion (assuming the associated matrices are invertible) are also important to know.

1. AA^-1 = I

2. (AB)^-1 = B^-1A^-1

3. (A^T)^-1 = (A^-1)^T

2.3.5 Eigenvalues

The Eigenvalue problem is defined as follows:

For an n × n matrix, find all scalars λ such that the equation

has a nonzero solution x. Such a scalar λ is called the eigenvalue of A, and any nonzero n × 1 vector, x, satisfying Eq. 2.24 is called the eigenvector corresponding to λ.

Given a matrix A, the eigenvalues of A, denoted by λ, can be computed by finding the roots of the equation |A − λI| = 0. This equation |A − λI| = 0 is called the characteristic equation. The following example illustrates how to find the eigenvalues of a 2 × 2 matrix.

Example 9

The characteristic equation of A can be written as |A − λI| = 0, where λ is the eigenvalue we want to compute.

The above quadratic equation is the characteristic equation of A. Recall that for a quadratic equation given by ax² + bx + c = 0, the roots are given as . The eigenvalues of A are the roots of λ² + 7λ + 6 = 0, which are found to be λ ₁ = −1 and λ₂ = −6.

2.3.6 Eigenvectors

Given a matrix A, consider the equation (A−λI)x = 0, where λ is an eigenvalue of A. The nonzero values of x that satisfy the above equation for each eigenvalue are called the Eigenvectors of A. We will learn how to compute eigenvectors with the help of an example. Consider the matrix A in Example 9.

Example 10: Note that it is important to compute eigenvalues before we compute eigenvectors. Previously, in Example 9, we obtained the eigenvalues of A as λ₁ = −1 and λ₂ = −6. For the first eigenvalue λ₁ = −1, we find values of x such that (A−λ₁I)x = 0, or (A − (−1)I)x = 0.

Expanding the above matrix, we obtain

In order to find the eigenvector corresponding to λ₁ = −1, we need to find the values of x₁ and x₂ that satisfy the above two equations. By inspection, we find that x₁ = 1 and x₂ = 2 satisfy the above equations. Thus, the vector [1,2]^T is an eigenvector corresponding to the eigenvalue λ₁ = −1.

After finding a particular x as an eigenvector for a given eigenvalue, note that a multiple of x, for example kx, will also be an eigenvector for that given eigenvalue. For instance, for λ₁ = −1, [, 1]^T is also a valid eigenvector. Using the procedure outlined above, we can compute the eigenvector for the eigenvalue of λ₂ = −6 to be [2,−1]^T.

Note that there could be several linearly independent eigenvectors possible for a single eigenvalue. The maximum number of linearly independent eigenvectors corresponding to an eigenvalue of λ is called the geometric multiplicity of λ.

2.3.7 Positive Definiteness

A matrix is said to be positive definite if all its eigenvalues are positive. A matrix is said to positive semidefinite if all its eigenvalues are non-negative (that is, including zero).

A matrix is said to be negative definite if all its eigenvalues are negative. A matrix is said to negative semidefinite if all its eigenvalues are non-positive (that is, including zero).

2.4 Basic Calculus: Types of Functions, Derivative, Integration and Taylor Series

You can find a mathematical definition of function in numerous books. Instead of using mathematical language, we define function on a lighter note. Think about a vending machine that takes in money and gives you soda or coffee. Functions behaves similarly. They generally take in one or more numbers and output a number. For example, consider a simple trigonometric function f (x) = sin(x). Now, when we input x = π∕2, we obtain f (x) = 1. Thus, the sinefunction maps the input π∕2 to the output, which is 1. Try typing sin(pi/2)in MATLAB. Most optimization books provide some useful mathematical background (Refs. [2, 3]). Note that our simplistic discussion here avaded many important issues, such as invertibility.

2.4.1 Types of Functions

In this section, we will introduce different types of functions commonly encountered in optimization.

Continuous Functions

A function f (x) is continuous over an interval [a,b] if the following conditions are satisfied for any point p (a ≤ p ≤ b).

1. f (x) is defined on the interval [a,b].

2. The limit of f (x), as x tends to p, should exist.

3. The limit of f (x) as x tends to p is equal to f (p). In other words, the limit should be equal to the value of the function evaluated at x = p.

The first plot in Fig. 2.2 illustrates a continuous function. For every value of x, there exists a unique value of f (x). In simple terms, we note that if a function can be traced without lifting the hand, it is continuous.

Figure 2.2. Type of Functions

Discontinuous Functions

Functions that do not satisfy the three conditions stated in the previous subsection are called discontinuous functions. As illustrated in the second plot in Fig. 2.2, at x = a, the function has two values, f (a)^-and f (a)⁺. As such, it violates the third condition. A discontinuous function cannot be traced from one end to the other without lifting the hand. Try it on the discontinuous function shown in Fig. 2.2.

Discrete Function

Discrete functions are not defined for all values of x within the given interval; rather, they are defined at particular values of x. As seen in the third plot in Fig. 2.2, function f (x) is defined for discrete values of x. Some optimization algorithms approximate the discrete function using a continuous function.

Monotonically Increasing Function

A function f (x) is said to be monotonically increasing if it satisfies the following property. For two points x = a and x = b, such that b > a, if f (b) ≥ f (a), then the function is monotonically increasing. Monotonically increasing functions are shown by A and B in Fig. 2.3.

Figure 2.3. Monotonic Functions

A function is called Strictly increasing if f (b) > f (a), as represented by A in Fig. 2.3.

Monotonically Decreasing Function

A function f (x) is monotonically decreasing if it satisfies the following property. For two points x = a and x = b, such that b > a, if f (b) ≤ f (a), then the function is monotonically decreasing. Monotonically decreasing functions are shown by C and D in Fig. 2.3.

A function is called Strictly decreasing if, for any b>a, f (b)<f (a); as represented by C in Fig. 2.3.

Unimodal Functions

Unimodal functions have a single optimum in a given interval (other than end-points), which may be either a maximum or a minimum. A unimodal function that has a minimum value at x = p is represented by A in Fig 2.4. We note that f (x) is strictly decreasing for x < p and strictly increasing for x > p. In Fig. 2.4, B represents a special type of unimodal function. Unimodal functions need not be continuous. Function C in Fig. 2.4 is a discrete unimodal function.

Figure 2.4. Unimodal and Multimodal Functions

Multimodal Functions

Unlike the previous functions, multimodal functions have multiple maxima or minima. One such multimodal function is represented by D in Fig. 2.4, which has two minima.

Convex Functions

A convex function is one for which the line joining any two points on the function lies entirely on or above the function defined between these two points. The left plot in Fig. 2.5 displays a convex function. As shown in Fig. 2.5, aand b are any two points in the domain of a function f (x). The line joining their function values is entirely on or above the function defined between a and b.

Figure 2.5. Convex and Concave Functions

If f (x) is twice differentiable (that is, you can find its second derivative) in [a,b], then a necessary and sufficient condition for it to be convex on that interval is that we have the second derivative f′′(x) > 0 for all x in [a,b].

Concave Functions

A function f (x) is said to be concave on an interval [a,b] if the function −f (x) is convex in that interval. Thus, the definition of concave functions is exactly opposite that of convex functions. The right plot in Fig. 2.5 illustrates a concave function. As shown in Fig. 2.5, the line joining the function values of a and b lies entirely on or below the function defined between a and b.

2.4.2 Limits of Functions

Consider a function f (x), and let the function f (x) have a limit L when x tends to a value x₀. In simple language, the function f (x) reaches a value L as x approaches the value x₀. Mathematically, it is denoted by

Example 2.1 chap_math_limit Let the function be f (x) = ((a + x)² − a²)∕x. The limit of this function as x tends to 0 can be determined as

To find the limit of f (x) as x tends to 0, simply substitute x = 0 in the above equation, and obtain

2.4.3 Derivative

The derivative of a function f (x) at a certain point x is a measure of the rate at which that function is changing as the variable x changes. That is, a derivative represents the rate of change of a function with respect to the input variable, or the derivative is the computation of the instantaneous slope of f (x) at point x. Mathematically, the derivative is represented as

where h is an infinitesimally small deviation in x.

2.4.4 Partial Derivative

For a function of several variables, it is often useful to examine the variation of the function with respect to one of the variables while all the other variables remain fixed. This is the purpose of a partial derivative. The partial derivative is obtained in the same way as ordinary differentiation with this constraint. Partial derivatives are defined as derivatives of a function of multiple variables when all but the variable of interest are held fixed during thedifferentiation. Consider a function f (x,y), which is a function of two variables, x and y. The partial derivative of this function with respect to x is defined as the derivative of the function when y is held constant.

Similarly, the partial derivative of the function f (x,y) with respect to y is defined as the derivative of the function when x is held constant.

2.4.5 Indefinite Integration

The previous subsection presented the derivative of a function. Let us assume that the derivative of a function f (x) is F(x). It is possible to recover f (x), within a constant, by integrating F(x), as follows

where, C is the integration constant. For example, if F(x) = x² + 2, then

2.4.6 Definite Integration

Definite integration is the integration of a function, F(x), over a particular range of the variable x. It is denoted by

where a and b are the limits of integration. Let f (x) be the indefinite integral of F(X). The definite integral is determined as follows

For example, if F(x) = x² + 2, then from Eq. 2.30 we have f (x) = + 2x + C. Now let us evaluate the definite integral over the interval from x = 1 to x = 2.