Decomposition methods for global optimization

The goal of this project is to create a general-purpose global optimization method (i) that finds all global optima of nonlinear optimization problems or all solutions to systems of nonlinear equations; (ii) such that the solutions are guaranteed to be correct even in presence of round-off errors; (iii) which can prove infeasibility; (iv) for which assuming that the Jacobian is sparse and the problem can be properly decomposed into smaller subproblems the computational costs scale polynomially with the number of subproblems and, in the worst-case, exponentially only with the size of the biggest subproblem. Numerical evidence suggests that linear time complexity is achievable for distillation columns, which are of major interest to this project. Global convergence will be guaranteed by using branch-and-bound and interval arithmetic. Interval arithmetic automatically encloses the round-off errors. Unlike in conventional iterative methods, proving infeasibility happens naturally in a branch-and-bound framework. A decomposition method will ensure that the computational costs scale well with the problem size (assuming a sparse Jacobian with appropriate structure). In chemical engineering, perhaps the first published decomposition method for reducing the computational work is the famous stage-by-stage method from the 1930s: The high-dimensional steady-state model is decomposed and a sequence of low-dimensional subproblems is solved instead. This idea of decomposition was later extended and became known as partitioning, precedence ordering and tearing. Unfortunately, the decomposed system can be extremely sensitive to the initial estimates, so that solving it can be notoriously difficult or even impossible. The sensitivity issues were never satisfactorily resolved. Tearing resembles tree decomposition; the main difference is that tearing is adapted to continuous problems whereas tree decomposition is suited for discrete optimization and constraint satisfaction problems (CSPs). Tree decomposition is quite popular in other fields of science since the discrete case is inherently free of those sensitivity issues that are characteristic of tearing. The most recent results of our group put us on the verge of a breakthrough: We have discovered that the sensitivity issues of the tearing method (unsolved since the 1930s despite the enormous amount of research that went into it) can be resolved; it is possible to adapt tree decomposition to continuous nonlinear problems as well. The proof of concept implementation of the novel method finds all solutions to challenging chemical engineering problems without any assistance from the user and without any initial estimates. Branch-and- bound or interval methods have not been integrated into our proof of concept implementation yet. Within this project, we would like to advance the state of our methods from the first results are very promising to generic algorithms that are stable and efficient.

Global optimization is the task of finding the absolutely best choice of values for a set of problem variables, so that predefined relations between the chosen values are respected. The quality of the choice is thereby measured by the values of the so-called objective function, and the relations between the variables are mathematically modeled using equations and inequalities, the so-called constraints. Objective function and constraints together define a global optimization problem. Such problems have a multitude of applications in technology, science, and economics. If the objective function is constant, i.e. the values of all possible choices are equal, then the main task is to find any combination of variable values that satisfies all constraints. In that case, the objective function is redundant, and we call the problem a constraint satisfaction problem. In general, global optimization and constraint satisfaction problems are extremely difficult to solve, especially if the dimension the number of variables is high. In the course of this project we have taken important steps towards a solution method for global optimization problems that provably finds all global optima of a nonlinear optimization problem, or all solutions of a nonlinear constraint satisfaction problem, even in the presence of roundoff errors. What is special about the methods developed in this project is the decomposition of the problem into weakly interconnected small subproblems if the problem structure permits such a decomposition so that the solution algorithm will need a significantly smaller computational effort compared to algorithms that tackle the whole problem. In chemical engineering decomposition methods are known since the 1930s, in general under the name tearing. However, in higher dimensions the problems get numerically very unstable if they are decomposed into a tree structure, and those sensitivity issues were virtually unsolved before this project. The methods developed here permit to overcome these numerical difficulties and to solve high dimensional equilibrium problems very efficiently. We have developed a special algorithm for such problems, and the decomposition methods have been integrated into Gloptlab, one of the software platforms for global optimization developed in our research group.