Global Optimization Algorithms for Semi-infinite and Generalized Semi-infinite Programs
Author: Panayiotis Lemonidis
Publisher:
Published: 2008
Total Pages: 249
ISBN-13:
DOWNLOAD EBOOKThe goals of this thesis are the development of global optimization algorithms for semi-infinite and generalized semi-infinite programs and the application of these algorithms to kinetic model reduction. The outstanding issue with semi-infinite programming (SIP) was a methodology that could provide a certificate of global optimality on finite termination for SIP with nonconvex functions participating. We have developed the first methodology that can generate guaranteed feasible points for SIP and provide e-global optimality on finite termination. The algorithm has been implemented in a branch-and-bound (B & B) framework and uses discretization coupled with convexification for the lower bounding problem and the interval constrained reformulation for the upper bounding problem. Within the framework of SIP we have also proposed a number of feasible-point methods that all rely on the same basic principle; the relaxation of the lower-level problem causes a restriction of the outer problem and vice versa. All these methodologies were tested using the Watson test set. It was concluded that the concave overestimation of the SIP constraint using McCormcick relaxations and a KKT treatment of the resulting expression is the most computationally expensive method but provides tighter bounds than the interval constrained reformulation or a concave overestimator of the SIP constraint followed by linearization. All methods can work very efficiently for small problems (1-3 parameters) but suffer from the drawback that in order to converge to the global solution value the parameter set needs to subdivided. Therefore, for problems with more than 4 parameters, intractable subproblems arise very high in the B & B tree and render global solution of the whole problem infeasible.
