In optimisation we are in a situation where a variety of acceptable answers are available to our problem. The aim is to determine which one is best in terms of some specified criterion.
Note that:
`Given a set of variables x_{i}, i = 1, 2 ,... n and an objective function P (x_{1}, x_{2}, x_{3} ...) find values for the x_{i} such that P is a minimum (or a maximum).'
This is called an unconstrained optimisation problem.
The next most complicated class of problem conceptually is an optimisation with inequality constraints. We may write the definition of this as:
`Given a set of variables x_{i}, i = 1, 2 ,...
n and an
objective function
P (x_{1}, x_{2},
x_{3} ...) find values for the x_{i}
such that P is a minimum but such that a set of inequalities:
g_{1} (x_{1}, x_{2},
x_{3} ...) < 0
g_{2} (x_{1}, x_{2},
x_{3} ...) < 0
.....
g_{m} (x_{1}, x_{2},
x_{3} ...) < 0
are not violated.'
As noted above we cam maximise the o.f. by changing its sign and minimising, and so can drop the explicit reference to maximisation. Similarly, we can express any kind of inequality in the above form by appropriate manipulation of the expression. The above definitions are of an optimisation involving n decision variables. Note that the number of inequality constraints, given above as m is in no way connected to the number of variables n. There may be either more or fewer inequality constraints than variables.
This may be seen most easily with a simple example.
Minimise P = x²
2. For case 1 the optimum is the same as in the unconstrained case, because its value, x=0, satisfies both the inequalities. The constraints have no effect and so are said to be inactive.
For case 2. the unconstrained optimum does not satisfy the new third inequality. The lowest value of the o.f. which satisfies it will lie at x=2, i.e. actually on the constraint, with an o.f. value of 4. The constraint is said to be active and is in effect an equality constraint since it forces x to be 2.
3. If the equality constraint is satisfied, then x must equal 2. This is no longer an optimisation problem, as its solution is found by solving an equation, which corresponds to the equality constraint.
In general every equality constraint reduces the effective number of `free' or design variables in an optimisation problem by one. Thus if there are:
These are based on the techniques used to solve sets of linear equations.
The principles of linear programming are very simple. If the objective function is linear, then it cannot have an unconstrained minimum at any finite values of the variables. The unconstrained minimum must be minus infinity and lie at values of the variables which are either plus or minus infinity..
This is clear if you consider a single variable example, e.g.
Minimise P = x + 4
Clearly the unconstrained minimum must lie at x=-oo
The optimum of an LP must lie at a point which satisfies all the equality constraints, the active inequality constraints treated as equalities. LP can thus be thought of as a trial and error procedure which involves repeatedly solving sets of linear equations in order to find which constraints are active.
Many highly developed LP packages are available commercially and are quite user friendly. We will give one example here, but in general will not say any more about this technique.
Situations which involve discrete valued decisions, e.g. whether to have one type of equipment or another type or none at all.
Example: In a particular process we may install 1, 2 or 3 CSTRs of the same size in series. This is an IP problem in a single variable to which the answer may be 1, 2 or 3.
Since there are always a finite number of solutions to an IP problem (for a problem with continuous variables there will be an infinite number) it is possible in principle to solve by complete enumeration, i.e. simply generating and evaluating all solutions. For small problems such as this one this approach is quite feasible.
Consider what would happen if instead of having only a single size of reactor we had a choice of two and could install either a large or a small unit in each of the positions in series. The number of alternatives is now much larger, and can be illustrated as in this diagram.
This tree diagram is one of the classical ways of representing IP problems. The tree has its root at the square box labelled `Reactor 1', and its leaves are the ellipses marked `Evaluate'. The square boxes represent decision nodes at which it is decided what size of reactor to install, and the branches leaving these nodes are labelled L, S or N depending on whether a large or small reactor, or none at all, has been chosen.
At each of the leaves or terminal nodes one complete process alternative has been specified and may be evaluated.
Different IP methods involve different ways of generating and searching the tree of alternatives. `Smart' methods involve two main ideas:
One way of approaching IP problems such as this which represent process structural alternatives is to generate a `superflowsheet' or superstructure which contains within it all possible process structures. Here is such a superstructure for the three reactors with two possible sizes. The large square boxes represent the large reactors and the small ones the small. The circles can be though of as representing two-way on-off valves which may switch the input from the left to either of two outputs to the right.
It can be seen that this process involves 9 decision variables, one for each `valve'. In modelling this process for optimisation, if no feed reaches a reactor then it is deemed not to be needed and so has no cost. We could have used a smaller number of `three-way valves' but most of the classical IP techniques actually allow variables to have only two values, i.e. they are binary numbers. The superstructure has thus been set up to use only binary valves.
A MILP problem must firstly involve only linear linear constraints (i.e. equations) and a linear objective function.
The examples described in section 5.3.1 are all one variable NLP problems.
For general multivariable nonlinear optimisation, extensions of the methods described for single variables can be used. However, for a large and complicated problem the effort involved in differentiation for the first derivatives (of which there will be a matrix called a Jacobian matrix) and then the second derivatives (called the Hessian matrix) can be considerable.
Non-gradient methods are available, but are very inefficient compared with their performance for single variables.
We describe briefly below two NLP methods which seek to get round these difficulties.
A new linear approximation can now be made, and solved, and then the process repeated. The approach is thus similar conceptually to equation solving procedures which use linear approximations.
Unfortunately, because a linear program always finds its optimum on a constraint, if the optimum for the NLP is not in fact constrained, this method will not find it! Although it has some disadvantages, SLP may be an effective method if the optimum is known to lie on a constraint. There are even ways of making it work when the optimum is unconstrained, but this uses a concept known as a `trust region' and is not a commonly available technique.
SLP is not much used for process engineering problems, SQP, described below, is more usual.
Special and efficient methods exist for solving this type of problem.
SQP (successive quadratic programming) works like SLP except that the o.f. is made approximately quadratic rather than linear. This means that the optimum may lie away from a constraint. The constraints are given linear approximations. Section 5.3.3 describes quadratic approximation as applied to a one variable situation.
SQP is one of the most effective NLP techniques and is now the preferred method for most large scale optimisation.
As might be expected, this class of problem is hard to solve. the most usual approach is to decompose the problem into an MILP and an NLP and solve these alternately, feeding the results of one stage into the next.
Next - Section 5.2.1: Data Fitting as
Optimisation
Return to Section 5 Index
Course Organiser Last Modified 4/9/00