Structure driven methods for large-scale optimization

The aim of this project is to elaborate novel global optimization methods for solving real-life, large-scale chemical engineering problems. In order to address the special challenges of the large-scale problems, consistency techniques, splitting strategies and decomposition methods will be developed that exploit the structure of the problem. The newly researched structure-driven algorithms will be integrated into the GloptLab framework and extensively tested in it. GloptLab is a state of the art platform for rigorous global optimization, developed between 2007 and 2010 at the University of Vienna. Even professional simulation software packages are inherently incapable of enumerating all solutions to a given mathematical model. However, finding all solutions is critical to proper design, simulation, control and operation of equipments used in the chemical industry. Branch-and-prune methods are guaranteed to find all solutions. This guarantee comes at a certain expense. Branch-and-prune methods tend to require drastically increasing computational efforts as the number of variables increases. A vast number of engineering problems are large-scale problems, having several hundred or thousand variables. The problem size is not necessarily a good measure of the intrinsic difficulty of a problem. Still, the major source of difficulties in solving certain engineering problems seems to be the size of the problem. Interval arithmetic based branch-and-prune methods have been successfully applied to a wide variety of chemical engineering problems. Apart from some exceptions, the problems are small-scale, having less than one hundred variables. Recently, one of us published a novel structure-driven algorithm for solving certain large-scale chemical engineering problems. Based on this numerical evidence and others published in the literature, we are convinced that many large-scale engineering problems fall into a tractable problem class. These preliminary results will be completed, and then generalized during the project. Tractable problem classes can be identified as a result. The practical significance is evident. We combine the knowledge of applied mathematicians with the expertise of engineers to increase the efficiency of our algorithms. Enhancing and combining two promising and already existing solvers, one written from the engineer`s point of view (ASOL), the other from the mathematician`s (GloptLab), builds a bridge between theory and application. Since global optimization is a very active field of research (powered by the wide spectrum of applications) researchers will greatly benefit from the new methods developed during the project.

Most engineering processes are highly nonlinear. Therefore, the need for solving systems of nonlinear equations, and for optimizing parameters in such a system, often arises in the everyday practice of engineering. Finding all solutions, proving uniqueness of a solution, or proving that the best solution was found typically requires a complicated case study. Worse, such a study often fails, due to nonconvergence of the solver from poor starting points, due to the inability of the solver to recognize that not yet all solutions were found, or due to convergence to nonglobal minimizers only. The goal of the research project was to improve the overall efficiency of algorithms designed to find all solutions, so that they finish in reasonable time for problems of previously untractable size. The target application was the computation of multiple steady states in distillation columns, where finding all solutions is an important part of the design cycle. (This is of highly practical importance, as in a typical chemical plant, 40-80% of the investment is spent on distillation equipment.) These problems are highly structured, and structure exploitation to achieve the needed improvement in the solution methods was the declared main goal of the project. We introduced an efficient method for globally solving large constrained systems of equations representing the steady state of highly difficult distillation problems. Our new method is the first one that fixes the flaws of the so-called stage-by-stage method, well known since the 1930's, without giving up the stage-by-stage-principle. The advance is due to a new structural analysis of the equations and a new way to exploit the structure by a sequence of local variable transformations. We also improved our global optimization package GloptLab so that it is more efficient in solving structured global optimization problems. GloptLab uses the branch-and-prune paradigm to search for the global minimizer of a constrained optimization problem by successively shrinking (pruning) the domain where the best solution can lie. Powerful new pruning procedured were discovered and implemented. They take into account structural information about the problem. They are particularly effective in pruning the search space close to the best solution, where traditional techniques are very inefficient. An innovative method based on projective geometry is used to handle many problems with an unbounded domain that were untractable before.