Nonlinear Systems and Optimization for the Chemical Engineer
Description
More details
Other editions
Additional editions
Persons
Flavio Manenti is assistant professor of chemical engineering at Politecnico di Milano, Italy. He obtained his academic degree and PhD at Politecnico di Milano, where he currently collaborates with Professor Buzzi-Ferraris. He holds courses on "Process Dynamics and Control of Industrial Processes" and "Supply Chain Optimization" and he works on numerical analysis, process control and optimization. He has also received international scientific awards, such as Memorial Burianec (Prague, CZ) and Excellence in Simulation (Lake Forest, CA, USA), for his research activities and scientific publications.
Content
FUNCTION ROOT-FINDING
Introduction
Substitution Algorithms
Bolzano's Algorithm
Function Approximation
Use of a Multiprocessor Machine with a Known Interval of Uncertainty
Search for an Interval of Uncertainty
Stop Criteria
Classes for Function Root-Finding
Case Studies
Tests for BzzFunctionRoot and BzzFunctionRootMP Classes
Some Caveats
ONE-DIMENSIONAL OPTIMIZATION
Introduction
Measuring the Efficiency of the Search for the Minimum
Comparison Methods
Parabolic Interpolation
Cubic Interpolation
Gradient-Based Methods
Combination of Algorithms in a General Program
Parallel Computations
Search for the Interval of Uncertainty
Stop Criteria
Classes for One-Dimensional Minimization
Case Studies
Tests
UNCONSTRAINED OPTIMIZATION
Introduction
Heuristic Methods
Gradient-Based Methods
Conjugate Direction Methods
Newton's Method
Modified Newton Methods
Quasi-Newton Methods
Narrow Valley Effect
Stop Criteria
BzzMath Classes for Unconstrained Multidimensional Minimization
Case Study
Tests
LARGE-SCALE UNCONSTRAINED OPTIMIZATION
Introduction
Collecting a Sparse Symmetric Matrix
Ordering the Hessian Rows and Columns
Quadratic Functions
Hessian Evaluation
Newton's Method
Inexact Newton Methods
Practical Preconditioners
openMP Parallelization
Class for Large-Scale Unconstrained Minimization
ROBUST UNCONSTRAINED MINIMIZATION
Introduction
One-Dimensional Minimization
Classes for One-Dimensional Robust Minimization
Examples in One-Dimensional Space
Examples in Multidimensional Space
Two-Dimensional Space
Classes for Robust Two-Dimensional Minimization
Examples for BzzMinimizationTwoVeryRobust Class
Multidimensional Robust Minimization
Class for Robust Multidimensional Minimization
ROBUST FUNCTION ROOT-FINDING
Introduction
Class and Examples
NONLINEAR SYSTEMS
Introduction
Comparing Nonlinear Systems to Other Iterative Problems
Convergence Test
Substitution Methods
Minimization Methods
Jacobian Evaluation
Newton's Method
Gauss-Newton Method
Modified Newton Methods
Newton's Method and Parallel Computations
Quasi-Newton Methods
Quasi-Newton Methods and Parallel Computing
Stop Criteria
Classes for Nonlinear System Solution with Dense Matrices
Tests for the BzzNonLinearSystem Class
Sparse and Large-Scale Systems
Large Linear System Solution with Iterative Methods
Classes for Nonlinear System Solution with Sparse Matrices
Continuation Methods
Solution of Certain Equations with Respect to Certain Variables
Case Studies
Special Cases
Some Caveats
UNDERDIMENSIONED NONLINEAR SYSTEMS
Introduction
Underdimensioned Linear Systems
Class for Underdimensioned Nonlinear System Solution
CONSTRAINED MINIMIZATION
Introduction
Equality Constraints
Equality and Inequality Constraints
Lagrangian Dual Problem
LINEAR PROGRAMMING
Introduction
Basic Attic Method Concepts
Attic Method
Differences between the Attic Method and Traditional Approaches
Explosion in the Number of Iterations
Degeneracy
Duality
General Considerations
QUADRATIC PROGRAMMING
Introduction
KKT Conditions for a QP Problem
Equality-Constrained QP
Equality- and Inequality-Constrained Problems
Class for QP
Projection or Reduced Direction Search Methods for Bound-Constrained Problems
Equality, Inequality, and Bound Constraints
Tests
CONSTRAINED MINIMIZATION: PENALTY AND BARRIER FUNCTIONS
Introduction
Penalty Function Methods
Barrier Function Methods
Mixed Penalty-Barrier Function Methods
CONSTRAINED MINIMIZATION: ACTIVE SET METHODS
Introduction
Class for Constrained Minimization
Successive Linear Programming
Projection Methods
Reduced Direction Search Methods
Projection or Reduced Direction Search Methods for Bound-Constrained Problems
Successive Quadratic Programming or Projected Lagrangian Method
Narrow Valley Effect
The Nonlinear Constraints Effect
Tests
PARAMETRIC CONTINUATION IN OPTIMIZATION AND PROCESS CONTROL
Introduction
Algebraic Constraints
1
Function Root-Finding
Examples of this chapter can be found in the Vol3_Chapter1 directory in the WileyVol3.zip file available at www.chem.polimi.it/homes/gbuzzi.
1.1 Introduction
This chapter deals with the problem of finding the value that zeroes a function in the one-dimensional space:
(1.1)
We will, for instance, find the value of that zeroes the function
(1.2)
in the interval .
Only real problems involving the variable are considered.
Later, we describe the main iterative methods used to numerically solve this problem: these are referred to as iterative because they provide a series of values such that the value of for a sufficiently large approximates the solution with the required precision.
A series converges to the solution with the order if
(1.3)
where C and are appropriately selected.
The function could prove very complicated and it is not necessary to have it as an explicit algebraic function. For example, the problem might be to find either the value that zeroes the integral
(1.4)
with or the value for which a combination of the elements of the vector is zero during the integration of a differential system
(1.5)
When the function is particularly simple, however, certain special algorithms can be used.
Only general algorithms are proposed here and the potential peculiarities of the function are not exploited. This means, for instance, that special methods designed to find the roots of a -degree polynomial are not considered.
It is important to distinguish between the following three situations:
1. The function assumes values with opposite signs at the interval boundaries . Furthermore, the function is continuous within the interval where a single solution exists or, if there is more than one solution, the program need find only one of them. The interval , in which function continuity and opposite signs at the boundaries are both present, is called the interval of uncertainty. 2. The interval of uncertainty is unknown but the function is monotone. 3. Neither the interval of uncertainty nor the function monotonicity is known. The function may have several solutions with the objective being to find all of them. Alternatively, it may have some discontinuities or may be zero in several points without changing the sign locally.When zeroing a function, there is a considerable difference between the first two situations and the third one.
This chapter introduces the algorithms that solve the first two families of problems. The third family of problems, however, demands more robust algorithms (see Chapter 6).
When the interval of uncertainty for a function is known or the function is monotone, special algorithms can be used to guarantee the following appealing features:
1. A solution with a finite number of calculations. 2. A solution with a predictable number of calculations for every required accuracy. 3. High performance.It is also necessary to distinguish between two different situations in this discussion:
- The computer is either a monoprocessor or parallel computing is unsuitable or cannot be exploited. Specifically, it is unsuitable when the function is very simple and it cannot be exploited when root-finding is part of a calculation in which parallel computations have already been used.
- It is possible – and helpful – to exploit parallel computing for function root-finding.
The algorithms used to find roots of functions can be grouped into three families:
1. Substitution algorithms. 2. Bolzano algorithms. 3. Algorithms that approximate the function with a simpler function.Analyzing simple problems and algorithms like this is particularly instructive as it illustrates the various ways of solving numerical problems: by using manual methods and classical analysis (without round-off errors) or, alternatively, a computer program (in which round-off errors play an important role) (Vol. 1 – Buzzi-Ferraris and Manenti, 2010a).
Anyone working on numerical problems may benefit from writing their own general root-finding function.
In the following, we will refer to the function evaluated in () simply as . We will also refer to the derivative as .
Before proceeding, however, we feel it is useful to reiterate an important statement from Vol. 1 (Buzzi-Ferraris and Manenti, 2010a).
When a problem is numerically solved on a computer, the round-off errors may become so relevant that even certain modifications to traditional classical analysis thought appear necessary.
Some methods for the collocation of a new point given a series of values demand function monotonicity.
A function, which is theoretically monotone in classical analysis (without round-off errors), can be constant in numerical analysis with respect to two points, if they are too close.
For instance, given the function
(1.6)
and two points and , the function value is the same in double precision because of the round-off errors.
The resolution, , represents the minimum distance required to ensure that a theoretically monotone function is also numerically monotone.
It is interesting to estimate the order of magnitude of for the root-finding problem. Let us suppose that the function can be expanded in Taylor series in the neighborhood of the solution, :
(1.7)
The term is not negligible with respect to when
In these relations, is the macheps of the calculation.
From (1.8), we obtain
(1.9)
The root of a function can be commonly found with a precision in the order of the macheps.
The previous discussion is valid only if ; otherwise, the function intersects the axis of abscissa horizontally and the points must be at least at a distance
(1.10)
When at the solution, the precision of a numerical method is proportional to rather than to . In double precision on 32 bit computers, the error is on the 6–7th significant digit rather than the 14–15th.
1.2 Substitution Algorithms
These algorithms transform the problem to produce expressions such as
(1.11)
so as to exploit the iterative formulation:
(1.12)
For example, given the function
(1.13)
we have
(1.15)
(1.16)
Starting from an initial point , the following series are obtained in correspondence with the functions (1.14)–(1.17), respectively:
- : the series diverges.
- : the series diverges.
- : the series diverges.
- : the series properly converges to the problem solution.
This approach was often adopted when the calculations were manual as no general programs were available to solve the problem in its original form.
However, this kind of procedure also has numerous disadvantages.
The iterative procedure can also diverge with very simple functions; for example, it can diverge with a linear equation.
If the iterative formula is linear
(1.18)
the method converges only if
(1.19)
It is useful to plot the two trends to illustrate the reason for this limitation:
(1.20)
and proceed with the iterations. Note that the method diverges if equation (1.21) has a slope and (Figure 1.1).
Figure 1.1 Convergence conditions of substitution algorithms.
When the procedure converges, the convergence is usually slow.
For example, the problem mentioned above
(1.22)
is solved using Newton's method, which has quadratic convergence, yielding the following series results: .
If the substitution method converges, the convergence speed can be improved using the Aitken method (Buzzi-Ferraris and Manenti, 2010a).
Given a linearly convergent series of , the Aitken formula generates a new and more efficient series :
(1.23)
For example, given the series
(1.24)
linearly converging to the value , the series from Table 1.1 is obtained.
A laborious preliminary study is required to convert the problem into a convergent form.
The substitution method is only useful from an educational point of view.
When such calculations were performed manually, a lot of time had to be devoted to search for a special method for solving a specific problem. We encountered several disadvantages to retaining this approach when developing computer programs:
1. Intrinsically similar problems (e.g., root-finding for different functions) are not solved by the same calculation procedure. 2. Techniques adopted to solve the problem are inextricably linked to the...