Chapter 1 - Introduction

Perspective
Formulation of Optimization Problems
Topics in Optimization
Method of Attack
Summary

Perspective

The objective of optimization is to select the best possible decision for a given set of circumstances without having to enumerate all of the possibilities. From experience, designers learn to recognize good proportions and critical restrictions so their preliminary work will not require significant modification and improvement. The subject which formulates and explains this talent is a branch of applied mathematics known as optimization theory, a science that studies the best (1). In recent years the subject of optimization has matured and is widely used in numerous applications, e.g., petroleum refining operations, routes for commercial aircraft, livestock feed blending and missile trajectories. Optimization methods take advantage of the mathematical structure of the problem to find the best values efficiently; and the size of the problems being solved has followed the growth in computer capability, especially in the case of linear programming.

Scientists, especially mathematicians, have always been occupied with questions of optimization, i.e., finding extreme points (maxima and minima). Euclid in 300 B.C. was associated with the problem of finding the shortest distance which may be drawn from a point to a line, and Heron of Alexandria in 100 B.C. studied the optimization problem of light traveling between two points by the shortest path. It was Fermat in 1657 who developed the more general principle that light travels between two points in a minimum time. In 1857 Gibbs developed the law which states that a system is in chemical equilibrium if the free energy is a minimum (2). This result is routinely used today to compute the equilibrium composition of a multicomponent mixture of gases, liquids and solids.
The development of mathematical theory for optimization followed closely with the development of calculus, as pointed out by Hancock(3). In fact, Hancock wrote the first modern book on the subject, entitled Theory of Maxima and Minima, which was published in 1917. This definitive work serves even today as an authoritative source.

In the late 1930's there was a spurt of interest in the subject of the calculus of variations, but the real impetus to optimization came with World War II and the development of the digital computer. In the 1940's Dantzig (4) recognized the mathematical structure of some military logistics problems and developed the Simplex Method of linear programming. Linear programming has moved from an interesting mathematical topic to probably the most important and widely applied optimization procedure. Its development followed closely the continually increasing capabilities of the digital computer. The ability to solve large sets of linear equations with the computer has permitted the application of linear programming to industrial problems, such as the optimization of a large petroleum refinery.
Again in the 1950's optimization received another boost with the advent of the space age. The optimal trajectory for a missile was one of a number of problems for which the methods of dynamic programming and the maximum principle were developed in this country and the U.S.S.R. These methods are now being used in areas that are not space-related.

Formulation of Optimization Problems

Three basic components are required to optimize an industrial process. First, the process or a mathematical model of the process must be available, and the process variables which can be manipulated and controlled must be known. Often, obtaining a satisfactory process model with known control variables is the most difficult task. Secondly, an economic model of the process is required. This is an equation that represents the profit made from the sale of products and costs associated with their production, such as raw materials, operating costs, fixed costs, taxes, etc. Finally, an optimization procedure must be selected which locates the values of the independent variables of the process to produce the maximum profit or minimum cost as measured by the economic model. Also, the constraints in materials, process equipment, manpower, etc. must be satisfied as specified in the process model.
Figure 1-1 is a diagram that helps place industrial practice in perspective by relating process and economic models and the two levels of optimization. Plant optimization finds the best operating conditions for a plant made up of process units manufacturing specified amounts of various products to maximize the company's profits within the constraints set by the available raw materials and how these raw materials can be transformed in the plant. Plant optimization usually approximates the individual process units in a relatively simple manner to obtain a satisfactory answer in a reasonable time. This requires that the optimal operating conditions of the individual process unit be known, and these results be used in the plant optimization to have the plant operating with the maximum profit. Also, due to the complexity of large industrial plants, individual process models are usually simplified by using simulation equations to keep the computer programming efforts and computer costs within reason. However, with individual process units it is feasible to use more detailed models to determine more precisely the optimal operating conditions, e.g., temperatures, pressures, recycle rates, etc. to have minimum operating cost known as a function of these variables.

As shown in   Figure 1-1, simulation equations are obtained from process models. The procedure is to develop precise process models based on the fundamentals of thermodynamics, kinetics and transport phenomena. This usually leads to process models which accurately represent the physical and chemical changes taking place over a wide range of conditions. However, these models usually are more complicated in mathematical form and may require the solution of differential equations. Consequently, these process models are usually exercised over the range of operation of the process, and simulation (regression) equations of a simplified mathematical form are developed, which are then used with the optimization method for the plant optimization. However, it may not be necessary to go through the simulation equations step if the equation that describe the key variables, i.e., the ones that effect the economic performance of the process or plant, are not complicated.

Topics in Optimization

The two areas of optimization theory are mathematical programming and variational methods, as shown in Figure 1-2. Also, a number of techniques are listed under each of these areas. In mathematical programming, the objective is to locate a best point x (x1,x2,...xn) which optimizes (maximizes or minimizes) the economic model of the process. In variational methods, the objective is to locate the optimal function which maximizes or minimizes the economic model. An example of an optimization problem for each division is given in the figure. Generally, mathematical programming methods are applicable to steady-state problems, and variational methods are for dynamic problems.

Mathematical programming methods are of two types and are referred to as direct or indirect methods. Direct methods, such as multivariable search methods and linear programming, move from a starting point through consistently improved values of the economic model to arrive at the optimum. Indirect methods, such as analytical methods and geometric programming, solve a set of algebraic equations, and the solution to the set of equations may be the optimum of the economic model. For example, in analytical methods the algebraic equation set is obtained by differentiating the economic model with respect to each independent variable and setting the resulting equations equal to zero.

In this book, the first seven mathematical programming methods listed in Figure 1-2 will be discussed as will the topic of the calculus of variations under variational methods. These were selected because they are the more widely used in industrial practice. A bibliography of texts on each of these subjects is given at the end of each chapter.

To briefly describe the topics given in Figure 1-2, analytical methods are also called the classical theory of maxima and minima which is concerned with finding the extreme points of a function. This topic is discussed in Chapter 2 for both unconstrained and constrained optimization problems. Geometric programming may be considered an extension of analytical methods where the economic model and constraints are polynomials, and a dual problem is constructed that may be significantly easier to optimize than the original or primal problem as described in Chapter 3.

Optimization

 

Figure 1-2 Areas and Topics in Optimization

Linear programming requires that both the economic model and the set of constraint equations be linear, and the Simplex Method is the algorithm which locates the optimum by beginning at a feasible starting point (initially feasible basis) as discussed in Chapter 4. In quadratic programming, the economic model is a quadratic equation and the constraint equations are linear. Using analytical methods, this problem can be converted to a linear programming problem and solved by the Simplex Method as shown in Chapter 6. For convex programming, the economic model is a concave function, and the constraint equations are convex functions. The details on this procedure are given in Chapter 2 as part of general analytical methods and show that a global optimum will be located. Dynamic programming uses a series of partial optimizations by taking advantage of the stage structure in the problem and is effective for resource allocation and optimization through time as discussed in Chapter 7. Nonlinear programming or multivariable search methods, as the theory and algorithms are called, must begin at a feasible starting point and move toward the optimum in steps of improved values of the economic model. The algorithms described in Chapter 6 have been effective for optimization of industrial processes, and they are based on the theory of Chapter 2.
Integer programming is an extension of linear programming where the variables must take on discrete values, and a text on this topic is by Taha(5). Separable programming is an extension of linear programming where a small number of nonlinear constraints are approximated by piecewise linear functions. However, the nonlinear functions must have the form so they can be separated into sums and differences of nonlinear functions of one variable, and the IBM MPSX code(6) is capable of solving these problems. Goal programming is an extension of linear programming also where multiple, conflicting objectives (or goals) are optimized using weights or rankings, for example, and this technique is described by Ignizio(7). Combinatorial programming has been described by Popadimitriou and Steiglitz(1) as a body of mathematical programming knowledge including linear and integer programming, graph and network flows, dynamic programming and related topics. The maximum principle is comparable to dynamic programming in using the stage structure of the system, but it uses constrained derivatives that require piecewise continuously differentiable functions and successive approximations(2). Finally, the term heuristic programming has been used to describe rules-of-thumb that can be used for approximations to optimization.

In discussing the various topics in optimization, the economic model has been given several different names. These names arose in the literature as the optimization procedures were being developed. Regardless of the name, the economic model is the equation which expresses the economic return from the process for specified values of the control (manipulative, decision or independent) variables. The two most common names are the profit function or cost function. However, in linear programming the term objective function is used, and in dynamic programming the term return function is employed. Other synonymous names are: benefit function, criterion, measure of effectiveness and response surface.

Method of Attack

In solving an optimization problem, the structure and complexity of the equations for the economic model and process or plant constraints are very important, since most mathematical programming procedures take advantage of the mathematical form of these models. Examples are linear programming, where all of the equations must be linear, and geometric programming, where all of the equations must be polynomials. Consequently, it is extremely important to have the capabilities of the various optimization techniques in mind when the economic and process models are being formulated. For example, if a satisfactory representation of the economics and process performance can be obtained using all linear equations, the powerful techniques of linear programming can be applied, and this method guarantees that a global optimum is found. However, if one has to resort to nonlinear equations to represent the economics and process performance, it may be necessary to use a multivariable search method to locate the optimum. Unfortunately, these search techniques only find points that are better than the starting point, and they do not carry any guarantee that a global or a local maximum or minimum has been found.

Figure 1-3, shows a simplified approach to attacking an optimization problem, and it incorporates some thoughts which should be remembered as the particular optimization techniques are studied. Also, it will give some reasons for the order in which the techniques are presented. At the start, it is necessary to determine if the problem requires an optimal point or function. If it is a point, mathematical programming is applicable; and if an optimal function, variational methods. Let us follow through with mathematical programming. If the equation for the economic model is relatively simple and there are no applicable constraints (process model), it is possible to locate the optimum by differentiating the economic model with respect to the independent variables, setting these equations equal to zero, and solving for the optimum. However, if there are constraints, and there usually are, but the equations are relatively simple, the method of Lagrange multipliers may be used. This converts the constrained problem to an unconstrained problem, and the previous procedure for unconstrained problems is used.

Now, if the problem has a large number of independent variables and the precision needed for the economic and process models can be obtained with linear equations, then linear programming may be used. However, if nonlinear equations are required and polynomial will suffice, it may be possible to determine the optimum rapidly and easily using geometric programming (1).

Not having been successful to this point, it may be feasible to take advantage of the stage structure of the problem and apply dynamic programming with a series of partial optimizations. However, if this is not successful it will be necessary to resort to multivariable search techniques and seek best values without having a guarantee of finding the global optimum.

Summary

This chapter presented a brief discussion of the historical background of optimization. Then the relation of process and plant optimization was described in terms of using simulation equations and problem size. The topics in the areas of mathematical programming and variational methods were diagrammed, and a simplified method of attack was described to give some perspective about the different methods as they are studied. The next chapter reviews analytical methods and sets the stage for more modern techniques.

References

1. Wilde, D.J., Globally Optimal Design, John Wiley and Sons, Inc., New York (1978).
2. Wilde, D.J. and C.S. Beightler, Foundations of Optimization, Prentice Hall, Inc., Englewood Cliffs, New Jersey (1967).
3. Hancock, Harris, Theory of Maxima and Minima, Dover Publications, Inc., New York (1960).
4. Dantzig, G.B., Linear Programming and Extensions, Princeton University Press, Princeton, New Jersey (1963).
5. Taha, H.H., Integer Prograsmming: Theory, Applications and Computations, Academic Press, New York (1975).
6. IBM Mathemcatical Programming Systems Extended/370 (MPSX/370) Program Reference Manual, Fourth Edition, SH19-1095-3, IBM Corporation, White Plains, New York (December, 1979).
7. Ignizio, J.P., Linear Programming in Single- and Multiple-Objective Systems, Prentice-Hall, Inc., Englewood Cliffs, New Jersey (1982).
8. Papadimitriou, C.H., and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Inc., Englewood Cliffs, New Jersey (1982).