Engineering Optimization: Theory and Practice, Fourth Edition

390 Nonlinear Programming III: Constrained Optimization Techniques

Figure 7.6 Linearization of constraint aboutc.

g(c)+

dg

dx

(c)(x−c)≤ 0 (7.24c)

g(e)+

dg

dx

(e)(x−e)≤ 0 (7.24d)

The permissible range ofx, according to the constraints( 7. 24 b),( 7. 24 c), and( 7. 24 d),

can be seen to bef≤x≤dfrom Fig. 7.7. The optimum solution of the LP problem

of Eqs. (7.24) can be obtained asx∗=f.

We then linearize g(x)≤0 about the present point x∗= f and add it to the

previous constraint set [Eqs. (7.24)] to define a new approximating LP problem. This

procedure has to be continued until the optimum solution is found to the desired level of

accuracy. As can be seen from Figs. 7.6 and 7.7, the optimum of all the approximating

LP problems (e.g., pointsc, e, f,.. .)lie outside the feasible region and converge toward

the true optimum point,x=a. The process is assumed to have converged whenever

the solution of an approximating problem satisfies the original constraint within some

specified tolerance level as

g(xk∗)≤ε

whereεis a small positive number andxk∗is the optimum solution of thekth approx-

imating LP problem. It can be seen that the lines (hyperplanes in a general problem)

defined byg(xk∗) +dg/dx(xk∗)(x−x∗k) ut off a portion of the existing feasible region.c

Hence this method is called thecutting plane method.