4

O PTIMISATION

‰ Introduction
‰ Single Variable Unconstrained Optimisation
‰ Multivariable Unconstrained Optimisation
‰ Linear Programming
Chapter 4 Optimisation / 2

4.1 Introduction
• In an engineering analysis, sometimes extremities, either minimum or
maximum value, has to be obtained.

f(x) Global maximum

Local maximum

Local minimum

Global minimum

FIGURE 4.1 Extremities for a single variable function

• Extremity value can be obtained via optimisation, which is divided into:

1. Unconstrained optimisation — f ′( x ) = 0 .
2. Constrained optimisation — linear/non-linear programming.
Chapter 4 Optimisation / 3

4.2 Single Variable Unconstrained Optimisation

• Extremities, if any, can be evaluated using either the quadratic interpolation
method or the Newton method using the condition of f ′( x ) = 0 .

• For the quadratic interpolation method, consider a second order

Lagrange interpolation equation as followed:

f (x ) =
(x − x1 )(x − x2 ) f (x ) + (x − x0 )(x − x2 ) f (x )
(x0 − x1 )(x0 − x2 ) 0 (x1 − x0 )(x1 − x2 ) 1
+
(x − x0 )(x − x1 ) f (x ) (4.1)
(x2 − x0 )(x2 − x1 ) 2

f(x) Approximated
maximum Actual
maximum

x0 x1 x3 x2 x
FIGURE 4.2 Evaluation of extremities using a quadratic function

Eq. (4.1) is differentiated to yield:

2 x − x1 − x2 2 x − x0 − x2
f ′( x ) = 0 = f ( x0 ) + f (x )
(x0 − x1 )(x0 − x2 ) (x1 − x0 )(x1 − x2 ) 1
2 x − x0 − x1
+ f (x )
(x2 − x0 )(x2 − x1 ) 2
Thus, it can be rearranged to get an optimised value of x = x3 :

x3 =
( ) ( ) (
f ( x0 ) x12 − x22 + f ( x1 ) x22 − x02 + f ( x2 ) x02 − x12 )
2 f ( x0 )( x1 − x2 ) + 2 f ( x1 )( x2 − x0 ) + 2 f ( x2 )( x0 − x1 )
(4.2)

Eq. (4.2) can be repeated until converged.

Chapter 4 Optimisation / 4

Example 4.1

Use the quadratic interpolation method to obtain a maximum value of the

following function accurate to four decimal places:
f ( x ) = sin x − 0.2 x 2
using initial values of x0 = 0, x1 = 1 dan x2 = 2.
Solution
From the given function:
f (0) = sin (0) − 0.2(0) = 0
2

f (1) = sin (1) − 0.2(1) = 0.6415

2

f (2) = sin (2) − 0.2(2) = 0.1093

2

Using Eq. (4.2), the value of x3 can be estimated as followed:

(0 )(12 − 2 2 ) + (0.6415 )(2 2 − 0 2 ) + (0.1093)(0 2 − 12 )
x3 = = 1.0466
2(0 )(1 − 2 ) + 2(0.6415 )(2 − 0 ) + 2(0.1093)(0 − 1)
f ( x3 ) = sin (1.0466 ) − 0.2(1.0466 ) = 0.6466
2

The overal process is as followed:

i x0 f(x0) x1 f(x1) x2 f(x2) x3 f(x3)
1 0 0 1 0.6415 2 0.1093 1.0466 0.6466
2 1 0.6415 1.0466 0.6466 2 0.1093 1.1057 0.6493
3 1 0.6415 1.0466 0.6466 1.1057 0.6493 1.1110 0.6493
4 1.0466 0.6466 1.1057 0.6493 1.1110 0.6493 1.1105 0.6493
5 1.1057 0.6493 1.1105 0.6493 1.1110 0.6493 1.1105 0.6493

Hence, the maximum value is f(x) = 0.6493 at x = 1.1105.

`

• An extremity can either be a minimum or maximum value, or otherwise,

depending on the second derivative f ′′( x ) :

1. f ′′( x ) > 0 — f(x) is minimum,

2. f ′′( x ) < 0 — f(x) is maximum,
3. f ′′(x ) = 0 — the coordinate [x, f ( x)] is an inflection point.
Chapter 4 Optimisation / 5

• For the Newton method, consider an equation similar to the Newton-

Raphson formula (requiring only one initial value):

g ( xi )
xi +1 = xi −
g ′( xi )

If f(x) is the first derivative of g(x), i.e. g ( x ) = f ′( x ) = 0 , this the root of

g(x) is an extremity for f(x), or

f ′( xi )
xi +1 = xi −
f ′′( xi )
(4.3)

Example 4.2

Use the Newton method to obtain the maximum value of the function:
f (x ) = sin x − 0.2 x 2
using an initial value of x0 = 1. Use the convergence criterion of an
approximated error of less than 0.05%.
Solution
From the given function:
f ′( x ) = cos x − 0.4 x
f ′′( x ) = − sin x − 0.4
Using Eq. (4.3), the iteration formula is:
cos xi − 0.4 xi
xi +1 = xi +
sin xi + 0.4
which produces
i xi f(xi) f′(xi″) f″(xi) ||εa|| (%)
0 1 0.64147 0.140302 −1.24147 11.30
1 1.11301 0.64928 −0.00324 −1.29703 0.250
2 1.11051 0.64928 −1.4E−06 −1.29593 0.000
3 1.11051 0.64928 −2.5E−13 −1.29593 0.000

Hence, the maximum value is f(x) = 0.64928 at x = 1.11051.

`
Chapter 4 Optimisation / 6

4.3 Multivariable Unconstrained Optimisation

• For a multivariable case, extremities can be evaluated using the gradient
method via the steepest slope condition.

• For a multivariable case, the gradient vector can be written as

T
⎛ ∂ ∂ ∂ ⎞
∇f = ⎜⎜ f (x ), f (x ), K , f (x )⎟⎟
⎝ ∂x1 ∂x2 ∂xn ⎠
z = f(x,y)

y x

FIGURE 4.3 Optimisation for the 2-D case z = f ( x, y )

• Consider the equation of two variables:

z = f ( x, y ) (4.4)

The objective is to obtain a condition where ∇f = 0 , and for this case:

∂f ∂f
∇f = i+ j
∂x ∂y

This vector will guide the solution towards a normal direction (or
orthogonal) to a contour line of constant f(x,y).
Chapter 4 Optimisation / 7

If h is the distance needed to reach the extremity, the next approximation to

x and y are

∂f ∂f
x = x0 + h , y = y0 + h (4.5)
∂x ∂y

Thus a function g(h) can be formed such that

⎛ ∂f ∂f ⎞
g (h ) = f ⎜⎜ x0 + h, y0 + h ⎟⎟ (4.6)
⎝ ∂x ∂y ⎠

and the relation g ′(h ) = 0 gives the optimised h and hence the optimised
values of x and y.

• For the multivariable cases, the type of extremities is determined using the
Hessian |H| parameter, which has been defined as
2
∂2 f ∂2 f ⎛ ∂2 f ⎞
H = 2 −⎜ ⎟
∂x ∂y 2 ⎜⎝ ∂x ∂y ⎟⎠
(4.7)

The parameter |H| is equivalent to f ′′( x ) for a single variable case, where:

1. H > 0 and ∂ 2 f ∂x 2 > 0 — f(x,y) has a local minimum,

2. H > 0 dan ∂ 2 f ∂x 2 < 0 — f(x,y) has a local maximum,
3. H < 0 — f(x,y) has a plateau.

Example 4.3

Maximise the following function:

f ( x, y ) = 2 xy + 2 x − x 2 − 2 y 2
using the gradient method of the steepest slope using an initial values of
x0 = −1 dan y0 = 1. Get the answer accurate to three decimal places.
Solution
In the first iteration:
∂f
= 2 y + 2 − 2 x = 2(1) + 2 − 2(− 1) = 6
∂x
∂f
= 2 x − 4 y = 2(− 1) − 4(1) = −6
∂y
Chapter 4 Optimisation / 8

g (h ) = f (− 1 + 6h,1 − 6h )
= 2(− 1 + 6h )(1 − 6h ) + 2(− 1 + 6h ) − (− 1 + 6h ) − 2(1 − 6h )
2 2

= −180h 2 + 72h − 7
g ′(h ) = 0 = −360h + 72 ⇒ h = 0.2
Thus after the first iteration:
x = −1 + 6(0.2 ) = 0.2
y = 1 − 6(0.2 ) = −0.2
In the second iteration:
∂f
= 2(− 0.2 ) + 2 − 2(0.2 ) = 1.2
∂x
∂f
= 2(0.2 ) − 4(− 0.2 ) = 1.2
∂y
g (h ) = f (0.2 + 1.2h,−0.2 + 1.2h ) = −1.44h 2 + 2.88h + 0.2
g ′(h ) = 0 = −2.88h + 2.88 ⇒ h = 1
x = 0.2 + 1.2(1) = 1.4
y = −0.2 + 1.2(1) = 1
The overall process is as followed:
i xi−1 yi−1 ∂f ∂x ∂f ∂y h xi yi
1 −1 1 6 −6 0.2 0.2 −0.2
2 0.2 −0.2 1.2 1.2 1 1.4 1
3 1.4 1 1.2 −1.2 0.2 1.64 0.76
4 1.64 0.76 0.24 0.24 1 1.88 1
5 1.88 1 0.24 −0.24 0.2 1.928 0.952
6 1.928 0.952 0.048 0.048 1 1.976 1
7 1.976 1 0.048 −0.048 0.2 1.986 0.990
8 1.986 0.990 0.0096 0.0096 1 1.995 1
9 1.995 1 0.0096 −0.0096 0.2 1.997 0.998
10 1.997 0.998 0.00192 0.00192 1 1.999 1
11 1.999 1 0.00192 −0.00192 0.2 1.999 1.000
12 1.999 1.000 0.00038 0.00038 1 2.000 1
13 2.000 1 0.00038 −0.00038 0.2 2.000 1.000

Finally, the solution converges at the 13-th iteration where x = 2 dan y = 1

resulting in a maximum value of f ( x, y ) = f (2,1) = 2 .

`
Chapter 4 Optimisation / 9

4
−70
−50
−60
3 −10
−40 −30 −20
0
2

Maximum
1
y

0
−10
−20
−1
−30
−40
−2
−4 −3 −2 −1 0 1 2 3 4 5 6
x
FIGURE 4.4 Propagation of estimated points of Example 4.3
Chapter 4 Optimisation / 10

4.4 Linear Programming

• In this topic, only the linear case is considered.

• The objective of linear programming is to minimise or maximise an

objective function Z, i.e.,

Maksimumkan: Z = c1 x1 + c2 x2 + L + cn xn (4.8)

Eq. (4.8) is subjected to several constraints, i.e.

ai1 x1 + ai 2 x2 + L + ain xn ≤ bi (4.9)

If the variable xj represents a positive physical parameter, thus

xj ≥ 0 (4.10)

• The simplest approach is via a graphical method.

Example 4.4

Use the graphical method to maximise the following objective function:

Z = 150 x + 175 y
where the conditions or constraints are:
(1) 7 x + 11 y ≤ 77 ,
(2) 10 x + 8 y ≤ 80 ,
(3) x ≤ 9,
(4) y ≤ 6,
(5) x ≥ 0,
(6) y ≥ 0.
Solution
From the figure, the optimum point is (4 89 ,3 89 ) which produces the
maximum value of Z = 1413 89 . Noted that condition (3) is redundant.

`
Chapter 4 Optimisation / 11

6 4
1

4 3
5
2 2

6
0 2 4 6 8 x
FIGURE 4.5 Linear programming graph for Example 4.4

• One of the numerical approach is the simplex method, where the searching
for the optimum point is guided by the slag variable Si, as followed:

Z − c1 x1 − c 2 x 2 − L − c n x n = 0 (4.11)
ai1 x1 + ai 2 x2 + L + ain xn + S i = bi (4.12)
xj + Sj = 0 (4.13)

If this system contains k equations and l variables including the slag

variables, where usually k < l, hence there are (l–k) variables which has to
be made zeros (non-basis — a non-zero variable is known as basis).

The Gauss-Jourdan elimination can be performed to minimise the objective

function.

The elimination can be stopped when all the basis variables become zeros.

Example 4.5

Repeat Example 4.4 using the simplex method.

Chapter 4 Optimisation / 12

Solution
The system can be rewritten as followed:
Maximise: Z − 150 x − 175 y = 0 ,
With conditions: (1) 7 x + 11 y + S1 = 77 ,
(2) 10 x + 8 y + S 2 = 80 ,
(3) x + S3 = 9 ,
(4) y + S4 = 6 ,
(5) x, y, S1 , S 2 , S 3 , S 4 ≥ 0 .
Begin with Z = x = y = 0. Then form the following table:

Basis Z x y S1 S2 S3 S4 Solution
Z 1 − 150 − 175 0 0 0 0 0
S1 0 7 11 1 0 0 0 77
S2 0 10 8 0 1 0 0 80
S3 0 1 0 0 0 1 0 9
S4 0 0 1 0 0 0 1 6

At column x, the element at row S2 can be a pivot, hence x is selected to be

the inbound variable replacing S2. Then, perform the Gauss elimination:
Basis Z x y S1 S2 S3 S4 Solution
Z 1 0 − 55 0 15 0 0 1200
x 0 1 0.8 0 0.1 0 0 8
S1 0 0 5.4 1 − 0.7 0 0 21
S3 0 0 − 0.8 0 − 0.1 1 0 1
S4 0 0 1 0 0 0 1 6

The coefficient of y at row Z is still negative, thus Z is still not maximum.

Hence, y is selected to replace S1:
Basis Z x y S1 S2 S3 S 4 Solution
Z 1 0 0 10.1852 7.8704 0 0 1413.889
x 0 1 0 − 0.1481 0.2037 0 0 4.889
y 0 0 1 0.1852 − 0.1296 0 0 3.889
S3 0 0 0 0.1481 − 0.2037 1 0 4.111
S4 0 0 0 − 0.1852 0.1296 0 1 2.111
Chapter 4 Optimisation / 13

Therefore the maximum of Z is 1413.889 which is produced at x = 3.889

and y = 4.889.
`

• In linear and non-linear programming, there are four possible outcomes:

1. Unique solution,
2. Multiple solutions,
3. No possible solution,
4. Unbounded problem.

For cases 2-4, the simplex method cannot be used.

y y

x x
(a) Multiple solutions (b) No possible solution
y

x
(c) Unbounded problem
FIGURE 4.6 Cases where the simplex method is not applicable
Chapter 4 Optimisation / 14

Exercises

1. Obtain the minimum value of the following function at x ≥ 0 using the quadratic
interpolation function using the initial values of 0.1, 0.5 and 5.0, and the Newton
method using the initial value of 0.5:

f (x ) = x +
1
x

2. Obtain the maximum value of the following function via the steepest slope with the
initial value of (x, y) = (0, 0):
f ( x ) = 3.5 x + x 2 − x 4 − 2 xy + 2 y − y 2

3. A company produces two types of products, A and B. These products are produced
during normal working days of 40 hours per week and are marketed on the same
weekends. The company needs 20 kg and 5 kg of raw materials for products A and B,
respectively. However, the company warehouse can only stores 10,000 kg of raw
materials per week. Only one product is produced at one time, where product A
requires 0.05 hour, while product B requires 0.15 hour. Nevertheless, the temporary
storage section can only keep 550 products per week. Product A is sold at RM45 per
unit while product B is sold at RM30 per unit. By using the linear programming using
the simplex method:
a. Maximise the company profit.
b. Which factor where its increase leads to the fastest increase in profit: raw
materials, capacity of temporary storage section or production time?