Fachbereiche  

Buchreihen (76) 
1012

Geisteswissenschaften 
1921

Naturwissenschaften 
5024

Mathematik  211 
Informatik  278 
Physik  938 
Chemie  1271 
Geowissenschaften  119 
Humanmedizin  214 
Zahn, Mund und Kieferheilkunde  8 
Veterinärmedizin  78 
Pharmazie  138 
Biologie  780 
Biochemie, Molekularbiologie, Gentechnologie  105 
Biophysik  21 
Ernährungs und Haushaltswissenschaften  39 
Land und Agrarwissenschaften  946 
Forstwissenschaften  196 
Gartenbauwissenschaft  13 
Umweltforschung, Ökologie und Landespflege  126 
Ingenieurwissenschaften 
1508

Allgemein 
74

Leseprobe, PDF (120 KB)
Inhaltsverzeichnis, PDF (49 KB)
ISBN13 (Printausgabe)  9783954044740 
ISBN13 (EBook)  9783736944749 
Sprache  Englisch 
Seitenanzahl  252 
Umschlagkaschierung  matt 
Auflage  1. Aufl. 
Erscheinungsort  Göttingen 
Promotionsort  Zürich 
Erscheinungsdatum  16.09.2013 
Allgemeine Einordnung  Dissertation 
Fachbereiche 
Angewandte Mathematik

Schlagwörter  Convex ralaxations, convex envelope, MixedInteger Nonlinear Programs 
This thesis deals with new techniques to construct a strong convex relaxation for a mixedinteger nonlinear program (MINLP). While local optimization software can quickly identify promising operating points of MINLPs, the solution of the convex relaxation provides a global bound on the optimal value of the MINLP that can be used to evaluate the quality of the local solution. Certainly, the efficiency of this evaluation is strongly dependent on the quality of the convex relaxation.
Convex relaxations of general MINLPs can be constructed by replacing each nonlinear function occurring in the model description by convex underestimating and concave overestimating functions. In this setting, it is desired to use the best possible convex underestimator and concave overestimator of a given function over an underlying domain — the socalled convex and concave envelope, respectively. However, the computation of these envelopes can be extremely difficult so that analytical expressions for envelopes are only available for some classes of wellstructured functions.
Another factor influencing the strength of the estimators is the size of the underlying domain: The smaller the domain, the better the quality of the estimators. In many applications the initial domains of the variables are chosen rather conservatively while tighter bounds are implicitly given by the constraint set of the MINLP. Thus, bound tightening techniques, which exploit the information of the constraint set, are an essential ingredient to improve the estimators and to accelerate global optimization algorithms.
The focus of this thesis lies on the development and computational analysis of new convex relaxations for MINLPs, especially for two applications from chemical engineering. In detail, we derive a new bound tightening technique for a general structure used for modeling chemical processes and provide different approaches to generate strong convex relaxations for various nonlinear functions.
Initially, we aim at the optimal design of hybrid distillation/meltcrystallization processes, a novel process configuration to separate a m ixture into its component. A crucial part in the formal representation of this process as well as other separation processes is to model the mass conservation within the process. We exploit the analytical properties of the corresponding equation system to reduce the domains of the involved variables. Using the proposed technique, we can accelerate the computations for hybrid distillation/meltcrystallization processes significantly compared to standard software.
Then, we concentrate on the generation of convex relaxations for nonlinear functions. First, we exploit the existing theory for two interesting classes of bivariate functions. On the one hand, we elaborate, implement, and illustrate the strength of a cutgeneration algorithm for bivariate functions which are convex or concave in each variable and for which the sign of the Hessian is the same over the entire domain. On the other hand, relaxation strategies for advanced equilibrium functions in chromatographic separation processes are analyzed and finally applied to completely describe the feasible separation regions of these processes.
Second, we suggest to derive the envelopes in an extended space to overcome the combinatorial difficulties involved in the computation of the convex envelope in the original space. In particular, we consider a class of functions accounting for a large amount of all nonlinearities in common benchmark libraries. These functions are componentwise concave in one part of the variables and convex in the other part of the variables. For this general class of functions the convex envelopes in the original variable space have not been discovered so far. We provide closedform expressions for the extended formulation of their convex envelopes based on the simultaneous convexification with multilinear monomials. By construction, this approach does not only yield an extended formulation for the convex envelope of a function, but also a strong simultaneous relaxation of the function and the involved multilinear monomials. Several examples show that this simultaneous relaxation can be orders of magnitude better than the individual relaxation of the functions.
Finally, inspired by the strength and the computational impact of the simultaneous relaxation of a function and multilinear monomials, we further focus on the simultaneous convexification of several functions. In such an approach the relaxation of a MINLP involving several functions in the same variables is much tighter because the interdependence between the different functions is taken into account. We study the simultaneous convex hull of several functions for which we derive theoretical results concerning their inner and outer description by means of the rich theory of convex envelopes. Moreover, we apply these results to provide formulas for tight convex relaxations of several univariate convex functions.
Implementations of all convexification techniques are available as plugins for the opensource MINLP solver scip. The computational results of several case studies reveal the benefit of the proposed techniques compared to stateoftheart methods.