The primary objective of this thesis is to develop and implement a global optimization algorithm to solve a class of nonconvex programming problems, and to test it using a collection of engineering design problem applications.The class of problems we consider involves the optimization of a general nonconvex factorable objective function over a feasible region that is restricted by a set of constraints, each of which is defined in terms of nonconvex factorable functions. Such problems find widespread applications in production planning, location and allocation, chemical process design and control, VLSI chip design, and numerous engineering design problems. This thesis offers a first comprehensive methodological development and implementation for determining a global optimal solution to such factorable programming problems. To solve this class of problems, we propose a branch-and-bound approach based on linear programming (LP) relaxations generated through various approximation schemes that utilize, for example, the Mean-Value Theorem and Chebyshev interpolation polynomials, coordinated with a {em Reformulation-Linearization Technique} (RLT). The initial stage of the lower bounding step generates a tight, nonconvex polynomial programming relaxation for the given problem. Subsequently, an LP relaxation is constructed for the resulting polynomial program via a suitable RLT procedure. The underlying motivation for these two steps is to generate a tight outer approximation of the convex envelope of the objective function over the convex hull of the feasible region. The bounding step is thenintegrated into a general branch-and-bound framework. The construction of the bounding polynomials and the node partitioning schemes are specially designed so that the gaps resulting from these two levels of approximations approach zero in the limit, thereby ensuring convergence to a global optimum. Various implementation issues regarding the formulation of such tight bounding problems using both polynomial approximations and RLT constructs are discussed. Different practical strategies and guidelines relating to the design of the algorithm are presented within a general theoretical framework so that users can customize a suitable approach that takes advantage of any inherent special structures that their problems might possess. The algorithm is implemented in C++, an object-oriented programming language. The class modules developed for the software perform various functions that are useful not only for the proposed algorithm, but that can be readily extended and incorporated into other RLT based applications as well. Computational results are reported on a set of fifteen engineering process control and design test problems from various sources in the literature. It is shown that, for all the test problems, a very competitive computational performance is obtained. In most cases, the LP solution obtained for the initial node itself provides a very tight lower bound. Furthermore, for nine of these fifteen problems, the application of a local search heuristic based on initializing the nonlinear programming solver MINOS at the node zero LP solution produced the actual global optimum. Moreover, in finding a global optimum, our algorithm discovered better solutions than the ones previously reported in the literature for two of these test instances. / Master of Science
| Identifer | oai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/36823 |
| Date | 12 June 1998 |
| Creators | Wang, Hongjie |
| Contributors | Industrial and Systems Engineering, Sherali, Hanif D., Sarin, Subhash C., Nachlas, Joel A. |
| Publisher | Virginia Tech |
| Source Sets | Virginia Tech Theses and Dissertation |
| Detected Language | English |
| Type | Thesis |
| Format | application/pdf |
| Rights | In Copyright, http://rightsstatements.org/vocab/InC/1.0/ |
| Relation | wang.pdf |
Page generated in 0.002 seconds