Global optimization algorithms for semi-infinite and generalized semi-infinite programs

The 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.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Chemical Engineering.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2008

Author dc:creator

• Lemonidis, Panayiotis

Advisor dc:contributor.advisor

• Paul I. Barton and William H. Green, Jr.

• Chemical Engineering.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/43200

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/43200