Global optimization of nonconvex separable programs

In this dissertation consideration is given to the optimization of a function of n variables subject to constraints which restrict the allowable solution space. In particular, the functions composing the problem must be of a separable nature. Thus it must be possible to describe the functional to be optimized and the constraints comprising the problem as sums of functions of a single variable. The approach to solving the problem in question is to first replace the nonlinear problem by an approximating problem. In particular, the nonlinear functions in the problem are replaced by polygonal approximations. The approximating problem developed will offer from previous approximations in that it is a linear, mixed-integer problem. This approach will have the advantage that the solution of the problem is the global optimum of the approximating problem. Conversely, there is the disadvantage of involving integer programming problems has been disappointing for even problems of moderate size. However, this difficulty is resolved by the development of a specialized algorithm. After construction of the approximation problem, which in essence divides the solution space into a series of hypercubes, a particular problem is solved by simplex methods to yield the optimum for specified hypercube. The hypercube specified is determined by the choice of a [articular vector of zeroes and ones, called the u-vector, for there exists a one-to-one relationship between u-vectors and hypercubes &