Representation of the convex envelope of bilinear terms in a reformulation framework for global optimization

A1 Journal article (refereed)


Internal Authors/Editors


Publication Details

List of Authors: Andreas Lundell, Tapio Westerlund
Publication year: 2015
Journal: Computer Aided Chemical Engineering
Journal acronym: COMPUT-AIDED CHEM EN
Volume number: 37
Start page: 833
End page: 838
Number of pages: 6


Abstract

Branch-and-bound in combination with convex underestimators constitute the basis for many algorithms in global nonconvex mixed-integer nonlinear programming (MINLP). Another option is to rely on reformulation-based techniques such as the alpha signomial global optimization (alpha SGO) algorithm, where power and exponential transformations for signomial or polynomial function and the alpha reformulation (alpha R) technique for general nonconvex twice-differentiable functions are used to reformulate the nonconvex problem. The transformations are approximated using piecewise linear functions (PLFs), resulting in a convex relaxation of the original nonconvex problem in an extended variable space. The solution to this reformulated problem provides a lower bound to the global minimum (of a minimization problem), and by iteratively refining the PLFs, the epsilon-global solution can be obtained. A drawback with many reformulation-based techniques is that known convex envelopes cannot directly be utilized. However, in this paper, a formulation for expressing the convex envelope of bilinear terms in the alpha SGO framework is described, and it is shown that this improves the tightness of the lower bound.


Keywords

alpha R technique, alpha SGO algorithm, bilinear terms, convex envelope, MINLP, Nonconvex global optimization, reformulation framework, signomial functions

Last updated on 2019-19-06 at 04:43