Engineering Optimization: Theory and Practice, Fourth Edition

388 Nonlinear Programming III: Constrained Optimization Techniques

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

Ifgj(Xi+ 1 )>εfor somej, or|hk(Xi+ 1 ) |>εfor somek, find the most violated

constraint, for example, as

gk(Xi+ 1 ) =max

j

[gj(Xi+ 1 )] (7.19)

Relinearize the constraintgk( X)≤ 0 about the pointXi+ 1 as

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

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

6.Set the new iteration number asi=i+1, the total number of constraints in

the new approximating LP problem asm+1 inequalities andpequalities, and

go to step 4.

The sequential linear programming method has several advantages:

1.It is an efficient technique for solving convex programming problems with

nearly linear objective and constraint functions.

2.Each of the approximating problems will be a LP problem and hence can be

solved quite efficiently. Moreover, any two consecutive approximating LP prob-

lems differ by only one constraint, and hence the dual simplex method can be

used to solve the sequence of approximating LP problems much more effi-

ciently.†

3. he method can easily be extended to solve integer programming problems. InT
   this case, one integer LP problem has to be solved in each stage.

Geometric Interpretation of the Method. The SLP method can be illustrated with

the help of a one-variable problem:

Minimizef (x)=c 1 x

subjectto

g(x)≤ 0 (7.21)

wherec 1 is a constant andg(x)is a nonlinear function ofx. Let the feasible region and

the contour of the objective function be as shown in Fig. 7.5. To avoid any possibility

of unbounded solution, let us first take the constraints onxasc≤x≤d, wherecand

drepresent the lower and upper bounds onx. With these constraints, we formulate the

LP problem:

Minimizef (x)=c 1 x

†The dual simplex method was discussed in Section 4.3.