Engineering Optimization: Theory and Practice, Fourth Edition

4.7 Karmarkar’s Interior Method 227

2.Test for optimality. Sincef=0 at the optimum point, we stop the procedure

if the following convergence criterion is satisfied:

||cTX(k)|| ≤ε (4.67)

whereεis a small number. If Eq. (4.67) is not satisfied, go to step 3.

3.Compute the next point,X(k+^1 ). For this, we first find a pointY(k+^1 )in the

transformed unit simplex as

Y(k+^1 )=

{

1

n

1

n

· · ·

1

n

}T

−

α([I]−[P]T( [[P]P]T)−^1 [ P])[D(X(k))]c

||c||

√

n(n− 1 )

(4.68)

where||c||is the length of the vectorc, [I] the identity matrix of ordern,

[D(X(k))] ann×nmatrix with all off-diagonal entries equal to 0, and diagonal

entries equal to the components of the vectorX(k)as

[D(X(k))]ii=x(k)i , i= 1 , 2 ,... , n (4.69)

[P] is an (m+1)×nmatrix whose firstmrows are given by [a] [D(X(k))]

and the last row is composed of 1’s:

[P]=

[

[a][D(X(k))]

1 1 · · · 1

]

(4.70)

and the value of the parameterαis usually chosen asα=^14 to ensure con-

vergence. OnceY(k+^1 )is found, the components of the new pointX(k+^1 )are

determined as

xi(k+^1 )=

x(k)i yi(k+^1 )

∑n

r= 1 x

(k)

r y

(k+ 1 )

r

, i= 1 , 2 ,... , n (4.71)

Set the new iteration number ask=k+1 and go to step 2.

Example 4.13 Find the solution of the following problem using Karmarkar’s method:

Minimizef= 2 x 1 +x 2 −x 3

subject to

x 2 −x 3 = 0

x 1 +x 2 +x 3 = 1

xi≥ 0 , i= 1 , 2 , 3 (E.1)

Use the value ofε= 0 .05 for testing the convergence of the procedure.

SOLUTION The problem is already in the required form of Eq. (4.59), and hence
the following iterative procedure can be used to find the solution of the problem.