Structure-driven methods for large-scale optimization

Because of the possibility of multiple solutions, these problems are computationally troublesome, hence the need for reliable methods. Current solver technology only covers problems that are small-scale, having less than about one hundred variables.

The goal of the project is to extend these methods to work reliably in higher dimensions, by exploiting the problem structure.

We are pursuing primarily two different approaches:

In each case, exploiting the connectivity structure of the variables and equations plays a crucial role in improving the efficiency in the large-scale case.

Papers and Preprints

A. Baharev, F. Domes and A. Neumaier,
Sampling solutions of sparse nonlinear systems, Submitted, 2015, supplementary material, including source code

The algorithm proposed in the present paper aims at robustly sampling from a manifold implicitly defined by an underdetermined system of equations and bound constraints on the $n$ variables. A representative sample of the solution manifold of the input system can have several uses. For example, the sample can be used to generate starting points for solving arbitrary systems obtained by augmenting the original underdetermined system by further equations such that the system becomes well-defined. The sample is also useful for the robust computation of bifurcation diagrams. Direct sampling of the manifold means sampling in a very thin subset of $\mathbb{R}^n$, with a typical work that grows exponentially with $n$. Therefore, we first decompose the input problem into a well-chosen sequence of lower-dimensional subsystems. The proposed algorithm then only samples the solution set of these subsystems in order. This leads to substantial computational savings because the work grows exponentially only with the largest subproblem size, which is usually significantly smaller than $n$. The robustness of the method is demonstrated on numerically challenging steady-state models of distillation columns where even problem-specific methods were reported to miss one solution. When started from the sample points generated by the proposed method, a general-purpose gradient-based solver finds all solutions to these steady-state models without problem-specific assumptions. There is no theoretical guarantee that all solutions will be found in the general case, although, increasing the sample size is expected to improve robustness.

A. Baharev and A. Neumaier,
A globally convergent method for finding all steady-state solutions of distillation columns, AIChE Journal, 2014, 60 (2), 410-414 DOI,
supplementary material, including source code

A globally convergent method is proposed that either returns all solutions to steady-state models of distillation columns or proves their infeasibility. Initial estimates are not required. The method requires a specific but fairly general block-sparsity pattern; in return, the computational efforts grow linearly with the number of stages in the column. The well-known stage-by-stage (and the sequential modular) approach also reduces the task of solving high-dimensional steady-state models to that of solving a sequence of low-dimensional ones. Unfortunately, these low-dimensional systems are extremely sensitive to the initial estimates, so that solving them can be notoriously difficult or even impossible. The proposed algorithm overcomes these numerical difficulties by a new reparameterization technique. The successful solution of a numerically challenging reactive distillation column with seven steady-states shows the robustness of the method. No published software known to the authors could compute all solutions to this difficult model without expert tuning.

A. Baharev, K. Kofler, and A. Neumaier.
Steady-state chemical process models — a structural point of view, 2013. Draft of a technical report, 57 pages.

A. Baharev and A. Neumaier,
Chemical Process Modeling in Modelica, Proceedings of the 9th International Modelica Conference, pages 955--962. Munich, Germany; Sep 3-5, 2012, DOI
One-page abstract
supplementary material, including source code

Chemical process models are highly structured. Information on how the hierarchical components are connected helps to solve the model efficiently. The structural information retrieved from the JModelica environment will play an important role in the development of our novel optimization methods.
Foundations of a Modelica library for general-purpose chemical process modeling have been built. Multiple steady-states in ideal two-product distillation were computed as a proof of concept. The Modelica source code is available at the project homepage. The issues encountered during modeling may be valuable to the Modelica language designers.