Construction of Convex Relaxations Using Automated Code Generation Techniques

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 aBB and the method of McCormick.