April 25, 2014 Post doc researchers

In global optimization, i.e., when trying to find the global optimal solution to an optimization problem subject to certain constraints, nonlinear functions often lead to nonconvex problems. These types of problems have the property that they may have local solutions which are not globally optimal, and hence, it is usually not possible to say whether a solution found actually is the best one. Thus, special techniques are required for solving nonconvex problems.

We have especially considered global optimization of mixed integer nonlinear programming (MINLP) problems containing signomial functions, so called mixed integer signomial programming (MISP) problems. Signomial functions are defined as sums of positive or negative signomial terms, where each term is a product of a number of single-variable power functions. Since, signomial functions are generally highly nonlinear and nonconvex, solving such optimization problems is a difficult and time-consuming task.

The method we have developed for solving MISP problems – the signomial global optimization (SGO) algorithm – can be used to solve any MINLP problems where the only nonconvexities are the signomial functions. In the algorithm, convex underestimators for the signomials are obtained term-wise by applying single-variable power or exponential transformations x = T(X) to the individual variables in the nonconvex terms. After this, the convexified terms are underestimated by approximating the relationship between the introduced transformation variables X and the original variables x with piecewise linear functions (PLFs). This results in a convex overestimated problem, which can be solved using any convex MINLP solver. Since only the part of the problem involving the nonconvex signomial functions is altered, the result is a flexible technique for transforming the problem to a convex overestimated form.

The transformations can be selected in many different ways, and therefore, we have developed an automatic method for selecting an optimized set of transformations for convexifying the problem. This is done by solving a mixed integer linear programming (MILP) problem. The MILP method is included in the preprocessing stage of the SGO algorithm.

After the transformations have been obtained, the convexified and overestimated problem is solved iteratively using any MINLP solver. In each iteration, additional breakpoints are added to the PLFs, and thus, the solution of the overestimated problem will, under certain conditions, converge to that of the original nonconvex problem.