OPTIMIZATION TECHNIQUES

Module 6: Constrained Nonlinear Programming

Module 6

1 Introduction

2 Direct Method: Sequential Linear Programming

3 Direct Method: Zoutendijk’s Method of Feasible Directions

4 Indirect Method: Interior Penalty Function Method

5 Indirect Method: Exterior Penalty Function 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 / 126
Introduction contd.,

Direct Method Indirect Method

Sequential Linear Programming method Interior Penalty Function method

Zoutendijk’s method Exterior Penalty Function method

Table 1.1: Constrained Optimization Techniques

4 / 126
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.

5 / 126
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
T
hk (Xi ) + ∇hk (Xi ) (X − Xi ) = 0, k = 1, 2..., p
6 / 126
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

7 / 126
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.

8 / 126
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.

9 / 126
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
10 / 126
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

11 / 126
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

12 / 126
Sequential Linear Programming contd.,

The standard form of the LP problem becomes,

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

subject to
y1 + s1 = 4
y2 + s2 = 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

13 / 126
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

14 / 126
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

15 / 126
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

16 / 126
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
 

   
x −2
X − X2 = 1 −
x2 2
 
x +2
= 1
x2 − 2
17 / 126
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

18 / 126
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

19 / 126
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

20 / 126
Sequential Linear Programming contd.,
The standard form of the LP problem becomes,

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

subject to
y1 + s1 = 4
y2 + s2 = 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 − Cj -1 1 0 0 0
21 / 126
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

22 / 126
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

23 / 126
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
24 / 126
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
25 / 126
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

26 / 126
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

27 / 126
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
28 / 126
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
29 / 126
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

30 / 126
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

31 / 126
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
32 / 126
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
33 / 126
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

34 / 126
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

35 / 126
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
36 / 126
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.

37 / 126
Zoutendijk’s Method
Step 3: Find usable feasible direction S by

Minimize − α
Subject to
n
∂g1 ∂g1 ∂g1 X ∂g1
t1 + t2 + .... + tn + θ 1 α + y1 =
∂x1 ∂x2 ∂xn ∂xi
i=1
n
∂g2 ∂g2 ∂g2 X ∂g2
t1 + t2 + .... + tn + θ 2 α + y2 =
∂x1 ∂x2 ∂xn ∂xi
i=1
.
.
.
n
∂gp ∂gp ∂gp X ∂gp
t1 + t2 + .... + tn + θ p α + yp =
∂x1 ∂x2 ∂xn ∂xi
i=1

38 / 126
Zoutendijk’s Method

n
∂f ∂f ∂f X ∂f
t1 + t2 + .... + tn + α + yp+1 =
∂x1 ∂x2 ∂xn ∂xi
i=1
t1 + yp+2 = 2
t2 + yp+3 = 2
.
.
tn + yp+n+1 = 2
t1 ≥ 0
t2 ≥ 0
.
.
tn ≥ 0
α≥0
39 / 126
Zoutendijk’s Method

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.

  ∗ 
s1 t1 − 1
s2  t∗ − 1
  2 
S= . = . 
   
.  . 
sn tn∗ − 1

40 / 126
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.

41 / 126
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.03, ε2 = 0.03, and ε3 = 0.2.
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 42 / 126
Zoutendijk’s Method

Iteration 1:
Since g1 (X1 ) < 0, we take the search direction as
" #
∂f
∂x1
S1 = −∇f (X1 ) = − ∂f
∂x2
 
2x1 − 4
=−
2x2 − 4
 
2(0) − 4
=−
2(0) − 4
 
−4
=−
−4
   
s 4
S1 = 1 =
s2 4

43 / 126
Zoutendijk’s Method

This can be normalized by

S1
S1 =
Max {|s1 |, |s2 |}
 
1 4
S1 =
Max {4, 4} 4
 
1 4
S1 =
4 4
 
1
S1 =
1

44 / 126
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

45 / 126
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
46 / 126
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
g01 (λ0 )
λ̄ = − λ1
g001 (λ1 ) − g01 (λ0 )
Let λ1 = 0
g1 (x1 , x2 ) =x1 + 2x2 − 4
g01 (λ1 , λ1 ) =λ1 + 2λ1 − 4
g01 (0) =0 + 2(0) − 4
=0 − 4
=−4 47 / 126
Zoutendijk’s Method
Let λ1 = 2
g1 (x1 , x2 ) =x1 + 2x2 − 4
g001 (λ1 , λ1 ) =λ1 + 2λ1 − 4
g001 (2) =2 + 2(2) − 4
=2 + 4 − 4
=2
The linear interpolation give the new step length is
g01 (λ0 )
λ̄ = − λ1
g1 (λ1 ) − g01 (λ0 )
00

−(4)
=− 2
2 − (−4)
4
= (2)
6
=1.333
48 / 126
Zoutendijk’s Method

The new corrected point X2 = (1.333, 1.333)

The objective function is

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

f (1.333, 1.333) =(1.333)2 + (1.333)2 − 4(1.333) − 4(1.333) + 8
=1.7777 + 1.7777 − 5.3332 − 5.3332 + 8
=3.5554 − 10.6664 + 8
=0.889

The objective function value f (X2 ) = 0.889

49 / 126
Zoutendijk’s Method

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

f (X1 ) − f (X2 )
| | ≤ ε2
f (X1 )
8 − 0.889
=| |
8
7.111
=
8
=0.8889  0.03

50 / 126
Zoutendijk’s Method

X1 = (0, 0), X2 = (0.889, 0.889)

Distance between two points

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

||X1 − X2 || < ε3
q
= (0 − 0.889)2 + (0 − 0.889)2
√
= 0.7903 + 0.7903
√
= 1.5806
=1.2572 ≮ 0.2

Hence the convergence criteria are not satisfied.

51 / 126
Zoutendijk’s Method

Iteration 2:
check the constraint at the new point is X2 = (1.333, 1.333)

g1 (X2 ) = x1 + 2x2 − 4 ≤ 0
= 1.333 + 2(1.333) − 4
= 1.3333 + 2.666 − 4
=4−4
=0

The constraint value is g1 (X2 ) ≤ 0

This condition is satisfied. and go to next step.

52 / 126
Zoutendijk’s Method

Let θi = 1, i = 1, 2, ..., n

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

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

Differentiate f (x1 , x2 ) with respect to x1 and x2 at the point X2 = (1.333, 1.333)

∂f
= 2x1 − 4 = 2(1.333) − 4 = −1.334
∂x1
∂f
= 2x2 − 4 = 2(1.333) − 4 = −1.334
∂x2

Differentiate g1 (x1 , x2 ) with respect to x1 and x2

∂g1 ∂g1
= 1, =2
∂x1 ∂x2
53 / 126
Zoutendijk’s Method
As g1 (X2 ) = 0 , we proceed to find a usable feasible direction.
Minimize f = −α
Subject to
∂g1 ∂g1 ∂g1 ∂g1
t1 + t2 + θ 1 α + y1 = +
∂x1 ∂x2 ∂x1 ∂x2
∂f ∂f ∂f ∂f
t1 + t2 + θ 2 α + y2 = +
∂x1 ∂x2 ∂x1 ∂x2
t1 + yp+2 = 2
t2 + yp+3 = 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.
54 / 126
Zoutendijk’s Method

Substituting the values of the partial derivatives in the above constraints, we

get
Minimize f = −α
Subject to

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

55 / 126
Zoutendijk’s Method

56 / 126
Zoutendijk’s Method

57 / 126
Zoutendijk’s Method

58 / 126
Zoutendijk’s Method

59 / 126
Zoutendijk’s Method

Solve the above Linear Programming problem by using Simplex Method, We

get the following solutions
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

60 / 126
Zoutendijk’s Method

The minimum value is

4
−fmin = −α∗ = − = −0.4
10
Since α∗ > ε1 , we go to the next step.
∗ 
t1 − 1
S2 = ∗
t2 − 1
 
2−1
=
0.3 − 1
 
1.0
=
−0.7

61 / 126
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λ)

62 / 126
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

63 / 126
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

64 / 126
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

65 / 126
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

66 / 126
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

67 / 126
Zoutendijk’s Method

X2 = (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 satisfied.

68 / 126
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.

69 / 126
Zoutendijk’s Method

Iteration table
I Xi f (Xi ) g(Xi ) | f (Xi )−f (Xi +1)
f (Xi ) | ≤ ε2 kXi − Xi+1 k < ε3
(0,0) 8 −4 - -
1 (1.33, 1.33) 0.889 0 0.8889  0.03 1.2572 ≮ 0.2
2 (1.467, 1.239) 0.8631 −0.0554 0.0291 ≤ 0.03 0.13 < 0.2

70 / 126
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.86

The optimum point X ∗ = (1.46, 1.23)

The objective function value is fmin = 0.86

71 / 126
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. If Xk∗
is optimum, terminate the process. Otherwise, go to next step.

72 / 126
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.

73 / 126
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

74 / 126
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
75 / 126
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

76 / 126
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/2 1 1
φmin (r) = [(r + 1)1/2 + 1]3 + r1/2 − r( 1/2 1/2
− 1/2 )
3 −(r + 1) + 1 r
1 1
φmin (r) = [(r1/2 + 1)1/2 + 1]3 + 2r1/2 −
3 (1/r) − (1/r3/2 + 1/r2 )1/2

77 / 126
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.

78 / 126
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
=376.2636

79 / 126
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
=132.4003

80 / 126
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
=3.31662.

x2∗ (r) =r1/2

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

81 / 126
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 (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
=89.9772

82 / 126
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
=36.8109

83 / 126
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.

84 / 126
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 (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
=25.3048

85 / 126
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
=12.5286

86 / 126
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.

87 / 126
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 (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
=9.1046

88 / 126
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
=5.6904

89 / 126
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.

90 / 126
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.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
=4.6117

91 / 126
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
=3.6164

92 / 126
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.

93 / 126
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) = [(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
=3.2716

94 / 126
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
=2.9667

95 / 126
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.

96 / 126
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
=2.6666
97 / 126
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
=2.6666

98 / 126
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
99 / 126
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.

100 / 126
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)
101 / 126
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.

102 / 126
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.

103 / 126
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

104 / 126
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 105 / 126
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 − 2r ± 4r2 + 16r
x1 =
2
p
x1 = −1 − r ± r2 + 4r

106 / 126
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

107 / 126
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.

108 / 126
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

109 / 126
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

110 / 126
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.

111 / 126
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

112 / 126
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

113 / 126
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.

114 / 126
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

115 / 126
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

116 / 126
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.

117 / 126
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

118 / 126
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

119 / 126
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.

120 / 126
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

121 / 126
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

122 / 126
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.

123 / 126
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

124 / 126
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

125 / 126
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→∞

126 / 126