Convex relaxations and convex envelopes for deterministic global optimization.

摘要

Deterministic global optimization algorithms based on convex relaxations are powerful methods for nonconvex nonlinear programming (NLP) and mixed integer nonlinear programming (MINLP) chemical engineering problems.; This dissertation examines the convex underestimation of the following classes of functions: (a) Twice continuously differentiable functions over hyperrectangles. The αBB approach to the convex underestimation of such functions is based on Hessian eigenvalue bound estimates and a quadratic perturbation function. A tighter underestimation scheme that extends this idea is proposed in which smooth convex underestimators are constructed using spline-like piecewise quadratic perturbation functions. (b)  Trilinear monomials over hyperrectangles. Formulae for the facets of the convex envelope of trilinear monomials over a hyperrectangle are derived. It is shown that the convex envelope may be substantially tighter than commonly used underestimation schemes. (c) Edge-concave functions over hyperrectangles. An algorithm for computing the facets of the vertex polyhedral convex envelopes of such functions in $R3$ is described. Conditions are derived under which a sum of convex envelopes is equivalent to the convex envelope of a sum.; Convex-relaxation-based global optimization algorithms for the following classes of non-convex optimization problems are explored: (a)  NLP's with nonfactorable constraints. A novel approach is proposed for the global optimization of constrained nonlinear programming problems in which some of the constraints are defined by a computational model. A two phase approach is considered in which the nonfactorable functions are first sampled and an interpolation function constructed, then the interpolants are used as surrogates in a deterministic global optimization algorithm. The form of the interpolants enables valid over- and under-estimation functions to be constructed. (b) MINLP's with convex continuous relaxations . A branch and cut algorithm for the solution of mixed integer nonlinear programming problems with convex continuous relaxations is proposed. A disjunctive programming approach is developed for the generation of valid cutting planes. (c) Large-scale nonconvex, MINLP's with bilinear nonconvexities . Global optimization approaches are proposed for a generalized pooling problem involving the minimization of wastewater treatment costs under environmental constraints. Several formulations of a lower bounding problem are described, based on convex envelopes, the Reformulation Linearization Technique, and a piecewise linear underestimation approach.