Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-06-27
2003-02-04
Amsbury, Wayne (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C703S002000
Reexamination Certificate
active
06516313
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to optimizing complex systems, and more particularly to methods for handling constraints in a vertex based optimization of a continuous constrained complex system.
BACKGROUND OF THE INVENTION
In a complex physical system, such as a power or chemical plant, various attributes, e.g., cost, profit, product, waste, quality, and efficiency, can be modeled by an objective function F(x), where x represents design (input) parameters that determine a performance (output) of the objective function. The design parameters define a search space, where each instantiation of x of the search space has a corresponding performance.
It is desired to optimize the performance of the system. This can be done by locating an optimum performance in the search space. Typically, optimization minimizes waste, and maximizes product, quality, and efficiency.
Due to engineering complexities, the design parameters may also have to conform to physically feasible limits called constraints C(x). The constraints can be dependent or independent of the objective function. For some design parameters, the performance may be infeasible.
In many complex physical systems the objective function and the constraints are non-linear, non-differentiable, and noisy. This makes it more difficult to optimize the objective function.
Formally, the optimization problem can be stated as follows. Maximize the objective function F(x) subject to constraints C
i
(x)≧0, where x is a real-valued vector of design parameters x
1
, x
2
, x
3
, . . . , x
n
for all x&egr;R
n
, and i=1, . . . , m. If function minimization is required, then multiply the objective function by negative one to recast the problem to function maximization. Similarly, any constraint in the form C
i
(x)≦0 can be recast into the canonical form by multiplying C
i
(x) by negative one. In the following, the terms “better and worse” performance will be used to cover both maximization and minimization problems.
FIG. 1
shows an example chemical plant
100
in simplified form. Using a cooler
101
and a heater
102
, the system separates product
103
and waste
104
from an input stream
105
. The system includes a condenser
106
, a reboiler
107
, and reactive plates
108
in a distillation or fractionating column.
The objective function F(x)
110
that models the system
100
maximizes the amount of the product (P)
113
, and minimizes waste (W)
114
for a particular input stream (I)
115
. The design parameters
111
, vector x, can include the rate of flow in the input, the heating and cooling rates applied, the liquid and vapor compositions of each component on each plate, and the vapor pressure.
The design parameters x are subject to restrictions or interrelations, i.e., constraints C(x)
116
of many kinds. For example, compositions and flows must be positive, temperatures must not exceed certain upper bounds. More complicated constraints indicate how components interact physically. For instance, vapor and liquid compositions are related by a highly non-linear function of temperature. Careful analysis of the system
100
allows one to generate the appropriate objective function F(x)
110
and constraints C(x)
116
. The function F can then be optimized to maximize product and minimize waste under particular operating conditions.
Many constrained optimization functions are solved by searching for optima in the search space using an adaptive optimization method. Often the optima lie near constraint boundaries. Consequently, avoiding search in constrained space can hinder the optimization method's path to the optima.
The original idea for an adaptive optimization method was described by Box in “Evolutionary Operation: A Method for Increasing Industrial Productivity,” International Conference on Statistical Quality Control, Paris, July 1955, reproduced in
Applied Statistics
, VI, pp. 3-22, 1957. Box developed an idea he called “evolutionary operation.” Evolutionary operation pertains to an empirical optimization of full scale processes, subject to errors in observations. The basic idea is to replace the static operation of a process by a continuous and systematic scheme of slight perturbations in the control parameters. The effect of these perturbations is evaluated and the process is shifted in the direction of improvement. Box was interested in increasing production by systematically adjusting process parameters that affect output. His idea for evolutionary operation was more related to an operational procedure which a plant manager might follow than it was to optimization with a computer system.
In 1962, Spendley et al., in “
Sequential Application of Simplex Designs in Optimization and Evolutionary Optimization
,” Technometrics, November 1962, applied a simplex method to the problem of non-linear numerical optimization. This simplex method should not be confused with the simplex method for linear programming.
A simplex is a geometric construct that has one more vertex than the number of dimensions in the search space. If k is the number of dimensions in the search space, then the simplex is defined by k+1 vertices in that search space. As shown in
FIG. 2
, a simplex in two dimensions is defined by three vertices. In one, two, and three dimensions, the simplex is respectively a line, a triangle, and a tetrahedron. In complex systems, the dimensionality of the search space can be quite large, for example, twenty or more. The lines connecting the vertices are used to visualize the simplex. They have no other function. Each vertex is a graphical representation of one of the objective function's constraint relations and an associated performance of F(x) that determines its relative worth to the simplex.
A simplex process locates an optimum of the objective function F based on the movement of the simplex through the search space. The simplex is driven through a sequence of logical moves based on the performance evaluated as each vertex, and the orientation of the simplex. While the simplex is moved, it can adaptively change in shape as the spacing and curvature of the contours of the search space defined by the objective function F change.
As shown in
FIG. 3
, the basic simplex method.
300
is easy to understand and apply. The optimization begins with initial trials. The trial conditions are spread out evenly. The number of initial trials is equal to the number of design parameters plus one. The initial trials form the first simplex.
The basic simplex method has the following rules. The first rule rejects the trial with the worst performance in the current simplex. A next performance value is determined, by reflection
320
into the search space opposite the undesirable result. This next trial replaces
330
the worst trial in the simplex. This leads to a next worst performance in the simplex that, in turn, leads to another next trial, and so on. At each step, one moves away from the worst performance. By that, the simplex moves steadily towards a better performance.
The second rule never returns to the performance that has just been rejected. The calculated reflection in the search space can also produce a worst performance. Without this second rule the simplex would just oscillate between the performance values. This problem is nicely avoided by choosing the second worst performance and moving away from it.
Besides these two main rules, two additional rules are also used. Trials retained in the simplex for a specified number of steps are reevaluated
340
. In the presence of noise, where identical design parameters give different performance values, the reevaluation rule avoids the simplex from getting stuck around a false worst performance. Trials never cross a constraint boundary of the search space. Instead, a very unfavorable performance is applied, forcing the simplex to move away from the constraint boundary.
A modified simplex method can adjust the shape and size of the simplex depending on the response in each step. This method is also called the variable-size simple
Al-hashemi Sana
Amsbury Wayne
Brinkman Dirk
Mitsubishi Electric Research Laboratories Inc.
LandOfFree
Method for dynamic constraint handling in vertex based... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for dynamic constraint handling in vertex based..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for dynamic constraint handling in vertex based... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3139039