Primal-relaxed dual global optimization approach

A deterministic global optimization approach is proposed for nonconvex constrained nonlinear programming problems. Partitioning of the variables, along with the introduction of transformation variables, if necessary, converts the original problem into primal and relaxed dual subproblems that provide valid upper and lower bounds respectively on the global optimum. Theoretical properties are presented which allow for a rigorous solution of the relaxed dual problem. Proofs of -finite convergence and -global optimality are provided. The approach is shown to be particularly suited to (a) quadratic programming problems, (b) quadratically constrained problems, and (c) unconstrained and constrained optimization of polynomial and rational polynomial functions. The theoretical approach is illustrated through a few example problems. Finally, some further developments in the approach are briefly discussed.The authors gratefully acknowledge financial support from National Science Foundation Presidential Young Investigator Award CBT-88-57013. The authors are also grateful to Drs. F. A. Al-Khayyal, B. Jaumard, P. M. Pardalos, and H. D. Sherali for helpful comments on an earlier draft of this paper.