tutorial solutions 2005

Eng732

Informations

• Publié par: Insya
• Nombre de lectures: 9
• Langue: English

Extrait

EG5090: Mathematical Optimisation

Tutorial Solutions

2005-06


1: 1a

With reference to the figure:

f x( )
x = b1x = c = (a +b )2
x = a
x


the algorithm operates by examining the value of f(x) at the centre point x = c of an interval
x = a to x = b that is known to bracket at least one root: that is, as shown,
signum(f(a)) ≠ signum(f(b)). Then, depending on the sign of f(c), it can be determined
whether the root lies in the upper or lower half of the original range. The appropriate half is
then bisected in the same fashion, and the process is continued to convergence.

1b

Using PDL, this algorithm can be represented by:

function x = root(f,a,b,tol)
if f(a) != f(b) then error(“points do not bracket root”)
if f(a) > f(b) then exchange a and b
convgd = FALSE
while(not convgd)
c = (a+b)/2
if f(c) > 0 then b = c else a = c
if c – a < tol then convgd = TRUE
end while
return x = c



11c

Linear convergence: the solution interval h after k iterations is given by k

h = ε h k k −1 k −1

where ε is either constant or weakly dependent on k. Thus the solution interval (or search k-1
space) reduces by a constant, or nearly constant, fraction on each iteration. Each factor of 10
improvement in precision, for instance, will require a similar number of additional iterations.

1In the case of the bisection method, the interval is halved at each step: h = h . k k −12

100 4For a reduction of interval to 0.01%, exhaustive search requires of order = 1 ×10 steps,
0.01
⎛ 100 ⎞
bisection requires log = 13.29 steps, or 14 steps, a speed advantage of a factor of ⎜ ⎟2 0.01⎝ ⎠
41 ×10 14 = 714.29 .

1d

Methods include Newton’s method and the secant method, both of which approximate the
form of f(x) by a straight line, and are able to find the root in one step for an exactly linear
function. Newton’s method is defined by

f()xk x = x − . k +1 k df()x dxk

In the secant method, an interval is maintained (as in the bisection method) but these are
used to approximate the slope of the function: at each step a new estimate is added using

f()xk x = x − ()x − x . k +1 k k k −1f()x − f(x )k k −1

Newton’s method is shown by (a similar diagram can be used for the secant method):

f(x)
f(x)
x
x k+1 x k

2
1e

In either of these methods, there is no guarantee of convergence. If the function shows a
region of negative slope at x in the above figure for instance, the step will move x further k k+1
from the root. In the secant method, although a pair of points is used, there is no check of
sign reversal and there is no guarantee that the root will be bracketed.

Accordingly, such methods can be combined with a check to confirm that a step has been
successful, according to some criterion (the most conservative being sign reversal) . If the
step is successful, the next step is taken using the “fast” algorithm. Otherwise, a bisection
step can be taken.



2: 2a

The triplet a<b<c “brackets” a minimum of f(x) if f(b)<f(a) and f(b)<f(c). Thus f(x) has a
minimum in the interval a<x<c. (Similar statements hold for a maximum.)

2b

Consider such a triplet, shown as points 1, 2, 3 in Fig (i), corresponding to a, b, c
respectively. Then choose a new position 4 within the bracketing interval, as in Fig (ii).
Since f(x )>f(x ), position 4 is taken as a new point c, replacing 3. 4 2

f(x) f(x)
1 1
3 3
4
2 2
x x
(i) (i)
f(x) f(x)
1 1
3 3
5 54 4
2 2
6
x x
(i) (iv)

Similarly in Fig. (iii), point 5 replaces 1 as a new point a. In Fig. (iv), new point 6 has
f(x )<f(x ), so that point 6 becomes a new point b and point 2 becomes a new point a. After 5 2
this sequence, the minimum is bracketed by points 2, 6 and 4. This process is repeated until
the minimum is bracketed sufficiently closely, and the final point b gives the approximation
of the minimum.
3
2c

In the scheme described in (b), suppose that the positions of a, b, c are at any stage related by

b − a
= A (1)
c − a

at each stage the new point x is chosen at a fractional distance B in the interval:

x − a
= B. 2)
c − a

Suppose also that B>A. Depending on the outcome of introducing the new point, the new
bracketing triplet is then either a, b, x or b, x, c and so is of fractional length B or 1-A,
respectively. To provide a uniform length reduction, independent of which step is taken,
make these equal:

B = 1 − A. (3)

Also require that the relative distances in the new interval are the same as those in the
original interval, or

B − A
= A 4)
1 − A

and, putting (3) and (4) together, this gives

3 ± 52 A − 3A +1 = 0 or A = .
2

This is the so-called golden section.

2d

The method outlined above gives at iteration i+1 an interval ∆x such that: i+1

∆x = A ∆x i +1 i

where A is the constant given above. Hence the precision after iteration i+1 is linearly related
to the precision at the previous iteration.

a, b, c to obtain an To improve on this, quadratic interpolation can be used on the triplet
improved estimate of the minimum (maximum) position, on the assumption that the function
f(x) behaves quadratically, at least near its turning points. In practice, quadratic interpolation
is combined with golden section search (Brent’s method).





43: 3a

With reference to the figure below, a triplet of points a < b < c is chosen along the x-axis to
“bracket” the minimum, the requirement for which is f(b) < f(a) and f(b) < f(c). A fourth
point x = d is chosen within the interval a,c. (To secure an optimal rate of convergence, the
position of point d should be within the longer of the two intervals a,b and b,c and should
divide that interval in the “golden” ratio (3 − 5 ) 2 ≈ 0.382. However, neither proof nor
demonstration of this is required here.) There are now two possible cases to consider. In case
1 (as shown) f(d) > f(b) and the triplet a,b,d brackets the minimum. In case 2 f(d) < f(b) and
the triplet b,d,c brackets.

f(x)
case 1: f(d) > f(b)
new triplet is a,b,d
f(d)
f(b)
abdc x

the minimum. The new bracketing triplet is chosen, so that in case 1 the interval d,c is
discarded, or in case 2 the interval a,b is discarded. (For the optimal golden section choice of
position, either of the new triplets has overall length ≈0.618 of the original triplet.) This
process is continued until a sufficiently short triplet is reached.

3b

This would reduce the interval to 0.5 of its previous lengh at each iteration, rather than to the
“golden” ratio ≈0.618. However, it is necessary to check which half of the original interval
contains the minimum. A “natural” procedure is to select new points, again bisecting each
half-interval (see figure below).

f(d) > f(b), so that a,d,b does not
f(x) “bracket minimum, even though
minimum lies in interval a,b
b + c
e =
2
a + b
d =
2
a c x
a + c
b =
2
5As in this example, neither a,d,b nor b,e,c is guaranteed to bracket the minimum. Thus, the
original proposal is not a good idea. However, d,b,e does bracket, and is also of length 0.5.
Thus the method can be used, at the cost of a three-way rather than two-way decision at each
stage. As each decision requires one “wasted” computation of f(x), the final balance of
computational cost is not clear-cut.















































6