• PDF / 11,641,011 Bytes
• 122 Pages / 594 x 828 pts Page_size
• 61 Downloads / 212 Views

DOWNLOAD

REPORT

---

G e n e r a l f r a m e w o r k . The c~BB algorithm guarantees finite e-convergence to the global solution of nonlinear programming problems (NLPs) belong-

ing to the general class min

f(x)

X

s.t.

g(x) < 0

(1)

h(x) = 0 x e Ix L x U]

where ](x), g(x) and h(x) are continuous twicedifferentiable functions. The solution scheme is based on the generation of a nonincreasing sequence of upper bounds and a nondecreasing sequence of lower bounds on the global solution. The monotonicity of these sequences is ensured through successive partitioning of the search space which enables the construction of increasingly tight relaxations of the problem. The validity of the bounds obtained is of crucial importance in a rigorous global optimization approach. The upper bounding step does not present any theoretical difficulties and consists of a local optimization of the nonconvex problem. The lower bounding step is a more challenging operation in which the nonconvex problem must be convexifled and underestimated in the current subdomain. The strategy adopted dictates the applicability of the algorithm and plays a pivotal role in its performance as it determines the tightness of the lower bounds obtained. The procedure followed in the c~BB algorithm is discussed in the next section. Finally, the branching step involves the partition of the solution domain with the smallest lower bound on the global optimum solution into a covering set of subdomains. Although this is a simple task, the choice of partition has implications for the rate of

c~BB algorithm convergence of the algorithm and efficient branching rules must be used. Convexification and Underestimation Strate g y . A convex relaxation of problem (1) is ob-

tained by constructing convex underestimators for the nonconvex objective function and inequality constraints and by relaxing the nonlinear equality constraints, replacing them with less stringent linear equality constraints or a set of two convex inequalities. The general convexification/relaxation procedure used is first discussed for the objective function and nonconvex inequalities.

Function Decomposition. A convex underestimator for a twice continuously differentiable function is constructed by following a two-stage procedure. In the first stage, the function is decomposed into a summation of terms of special structure, such as linear, convex, bilinear, trilinear, fractional, fractional trilinear, concave in one variable and general nonconvex terms. Then, based on the fact that the summation of convex functions results in a convex function, a tailored convex underestimator is used for each different term type. Thus, a twicedifferentiable function F ( x ) defined over the domain [x L, x U] is written as bt

bixs,,lXs,,2

F ( x ) - cTx + F C ( X ) + ~

(2)

pating in the fractional term; f t t is the number of fractional trilinear terms, Sti is the coefficient of the ith fractional trilinear term and XFT~,l, X F T i , 2 a n d XFTi,3 are the three variables participating in the fractional trilinear term; uct is