Structure-driven methods for large-scale optimization

http://www.mat.univie.ac.at/~neum/structure.html


Project goals

This project aims at the reliable solution of large-scale optimization problems with multiple solutions, coming from chemical engineering. This includes continuous constraint satisfaction problems (nonlinear systems of equations with additional inequality constraints), as these are typically solved by optimization techniques.

Note that the techniques are expected to transfer without difficulties to other large-scale optimization problems.

This project is funded by a grant of the Austrian Science Fund FWF under contract number P23554.

A wide variety of chemical engineering problems give rise to optimization problems or continuous constraint satisfaction problems that may have multiple solutions:

  • analyzing distillation columns;
  • computation of fluid phase equilibrium from activity coefficient models and cubic equation-of-state models;
  • modeling liquid-liquid equilibrium of ionic liquid systems;
  • computation of solid-liquid equilibrium;
  • location of homogeneous azeotropes and reactive azeotropes;
  • calculation of critical points from cubic equation-of-state models;
  • parameter estimation using standard least squares and error-in-variables (EIV) approach;
  • global optimization of molecular structures;
  • computing high-pressure chemical and multiphase equilibrium;
  • process simulation;
  • automated controller synthesis in quantitative feedback theory.


    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:

  • Ensemble methods for stage-by-stage calculations;
  • Branch and bound methods using interval techniques, in particular affine arithmetic and linear or quadratic relaxations.


    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.


    my home page (http://www.mat.univie.ac.at/~neum/)

    Arnold Neumaier (Arnold.Neumaier@univie.ac.at)