Many methods employed for the modeling, analysis, and control of dynamical systems are based on underlying optimization schemes, e.g., parameter estimation and model predictive control. For the popular single and multiple shooting optimization approaches, in each optimization step one or more simulations of the commonly high-dimensional dynamical systems are required. This numerical simulation is frequently the biggest bottleneck concerning the computational effort. In this work, systems described by parameter dependent linear ordinary differential equations (ODEs) are considered. We propose a novel approach employing model order reduction, improved a posteriori bounds for the reduction error, and nonlinear optimization via vertex enumeration. By combining these methods an upper bound for the objective function value of the full order model can be computed efficiently by simulating only the reduced order model. Therefore, the reduced order model can be utilized to minimize an upper bound of the true objective function, ensuring a guaranteed objective function value while reducing the computational effort. The approach is illustrated by studying the parameter estimation problem for a model of an isothermal continuous tube reactor. For this system we derive an asymptotically stable reduction error estimator and analyze the speed-up of the optimization. (C) 2012 Elsevier Ltd. All rights reserved.