Chapter 5

Chapter 5

One Dimensional Search

1
 Unidimensional Search

(1) If have a search direction, want to minimize in that

direction by numerical methods
Chapter 5

(2) Search Methods in General

2.1. Non Sequential – Simultaneous evaluation of f at n
points – no good (unless on parallel computer).
2.2. Sequential – One evaluation follows the other.
2
 (3) Types of search that are better or best is often
problem dependent. Some of the types are:
a. Newton, Quasi-Newton, and Secant methods.
b. Region Elimination Methods (Fibonacci, Golden
Section, etc.).
Chapter 5

c. Polynomial Approximation (Quadratic Interpolation,

etc.).
d. Random Search

(4) Most methods assume

(a) a unimodal function, (b) that the min is
bracketed at the start and (c) also you start in a
direction that reduces f.

3
Chapter 5 To Bracket the Minimum

1. Compute f ( x ( 0 ) ) and f ( x 0  x)

If f ( x ( 0)  x)  f ( x ( 0) ), let x NEW  xOLD
If f ( x ( 0)  x)  f ( x ( 0) ), let x NEW  2xOLD

2. Compute f ( x (1) )  f ( x ( 0)  x NEW )

Continue doubling x until f ( x ( 0 )  x ( k ) )  f ( x ( 0)  x ( k 14) )
 3. Compute f ( x ( k 1)  x ( k  2 ) )
1
(2 )
You now have 4 equally spaced points x (3) , x 2
, x ( 2 ) , x (1) .
Discard the point that enables you to keep a bracket
Chapter 5

on the point giving the minimum f(x) (using the

closest points)

5
 1. Newton’s Method
Newton’s method for an equation is
f ( x)  f ( x0 )  f ( x0 )( x  x0 )  0
f ( x0 ) f ( x0 )
( x  x0 )   or x  x0 
f ( x0 ) f ( x0 )
Chapter 5

Application to Minimization

The necessary condition for f(x) to have a local minimum

is f′(x) = 0. Apply Newton’s method.

 (k )
f (x )
x ( k 1) x 
(k )

 (k )
f (x )
6
 Examples
Minimize
f ( x)  a0  a1 x  a2 x 2
f ( x)  a1  2a2 x
f ( x)  2a2
a1  2a2 x ( 0 )
Chapter 5

a1 a1
x (1)
x (0)
 x 
(0)
x 
(0)

2a2 2a2 2 a2

Minimize
f ( x)  x 4  x 2  1
f ( x)  4 x 3  2 x
f ( x)  12 x 2  2
3x 4  2 x
x (1)
x (0)

12 x 2  2
3 2
Start at x (0)
 1, x (1)
 1  0.100
12  2 7
Continue
 Advantages of Newton’s Method

(1) Locally quadratically convergent (as long as f′(x) is

positive – for a minimum).
(2) For a quadratic function, get min in one step.
Chapter 5

Disadvantages

(1) Need to calculate both f′(x) and f″(x)

(2) If f″(x)→0, method converges slowly
(3) If function has multiple extrema, may not converge
to global optimum.

8
 2. Finite-Difference Newton Method
Replace derivatives with finite differences
f ( x  h )  f ( x  h)
x ( k 1)  x(k )  2h
f ( x  h)  2 f ( x )  f ( x  h)
Chapter 5

h2
Disadvantage
Now need additional function evals (3 here vs. 2 for Newton)

9
 3. Secant(Quasi-Newton) Method

Analogous equation to (A) is

f ( x ( k ) )  m( x  x ( k ) )  0 ( B)

The secant approximates f″(x) as a straight line

Chapter 5

f ( x ( q ) )  f ( x ( p ) )
m
x (q)  x ( p)
( k 1) f ( x (k )
)
x x  (k )

f ( x ( q ) )  f ( x ( p ) )
x ( q )  x ( p ) 10
 Start the Secant method by using 2 points spanning x at
which first derivatives are of opposite sign.

For next stage, retain either x(q) or x(p) so that the pair of
derivatives still have opposite sign.
Chapter 5

11
 Order of Convergence
Can be expressed in various ways. Want to consider how
(k ) *
x  x as k  
Chapter 5

Linear
( k 1) *
x x
(k ) *
c 0  c 1
x x

usually slow in practice

12
 Order P
( k 1) *
x x
c c0 p 1
(k ) * p
x x

Fastest in practice
Chapter 5

If p = 2, quadratic convergence
p = 1.32 ?
Superlinear
( k 1) *
x x
lim (k ) *
0 (r  ck and ck  0 as k  )
k 
x x
Usually fast in practice

Some methods can show theoretically what 13

the order is.
 Chapter 5

14
 Chapter 5

15
 Chapter 5

16
 Chapter 5

17
 Chapter 5

18
Chapter 5 Quadratic Interpolation

Approximate f(x) by a quadratic function.

Use 3 points
f ( x)  a  bx  cx 2
b
Minimize : f ( x)  0  b  2cx so x*  
2c
Evaluate f(x) at the 3 points f(x1 ), f ( x2 ), f ( x3 )
Solve 3 simultaneo us equations for a, b, c
f ( x1 )  a  bx1  cx12
f ( x2 )  a  bx2  cx22
19
f ( x3 )  a  bx3  cx 2
3
 1 f ( x1 ) x12 1 x1 f ( x1 )
2
1 f ( x2 ) x 2 1 x2 f ( x2 )
2
1 f ( x3 ) x 3 1 x3 f ( x3 )
b 2
c
1 x1 x
1 1 x1 x12
Chapter 5

2
1 x2 x
2 1 x2 x22
2 2
1 x3 x
3 1 x3 x3

(or use Gaussian elimination)

20
 b  1  f ( x2 ) x32  f ( x3 ) x22   1  f ( x1 ) x32  f ( x3 ) x12 
1  f ( x1 ) x22  f ( x2 ) x12  : Numerator
Chapter 5

c  f ( x1 )   x32  x22    f ( x2 )  x32  x12   f ( x3 ) ( x22  x12 ) 

 f ( x1 )( x22  x32 )  f ( x2 )( x32  x12 )  f ( x3 )( x  x22 ) :
Denominator

b
x*  
2c

21
 Chapter 5

22
 Chapter 5

23
 Chapter 5

24
 Chapter 5

25
 Chapter 5

26
 Chapter 5

27
 Chapter 5

28