Construction of Convex Relaxations Using Automated Code Generation Techniques

TitleConstruction of Convex Relaxations Using Automated Code Generation Techniques
Publication TypeJournal Article
Year of Publication2002
AuthorsGatzke EP, Tolsma JE, Barton PI
JournalOptimization and Engineering
Keywordsautomatic code generation, convex relaxation, DAEPACK, global optimization

This paper describes how the automated code generation tool {DAEPACK} can be used to construct convex relaxations of codes implementing nonconvex functions. Modern deterministic global optimization algorithms involving continuous and/or integer variables often require such convex relaxations. Within the described framework, the user supplies a code implementing the objective and constraints of a nonconvex optimization problem. {DAEPACK} then analyzes this code and automatically generates a collection of subroutines based upon various symbolic transformations used by automatic convexification algorithms. The methods considered include the convex relaxations of McCormick, {$\alpha$BB} of Floudas and coworkers, and the linearization strategy of Tawarmalani and Sahinidis. It should be noted that the user supplied code can be quite complex, including arbitrary nonlinear expressions, subroutines, and iterative loops. The code generation approach has the advantage that it can be applied to general, legacy models coded in programming languages such as {FORTRAN}. It also provides a generic symbolic transformation service for researchers interested in developing new global optimization algorithms. Numerical results are presented, including a study of how these techniques can be used to generate convex relaxations based on a hybridization of {$\alpha$BB} and the method of McCormick.