This dissertation is concerned with the global optimization of polynomial programming problems, and a detailed treatment of its particular special case, the indefinite quadratic programming problem. Polynomial programming problems are generally nonconvex, involving the optimization of a polynomial objective function over a compact feasible region defined in terms of polynomial constraints. These problems arise in a variety of applications in the context of engineering design and chemical process design situations.; We present a branch and bound algorithm that uses a Reformulation Linearization Technique (RLT) to generate tight linear programming relaxations. This bounding scheme involves an automatic reformulation of the problem via the addition of certain nonlinear implied constraints that are generated by using the products of the simple bounding restrictions and, optionally, products involving the structural constraints. Subsequently, in a linearization phase, each distinct nonlinear term in the resulting problem is replaced by a new variable to obtain a linear program. The underlying purpose of this procedure is to closely approximate the convex envelope of the objective function over the convex hull of the feasible region. Various implementation issues regarding the derivation of such a bounding problem using the RLT, and the dominance of such bounds over existing alternative schemes, are investigated, both theoretically and computationally. The principal thrust of the proposed method is to construct a tight linear programming relaxation of the problem via an appropriate RLT procedure, and to use this in concert with a suitable partitioning strategy, in order to derive a practically effective algorithm that is theoretically guaranteed to be globally convergent.; This approach is also specialized and further enhanced for the particular class of indefinite (and concave) quadratic programming problems. These problems are important in their own right, and arise in many applications such as in modelling economies of scale in a cost structure, in location-allocation problems, several production planning and risk management problems, and in various other mathematical models such as the maximum clique problem and the jointly constrained bilinear programming problem. Computational results are presented on a set of test problems from the literature to demonstrate the efficiency of the approach. (One of these test problems had not previously been solved to optimality.) It is shown that for many problems, including randomly generated problems having up to 50 variables, the initial relaxation itself produces an optimal or a near optimal solution. This is significant in that the proposed methodology affords an approach whereby such hard nonconvex problems can be practically solved via a single or a few higher dimensional linear programming problems. (Abstract shortened by UMI.)
展开▼
