Decomposition methods
for global optimization

Aims and scope

The goal of this project is to create a general-purpose global optimization method

  1. that finds all global optima of nonlinear optimization problems or all solutions to systems of nonlinear equations;
  2. such that the solutions are guaranteed to be correct even in presence of round-off errors;
  3. which can prove infeasibility;
  4. 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).

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

Keywords: optimization, numerical methods, decomposition methods, sparse matrix ordering , interval arithmetic, chemical process flowsheeting

Papers

  1. A. Baharev, A. Neumaier, H. Schichl. A manifold-based approach to sparse global constraint satisfaction problems. Journal of Global Optimization, 2019, 75, 949-971 (DOI; open access, BibTeX, GitHub repo)
  2. A. Baharev, A. Neumaier, H. Schichl. Failure modes of tearing and a novel robust approach. Proceedings of the 12th International Modelica Conference, pages 353-362. Prague, Czech Republic. May 15-17, 2017. (DOI; open access, BibTeX)
  3. A. Baharev, F. Domes, A. Neumaier. A robust approach for finding all well-separated solutions of sparse systems of nonlinear equations. Numerical Algorithms, 2017, 76, 163-189 (DOI; open access; online supplement, BibTeX)
  4. A. Baharev, H. Schichl, A. Neumaier, T. Achterberg. An exact method for the minimum feedback arc set problem. (submitted)
  5. A. Baharev, H. Schichl, A. Neumaier. Decomposition methods for solving sparse nonlinear systems of equations. (submitted)
  6. A. Baharev, H. Schichl, A. Neumaier. Ordering matrices to bordered lower triangular form with minimal border width. (submitted)
  7. A. Baharev, H. Schichl, E. Rév. Computing the noncentral-F distribution and the power of the F-test with guaranteed accuracy. Computational Statistics, 2017, 32, 763-779 (DOI; open access, BibTeX)

Presentations

  1. A. Baharev, H. Schichl, A. Neumaier. Decomposition methods for chemical process models. Technische Universität Berlin, Institut für Prozess- und Verfahrenstechnik, Fachgebiet Dynamik und Betrieb technischer Anlagen, Germany. October 4, 2018.
  2. A. Baharev, A. Neumaier, H. Schichl. Failure modes of tearing and a novel robust approach. Presentation at the 12th International Modelica Conference. Prague, Czech Republic. May 15-17, 2017.
    (jump to the peer-reviewed paper in the conference proceedings)
  3. A. Baharev, H. Schichl, A. Neumaier. Decomposition methods for technical systems. Lund University, Centre for Mathematical Sciences, Sweden. June 15, 2016.
  4. A. Baharev, H. Schichl, A. Neumaier. Optimal tearing. Zuse Institute Berlin (ZIB), Germany. May 2, 2016.