417309 Generalized Derivatives of Dynamic Systems with Lexicographic Linear Programs Embedded

Tuesday, November 10, 2015: 12:30 PM
Salon D (Salt Lake Marriott Downtown at City Creek)
Jose A. Gomez, Kai Höffner, Kamil A. Khan and Paul I. Barton, Process Systems Engineering Laboratory, Massachusetts Institute of Technology, Cambridge, MA

Bioprocesses involving microbial communities have widespread applications in the pharmaceutical, food and biofuels industries. Despite the complexity of these systems, their modeling relies heavily on unstructured models, which are inaccurate when modeling systems involving cyclic steady states, symbiotic and competitive relationships, and multiple nutrient limitations. These shortcomings can be addressed by dynamic flux balance analysis (DFBA) [1], [2], which combines genome-scale metabolic network reconstructions with dynamic process models to model accurately the behavior of bioprocesses involving microbial communities. DFBA models result in dynamic systems with linear programs (LPs) embedded [3]. 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. Until recently, the simulation of DFBA systems was challenging, but newly available simulators [3], [4] 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. In order to use DFBA to design optimal bioprocesses involving microbial communities, sensitivity information needs to be computed. Therefore, this paper presents the theory behind the computation of sensitivities for dynamic systems with LLPs embedded.

The objectives of a LLP in standard form as a function of its right-hand side are piecewise linear functions [5], 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 [6], but can be done efficiently for piecewise differentiable functions, such as LLPs parameterized by their right-hand side, with lexicographic-directional (LD) derivatives [7]. LD-derivatives of dynamic systems can be computed efficiently to obtain elements of the plenary hull of the generalized Jacobian, and in some instances, elements of the generalized Jacobian [8]. This information can be provided to bundle methods to optimize DFBA systems.

This paper derives first the LD-derivatives of LLPs, which are shown to be obtained by solving related LLPs. Next, LD-derivatives of dynamic systems with LLPs embedded are computed using event detection to integrate efficiently the sensitivity ODEs, which can have discontinuous right-hand sides. Finally, the theory developed is implemented to optimize a DFBA case study.

Keywords: Linear programming, generalized Jacobian, lexicographic differentiation, LD-derivative, lexicographic optimization, nonsmooth sensitivities, nonsmooth equation solving, flux balance analysis, dynamic flux balance analysis.



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, p. In Press., 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.

Extended Abstract: File Not Uploaded
See more of this Session: Dynamic Simulation and Optimization I
See more of this Group/Topical: Computing and Systems Technology Division