OPTIMIZATION TECHNIQUES

Module 4: Constrained Nonlinear Programming

Dr. R. Sakthivel

Assistant Professor Senior Grade

School of Computer Science and Engineering
Vellore Institute of Technology
Chennai
Module 4

Direct Method Indirect Method

Cutting plane method Interior Penalty Function
(Sequential Linear Programming method
method)
Methods of feasible directions Exterior Penalty Function
(Zoutendijk’s method) method
Introduction

This module deals with techniques that are applicable to the solution of the
constrained optimization problem:

Find X which minimizes (maximize) f (X)

Subject to
gj (X) ≤ 0, j = 1, 2, ..., m

hk (X) = 0, k = 1, 2, ..., p

There are many techniques available for the solution of a constrained

nonlinear programming problem.

A nonlinear equation has a degree greater than 1 for at least one variable.
Example:
x 2 + y2 = 1
2x2 − y = 2

3 / 125
Sequential Linear Programming

In the sequential linear programming (SLP) method, the solution of the

original nonlinear programming problem is found by solving a series of
linear programming problems.

Each LP problem is generated by approximating the nonlinear objective

and constraint functions using first-order Taylor series expansions about
the current design vector, Xi .

The resulting LP problem is solved using the simplex method to find the
new design vector Xi+1 .

If Xi+1 does not satisfy the stated convergence criteria, the problem is
relinearized about the point Xi+1 and the procedure is continued until the
optimum solution X ∗ is found.

The SLP method, also known as the cutting plane method.

4 / 125
Sequential Linear Programming contd.,
Algorithm:
Step 1: Start with an initial point X1 and set the iteration number as i = 1. The
point X1 need not be feasible.
Step 2: Linearize the objective and constraint functions about the point Xi as
f (X) ≈ f (Xi ) + ∇f (Xi )T (X − Xi )
subject to
gj (X) ≈ gj (Xi ) + ∇gj (Xi )T (X − Xi )
hk (X) ≈ hk (Xi ) + ∇hk (Xi )T (X − Xi )
Step 3: Formulate the approximating linear programming problem as
Minimize f (Xi ) + ∇fiT (X − Xi )
subject to
gj (Xi ) + ∇gj (Xi )T (X − Xi ) ≤ 0, j = 1, 2, ..., m
hk (Xi ) + ∇hk (Xi )T (X − Xi ) = 0, k = 1, 2..., p
5 / 125
Sequential Linear Programming contd.,

Step 4: Solve the approximating LP problem to obtain the solution vector Xi+1 .

Step 5: Evaluate the original constraints at Xi+1 ; that is, find

gj (Xi+1 ), j = 1, 2, ...m and hk (Xi+1 ), k = 1, 2, ..., p

Case 1: If gj (Xi+1 ) < ϵ for j = 1, 2.., m, and |hk (Xi+1 )| ≤ ϵ, k = 1, 2, ..., p,

where ϵ is a prescribed small positive tolerance, all the original constraints can
be assumed to have been satisfied. Hence stop the procedure by taking

Xopt ≃ Xi+1

6 / 125
Sequential Linear Programming contd.,

Case 2: If gj (Xi+1 ) > ϵ for some j, or |hk (Xi+1 )| > ϵ for some k, find the most
violated constraint, for example, as

gk (Xi+1 ) = max[gj (Xi+1 )]

j

Relinearize the constraint gk (X) ≤ 0 about the point Xi+1 as

gk (X) ≃ gk (Xi+1 ) + ∇gk (Xi+1 )T (X − Xi+1 ) ≤ 0

and add this as the (m + 1)th inequality constraint to the previous LP problem.

Step 6: Set the new iteration number as i = i+1, the total number of constraints
in the new approximating LP problem as m + 1 inequalities and p equalities,
and go to step 4.

7 / 125
Sequential Linear Programming contd.,

Geometric Interpretation of the Method:

The SLP method can be illustrated with the help of a one-variable

problem:
Minimize f (x) = c1 x
subject to
g(x) ≤ 0
where c1 is a constant and g(x) is a nonlinear function of x.

To avoid any possibility of unbounded solution, let us first take the

constraints on x as k ≤ x ≤ l,
where k and l represent the lower and upper bounds on x.

8 / 125
Sequential Linear Programming contd.,

Example 1:
Minimize f (x1 , x2 ) = x1 − x2
subject to
g(x1 , x2 ) = 3x12 − 2x1 x2 + x22 − 1 ≤ 0
using the cutting plane method. Take the convergence limit as ϵ = 0.5
Solution:
Iteration: 1
To avoid the possible unbounded solution, we first take the bounds on x1 and
x2 as

−2 ≤ x1 ≤ 2 and − 2 ≤ x2 ≤ 2

and solve the following LP problem: Minimize f = x1 − x2

subject to
−2 ≤ x1 ≤ 2
−2 ≤ x2 ≤ 2
9 / 125
Sequential Linear Programming contd.,

In the standard simplex method, all decision variables are typically

assumed to be non-negative (xj ≥ 0)

However, when variables have lower and upper bounds (e.g.,

−2 ≤ x1 ≤ 2), we need to adopt the variable substitution method to
handle bounded variables.

Let xj = yj + L, where L is the lower bound

In our problem, let

x1 = y1 − 2
x2 = y2 − 2

10 / 125
Sequential Linear Programming contd.,

Rewrite the LP problem as,

Minimize f = y1 − 2 − y2 + 2
subject to
−2 ≤ y1 − 2 ≤ 2
−2 ≤ y2 − 2 ≤ 2

Adding 2 on all sides, we get

0 ≤ y1 ≤ 4
0 ≤ y2 ≤ 4

∴ Minimize f = y1 − y2
subject to
0 ≤ y1 ≤ 4
0 ≤ y2 ≤ 4
and y1 , y2 ≥ 0

11 / 125
Sequential Linear Programming contd.,

The standard form of the LP problem becomes,

Minimize f = y1 − y2 + 0s1 + 0s2

subject to
y1 + s 1 = 4
y2 + s 2 = 4
and y1 , y2 , s1 , s2 ≥ 0

Iteration: 1 Cj 1 -1 0 0
B CB XB y1 y2 s1 s2 Min Ratio
s1 0 4 1 0 1 0 −−
4
s2 0 4 0 (1) 0 1 =4
1
Z=0 Zj 0 0 0 0
Zj − Cj -1 1 0 0

12 / 125
Sequential Linear Programming contd.,

Entering variable is y2 , leaving variable is s2

Iteration: 2 Cj 1 -1 0 0
B CB XB y1 y2 s1 s2 Min Ratio
s1 0 4 1 0 1 0
y2 -1 4 0 1 0 1
Z = −4 Zj 0 -1 0 -1
Zj − Cj -1 0 0 -1

Since all Zj − Cj ≤ 0
Min Z = −4 at y1 = 0, y2 = 4

Solution of the original problem is

x1 = 0 − 2 = −2
x2 = 4 − 2 = 2

13 / 125
Sequential Linear Programming contd.,
The solution of this problem can be obtained as
 
−2
X=
2

Here x1 = −2 and x2 = 2

 
−2
f (X) = f
2
= −2 − 2
= −4

Since we have solved one LP problem, we can take

 
−2
Xi+1 = X2 =
2

14 / 125
Sequential Linear Programming contd.,

g(X2 ) = 3(−2)2 − 2(−2)(2) + (2)2 − 1

= 3(4) + 8 + 4 − 1
= 23 > ϵ,

we linealize g(X) about point X2 as

g(X) ≃ g(X2 ) + ∇g(X2 )T (X − X2 ) ≤ 0

As
g(X2 ) = 23

" #
∂g
∂x1
∇g(X2 ) = ∂g
∂x2 X2

15 / 125
Sequential Linear Programming contd.,

 
6x1 − 2x2
∇g(X2 ) =
−2x1 + 2x2 (−2,2)
 
6(−2) − 2(2)
=
−2(−2) + 2(2)
 
−16
=
8

∇g(X2 )T = −16 8
 

   
x1 −2
X − X2 = −
x2 2
 
x +2
= 1
x2 − 2
16 / 125
Sequential Linear Programming contd.,

Substituting these values in g(X), we get

 
  x1 + 2
g(X) ≃ 23 + −16 8 ≤0
x2 − 2
 
≃ 23 + −16(x1 + 2) 8(x2 − 2) ≤ 0
≃ 23 − 16x1 − 32 + 8x2 − 16 ≤ 0
≃ −16x1 + 8x2 − 25 ≤ 0

By adding this constraint to the previous LP problem, the new LP problem

becomes,
Minimize f = x1 − x2
subject to
−2 ≤ x1 ≤ 2
−2 ≤ x2 ≤ 2
−16x1 + 8x2 − 25 ≤ 0

17 / 125
Sequential Linear Programming contd.,
Iteration: 2
Solve the LP problem by Simplex method.
Minimize f = x1 − x2
subject to

−2 ≤ x1 ≤ 2
−2 ≤ x2 ≤ 2
−16x1 + 8x2 ≤ 25
and x1 , x2 ≥ 0

Rewrite the LP problem as,

Minimize f = y1 − 2 − y2 + 2
subject to
−2 ≤ y1 − 2 ≤ 2
−2 ≤ y2 − 2 ≤ 2
−16(y1 − 2) + 8(y2 − 2) ≤ 25 =⇒ −16y1 + 32 + 8y2 − 16 ≤ 25

18 / 125
Sequential Linear Programming contd.,

Adding 2 on all sides, we get

0 ≤ y1 ≤ 4
0 ≤ y2 ≤ 4
−16y1 + 8y2 + 18 ≤ 27 =⇒ −16y1 + 8y2 ≤ 9

∴ Minimize f = y1 − y2
subject to
0 ≤ y1 ≤ 4
0 ≤ y2 ≤ 4
−16y1 + 8y2 ≤ 9
and y1 , y2 ≥ 0

19 / 125
Sequential Linear Programming contd.,
The standard form of the LP problem becomes,

Minimize f = y1 − y2 + 0s1 + 0s2

subject to y1 + s1 = 4
y2 + s 2 = 4
−16y1 + 8y2 + s3 = 9
and y1 , y2 , s1 , s2 , s3 ≥ 0

Iteration: 1 Cj 1 -1 0 0 0
B CB XB y1 y2 s1 s2 s2 Min Ratio
s1 0 4 1 0 1 0 0 −−
4
s2 0 4 0 1 0 1 0 =4
1
9
s3 0 9 -16 (8) 0 0 1 = 1.125
8
Z=0 Zj 0 0 0 0 0
Zj − C j -1 1 0 0 0

20 / 125
Sequential Linear Programming contd.,

Entering variable is y2 , leaving variable is s3

Iteration: 2 Cj 1 -1 0 0 0
B CB XB y1 y2 s1 s2 s2 Min Ratio
4
s1 0 4 1 0 1 0 0 =4
1
2.875
s2 0 2.875 (2) 0 0 1 -0.125 = 1.4375
2
y2 -1 1.125 -2 1 0 0 0.125 −−
Z = −1.125 Zj 2 -1 0 0 -0.125
Zj − Cj 1 0 0 0 -0.125

21 / 125
Sequential Linear Programming contd.,

Entering variable is y1 , leaving variable is s2

Iteration: 3 Cj 1 -1 0 0 0
B CB XB y1 y2 s1 s2 s2 Min Ratio
s1 0 2.5625 0 0 1 -0.5 0.0625
y1 1 1.4375 1 0 0 0.5 -0.0625
y2 -1 4 0 1 0 1 0
Z = −2.5625 Zj 1 -1 0 -0.5 -0.0625
Zj − Cj 0 0 0 -0.5 -0.0625

Since all Zj − Cj ≤ 0
Min Z = −2.5625 at y1 = 1.4375, y2 = 4

Solution of the original problem is

x1 = 1.4375 − 2 = −0.5625
x2 = 4 − 2 = 2

22 / 125
Sequential Linear Programming contd.,
 
−0.5625
X3 =
2
f3 = f (X3 ) = −2.5625

g(X3 ) = 3(−0.5625)2 − 2(−0.5625)(2) + (2)2 − 1

= 3(0.3164) + 2.25 + 4 − 1
= 0.9492 + 2.25 + 4 − 1 = 6.1992 > ϵ = 0.5,
we linealize g(X) about point X3 as
g(X) ≃ g(X3 ) + ∇g(X3 )T (X − X3 ) ≤ 0
As
g(X3 ) = 6.1992
" #
∂g
∂x1
∇g(X3 ) = ∂g
∂x2 X3
23 / 125
Sequential Linear Programming contd.,

 
6x1 − 2x2
∇g(X3 ) =
−2x1 + 2x2 (−0.5625,2)
 
6(−0.5625) − 2(2)
=
−2(−0.5625) + 2(2)
 
−7.375
=
5.125

∇g(X3 )T = −7.375 5.125

 

   
x1 −0.5625
X − X3 = −
x2 2
 
x1 + 0.5625
=
x2 − 2
24 / 125
Sequential Linear Programming contd.,

Substituting these values in g(X), we get

 
  x1 + 0.5625
g(X) ≃ 6.1992 + −7.375 5.125 ≤0
x2 − 2
 
≃ 6.1992 + −7.375(x1 + 0.5625) 5.125(x2 − 2) ≤ 0
≃ 6.1992 − 7.375x1 − 4.1484 + 5.125x2 − 10.25 ≤ 0
≃ −7.375x1 + 5.125x2 − 8.1992 ≤ 0

By adding this constraint to the initial LP problem, the new LP problem be-
comes,
Minimize f = x1 − x2
subject to
−2 ≤ x1 ≤ 2
−2 ≤ x2 ≤ 2
−7.375x1 + 5.125x2 ≤ 8.1992

25 / 125
Sequential Linear Programming contd.,

Iteration: 3
Solve the LP problem by Simplex method.
Minimize f = x1 − x2
subject to

−2 ≤ x1 ≤ 2
−2 ≤ x2 ≤ 2
−7.375x1 + 5.125x2 ≤ 8.1992
and x1 , x2 ≥ 0

Solve this by using Variable Substitution, we get the optimum solution is

Min Z = −1.7219 at x1 = 0.2787, x2 = 2

26 / 125
Sequential Linear Programming contd.,
 
0.2787
X4 =
2
f4 = f (X4 ) = −1.7219

g(X4 ) = 3(0.2787)2 − 2(0.2787)(2) + (2)2 − 1

= 3(0.0777) − 1.1148 + 4 − 1
= 2.1183 > ϵ = 0.5,
we linealize g(X) about point X4 as
g(X) ≃ g(X4 ) + ∇g(X4 )T (X − X4 ) ≤ 0
As
g(X4 ) = 2.1183
" #
∂g
∂x1
∇g(X4 ) = ∂g
∂x2 X4
27 / 125
Sequential Linear Programming contd.,

 
6x1 − 2x2
∇g(X4 ) =
−2x1 + 2x2 (0.2787,2)
 
6(0.2787) − 2(2)
=
−2(0.2787) + 2(2)
 
−2.3278
=
3.4426

∇g(X4 )T = −2.3278 3.4426

 

   
x1 0.2787
X − X4 = −
x2 2
 
x1 − 0.2787
=
x2 − 2
28 / 125
Sequential Linear Programming contd.,

Substituting these values in g(X), we get

 
  x1 − 0.2787
g(X) ≃ 2.113 + −2.3278 3.4426 ≤0
x2 − 2
 
≃ 2.113 + −2.3278(x1 − 0.2787) 3.4426(x2 − 2) ≤ 0
≃ 2.113 − 2.3278x1 + 0.6488 + 3.4426x2 − 6.8853 ≤ 0
≃ −2.3275x1 + 3.4426x2 − 4.1235 ≤ 0

By adding this constraint to the initial LP problem, the new LP problem be-
comes,
Minimize f = x1 − x2
subject to
−2 ≤ x1 ≤ 2
−2 ≤ x2 ≤ 2
−2.3275x1 + 3.4426x2 ≤ 4.1235

29 / 125
Sequential Linear Programming contd.,

Iteration: 4
Solve the LP problem by Simplex method.
Minimize f = x1 − x2
subject to

−2 ≤ x1 ≤ 2
−2 ≤ x2 ≤ 2
−2.3275x1 + 3.4426x2 ≤ 4.1235
and x1 , x2 ≥ 0

Solve this by using Variable Substitution, we get the optimum solution is

Min Z = −1.3673 at x1 = −0.5297, x2 = 0.8375

30 / 125
Sequential Linear Programming contd.,
 
−0.5297
X5 =
0.8375
f5 = f (X5 ) = −1.3673

g(X5 ) = 3(−0.5297)2 − 2(−0.5297)(0.8375) + (0.8375)2 − 1

= 3(0.2806) + 0.8872 + 0.7014 − 1
= 1.4304 > ϵ = 0.5,
we linealize g(X) about point X4 as
g(X) ≃ g(X5 ) + ∇g(X5 )T (X − X5 ) ≤ 0
As
g(X5 ) = 1.4304
" #
∂g
∂x1
∇g(X5 ) = ∂g
∂x2 X5
31 / 125
Sequential Linear Programming contd.,

 
6x1 − 2x2
∇g(X5 ) =
−2x1 + 2x2 (−0.5297,0.8375)
 
6(−0.5297) − 2(0.8375)
=
−2(−0.5297) + 2(0.8375)
 
−4.8532
=
2.7344

∇g(X5 )T = −4.8532 2.7344

 

   
x1 −0.5297
X − X5 = −
x2 0.8375
 
x1 + 0.5297
=
x2 − 0.8375
32 / 125
Sequential Linear Programming contd.,

Substituting these values in g(X), we get

 
  x1 + 0.5297
g(X) ≃ 1.4304 + −4.8532 2.7344 ≤0
x2 − 0.8375
 
≃ 1.4304 + −4.8532(x1 + 0.5297) 2.7344(x2 − 0.8375) ≤ 0
≃ 1.4304 − 4.8532x1 − 2.5707 + 2.7344x2 − 2.2901 ≤ 0
≃ −4.8532x1 + 2.7344x2 − 3.4313 ≤ 0

By adding this constraint to the initial LP problem, the new LP problem be-
comes,
Minimize f = x1 − x2
subject to
−2 ≤ x1 ≤ 2
−2 ≤ x2 ≤ 2
−4.8532x1 + 2.7344x2 ≤ 3.4313

33 / 125
Sequential Linear Programming contd.,

Iteration: 5
Solve the LP problem by Simplex method.
Minimize f = x1 − x2
subject to

−2 ≤ x1 ≤ 2
−2 ≤ x2 ≤ 2
−4.8532x1 + 2.7344x2 ≤ 3.4313
and x1 , x2 ≥ 0

Solve this by using Variable Substitution, we get the optimum solution is

Min Z = −1.2134 at x1 = −0.05314, x2 = 1.16024

34 / 125
Sequential Linear Programming contd.,
 
−0.05314
X6 =
1.16024
f6 = f (X6 ) = −1.2134

g(X6 ) = 3(−0.05314)2 − 2(−0.05314)(1.16024) + (1.16024)2 − 1

= 0.4779 < ϵ = 0.5,

Condition is satisfied, we stop the iteration.

Iteration: i Xi+1 f (Xi+1 ) g(Xi+1 )

1 (−2, 2) −4 23
2 (−0.5625, 2) −2.5625 6.1992
3 (0.2787, 2) −1.7219 2.1183
4 (−0.5297, 0.8375) −1.3673 1.4304
5 (−0.05314, 1.16024) −1.2134 0.4779

Hence the optimum point is X ∗ = (−0.05314, 1.16024)

Optimum function value is f (X ∗ ) = −1.2134
35 / 125
Direct Method

Zoutendijk’s Method of Feasible Directions

Algorithm:

Step 1: Start with an initial feasible point X1 and small numbers ε1 , ε2 , and ε3
to test the convergence of the method. Evaluate f (x1 ) and gj (x1 ), j = 1, 2, ...m.
Set the iteration number as i = 1.

Step 2: If gj (Xi ) < 0, j=1,2,..m(i.e, Xi is an interior feasible point), set the

current search direction as
Si = −∇f (Xi )
Normalize Si in a suitable manner and go to step 5.
If at least one gj (Xi ) = 0, go to step 3.

36 / 125
Zoutendijk’s Method

Step 3: Find usable feasible direction S by

Minimize − α
Subject to

ST ∇f + α ≤ 0
ST ∇gj (Xi ) + θj α ≤ 0, j = 1, 2...p
− 1 ≤ si ≤ 1, i = 1, 2...n
α>0

Step 4: If the value of α∗ found in step 3 is very nearly equal to zero, that is
α∗ ≤ ε1 , terminate the process by taking Xopt = Xi .
If α∗ > ε1 go to step 5 by taking Si = S.

37 / 125
Zoutendijk’s Method

Step 5: Find a suitable step length λi along the direction Si and obtain a new
point Xi+1 as
Xi+1 = Xi + λi Si
Where λi is step length.

Step 6: Evaluate the objective function f (Xi + 1).

Step 7: Test for the convergence of the method. If

f (Xi ) − f (Xi + 1)
| | ≤ ε2 and ||Xi − Xi+1 || < ε3
f (Xi )

terminate the iteration by taking Xopt = Xi+1 .

Otherwise go to step 8.

Step 8: Set new iteration i = i + 1, and repeat from step 2.

38 / 125
Zoutendijk’s Method
Example 1:
Minimize f (x1 , x2 ) = x12 + x22 − 4x1 − 4x2 + 8
Subject to
g1 (x1 , x2 ) = x1 + 2x2 − 4 ≤ 0
with the starting point X1 (0, 0). Take ε1 = 0.001, ε2 = 0.001, and ε3 = 0.01.
Solution:
At X1 (0, 0)
f (x1 , x2 ) = x12 + x22 − 4x1 − 4x2 + 8
f (0, 0) = 02 + 02 − 4(0) − 4(0) + 8
f (X1 ) = 8
g1 (x1 , x2 ) = x1 + 2x2 − 4
g1 (0, 0) = 0 + 2(0) − 4
g1 (X1 ) = −4

39 / 125
Zoutendijk’s Method

Iteration 1:
Since g1 (X1 ) < 0, we take the search direction as
" #
∂f  
∂x1 2x1 − 4
S1 = −∇f (X1 ) = − ∂f = −
∂x2
2x2 − 4
 
2(0) − 4
=−
2(0) − 4
 
−4
=−
−4
 
4
=
4
 
1
This can be normalized to obtain S1 =
1

40 / 125
Zoutendijk’s Method

X1 = (0, 0), S1 = (1, 1)

Find Step Length

X2 =X1 + λ1 S1
   
0 1
= + λ1
0 1
   
0 λ
= + 1
0 λ1
 
λ
= 1
λ1

41 / 125
Zoutendijk’s Method
X2 = (λ1 , λ1 )
f (X) =x12 + x22 − 4x1 − 4x2 + 8
f (X2 ) =λ21 + λ21 − 4(λ1 ) − 4(λ1 ) + 8
=2λ21 − 8λ1 + 8

Differentiate with respect to λ1

df
= 2λ21 − 8λ1 + 8 =0
dλ1
4λ1 − 8 =0
4λ1 =8
8
λ1 =
4
λ1 =2
42 / 125
Zoutendijk’s Method
λ1 = 2, at the new point is given by X2 = (2, 2)
g1 (x1 , x2 ) = x1 + 2x2 − 4
g1 (2, 2) = 2 + 2(2) − 4
g1 (X2 ) = 2 ≰ 0
Since the constraint is violated.
The linear interpolation give the new step length is
g′1 (0)
λ̄ = − λ1
g1 (2) − g′1 (0)
′′

Let λ1 = 0
g1 (x1 , x2 ) =x1 + 2x2 − 4
g′1 (λ1 , λ1 ) =λ1 + 2λ1 − 4
g′1 (0) =0 + 2(0) − 4 = 0 − 4
g′1 (0) = − 4
43 / 125
Zoutendijk’s Method
Let λ1 = 2

g1 (x1 , x2 ) =x1 + 2x2 − 4

g′′1 (λ1 , λ1 ) =λ1 + 2λ1 − 4
g′′1 (2) =2 + 2(2) − 4
=2 + 4 − 4
g′′1 (2) =2

The linear interpolation give the new step length is

g′1 (0) −(4)

λ̄ = − ′′ ′ λ1 = − 2
g1 (2) − g1 (0) 2 − (−4)
4
= (2)
6
4
λ̄ =
3
44 / 125
Zoutendijk’s Method

The new corrected point X2 = ( 43 , 34 )

The objective function is

f (x2 , x2 ) =x12 + x22 − 4x1 − 4x2 + 8

4 4 4 4 4 4
f ( , ) =( )2 + ( )2 − 4( ) − 4( ) + 8
3 3 3 3 3 3
16 16 16 16 16 + 16 − 48 − 48
= + − − +8= +8
9 9 3 3 9
32 − 96 + 72
=
9
104 − 96
=
9
8
=
9
8
The objective function value f (X2 ) = 9

45 / 125
Zoutendijk’s Method
Check Convergence
f (Xi ) − f (Xi + 1)
| | ≤ ε2
f (Xi )

f (X1 ) − f (X2 )
| | ≤ ε2
f (X1 )
8 − 98
=| |
8
(72 − 8)/9
=| |
8
64/9
=| |
8
8
=
9
=0.8888 ≰ ε2

46 / 125
Zoutendijk’s Method

X1 = (0, 0), X2 = ( 43 , 43 )
Distance between two points

||Xi − Xi+1 || < ε3

||X1 − X2 || < ε3
q
= (0 − 4/3)2 + (0 − 4/3)2
√
= 1.7777 + 1.7777
√
= 3.1110
=1.887 ≮ ε3

Hence the convergence criteria are not satisfied.

47 / 125
Zoutendijk’s Method

check the constraint at the new point is X2 = ( 43 , 34 )

g1 (X2 ) = x1 + 2x2 − 4 ≤ 0
4 4
= + 2. − 4
3 3
4 8
= + −4
3 3
4 + 8 − 12
=
3
12 − 12
=
3
=0

The constraint value is g1 (X2 ) ≤ 0

This condition is satisfied. And go to next iteration.

48 / 125
Zoutendijk’s Method
Iteration 2: As g1 (X2 ) = 0 , we proceed to find a usable feasible direction.

Minimize f = −α

Subject to

t1 + 2t2 + α + y1 = 3
−4 4 −8
t1 − t2 + α + y2 =
3 3 3
t1 + y 3 = 2
t2 + y 4 = 2
t1 ≥ 0, t2 ≥ 0, α ≥ 0

where
t1 , t2 are the components of the feasible direction.
α is represents a decreasing direction.
y1 , y2 , y3 , y4 are non-negative slack variables.
49 / 125
Zoutendijk’s Method

The given solution is

t1∗ = 2

3
t2∗ = = 0.3
10
4
α∗ = = 0.4
10
Slack variables

17
y∗4 = = 1.7
10

y∗1 = y∗2 = y∗3 = 0

50 / 125
Zoutendijk’s Method

The minimum value is

4
−fmin = −α∗ = − = −0.4
10
As α∗ > 0, the feasible direction is given by
∗ 
t1 − 1
S2 = ∗
t2 − 1
 
2−1
=
0.3 − 1
 
1.0
=
−0.7

51 / 125
Zoutendijk’s Method

   
1.0 1.333
S2 = , X2 =
−0.7 1.333
To find the minimize step length,

f (X2 + λS2 )
   
1.333 1.0
=f +λ
1.333 −0.7
=f (1.333 + λ, 1.333 − 0.7λ)

52 / 125
Zoutendijk’s Method

x1 = 1.333 + λ, x2 = 1.333 − 0.7λ

substitute into the objective function

f (x1 , x2 ) =x12 + x22 − 4x1 − 4x2 + 8

=(1.333 + λ)2 + (1.333 − 0.7λ)2 − 4(1.333 + λ)
− 4(1.333 − 0.7λ) + 8
=1.3332 + 2(1.333)λ + λ2 + 1.3332 − 2(1.333)0.7λ + 0.7λ2
− 5.332 − 4λ − 5.332 + 2.8λ + 8
=1.49λ2 − 0.4λ + 0.889

53 / 125
Zoutendijk’s Method

Derivative with respect to λ

df
= 1.49λ2 − 0.4λ + 0.889
dλ
2.98λ − 0.4 = 0
2.98λ = 0.4
0.4
λ=
2.98
λ = 0.134

54 / 125
Zoutendijk’s Method

The new point is given by

X3 =X2 + λS2
   
1.333 1.0
= + 0.134
1.333 −0.7
 
1.333 + 0.134
=
1.333 − 0.134(0.7)
 
1.333 + 0.134
=
1.333 − 0.2278
 
1.467
=
1.239

55 / 125
Zoutendijk’s Method

The new corrected point X3 = (1.467, 1.239)

The objective function is

f (x2 , x2 ) =x12 + x22 − 4x1 − 4x2 + 8

f (1.467, 1.239) =1.4672 + 1.2392 − 4(1.467) − 4(1.239) + 8
=2.1520 + 1.5351 − 5.868 − 4.956 + 8
=0.8631

The objective function value f (X3 ) = 0.8631

56 / 125
Zoutendijk’s Method

Check Convergence
f (Xi ) − f (Xi + 1)
| | ≤ ε2
f (Xi )

f (X2 ) − f (X3 )
| | ≤ ε2
f (X2 )
0.888 − 0.8631
=| |
0.888
0.0291
=| |
0.888
=0.0291 ≰ ε2

57 / 125
Zoutendijk’s Method

X2 = ( 43 , 43 ) = (1.333, 1.333) X3 = (1.467, 1.239)

Distance between two points

||Xi − Xi+1 || < ε3

||X2 − X3 || < ε3
q
= (1.333 − 1.467)2 + (1.333 − 1.239)2
√
= 0.0179 + 0.0088
√
= 0.0267
=0.13 ≮ ε3

Hence the convergence criteria are not satisfied.

58 / 125
Zoutendijk’s Method

Check constraints at the new point is X3 = (1.467, 1.239)

g1 (X3 ) = x1 + 2x2 − 4 ≤ 0
= 1.467 + 2(1.239) − 4
= 1.467 + 2.478 − 4
= −0.055 ≤ 0

The constraint value is g1 (X3 ) ≤ 0

This condition is satisfied.
The procedure is continued until the optimum point X ∗ = (1.6, 1.2)

59 / 125
Zoutendijk’s Method
Iteration 3:
Current point:  
1.467
X3 =
1.239
Since g1 (X3 ) < 0, the point is interior.
g1 (X3 ) = 1.467 + 2(1.239) − 4 = −0.055 < 0
Hence,
S3 = −∇f (X3 )
     
2x1 − 4 2(1.467) − 4 −1.066
∇f (x1 , x2 ) = = =
2x2 − 4 2(1.239) − 4 −1.522
 
1.066
S3 =
1.522
Normalize:  
0.700
S3 =
1.000
60 / 125
Zoutendijk’s Method
 
1.467 + 0.7λ
X4 = X3 + λS3 =
1.239 + λ
Substitute into objective function:
f (X3 + λS3 ) = 1.49λ2 − 1.98λ + 0.863
df
= 0 =⇒ 2.98λ − 1.98 = 0 =⇒ λ = 0.664
dλ
Check feasibility:
g1 (λ) = −0.055 + 2.7λ
Set g1 (λ) = 0:
λ = 0.020
Thus,  
1.481
X4 =
1.259
f (X4 ) = 0.842
61 / 125
Zoutendijk’s Method
Iteration 4:
Current point:  
1.481
X4 =
1.259
g1 (X4 ) = 1.481 + 2(1.259) − 4 ≈ 0
Since the constraint is active, we solve LP subproblem.
Minimize
f = −α
Subject to
−1.038t1 − 1.482t2 + α + y1 = 0
t1 + 2t2 + α + y2 = 0
t1 + y 3 = 1
t2 + y 4 = 1
t1 , t2 , α, yi ≥ 0
62 / 125
Zoutendijk’s Method

The given Solution:

t1∗ = 2, t2∗ = 0.3, α∗ > 0

Feasible direction:  
1
S4 =
−0.7

63 / 125
Zoutendijk’s Method
 
1.481 + λ
X5 = X4 + λS4 =
1.259 − 0.7λ
Substitute into objective:
f (λ) = 1.49λ2 − 0.238λ + 0.842
df
= 0 =⇒ 2.98λ − 0.238 = 0 =⇒ λ = 0.08
dλ
New point:  
1.561
X5 =
1.203
f (X5 ) = 0.803
The iterations continue until
 
∗ 1.6
X = =⇒ fmin = 0.8
1.2
64 / 125
Zoutendijk’s Method

Iteration 5:
Current point:  
1.561
X5 =
1.203

g1 (X5 ) = 1.561 + 2(1.203) − 4

= 1.561 + 2.406 − 4

= −0.033 < 0
Hence, X5 is an interior feasible point.

65 / 125
Zoutendijk’s Method

Since g1 (X5 ) < 0, we take

S5 = −∇f (X5 )
 
2x1 − 4
∇f (x1 , x2 ) =
2x2 − 4
   
2(1.561) − 4 −0.878
∇f (X5 ) = =
2(1.203) − 4 −1.594
Thus,  
0.878
S5 =
1.594
Normalize:  
0.551
S5 =
1.000

66 / 125
Zoutendijk’s Method
 
1.561 + 0.551λ
X6 = X5 + λS5 =
1.203 + λ
Substitute into objective function:
f (λ) = 1.49λ2 − 1.16λ + 0.803
df
= 0 =⇒ 2.98λ − 1.16 = 0 =⇒ λ = 0.389
dλ
Check feasibility:
g1 (λ) = −0.033 + 2.551λ
Set g1 (λ) = 0:
λ = 0.013
Thus,  
1.568
X6 =
1.216
f (X6 ) = 0.801
67 / 125
Zoutendijk’s Method

Iter Xi f (Xi ) g1 (Xi ) Si λi Xi+1

4
1 (0, 0) 8.000 −4.000 (1, 1) 3 (1.333, 1.333)
2 (1.333, 1.333) 0.889 0 (1, −0.7) 0.134 (1.467, 1.239)
3 (1.467, 1.239) 0.863 −0.055 (0.7, 1) 0.020 (1.481, 1.259)
4 (1.481, 1.259) 0.842 ≈0 (1, −0.7) 0.080 (1.561, 1.203)
5 (1.561, 1.203) 0.803 −0.033 (0.551, 1) 0.013 (1.568, 1.216)

X ∗ = (1.6, 1.2) fmin = 0.8

68 / 125
Zoutendijk’s Method

The objective function is

f (x1 , x2 ) =x12 + x22 − 4x1 − 4x2 + 8

=1.62 + 1.22 − 4(1.6) − 4(1.2) + 8
=2.56 + 1.44 − 6.4 − 4.8 + 8
=0.8

The optimum point X ∗ = (1.6, 1.2)

The objective function value is fmin = 0.8

69 / 125
Indirect Method

Penalty Function Method

The penalty function method is an optimization technique that

transforms a constrained optimization problem into a series of
unconstrained problems by adding a penalty term to the objective
function for violating constraints.

1. Interior Penalty Function Method

The unconstrained minimum of all lie in the feasible region and converge
to the solution of decreased sequence.

2. Exterior Penalty Function Method

The unconstrained minimum of all lie in the infeasible region and

converge to the solution of increased sequence.

70 / 125
Interior Penalty Function Method
Iterative Process:
Step 1: Start with an initial feasible point X1 satisfying all the constraints with
strict inequality sign, that is gj (X1 ) < 0 for j = 1, 2, ..m, and an initial value of
r1 > 0. Set k = 1.

Step:2 Minimize ϕ(X, rk ) by using unconstrained minimization methods and

obtain the solution Xk∗ .

where
m
X 1
ϕ(X, rk ) = f (X) − rk
gj (X)
j=1

Step 3: Test whether Xk∗ is the optimum solution of the original problem by

fmin (r) ≊ ϕmin (r).

If Xk∗ is optimum, terminate the process. Otherwise, go to next step.

71 / 125
Interior Penalty Function Method

Step 4: Find the value of the next penalty parameter rk+1 , as

rk+1 = crk

where
c < 1. the value of c can be taken as 0.1, 0.2, or 0.5.

Step 5: Set the new value of k = k + 1, take the new starting point as X1 = Xk∗ ,
and go to step 2.

72 / 125
Interior Penalty Function Method
Example 1:

1
Minimize f (x1 , x2 ) = (x1 + 1)3 + x2
3
Subject to
g1 (x1 , x2 ) = −x1 + 1 ≤ 0

g2 (x1 , x2 ) = −x2 ≤ 0
Solution:
The interior penalty function formula
m
X 1
ϕ(X, rk ) = f (X) − rk
gj (X)
j=1

73 / 125
Interior Penalty Function Method

1 1 1
ϕ(X, r) = (x1 + 1)3 + x2 − r( − )
3 −x1 + 1 x2
Derivative with respect to x1
∂ϕ r
= (x1 + 1)2 − =0
∂x1 (1 − x1 )2
r
(x1 + 1)2 =
(1 − x1 )2
(x1 + 1)2 (1 − x1 )2 =r
(x12 + 1 + 2x1 )(1 + x12 − 2x1 ) =r
x14 + 1 − 2x12 =r
(x12 − 1)2 =r
squring on both sides
√
x12 − 1 = r =⇒ x1 = (r1/2 + 1)1/2 =⇒ x1∗ = (r1/2 + 1)1/2 (x1 = x1∗ )
74 / 125
Interior Penalty Function Method

Derivative with respect to x2

1 1 1
ϕ(X, r) = (x1 + 1)3 + x2 − r( − )
3 −x1 + 1 x2

∂ϕ r
= 1 − 2 =0
∂x2 x2
x22 − r =0
x22 =r

squring on both sides

x2 = r1/2 =⇒ x2∗ = r1/2 (x2 = x2∗ )

75 / 125
Interior Penalty Function Method

These equations give

x1∗ (r) = (r1/2 + 1)1/2 , x2∗ (r) = r1/2
Substitude
1 1 1
ϕ(X, r) = (x1 + 1)3 + x2 − r( − )
3 −x1 + 1 x2
1 1 1
ϕmin (r) = [(r1/2 + 1)1/2 + 1]3 + r1/2 − r( − )
3 −(r1/2 + 1)1/2 + 1 r1/2
1 1
ϕmin (r) = [(r1/2 + 1)1/2 + 1]3 + 2r1/2 −
3 (1/r) − (1/r + 1/r2 )1/2
3/2

76 / 125
Interior Penalty Function Method

Iteration 1:
Let r = 1000,

x1∗ (r) =(r1/2 + 1)1/2

x1∗ (1000) =(10001/2 + 1)1/2
=(31.6227 + 1)1/2
=(32.6227)1/2
=5.71164.

x2∗ (r) =r1/2

x2∗ (1000) =10001/2
=31.6227.

77 / 125
Interior Penalty Function Method

1 1
ϕmin (r) = [(r1/2 + 1)1/2 + 1]3 + 2r1/2 −
3 (1/r) − (1/r + 1/r2 )1/2
3/2

1
ϕmin (1000) = [(10001/2 + 1)1/2 + 1]3 + 2(1000)1/2
3
1
−
(1/1000) − (1/10003/2 + 1/10002 )1/2
1
= [(31.6227 + 1)1/2 + 1]3 + 2(31.6227)
3
1
= [5.7116 + 1]3 + 63.2455 + 212.2405
3
1
= [302.3278] + 275.4860
3
=100.7759 + 275.4860
ϕmin (r) =376.2636

78 / 125
Interior Penalty Function Method

1
fmin (r) = (x1 (r) + 1)3 + x2 (r)
3
1
= (5.71164 + 1)3 + 31.62278
3
=100.7777 + 31.62278
fmin (r) =132.4003

fmin (r) ̸≊ ϕmin (r)

132.4003 ̸≊ 376.2636

79 / 125
Interior Penalty Function Method

Iteration 2:
Let r = 100,

x1∗ (r) =(r1/2 + 1)1/2

x1∗ (100) =(1001/2 + 1)1/2
=(10 + 1)1/2
=(11)1/2
x1∗ (r) =3.31662.

x2∗ (r) =r1/2

x2∗ (100) =1001/2
x2∗ (r) =10.00000.

80 / 125
Interior Penalty Function Method

1 1
ϕmin (r) = [(r1/2 + 1)1/2 + 1]3 + 2r1/2 −
3 (1/r) − (1/r3/2 + 1/r2 )1/2
1
ϕmin (100) = [(1001/2 + 1)1/2 + 1]3 + 2(100)1/2
3
1
−
(1/100) − (1/1003/2 + 1/1002 )1/2
1
= [(10 + 1)1/2 + 1]3 + 2(10) + 43.16624
3
1
= [4.31662]3 + 20 + 43.16624
3
=26.8109 + 63.16624
ϕmin (r) =89.9772

81 / 125
Interior Penalty Function Method

1
fmin (r) = (x1 (r) + 1)3 + x2 (r)
3
1
= (3.31662 + 1)3 + 10.00000
3
=26.81082 + 10.00000
fmin (r) =36.8109

fmin (r) ̸≊ ϕmin (r)

36.8109 ̸≊ 89.9772

82 / 125
Interior Penalty Function Method

Iteration 3:
Let r = 10,

x1∗ (r) =(r1/2 + 1)1/2

x1∗ (10) =(101/2 + 1)1/2
=(3.1622 + 1)1/2
=(4.1622)1/2
=2.04017.

x2∗ (r) =r1/2

x2∗ (10) =101/2
=3.16228.

83 / 125
Interior Penalty Function Method

1 1
ϕmin (r) = [(r1/2 + 1)1/2 + 1]3 + 2r1/2 −
3 (1/r) − (1/r3/2 + 1/r2 )1/2
1
ϕmin (10) = [(101/2 + 1)1/2 + 1]3 + 2(10)1/2
3
1
−
(1/10) − (1/103/2 + 1/102 )1/2
1
= [(3.16228 + 1)1/2 + 1]3 + 2(3.1622) + 9.61384
3
1
= [3.04014]3 + 6.32456 + 9.61384
3
=9.36618 + 15.93840
ϕmin (r) =25.3048

84 / 125
Interior Penalty Function Method

1
fmin (r) = (x1 (r) + 1)3 + x2 (r)
3
1
= (2.04017 + 1)3 + 3.16228
3
=9.36639 + 3.16228
fmin (r) =12.5286

fmin (r) ̸≊ ϕmin (r)

12.5286 ̸≊ 25.3048

85 / 125
Interior Penalty Function Method

Iteration 4:
Let r = 1,

x1∗ (r) =(r1/2 + 1)1/2

x1∗ (1) =(11/2 + 1)1/2
=(1 + 1)1/2
=(2)1/2
=1.41421.

x2∗ (r) =r1/2

x2∗ (1) =11/2
=1.00000.

86 / 125
Interior Penalty Function Method

1 1
ϕmin (r) = [(r1/2 + 1)1/2 + 1]3 + 2r1/2 −
3 (1/r) − (1/r3/2 + 1/r2 )1/2
1
ϕmin (1) = [(11/2 + 1)1/2 + 1]3 + 2(1)1/2
3
1
−
(1/1) − (1/13/2 + 1/12 )1/2
1
= [(1 + 1)1/2 + 1]3 + 2 + 2.41421
3
1
= [2.41421]3 + 4.41421
3
=4.69035 + 4.41421
ϕmin (r) =9.1046

87 / 125
Interior Penalty Function Method

1
fmin (r) = (x1 (r) + 1)3 + x2 (r)
3
1
= (1.41421 + 1)3 + 1.00000
3
=4.69033 + 1.00000
fmin (r) =5.6904

fmin (r) ̸≊ ϕmin (r)

5.6904 ̸≊ 9.1046

88 / 125
Interior Penalty Function Method

Iteration 5:
Let r = 0.1,

x1∗ (r) =(r1/2 + 1)1/2

x1∗ (0.1) =(0.11/2 + 1)1/2
=(0.31622 + 1)1/2
=(1.31622)1/2
=1.14726.

x2∗ (r) =r1/2

x2∗ (0.1) =0.11/2
=0.31622.

89 / 125
Interior Penalty Function Method

1 1
ϕmin (r) = [(r1/2 + 1)1/2 + 1]3 + 2r1/2 −
3 (1/r) − (1/r3/2 + 1/r2 )1/2
1
ϕmin (0.1) = [(0.11/2 + 1)1/2 + 1]3 + 2(0.1)1/2
3
1
−
(1/0.1) − (1/0.13/2 + 1/0.12 )1/2
1
= [(0.31622 + 1)1/2 + 1]3 + 2(0.31622) + 0.67902
3
1
= [2.14726]3 + 0.63244 + 0.67902
3
=3.30017 + 1.31146
ϕmin (r) =4.6117

90 / 125
Interior Penalty Function Method

1
fmin (r) = (x1 (r) + 1)3 + x2 (r)
3
1
= (1.14727 + 1)3 + 0.31623
3
=3.30018 + 0.31623
fmin (r) =3.6164

fmin (r) ̸≊ ϕmin (r)

3.6164 ̸≊ 4.6117

91 / 125
Interior Penalty Function Method

Iteration 6:
Let r = 0.01,

x1∗ (r) =(r1/2 + 1)1/2

x1∗ (0.01) =(0.011/2 + 1)1/2
=(0.1 + 1)1/2
=(1.1)1/2
=1.04881.

x2∗ (r) =r1/2

x2∗ (0.01) =0.011/2
=0.1000.

92 / 125
Interior Penalty Function Method

1 1
ϕmin (r) = [(r1/2 + 1)1/2 + 1]3 + 2r1/2 −
3 (1/r) − (1/r3/2 + 1/r2 )1/2
1
ϕmin (0.01) = [(0.011/2 + 1)1/2 + 1]3 + 2(0.01)1/2
3
1
−
(1/0.01) − (1/0.013/2 + 1/0.012 )1/2
1
= [(0.1 + 1)1/2 + 1]3 + 2(0.1) + 0.67902
3
1
= [2.04880]3 + 0.2 + 0.20488
3
=2.86670 + 0.40488
ϕmin (r) =3.2716

93 / 125
Interior Penalty Function Method

1
fmin (r) = (x1 (r) + 1)3 + x2 (r)
3
1
= (1.04881 + 1)3 + 0.1000
3
=2.8667 + 0.1000
fmin (r) =2.9667

fmin (r) ̸≊ ϕmin (r)

2.9667 ̸≊ 3.2716

94 / 125
Interior Penalty Function Method

Iteration 7:
Let r = 0,

x1∗ (r) =(r1/2 + 1)1/2

x1∗ (0) =(01/2 + 1)1/2
=(0 + 1)1/2
=(1)1/2
=1.

x2∗ (r) =r1/2

x2∗ (0) =01/2
=0.

95 / 125
Interior Penalty Function Method

1 1
ϕmin (r) = [(r1/2 + 1)1/2 + 1]3 + 2r1/2 −
3 (1/r) − (1/r + 1/r2 )1/2
3/2

1
ϕmin (0) = [(01/2 + 1)1/2 + 1]3 + 2(0)1/2
3
1
−
(1/0) − (1/03/2 + 1/02 )1/2
1
= [(0 + 1)1/2 + 1]3 + 2(0) + 0
3
1 3
= [2] + 0 + 0
3
1
= [8]
3
8
=
3
ϕmin (r) =2.6666
96 / 125
Interior Penalty Function Method

1
fmin (r) = (x1 (r) + 1)3 + x2 (r)
3
1
= (1 + 1)3 + 0
3
1
= [2]3 + 0
3
8
=
3
fmin (r) =2.6666

fmin (r) ≊ ϕmin (r)

2.6666 ≊ 2.6666

97 / 125
Interior Penalty Function Method

The values of f , x1∗ , x2∗ corresponding to a decreasing sequence of values of r are

shown in Table 1.1:
Value of r x1∗ (r) = (r1/2 + 1)1/2 x2∗ (r) = r1/2 ϕmin (r) fmin (r)
1000 5.71164 31.62278 376.2636 132.4003
100 3.31664 10.0000 89.9772 36.8109
10 2.04017 3.16228 25.3048 12.5286
1 1.41421 1.0000 9.1046 5.6904
0.1 1.14727 0.31623 4.6117 3.6164
0.01 1.04881 0.1000 3.2716 2.9667
0.001 1.0156 0.0316 2.8569 2.7615
0 1 0 2.6666 2.6666
To obtain the solution of the original problem, we know that
x1∗ = lim x1∗ (r) = 1
r→0

x2∗ = lim x2∗ (r) = 0

r→0

fmin = lim ϕmin (r) = 2.6666

r→0

98 / 125
Exterior Penalty Function Method

It can deal with both equality and inequality constraints.

The sequence of unconstrained minimum lie in the infeasible region.

It converges to the constrained minimum form the exterior of the feasible

region.

Since the rk can not be ∞, the final Xk∗ still locate in infeasible region.
This is an important property of exterior penalty function method.

99 / 125
Exterior Penalty Function Method
Algorithm:
Step 1: Start from any design X1 and a suitable value of r1 . Set k = 1.
Step 2: Find the vector Xk∗ that minimizes the function
m
X
ϕ(X, rk ) = f (X) + rk (gj (X))q
j=1

Where
rk is positive penalty parameter
The second term on the right side of the equation is called the Penalty
term.
q is nonnegative constant
The bracket function (gj (X)) is defined as
(gj (X)) =max(gj (X), 0)
(
gj (X) if gj (X) > 0 (constraint is violated)
=
0 if gj (X) ≤ 0 (constraint is satisfied)
100 / 125
Exterior Penalty Function Method

Step 3: Test whether the point Xk∗ satisfies all the constraints. If Xk∗ is optimum
and terminate the process. Otherwise, go to step 4.
Step 4: Choose the next value of the penalty parameter satisfies the relation

rk+1 > rk

Step 5:Set the new value of k = k + 1 and go to step 2. The value of rk+1 is
chosen according to the relation

rk+1 = crk

where c > 1.

101 / 125
Exterior Penalty Function Method
Example 1:

1
Minimize f (x1 , x2 ) = (x1 + 1)3 + x2
3
Subject to
g1 (x1 , x2 ) = −x1 + 1 ≤ 0

g2 (x1 , x2 ) = −x2 ≤ 0
Solution:
The exterior penalty function formula
m
X
ϕ(X, rk ) = f (X) + rk (gj (X))q
j=1

Let the value of q=2.

102 / 125
Exterior Penalty Function Method

1
ϕ(X, r) = (x1 + 1)3 + x2 + r[max(0, 1 − x1 )]2 + r[max(0, −x2 )]2
3
Derivative with respect to x1

∂ϕ
= (x1 + 1)2 − 2r[max(0, 1 − x1 )] = 0 (5.1)
∂x1
Derivative with respect to x2

∂ϕ
= 1 − 2r[max(0, −x2 )] = 0 (5.2)
∂x2

103 / 125
Exterior Penalty Function Method
These equations can be written as
min[(x1 + 1)2 , (x1 + 1)2 − 2r(1 − x1 )] = 0 (5.3)
min[1, 1 + 2rx2 ] = 0 (5.4)
Equation 0.3: min[(x1 + 1)2 , (x1 + 1)2 − 2r(1 − x1 )] = 0
Case 1:
(x1 + 1)2 = 0
x1 + 1 = 0 =⇒ x1 = −1
This violates the first constraint.
Case 2:
(x1 + 1)2 − 2r(1 − x1 ) = 0
(x1 + 1)2 = 2r(1 − x1 )
x12 + 2x1 + 1 = 2r − 2rx1
x12 + (2 + 2r)x1 = 2r − 1
x12 + (2 + 2r)x1 + (1 − 2r) = 0 104 / 125
Exterior Penalty Function Method
Apply the quadratic formula:
√
−b ± b2 − 4ac
x1 =
2a
Where
a = 1, b = 2 + 2r, c = 1 − 2r

p
−(2 + 2r) ± (2 + 2r)2 − 4.1.(1 − 2r)
x1 =
√ 2.1
−2 − 2r ± 4 + 8r + 4r2 − 4 + 8r
x1 =
√ 2
2
−2 − 2r ± 4r + 16r
x1 =
2
p
x1 = −1 − r ± r2 + 4r

105 / 125
Exterior Penalty Function Method

Equation 0.4: min[1, 1 + 2rx2 ] = 0

The only possibility is that

1 + 2rx2 = 0
−1
x2 =
2r
The solution of the unconstrained minimization problem is given by
p −1
x1∗ (r) = −1 − r ± r2 + 4r, x2∗ (r) =
2r

106 / 125
Exterior Penalty Function Method
Iteration 1:
Let r = 0.01,
p
x1∗ (r) = − 1 − r ± r2 + 4r
q
x1∗ (0.01) = − 1 − 0.01 + 0.012 + 4(0.01)
√
= − 1 − 0.01 + 0.0401
= − 1 − 0.01 + 0.2002
= − 0.80975.

−1
x2∗ (r) =
2r
−1
x2∗ (0.01) =
2(0.01)
= − 50.0000.

107 / 125
Exterior Penalty Function Method

1
ϕmin (r) = (x1 + 1)3 + x2 + r[max(0, 1 − x1 )]2 + r[max(0, −x2 )]2
3
1
ϕmin (0.01) = (−0.80975 + 1)3 − 50.0000
3
+ 0.01[max(0, 1 − (−0.80975))]2 + 0.01[max(0, −(−50.0000))]2
1
= (0.19025)3 − 50.0000
3
+ 0.01[max(0, 1.80975)]2 + 0.01[max(0, 50.0000)]2
1
= [0.00688] − 50.0000 + 0.01(1.80975)2 + 0.01(50.0000)2
3
=0.00229 − 50.0000 + 0.0327 + 25
= − 24.9650

108 / 125
Exterior Penalty Function Method

1
fmin (r) = (x1 (r) + 1)3 + x2 (r)
3
1
= (−0.80975 + 1)3 − 50.0000
3
1
= [0.00688] − 50.0000
3
=0.00229 − 50.0000
= − 49.9977

109 / 125
Exterior Penalty Function Method
Iteration 2:
Let r = 0.1,
p
x1∗ (r) = − 1 − r ± r2 + 4r
q
x1∗ (0.1) = − 1 − 0.1 + 0.12 + 4(0.1)
√
= − 1 − 0.1 + 0.41
= − 1 − 0.1 + 0.6403
= − 0.45969.

−1
x2∗ (r) =
2r
−1
x2∗ (0.1) =
2(0.1)
= − 5.0000.

110 / 125
Exterior Penalty Function Method

1
ϕmin (r) = (x1 + 1)3 + x2 + r[max(0, 1 − x1 )]2 + r[max(0, −x2 )]2
3
1
ϕmin (0.1) = (−0.45969 + 1)3 − 5.0000
3
+ 0.1[max(0, 1 − (−0.45969))]2 + 0.1[max(0, −(−5.0000))]2
1
= (0.54031)3 − 5.0000
3
+ 0.1[max(0, 1.45969)]2 + 0.1[max(0, 5.0000)]2
1
= [0.15773] − 5.0000 + 0.1(1.45969)2 + 0.1(5.0000)2
3
=0.05257 − 5.0000 + 0.21306 + 2.5
= − 2.2344

111 / 125
Exterior Penalty Function Method

1
fmin (r) = (x1 (r) + 1)3 + x2 (r)
3
1
= (−0.45969 + 1)3 − 5.0000
3
1
= [0.15773] − 5.0000
3
=0.05257 − 5.0000
= − 4.9474

112 / 125
Exterior Penalty Function Method
Iteration 3:
Let r = 1,
p
x1∗ (r) = − 1 − r ± r2 + 4r
q
x1∗ (1) = − 1 − 1 + 12 + 4(1)
√
=−1−1+ 5
= − 2 + 2.23606
=0.23607.

−1
x2∗ (r) =
2r
−1
x2∗ (1) =
2(1)
= − 0.50000.

113 / 125
Exterior Penalty Function Method

1
ϕmin (r) = (x1 + 1)3 + x2 + r[max(0, 1 − x1 )]2 + r[max(0, −x2 )]2
3
1
ϕmin (1) = (0.23607 + 1)3 − 0.50000
3
+ 1[max(0, 1 − (0.23607))]2 + 1[max(0, −(−0.50000))]2
1
= (1.23607)3 − 0.50000
3
+ 1[max(0, 0.76393)]2 + 1[max(0, 0.50000)]2
1
= [1.88855] − 0.50000 + 1(0.76393)2 + 1(0.50000)2
3
=0.62951 − 0.50000 + 0.58358 + 0.25
=0.9631

114 / 125
Exterior Penalty Function Method

1
fmin (r) = (x1 (r) + 1)3 + x2 (r)
3
1
= (0.23607 + 1)3 − 0.50000
3
1
= [1.8885] − 0.50000
3
=0.62951 − 0.50000
=0.1295

115 / 125
Exterior Penalty Function Method
Iteration 4:
Let r = 10,
p
x1∗ (r) = − 1 − r ± r2 + 4r
q
x1∗ (10) = − 1 − 10 + 102 + 4(10)
√
= − 1 − 10 + 140
= − 11 + 11.83215
=0.83216.

−1
x2∗ (r) =
2r
−1
x2∗ (10) =
2(10)
= − 0.05000.

116 / 125
Exterior Penalty Function Method

1
ϕmin (r) = (x1 + 1)3 + x2 + r[max(0, 1 − x1 )]2 + r[max(0, −x2 )]2
3
1
ϕmin (10) = (0.83216 + 1)3 − 0.05000
3
+ 10[max(0, 1 − (0.83216))]2 + 10[max(0, −(−0.05000))]2
1
= (1.83216)3 − 0.05000
3
+ 10[max(0, 0.16784)]2 + 10[max(0, 0.05000)]2
1
= [6.15021] − 0.05000 + 10(0.16784)2 + 10(0.05000)2
3
=2.05007 − 0.05000 + 0.28170 + 0.025
=2.3068

117 / 125
Exterior Penalty Function Method

1
fmin (r) = (x1 (r) + 1)3 + x2 (r)
3
1
= (0.83216 + 1)3 − 0.05000
3
1
= [6.15021] − 0.05000
3
=2.05007 − 0.05000
=2.0001

118 / 125
Exterior Penalty Function Method
Iteration 5:
Let r = 100,
p
x1∗ (r) = − 1 − r ± r2 + 4r
q
x1∗ (100) = − 1 − 100 + 1002 + 4(100)
√
= − 1 − 100 + 10400
= − 101 + 101.98039
=0.98039.

−1
x2∗ (r) =
2r
−1
x2∗ (100) =
2(100)
= − 0.00500.

119 / 125
Exterior Penalty Function Method

1
ϕmin (r) = (x1 + 1)3 + x2 + r[max(0, 1 − x1 )]2 + r[max(0, −x2 )]2
3
1
ϕmin (100) = (0.98039 + 1)3 − 0.00500
3
+ 100[max(0, 1 − (0.98039))]2 + 100[max(0, −(−0.00500))]2
1
= (1.98039)3 − 0.00500
3
+ 100[max(0, 0.01961)]2 + 100[max(0, 0.00500)]2
1
= [7.76697] − 0.00500 + 100(0.01961)2 + 100(0.005000)2
3
=2.58899 − 0.00500 + 0.03845 + 0.0025
=2.6249

120 / 125
Exterior Penalty Function Method

1
fmin (r) = (x1 (r) + 1)3 + x2 (r)
3
1
= (0.98039 + 1)3 − 0.00500
3
1
= [7.76697] − 0.00500
3
=2.58899 − 0.005000
=2.5840

121 / 125
Exterior Penalty Function Method

Iteration 6:
Let r = ∞,
p
x1∗ (r) = − 1 − r ±r2 + 4r
q
x1∗ (∞) = − 1 − ∞ + ∞2 + 4(∞)
=−1−∞+∞
= − 1.

−1
x2∗ (r) =
2r
−1
x2∗ (∞) =
2(∞)
=0.

122 / 125
Exterior Penalty Function Method

1
ϕmin (r) = (x1 + 1)3 + x2 + r[max(0, 1 − x1 )]2 + r[max(0, −x2 )]2
3
1
ϕmin (∞) = (1 + 1)3 + 0 + ∞[max(0, 1 − (1))]2 + ∞[max(0, −(0))]2
3
1 3
= (2) + 0 + 0 + 0
3
1
= [8]
3
8
=
3
=2.6666

123 / 125
Exterior Penalty Function Method

1
fmin (r) = (x1 (r) + 1)3 + x2 (r)
3
1
= (1 + 1)3 + 0
3
1
= [2]3 + 0
3
1
= [8]
3
8
=
3
=2.6666

124 / 125
Interior Penalty Function Method

The convergence of the method, as√r increases gradually, can be seen from Table 1.2.
Value of r x1∗ (r) = −1 − r + r2 + 4r x2∗ (r) = −1 2r ϕmin (r) fmin (r)
0.01 -0.80975 -50.0000 -24.9650 -49.9977
0.1 -0.45969 -5.0000 -2.2344 -4.9474
1 0.23607 -0.5000 0.9631 0.1295
10 0.83216 -0.0500 2.3068 2.0001
100 0.98039 -0.0050 2.6249 2.5840
1000 0.99800 -0.0005 2.6624 2.6582
∞ -1 0 2.6666 2.6666

To obtain the solution of the original problem, we know that

x1∗ = lim x1∗ (r) = 1

r→∞

x2∗ = lim x2∗ (r) = 0

r→∞

fmin = lim ϕmin (r) = 2.6666

r→∞

125 / 125