Deterministic global optimization algorithm based on outer approximation for the parameter estimation of nonlinear dynamic biological systems

BMC Bioinformatics

Research Article

Laureano Jiménez¹  Carlos Pozo¹  Anton Miró¹  Gonzalo Guillén-Gosálbez¹  Jose A Egea² 

[1] Departament d’Enginyeria Química, Universitat Rovira i Virgili, Tarragona, Spain;Departamento de Matemática Aplicada y Estadística, Universidad Politécnica de Cartagena, Cartagena, Spain;

关键词: Master Problem;    Dynamic Optimization Problem;    Bilinear Term;    Parameter Estimation Problem;    Orthogonal Collocation;   

DOI  :  10.1186/1471-2105-13-90

 received in 2011-11-07, accepted in 2012-05-10,  发布年份 2012

来源: Springer

【 摘 要 】

BackgroundThe estimation of parameter values for mathematical models of biological systems is an optimization problem that is particularly challenging due to the nonlinearities involved. One major difficulty is the existence of multiple minima in which standard optimization methods may fall during the search. Deterministic global optimization methods overcome this limitation, ensuring convergence to the global optimum within a desired tolerance. Global optimization techniques are usually classified into stochastic and deterministic. The former typically lead to lower CPU times but offer no guarantee of convergence to the global minimum in a finite number of iterations. In contrast, deterministic methods provide solutions of a given quality (i.e., optimality gap), but tend to lead to large computational burdens.ResultsThis work presents a deterministic outer approximation-based algorithm for the global optimization of dynamic problems arising in the parameter estimation of models of biological systems. Our approach, which offers a theoretical guarantee of convergence to global minimum, is based on reformulating the set of ordinary differential equations into an equivalent set of algebraic equations through the use of orthogonal collocation methods, giving rise to a nonconvex nonlinear programming (NLP) problem. This nonconvex NLP is decomposed into two hierarchical levels: a master mixed-integer linear programming problem (MILP) that provides a rigorous lower bound on the optimal solution, and a reduced-space slave NLP that yields an upper bound. The algorithm iterates between these two levels until a termination criterion is satisfied.ConclusionThe capabilities of our approach were tested in two benchmark problems, in which the performance of our algorithm was compared with that of the commercial global optimization package BARON. The proposed strategy produced near optimal solutions (i.e., within a desired tolerance) in a fraction of the CPU time required by BARON.

【 授权许可】

Unknown   
© Miró et al.; licensee BioMed Central Ltd. 2012. This article is published under license to BioMed Central Ltd. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.