Engineering Optimization: Theory and Practice, Fourth Edition

396 Nonlinear Programming III: Constrained Optimization Techniques

Eqs. (7.27) and (7.28), one would naturally be tempted to choose the “best” possible

usable feasible direction atXi.

Thuswe seek to find a feasible direction that, in addition to decreasing the value

off, also points away from the boundaries of the active nonlinear constraints. Such a

direction can be found by solving the following optimization problem. Given the point

Xi, find the vectorSand the scalarαthat maximizeαsubject to the constraints

ST∇gj(Xi)+θjα ≤ 0 , j∈J (7.34)

ST∇ f(Xi)+α≤ 0 (7.35)

whereJ represents the set of active constraints andSis normalized by one of the

following relations:

STS=

∑n

i= 1

s^2 i = 1 (7.36)

− 1 ≤si≤ 1 , i= 1 , 2 ,... , n (7.37)

ST∇ f(Xi)≤ 1 (7.38)

In this problem,θjare arbitrary positive scalar constants, and for simplicity, we can

take allθj=. Any solution of this problem with 1 α>0 is a usable feasible direction.

The maximum value ofαgives the best direction (S) that makes the value ofST∇fi

negative and the values ofST∇gj(Xi) s negative as possible simultaneously. In othera

words, the maximum value ofαmakes the directionSsteer away from the active

nonlinear constraint boundaries. It can easily be seen that by giving different values for

differentθj, we can give more importance to certain constraint boundaries compared to

others. Equations (7.36) to (7.38) represent the normalization of the vectorSso as to

ensure that the maximum ofαwill be a finite quantity. If the normalization condition

is not included, the maximum ofαmay be made to approach∞without violating the

constraints [Eqs. (7.34) and (7.35)].

Notice that the objective functionα, and the constraint equations (7.34) and (7.35)

are linear in terms of the variabless 1 , s 2 ,... , sn, The normalization constraint willα.

also be linear if we use either Eq. (7.37) or (7.38). However, if we use Eq. (7.36)

for normalization, it will be a quadratic function. Thus the direction-finding problem

can be posed as a linear programming problem by using either Eq. (7.37) or (7.38)

for normalization. Even otherwise, the problem will be a LP problem except for one

quadratic constraint. It was shown by Zoutendijk [7.5] that this problem can be han-

dled by a modified version of linear programming. Thus the direction-finding problem

can be solved with reasonable efficiency. We use Eq. (7.37) in our presentation. The

direction-finding problem can be stated more explicitly as

Minimize−α

subject to

s 1

∂g 1

∂x 1

+s 2

∂g 1

∂x 2

+ · · · +sn

∂g 1

∂xn

+θ 1 α≤ 0