A reformulation framework for global optimization

A1 Originalartikel i en vetenskaplig tidskrift (referentgranskad)


Interna författare/redaktörer


Publikationens författare: Andreas Lundell, Anders Skjäl, Tapio Westerlund
Förläggare: Springer
Publiceringsår: 2013
Tidskrift: Journal of Global Optimization
Volym: 57
Nummer: 1
Artikelns första sida, sidnummer: 115
Artikelns sista sida, sidnummer: 141


Abstrakt

In this paper, we present a global optimization method for solving nonconvex mixed integer nonlinear programming (MINLP) problems. A convex overestimation of the feasible region is obtained by replacing the nonconvex constraint functions with convex underestimators. For signomial functions single-variable power and exponential transformations are used to obtain the convex underestimators. For more general nonconvex functions two versions of the so-called αBB-underestimator, valid for twice-differentiable functions, are integrated in the actual reformulation framework. However, in contrast to what is done in branch-and-bound type algorithms, no direct branching is performed in the actual algorithm. Instead a piecewise convex reformulation is used to convexify the entire problem in an extended variable-space, and the reformulated problem is then solved by a convex MINLP solver. As the piecewise linear approximations are made finer, the solution to the convexified and overestimated problem will form a converging sequence towards a global optimal solution. The result is an easily-implementable algorithm for solving a very general class of optimization problems.

Senast uppdaterad 2019-06-12 vid 05:37