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

k	ak	bk	f(ak )	f(bk )	lk	rk	f(lk )	f(rk )
1	0.00	10.00	95.00	195.00	3.82	6.18	15.16	38.77
2	0.00	6.18	95.00	38.77	2.36	3.82	28.44	15.16
3	2.36	6.18	28.44	38.77	3.82	4.72	15.16	17.60
4	2.36	4.72	28.44	17.60	3.26	3.82	17.72	15.16
5	3.26	4.72	17.72	17.60	3.82	4.16	15.16	15.13
6	3.82	4.72	15.16	17.60	4.16	4.38	15.13	15.71
7	3.82	4.38	15.16	15.71	4.03	4.16	15.01	15.13
8	3.82	4.16	15.16	15.13	3.95	4.03	15.01	15.01
9	3.95	4.16	15.01	15.13	4.03	4.08	15.01	15.03
10	3.95	4.08	15.01	15.03	4.00	4.03	15.00	15.01

12.3.2 Polynomial Approximations: Quadratic Approximation

If we assume an objective function is unimodal and continuous inside an interval, then it can be approximated by a polynomial. A is the simplest interpolation of the objective function (see Ref. [3]). The quadratic approximationmethod consists of a sequence of reducing intervals, and iterative approximations in the reduced intervals. As the approximation approaches the actual minimum, its accuracy increases. When the error between the approximation and the actual function is less than a predefined tolerance, terminate the iteration.

A quadratic approximating function can be constructed given three consecutive points, x₁, x₂, and x₃, and their corresponding function values, f(x₁), f(x₂), and f(x₃). The quadratic function is expressed as follows.

(12.12)

At the three points, x₁, x₂, and x₃, (x) = f(x). The three constants, c₀, c₁, and c₂, can be determined as follows.

At the point x₁, since f(x₁) = (x₁) = c₀, the first constant is c₀ = f(x₁). At the point x₂, f(x₂) = (x₂) = c₀+c₁(x₂-x₁). The second constant, c₁, can be evaluated as follows.

(12.13)

At the point x₃, f(x₃) = (x₃) = c₀+c₁(x₃-x₁)+c₂(x₃-x₁)(x₃-x₂). The third constant, c₂, is obtained from the following equation.

(12.14)

Using the above quadratic approximation, the minimum point, x^*, should satisfy the first-order necessary conditions.

(12.15)

Then, the minimum point, x^*, can be expressed as

(12.16)

The quadratic approximation can be implemented in successively reduced intervals. A successive quadratic approximation method is outlined as follows.

1.Define the tolerance of the function successive-values difference, γ > 0, and the tolerance of the variable, > 0. Set Δx. Set the iteration number, k, to 1.

2.Set the initial point, x₁¹. Compute x₂¹ = x ₁¹ + Δx. Evaluate f(x₁¹) and f(x ₂¹). If f(x₁¹) > f(x₂¹), then x ₃¹ = x₂¹ + Δx. If f(x₁¹) < f(x ₂¹), then x₃¹ = x₁¹-Δx. Evaluate f(x₃¹).

3.Compare the function values at the three points, x₁^k, x₂^k, and x ₃^k. Find the minimum, f_min^k = min{f(x ₁^k),f(x ₂^k),f(x ₃^k)}, and the corresponding point, x_min^k.

4.Using the three points, x₁^k, x ₂^k, and x₃^k, construct a quadratic approximation. Compute the minimum point, x_k^*, using Eq. 12.16. Evaluate f(x_k^*).

5.If f(x_k^*) - f_min^k < γ and x_k^*-x _min^k < , take x_k^* as the minimum. Terminate the iteration.

6.Take the current best point x_k^* and the two points bracketing it as the three points for the next quadratic approximation. k = k + 1. Go to Step 3.

Example: Use the quadratic approximation method to solve the following optimization problem. The variable, x, is inside (1.001, 10).

(12.17)

Define the tolerance of the function successive-values difference as 0.01f(x_k^*) and the tolerance of the variable as 0.05x_k^*. Set Δx = 1. Set the initial point, x₁¹ = 2.

Define δf^k and δx^k as

(12.18)

(12.19)

The results for all the iterations are listed in Table 12.3.

Table 12.3. The Iterations for the Quadratic Approximation Method

At the end of the second iteration, the errors satisfy the tolerances. The iterations are terminated. The optimal point is 2.65 and the optimal function value is 12.57

12.4 Multivariable Optimization

Most practical unconstrained nonlinear optimization problems have multiple design variables. In this section, the methods for solving multivariable nonlinear optimization problems are illustrated.

12.4.1 Zeroth-Order Methods

Simplex Search Method

The Simplex Search method is a direct-search method that does not require function derivatives (see Ref. [4]). Although the name of this method includes the word simplex, it has no relationship to the Simplex method of linear programming.

In geometry, a Simplex is a triangle in two-dimensional space and a tetrahedron in three-dimensional space. In n-dimensional space, it is an n-dimensional polytope. The main idea of the Simplex method is that, at each iteration, based on the comparison of function values at all the vertices, one vertex is projected through the centroid of the other vertices at a suitable distance. At the beginning, the Simplex Search method sets up a regular Simplex in the space of the variables. The objective function is evaluated at each vertex. For minimization problems, the vertex with the highest function value is the one that is reflected through the centroid of the other vertices to generate a new point. The point and the remaining vertices construct the next Simplex.

At the beginning of the algorithm, it requires the first Simplex to be generated given a base point, x⁰, and an appropriate scale factor, α. Assuming the variable vector has N dimensions, two increments, δ₁ and δ₂, are defined by the following two expressions.

(12.20)

(12.21)

Using the two increments, the j^th dimension for the i^th vertex can be calculated using the following expression.

(12.22)

At each iteration, the vertex with the highest function value is selected as x_high. It is reflected through the centroid of the remaining points. The centroid is evaluated by the following expression.

(12.23)

The line passing through x_high and x_centroid is given by the following expression.

(12.24)

The selection of λ can yield the desired point on the line. If λ = 0, it yields the point, x_high. If λ = 1, the result is the point, x_centroid. In order to generate a symmetric reflection, λ is set as 2. The reflected point, x_reflected, is evaluated as

(12.25)

The reflection process is illustrated in Fig. 12.5. The point, x², has the highest function value, and it is reflected through the centroid of x¹ and x³.

Figure 12.5. Reflection of the Vertex with the Highest Function Value

During the optimization, the following two situations may occur.

1.At the current iteration, the vertex with the highest function value is the reflected point generated in the last iteration. In this situation, choose instead the vertex with the next highest function value and generate a reflected point.

2.The iterations can cycle between two or more Simplexes. If a vertex remains in the Simplex for more than M iterations, set up a new Simplex with the lowest point as the base point and reduce the size of the Simplex. Thenumber of the dimension for the variable is N. The value of M can be estimated by M = 1.65N + 0.05N² and M is rounded to the nearest integer.

The Simplex Search method is terminated when the size of the Simplex is sufficiently small or other termination criteria are met. The vertex with the lowest function value is taken as the minimum.

The Simplex construction and point reflection are illustrated in the following example.

Example: Use the Simplex Search method to minimize the following function.

(12.26)

The number of the dimensions is 2. Each Simplex has 3 vertices. Take x⁰ = [1, 1]^T as the starting point, and set α = 2. The increments, δ₁ and δ₂, can be evaluated as follows.

(12.27)

(12.28)

The coordinates of the other two vertices are calculated as follows.

(12.29)

(12.30)

The function values at the three points, x⁰, x¹, and x², are as follows.

(12.31)

(12.32)

(12.33)

Since the vertex, x⁰, has the highest function value, it is reflected to form a new Simplex. The centroid of the two remaining points, x¹ and x², is calculated as follows.

(12.34)

The reflected point, x_reflected, is calculated as follows.

(12.35)

At the point, x_reflected, f(x_reflected) = 2.3027. The vertex with the highest function value in this new Simplex is x¹. The algorithm will continue by reflecting the x¹, and the iterations proceed following the reflection rule until the optimal point, [2, 3]^T, is found.

Pattern Search Methods

The pattern search methods are a family of derivative-free numerical optimization methods. They can be applied to not only the optimization of continuous differentiable functions, but also to the optimization of discrete or nondifferentiable functions. The pattern search methods look along certain specified directions, and evaluate the objective function at a given step length along each of these directions. These points form a frame around the currentiteration. Depending on whether any point within the pattern has a lower objective function value than the current point, the frame shrinks or expands in the next iteration. The search stops after a minimum pattern size is reached.

An important decision in the pattern search methods is to choose the search direction set, D_k, at each iteration k. A key condition is that at least one direction in this set should give a descent direction for the objective function whenever the current point is not a stationary point. If a search direction, p, satisfies the following inequality, it can be a direction of descent for the objective function.

(12.36)

where δ is a positive constant.

If the search direction, p, satisfies Eq. 12.36 at each iteration, it is a descent direction. Choose the search direction set, D_k, so that at least one direction, p ∈ D_k, will satisfy cos θ > δ, regardless of the value of ∇f_k.

A second condition on D_k is that the lengths of the vectors in this set are all similar. The diameter of the frame formed by this set is captured adequately by the step length. This condition can be expressed as

(12.37)

where β_min and β_max are positive constants.

For the pattern search methods in n-dimensional space, examples of sets D_k that satisfy the above two conditions in Eqs. 12.36 and 12.37 include the coordinate direction set

(12.38)

and the set of n+1 vectors defined by

(12.39)

where e = (1, 1,..., 1)^T.

Another important decision in the pattern search method is how to choose a sufficient decrease function ρ(l). The sufficient decrease function is used to determine the convergence of the results. It is a function of the step length and its domain is [0,∞). It is an increasing function of l and the function values are positive. As l approaches 0, the limit of ρ(t)∕t is 0. An appropriate choice of the sufficient decrease function is Mt^3∕2, where M is some positiveconstant. If the decrease of the objective function value is less than the value of the sufficient decrease function, the pattern search is converged to the minimum.

At each iteration, the search direction set is D_k and the step length is l_k. The frame that consists of the points at the next iteration is x_k + l_kp_k for all p_k ∈ D_k. When one of the points in the frame yields a significant decrease of the objective function, it becomes the next searching point, x_k+1, and the next step length, l_k+1, is increased. If none of the points in the frame has a significantly smaller function value than f_k, the next step length, l_k+1, will be reduced.The procedure of the pattern search algorithm is illustrated as follows.

1.Define the sufficient decrease function ρ(l). Choose convergence tolerance l_tol, contraction parameter θ_max, and search direction set D_k. Choose initial point x₀, initial step length l₀, and initial direction set D₀. Set the iterationnumber, k, to 1.

2.Evaluate the objective function value f(x_k).

3.If the step length is l_k ≤ l_tol, take x_k as the optimal point, x^*. Stop.

4.If f(x_k+l_kp_k) < f(x_k) - ρ(l_k) for some p_k ∈ D_k, set x_k+1 as x_k+l_kp_k for some p_k ∈ D_k, and increase the step length for the next iteration.

5.If f(x_k+l_kp_k) ≥ f(x_k) - ρ(l_k) for all p_k ∈ D_k, use the same point x_k as the point x_k+1 for the next iteration. Reduce the step length for the next iteration, l_k+1. Set l_k+1 as θ_kl_k, where 0 < θ_k ≤ θ_max < 1.

6.Set k = k + 1. Go to Step 2.

MATLAB has the function, patternsearch, that finds the minimum of a function using the pattern search method. It can handle optimization problems with nonlinear, linear, and bound constraints, and does not require functions to be differentiable or continuous. An example is provided below to illustrate how to solve a nonlinear optimization problem without constraints using patternsearch.

Example: Use the pattern search method to solve the following three-dimensional quadratic problem.

(12.40)

(12.41)

(12.42)

The sufficient decrease function is set as ρ(l) = 10l^3∕2. The contraction factor is 0.5. The convergence tolerance is set as 0.001. The contraction factor, θ_max, is set as 0.5. The initial step length, l₀, is set as 0.5. The starting point, x₀, is [0, 0, 0]^T. The search directions set, D_k, is the coordinate direction set, which is as follows.

(12.43)

At the initial point, x₀, the function value, f(x₀), is 0. At the first iteration, the function values at x₀ +l₀p_k, (k = 1,..., 6) are 9, 10.5, 10.5, -7, -7.5, and -5.5. The value of sufficient decrease function is as follows.

(12.44)

For the six points x₀ + l₀p_k, three of them (k = 4, 5, 6) satisfy the equation, f(x_k+l_kp_k) < f(x_k)-(l_k). Set the point, x₀ + l₀p₅, as x₁, and increase the step length. The iterations continue. The minimum point is obtained as follows.

(12.45)

The optimal function value f(x^*) = -35.9.

This problem can also be solved by MATLAB function patternsearch. The result is the same. The main file is as follows.

clc
clear
X0 = [0; 0; 0];
[x,fopt]=patternsearch(@obj_fun,X0)

The file for the objective function is as follows.

function f = obj_fun(x)
Q = [2 0 0; 0 3 0; 0 0 5];
c = [-8; -9; -8];
f = 0.5*x’*Q*x-c’*x;

12.4.2 First-Order Methods

Steepest Descent

The steepest descent method is a first-order optimization algorithm. In each iteration, it takes the negative direction of the gradient as the descent direction of the objective function. This method takes steps along the descentdirection to find a local minimum. The procedure is as follows.

1.Choose a starting point x₀. Set k = 0.

2.Check the conditions of f(x_k). If x_k is the minimum, stop.

3.Calculate the descent direction, p_k, as follows.

(12.46)

4.Evaluate the step length, α_k. The step length, α_k, should be an acceptable solution to the following minimization problem.

(12.47)

5.Update the value of the variable, x_k+1, using the descent direction and the step length.

(12.48)

6.Set k = k+1 and go to Step 2.

The steepest descent method is the simplest Newton-type method for nonlinear optimization. The search direction is the opposite of the gradient. It does not require the computation of second derivatives, and it does not requirematrix storage. The computational cost per iteration is lower compared to other Newton-type methods. However, this method is very inefficient at solving most problems. It converges only at a linear rate. This means it requires more iterations. As a result, although the computational cost per iteration is low, the overall costs are high. However, the steepest descent method is theoretically useful in proving the convergence of other methods; and it provides a lower bound on the performance of other algorithms.

The procedure to solve an unconstrained nonlinear problem using the steepest descent method is illustrated with the following example. Only the first two iterations are illustrated in this example.

Example: Use the steepest descent method to solve the following three-dimensional quadratic problem.

(12.49)

(12.50)

(12.51)

In this problem, the steepest descent direction is

(12.52)

The step length used for exact line search x_k+1 = x_k + α_kp_k is

(12.53)

Choose an initial point x₀ = (0, 0, 0)^T. At x₀,

(12.54)

(12.55)

and

(12.56)

Since ∇f(x₀) > 0, go to the next iteration. The step length is α₀ = 0.1875. The next point is

(12.57)

At point x₁, the function value, the gradient, and the norm of the gradient are as follows.

(12.58)

(12.59)

and

(12.60)

The next step length is α₁ = 0.1715 and the new point is

(12.61)

At point x₂, the function value, the gradient, and the norm of the gradient are as follows.

(12.62)

(12.63)

and

(12.64)

The above are the first two iterations to solve this problem. It takes 36 iterations before the norm of the gradient is less than 0.001. The optimal solution is

(12.65)

The corresponding optimal function value is f(x^*) = -0.65.

Conjugate Gradient Methods

In addition to the Gaussian elimination method, iterative methods are also a valuable tool for solving linear equations in the form of Eq. 12.66. One of the many iterative methods is the conjugate gradient method, which is designed to solve Eq. 12.66 when the matrix A is symmetric and positive definite.

(12.66)

Equation 12.67 is an optimization problem that has a quadratic objective function.

(12.67)

The matrix A is symmetric and positive definite. The first-order necessary conditions require the gradient of f(x) to be equal to zero. The gradient can be expressed as Eq. 12.68.

(12.68)

Since the Hessian matrix, ∇²f(x) = A, is positive definite, the sufficient conditions for a local minimum are satisfied. This optimization problem is equivalent to the problem of linear equations as shown by Eq. 12.66.

If a set of vectors, p_i, satisfies Eq. 12.69, the vectors are said to be conjugate with respect to the matrix A. Any set of conjugate vectors is also linearly independent.

(12.69)

The residual of Eq. 12.68 is

(12.70)

In Eq. 12.67, if the matrix A is diagonal, the contours of the function f(x) are ellipses. The axes of the ellipses are aligned with coordinate directions. The conjugate directions are along the coordinate directions. Figure 12.6 illustratesthe conjugate directions in a two dimensional space. The minimum of the function can be found by performing successive one-dimensional minimizations along the conjugate directions.

Figure 12.6. Conjugate Directions for a Diagonal Matrix A

In Eq. 12.67, if Matrix A is non-diagonal, the contours of the function f(x) are also ellipses. However, the axes of the ellipses are not aligned with the coordinate directions. The conjugate directions are not along the coordinate directions. Figure 12.7 shows the conjugate directions for a non-diagonal matrix in a two dimensional space.

Figure 12.7. Conjugate Directions for a Non-diagonal Matrix A

The conjugate gradient methods used to solve the quadratic optimization problem (Eq. 12.67) exist in different versions of the algorithm. The steps for one of these versions are illustrated as follows.

1.Set an initial guess x₀. The residual is r₀ = Ax₀ - b. Set a vector with the same dimension of the conjugate vector, p₀ = -r₀. Specify the convergence tolerance, > 0. Initialize the iteration counter, i = 0.

2.Check the value of the residual r_i. If r_i < , stop.

3.Set α_i = r_i^Tr _i∕p_i^TAp _i.

4.Evaluate the next point, x_i+1 = x_i + α_ip_i.

5.Evaluate the residual, r_i+1 = r_i + α_iAp_i.

6.Set β_i+1 = r_i+1^Tr _i+1∕r_i^Tr _i.

7.Set the conjugate vector, p_i+1 = -r_i+1+β_i+1p_i.

8.Set i = i + 1. Go to Step 2.

Example: Use the above algorithm for conjugate gradient methods to solve the following three-dimensional quadratic problem.

(12.71)

(12.72)

(12.73)

The convergence tolerance, , is set as 0.01. Choose an initial point x₀ = (0, 0, 0)^T. At this point, the residual is r₀ = (8, 9, 8)^T. This point is not optimal. The algorithm performs several iterations in search of the optimal solution.Table 12.4 provides the results for all the iterations.

Table 12.4. The Iterations for the Conjugate Gradient Method

At the initial point x₀, r₀ = 14.46. In the first iteration, r₁ = 5.24. In the second iteration, r₂ = 1.22. In the third iteration, r₃ = 0. Since r₃ ≤ , the point x₃ = (-4.00,-3.00,-1.60)^T is the optimal solution to this example, and the optimal function value is f(x₃) = -35.9.

Different versions of the conjugate gradient method can be applied to quadratic optimization problems and general unconstrained nonlinear optimization problems. The Fletcher-Reeves method extends the conjugate gradient method to nonlinear optimization problems by making two changes. First, the one-dimensional minimum along each conjugate vector is identified by a line search. Second, the residual is replaced by the gradient of the nonlinear function. The steps of the Fletcher-Reeves method are as follows.

1.Set an initial guess x₀. At x₀, evaluate the function, f(x₀), and its gradient, ∇f(x₀). Set p₀ = -∇f(x₀). Specify the convergence tolerance of the residual, > 0. Set the iteration number, i, to 0.

2.Check the norm of the gradient ∇f(x_i). If ∇f(x_i) < , stop.

3.Use a line search along the direction of the conjugate vector to determine the minimum x_i+1 = x_i + α_ip_i.

4.Evaluate the gradient ∇f(x_i+1).

5.Set β_i+1 = ∇f(x_i+1)^T∇f(x _i+1)∕∇f(x_i)^T∇f(x _i).

6.Set the conjugate vector p_i+1 = -∇f(x_i+1) + β_i+1p_i.

7.Set i = i + 1. Go to Step 2.

12.4.3 Second-Order Methods

Newton Method

Newton’s method approximates the function f(x) with a quadratic function at each iteration. The approximated quadratic function is minimized exactly, and a descent direction is evaluated.

In each iteration, the function is approximated as follows.

According to the first-order necessary condition, the first derivative of (x) should satisfy ∇ (x) = 0. This condition can be expressed as

(12.75)

Solving the above equation,

(12.76)

Assuming the inverse of the Hessian exists, then

(12.77)

The second term in Eq. 12.77 is used as the reasonable direction to estimate x_k+1 in the next iteration.

(12.78)

The descent direction, p_k, can be expressed as

(12.79)

If [∇²f(x _k)]^-1 exists, p_k can be evaluated using Eq. 12.79. The other way to evaluate the descent direction, p_k, is by solving the following equation.

(12.80)

Equation 12.80 can be solved by Gaussian Elimination, Cholesky Factorization, or other suitable methods.

The expression of the descent direction is simple in Newton’s method. However, Newton’s method has certain shortcomings. (1) Newton’s method does not always find a minimum, and might only find a stationary (not minimum) point. (2) It converges only if one starts sufficiently near an optimal solution. (3) The computational cost to evaluate the inverse of the Hessian is high, especially for high-dimensional optimization problems.

The steps to solve an unconstrained nonlinear problem are illustrated with the following example.

Example: Use Newton’s method to minimize the following function.

(12.81)

The gradient of f(x) is as follows.

(12.82)

The Hessian of f(x) is as follows.

(12.83)

The inverse of ∇²f(x) is as follows

(12.84)

Choose an initial point, x₀ = (10, 10)^T. The next point, x₁, is evaluated as follows.

(12.85)

The point x₁ = (0, 0)^T is the optimal solution for this example, and the optimal function value is f(x₁) = 0.

Quasi-Newton Methods

Quasi-Newton methods are among the most widely used methods for nonlinear optimization. When the Hessian is difficult to compute, quasi-Newton methods are effective for solving these kinds of problems. There are differentquasi-Newton methods, but they are all based on approximations of the Hessian by another matrix to reduce the computational cost. In Sec. 12.4.3, Newton’s method estimates the search direction, p_k, that satisfies the following equation.

(12.86)

Quasi-Newton methods use an approximation of the Hessian, B_k, to obtain the search direction, p_k. The search direction is obtained by solving

(12.87)

For one-dimensional nonlinear optimization problems, quasi-Newton methods are generalizations of the secant method. The secant method approximates the Hessian using

(12.88)

where f′(x_k) can be approximated as

(12.89)

For multidimensional nonlinear optimization problems, the above condition is rewritten as

(12.90)

From the above Eq. 12.90, the condition for the approximation matrix B_k is derived, which can be expressed as

(12.91)

The matrix B_k has n² entries and the secant condition only has a set of n equations. This condition is insufficient to define B_k uniquely. The matrix B_k does not always have a unique solution for the secant condition.

There are several ways to approximate and update the matrix B_k. Define two vectors, s_k and y_k, as follows.

sk	= xk+1 - xk	(12.92)
yk	= ∇f(xk+1) -∇f(xk)	(12.93)

As one of the approximation formulae, the symmetric rank-one update formula can be expressed as

(12.94)

The B_k’s updated by Eq. 12.94 are symmetric. However, they are not necessarily positive definite.

As one of the most widely used formulae, the BFGS update formula can be expressed as

(12.95)

Upon selecting the appropriate update formula of B_k, the quasi-Newton algorithm is illustrated as follows.

1.Choose a starting point x₀. Choose an initial Hessian approximation B₀, which can be the diagonal matrix, I. Set k = 0.

2.If x_k is optimal, stop.

3.Determine the search direction, p_k, by solving B_kp_k = -∇f(x_k).

4.Find the step length, α_k, by a line search to minimize f(x_k+ α_kp_k).

5.Set x_k+1 = x_k + α_kp_k.

6.Update B_k+1 using the selected update formula.

7.Set k = k + 1 and go to Step 2.

The steps to solve an unconstrained nonlinear problem are illustrated with the following example.

Example: Use a quasi-Newton method with the symmetric rank-one B_k update formula to solve the following three-dimensional quadratic problem.

(12.96)

(12.97)

(12.98)

Choose an initial point x₀ = (0, 0, 0)^T. The initial guess is B₀ = I. At this point, x₀, ∇f(x₀) = -c = 14.4568, so this point is not optimal.

From B₀p = -∇f(x₀), the first search direction is derived as

(12.99)

The line search formula gives α₀ = 0.3025. The new estimated point is

(12.100)

The gradient at the new point x₁ is

(12.101)

To update B₁, first evaluate s₀ and y₀.

(12.102)

(12.103)

(12.104)

At this new point x₁, ∇f(x₁) = 5.2423. It is not optimal. The search direction is

(12.105)

The line search step length is α₁ = 0.3471. At the new point, x₂, the new estimates of the solution, the gradient, and the Hessian are

(12.106)

(12.107)

(12.108)

At the point x₂, ∇f(x₂) = 0.8397. It is not optimal. The new search direction is

(12.109)

and the step length α₂ = 0.4145. The line search yields the point

(12.110)

At point x₃,

(12.111)

The point x₃ is the optimal solution to this example, and the optimal function value is f(x₃) = -35.9.

12.5 Comparison of Computational Issues in the Algorithms

12.5.1 Rate of Convergence

The optimization algorithms discussed in this chapter are iterative methods, and are used to evaluate a sequence of approximate solutions. The rate of convergence is a measure of efficiency, which describes how quickly the estimates of the solution approach the exact solution. Efficient algorithms reduce the computational cost. Assume a sequence of points x_k converges to a solution x^*. The error at the k^th iteration can be defined as

(12.112)

As the sequence approaches the solution x^*, the limit of e _k is 0.

If Eq. 12.113 holds, the sequence x_k is said to converge to x^* with rate r and rate constant C. The constant C < ∞.

(12.113)

For a sequence of errors, when r = 1, the convergence is said to be linear, as Eq. 12.114 indicates. Note that if 0 < C < 1, then the norm of the error is reduced at every iteration. If C > 1, then the sequence diverges.

(12.114)

If r = 1 and C = 0, the rate of the convergence is said to be superlinear. For any r > 1, if

(12.115)

then Eq. 12.116 holds. Any convergence with r > 1 has a superlinear rate of convergence.

(12.116)

When r > 2, the convergence is called quadratic. The rates of convergence for some optimization algorithms in this chapter are listed in Table 12.5.

Table 12.5. Comparison of Optimization Methods for Unconstrained Nonlinear Problems