2011 Annual Meeting

(135e) Tight LP Relaxations for Optimization Problems with Nonlinear Parametric ODEs

Author

Benoit Chachuat - Presenter, Imperial College London


The ability to compute tight enclosures for the solutions of nonlinear, parametric ordinary differential equations (ODEs) such as
$\displaystyle \dot{\bf x}(t) = {\bf f}(t, {\bf x}(t), {\bf p}), \quad {\bf x}(t_0)={\bf h}({\bf p}), \quad {\bf p}\in P \subset \mathbb{R}^{n_p},$ (1)

is central to deterministic global optimization methods for nonconvex dynamic optimization. These enclosures are needed to compute lower or upper bounds for general functionals such as

$\displaystyle \EuScript{F}({\bf p}) = \phi({\bf x}(t_{\rm f}),{\bf p}) + \int_{t_0}^{t_{\rm f}} \psi({\bf x}(t),{\bf p}) dt,$    

which in turn can be exploited by branch-and-bound algorithms and their variants. Other related applications are in the field of mixed-integer dynamic optimization (MIDO) and bilevel dynamic optimization.

Two main classes of methods have been reported in the literature to construct the desired convex/concave relaxations. The first class proceeds by constructing an auxiliary system of ODEs, the solutions of which describe convex/concave functions [2,1] with respect to the parameters p, pointwise in the integration variable t. The second class builds upon verified solution methods for ODEs [3,4], whereby the integration domain is discretized into a finite number of steps, and it was shown in [5,6] how convex/concave bounds can be propagated at each step via a two-phase mechanism that uses high-order Taylor series expansion: compute an a priori enclosure of the solutions over the current integration step in the first phase; then, obtain convex/concave bounds on the solutions at the end of the current step in the second phase.

The aforementioned methods rely on the ability to propagate convex/concave bounds for factorable functions, e.g., using the McCormick technique [7]. This technique is appealing in that it does not require the introduction of auxiliary variables, yet it comes with two important limitations: (i) the resulting relaxations are typically nonsmooth; and (ii) the relaxation procedure has to be applied multiple times in order to obtain convex/concave bounds at multiple parameter values p in P. While both deficiencies can be addressed by deriving affine relaxations from subgradient information [8], this leads to weaker relaxations.

In deterministic global optimization of nonconvex NLP, much emphasis has been on the construction of LP relaxations, which provide lower/upper bounds on the global solution value both reliably and efficiently using state-of-the-art LP technology [9]. Following similar ideas, this paper presents a general approach for constructing LP relaxations for the solutions of the parametric ODEs (1). The proposed algorithm builds upon two-phase methods for verified ODE solution and is rigorous in its accounting of truncation errors. The first phase remains unchanged and determines both a finite integration step and an a priori enclosure of the ODE solutions over that step. In the second phase, in addition to propagating interval bounds for the ODE solutions at the end of the current step, affine cuts that enclose these solutions are appended to an LP relaxation model. A variant in which Taylor models are propagated in lieu of interval bounds is also considered. Both approaches have been implemented in C++ using an object-oriented approach and operator overloading. The resulting LP relaxations are illustrated by way of numerical examples, and comparisons with other relaxations methods for parametric ODEs are made to demonstrate their efficiency.

Bibliography

1.&nbsp&nbsp
A. B. Singer and P. I. Barton. Bounding the solutions of parameter dependent nonlinear ordinary differential equations. SIAM J Sci Comput, 27(6):2167-2182, 2006.
2.&nbsp&nbsp
J. K. Scott, B. Chachuat, and P. I. Barton. Nonlinear convex and concave relaxations for the solutions of parametric ordinary differential equations. In revision: SIAM J Control Optim, 2010.
3.&nbsp&nbsp
N. S. Nedialkov, K. R. Jackson, and G.F. Corliss. Validated solutions of initial value problems for ordinary differential equations. Appl Math Comput, 105:21-68, 1998.
4.&nbsp&nbsp
Y. Lin and M. A. Stadtherr. Validated solutions of initial value problems for parametric ODEs. Appl Numer Math, 57(10):1145-1162, 2007.
5.&nbsp&nbsp
A. M. Sahlodin and B. Chachuat. Discretize-then-relax approach for convex/concave relaxations of the solutions of parametric ODEs. Appl Numer Math, 61(7):803-820, 2011.
6.&nbsp&nbsp
A. M. Sahlodin and B. Chachuat. Convex/Concave Relaxations of Parametric ODEs using Taylor Models. Comput Chem Eng, 35(5):844-857, 2011.
7.&nbsp&nbsp
G. P. McCormick. Computability of global solutions to factorable nonconvex programs: Part I - Convex underestimating problems. Math Program, 10:147-175, 1976.
8.&nbsp&nbsp
A. Mitsos, B. Chachuat and P. I. Barton. McCormick-based relaxations of algorithms. SIAM J Optim, 20:573-601, 2009.
9.&nbsp&nbsp
M. Tawarmalani and N. V. Sahinidis. Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Nonconvex Optimization and Its Applications. Boston, MA: Kluwer Academic Publishers, 2002.