(359f) Decomposition of Optimization Problems Using Community Detection and Its Application in Nonlinear Model Predictive Control

For the nonlinear model predictive control of large-scale and complex process systems, centralized optimization can be computationally challenging. Decomposition is an important class of techniques to deal with problems on large scales, where the entire system is partitioned into multiple non- or weakly interacting sub-problems which can be solved with significantly reduced complexity. For nonlinear model predictive control, the complexity can be reduced with

• A decomposition on the level of linear algebra (see e.g. [1]) – The matrices involved in the optimization algorithm can be large but sparse and structured (tri-diagonal). This special structure can be utilized to decompose and parallelize the matrix inversion operations.
• A decomposition on the level of plant flowsheet (see e.g. [2]) – By analyzing the interactions between the process variables, the plant can be decomposed into distributed subsystems. Distributed model predictive controllers are assigned to the corresponding subsystems and make control decisions in a coordinated way through communication.

In this work, we seek a decomposition of the optimal control problems directly on the level of optimization formulations. This is inspired by the recent development of distributed optimization in machine learning (see e.g. [3]), which allows one to partition the monolithic optimization problem into smaller optimization problems.

Specifically, we represent optimization problems as bipartite networks, whose nodes represent the optimization variables and constraints, and edges capture the variable-constraint interactions. Community detection algorithms in network science, which aim to partition the nodes into groups with the largest statistical difference between intra- and inter-group interactions, are employed to generate the most suitable decomposition of optimization problems. For the optimal control problem of a benchmark reactor-separator process, the decompositions are examined with two different optimization algorithms – alternating direction method of multipliers (ADMM) [3], and a decomposed version of IPOPT algorithm [5]. Significant improvement in the computational performance of nonlinear model predictive control is observed.

References:

[1] Wan, W., Eason, J. P., Nicholson, B., & Biegler, L. T. (2017). Parallel cyclic reduction decomposition for dynamic optimization problems. Comput. Chem. Eng., in press.

[2] Daoutidis, P., Tang, W., & Jogwar, S. S. (2017). Decomposing complex plants for distributed control: Perspectives from network theory. Comput. Chem. Eng., in press.

[3] Boyd, S., et al. (2011). Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn., 3(1), 1-122.

[4] Fortunato, S., & Hric, D. (2016). Community detection in networks: A user guide. Phys. Rep., 659, 1-44.

[5] Wächter, A., & Biegler, L. T. (2006). On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Prog., 106(1), 25-57.