(28h) Computation of Sensitivities of Dynamic Systems with Lexicographic Linear Programs Embedded

Gomez, J. A., Massachusetts Institute of Technology
Barton, P. I., Massachusetts Institute of Technology
Bioprocesses involving microbial communities have widespread applications in the pharmaceutical, food and biofuels industries. These complex bioprocesses can be modeled accurately using dynamic flux balance analysis (DFBA) [1], [2], [3], which combines genome-scale metabolic network reconstructions with dynamic process models. DFBA models result in dynamic systems with linear programs (LPs) embedded [4]. These LPs are embedded because their right-hand side depends on the dynamic states and the dynamic states depend on the solution vector of the LP. Newly available simulators [4], [5] have made the reliable and efficient implementation of DFBA possible. These simulators transform the LP embedded into a lexicographic LP (LLP) to address complications associated with nonunique and infeasible LP solutions, and they exploit basis information to reformulate these ordinary differential equation (ODE) systems with LPs embedded as differential-algebraic equation (DAE) systems. In order to use DFBA to design optimal bioprocesses involving microbial communities, sensitivity information is required. This paper presents the theory behind the computation of sensitivities for dynamic systems with LLPs embedded and their numerical implementation.

The objectives of a LLP in standard form as a function of its right-hand side are piecewise linear functions [6], and therefore, nonsmooth. This source of nonsmoothness can be propagated to the parametric dependence of the final states of the dynamic system. Therefore, there exist some parameter values for which the Jacobian of the dynamic system may not exist. Computing elements of Clarke’s generalized Jacobian for complex nonsmooth functions is challenging [7], but can be done efficiently for piecewise differentiable functions, such as LLPs parameterized by their right-hand side, with lexicographic-directional (LD) derivatives [8]. LD-derivatives of nonsmooth dynamic systems can be computed to obtain elements of the plenary hull of the generalized Jacobian [9] if the right-hand side of the ODE is abs-factorable, which means it can be factored as analytic and absolute value functions. This is the case for ODE systems with LLPs embedded; however, obtaining explicitly the abs-factorable representation of a large LLP is intractable. Therefore, an algorithm that relies on LLP basis information instead is presented. This algorithm enables the efficient computation of LD-derivatives of DFBA systems, which is critical for their systematic optimization.

This paper first introduces the ODE system whose solution gives the LD-derivatives of ODE systems with LLPs embedded. Next, some complications regarding the computation of these LD-derivatives are illustrated. Next, an algorithm that addresses these challenges is presented. Finally, the theory developed is implemented to optimize a DFBA case study. 



A. Varma and B. Ø. Palsson, "Stoichiometric flux balance models quantitatively predict growth and metabolic by-product secretion in wild-type Escherichia coli W3110," Applied and Environmental Microbiology, vol. 60, no. 10, pp. 3724-3731, 1994.


J. D. Orth, I. Thiele and B. Ø. Palsson, "What is flux balance analysis?," Nature Biotechnology, vol. 28, pp. 245-248, 2010.


R. Mahadevan, J. Edwards and F. I. Doyle, "Dynamic flux balance analysis of diauxic growth in Escherichia coli.," Biophysical Journal, vol. 83, no. 3, pp. 1331-40, 2002.


K. Höffner, S. M. Harwood and P. I. Barton, "A reliable simulator for dynamic flux balance analysis," Biotechnology and Bioengineering, vol. 110, no. 3, pp. 792-802, 2013.


J. A. Gomez, K. Höffner and P. I. Barton, "DFBAlab: A fast and reliable MATLAB code for Dynamic Flux Balance Analysis," BMC Bioinformatics, vol. 15, p. 409, 2014.


D. Bertsimas and J. N. Tsitsiklis, Introduction to Linear Optimization, Nashua, NH: Athena Scientific, 1997.


F. H. Clarke, Optimization and Nonsmooth Analysis, Philadelphia: Society for Industrial and Applied Mathematics, 1990.


K. A. Khan and P. Barton, "A vector forward mode of automatic differentiation for generalized derivative evaluation," Optimization Methods & Software, vol. 30, no. 6, pp. 1185-1212, 2015.


K. A. Khan and P. I. Barton, "Generalized Derivatives for Solutions of Parametric Ordinary Differential Equations with Non-differentiable Right-Hand Sides," Journal of Optimization Theory and Applications, vol. 163, no. 2, pp. 355-386, 2014.