Page 233 - Compact Numerical Methods For Computers

Left-overs 221
enough to generate a reasonable derivative approximation. Note that both smaller
and larger values of h generated better approximations for the derivative of this
function. The exponential function is changing only very slowly near this point.

18.3. CONSTRAINED OPTIMISATION
The general constrained function minimisation problem is stated: minimise S( b)
with respect to the parameters b , i=1, 2, . . . , n, subject to the constraints
i
c (b)=0 j=1, 2, . . . ,m (18.7)
j
and
h (b)<0 k=1, 2, . . . , q. (18.8)
k
In general, if the constraints c are independent, m must be less than n, since via
solution of each constraint for one of the parameters b in terms of the others, the
dimensionality of the problem may be reduced. The inequality restrictions h, on
the other hand, reduce the size of the domain in which the solution can be found
without necessarily reducing the dimensionality. Thus there is no formal bound to
the number, q, of such constraints. Note, however, that the two inequalities

h(b)<0
(18.9)
h(b)>0
are obviously equivalent to a single equality constraint. Moreover, a very simple
change to the constraints (1 8.9) to give
h(b)+ e<0
(18.10)
h(b) - e> 0

for e > 0 shows that the inequality constraints may be such that they can never be
satisfied simultaneously. Problems which have such sets of constraints are termed
infeasible. While mutually contradicting constraints such as (18.10) are quite
obvious, in general it is not trivial to detect infeasible problems so that their
detection can be regarded as one of the tasks which any solution method should
be able to accomplish.
There are a number of effective techniques for dealing with constraints in
minimisation problems (see, for instance, Gill and Murray 1974). The problem is
by and large a difficult one, and the programs to solve it generally long and
complicated. For this reason, several of the more mathematically sophisticated
methods, such as Lagrange multiplier or gradient projection techniques, will not
be considered here. In fact, all the procedures proposed are quite simple and all
involve modifying the objective function S(b) so that the resulting function has its
unconstrained minimum at or near the constrained minimum of the original
function. Thus no new algorithms will be introduced in this section.

Elimination or substitution
The equality constraints (18.7) provide m relationships between the n parameters
b. Therefore, it may be possible to solve for as many as m of the b ’s in terms of