Global dynamic optimization arises in many engineering applications such as parameter estimation, global optimal control, and optimization-based worst-case uncertainty analysis. In branch-and-bound deterministic global optimization algorithms, a major computational bottleneck is generating appropriate lower bounds for the globally optimal objective value. These bounds are typically constructed using convex relaxations for the solutions of dynamic systems with respect to decision variables. Tighter convex relaxations thus translate into tighter lower bounds, which will typically reduce the number of iterations required by branch-and-bound. Subgradients, as useful local sensitivities of convex relaxations, are typically required by nonsmooth optimization solvers to effectively minimize these relaxations. This thesis develops novel techniques for efficiently computing tight convex relaxations with the corresponding subgradients for the solutions of ordinary differential equations (ODEs), to ultimately improve efficiency of deterministic global dynamic optimization. Firstly, new bounding and comparison results for dynamic process models are developed, which are more broadly applicable to engineering models than previous results. These new results show for the first time that in a state-of-the-art ODE relaxation framework, tighter enclosures of the original ODE system's right-hand side will necessarily translate into enclosures for the state variables that are at least as tight, which paves the way towards new advances for bounding in global dynamic optimization. Secondly, new convex relaxations are proposed for the solutions of ODE systems. These new relaxations are guaranteed to be at least as tight as state-of-the-art ODE relaxations. Unlike established ODE relaxation approaches, the new ODE relaxation approach can employ any valid convex and concave relaxations for the original right-hand side, and tighter such relaxations will necessarily yield ODE relaxations that are at least as tight. In a numerical case study, such tightness does indeed improve computational efficiency in deterministic global dynamic optimization. This new ODE relaxation approach is then extended in various ways to further tighten ODE relaxations. Thirdly, new subgradient evaluation approaches are proposed for ODE relaxations. Unlike established approaches that compute valid subgradients for nonsmooth dynamic systems, the new approaches are compatible with reverse automatic differentiation (AD). It is shown for the first time that subgradients of dynamic convex relaxations can be computed via a modified adjoint ODE sensitivity system, which could speed up lower bounding in global dynamic optimization. Lastly, in the situation where convex relaxations are known to be correct but subgradients are unavailable (such as for certain ODE relaxations), a new approach is proposed for tractably constructing useful correct affine underestimators and lower bounds of the convex relaxations just by black-box sampling. No additional assumptions are required, and no subgradients must be computed at any point. Under mild conditions, these new bounds are shown to converge rapidly to an original nonconvex function as the domain of interest shrinks. Variants of the new approach are presented to account for numerical error or noise in the sampling procedure. / Thesis / Doctor of Philosophy (PhD)

We propose interval arithmetic and interval constraint algorithms for global optimization. Both of these compute lower and upper bounds of a function over a box, and return a lower and an upper bound for the global minimum. In interval arithmetic methods, the bounds are computed using interval arithmetic evaluations. Interval constraint methods instead use domain reduction operators and consistency algorithms. The usual interval arithmetic algorithms for global optimization suffer from at least one of the following drawbacks: - Mixing the fathoming problem, in which we ask for the global minimum only, with the localization problem, in which we ask for the set of points at which the global minimum occurs. - Not handling the inner and outer approximations for epsilon-minimizer, which is the set of points at which the objective function is within epsilon of the global minimum. - Nothing is said about the quality for their results in actual computation. The properties of the algorithms are stated only in the limit for infinite running time, infinite memory, and infinite precision of the floating-point number system. To handle these drawbacks, we propose interval arithmetic algorithms for fathoming problems and for localization problems. For these algorithms we state properties that can be verified in actual executions of the algorithms. Moreover, the algorithms proposed return the best results that can be computed with given expressions for the objective function and the conditions, and a given hardware. Interval constraint methods combine interval arithmetic and constraint processing techniques, namely consistency algorithms, to obtain tighter bounds for the objective function over a box. The basic building block of interval constraint methods is the generic propagation algorithm. This explains our efforts to improve the generic propagation algorithm as much as possible. All our algorithms, namely dual, clustered, deterministic, and selective propagation algorithms, are developed as an attempt to improve the efficiency of the generic propagation algorithm. The relational box-consistency algorithm is another key algorithm in interval constraints. This algorithm keeps squashing the left and right bounds of the intervals of the variables until no further narrowing is possible. A drawback of this way of squashing is that as we proceed further, the process of squashing becomes slow. Another drawback is that, for some cases, the actual narrowing occurs late. To address these problems, we propose the following algorithms: - Dynamic Box-Consistency algorithm: instead of pruning the left and then the right bound of each domain, we alternate the pruning between all the domains. - Adaptive Box-Consistency algorithm: the idea behind this algorithm is to get rid of the boxes as soon as possible: start with small boxes and extend them or shrink them depending on the pruning outcome. This adaptive behavior makes this algorithm very suitable for quick squashing. Since the efficiency of interval constraint optimization methods depends heavily on the sharpness of the upper bound for the global minimum, we must make some effort to find the appropriate point or box to use for computing the upper bound, and not to randomly pick one as is commonly done. So, we introduce interval constraints with exploration. These methods use non-interval methods as an exploratory step in solving a global optimization problem. The results of the exploration are then used to guide interval constraint algorithms, and thus improve their efficiency.

Dans cette thèse, nous étudions les problèmes d'incertitudes dans les modèles probabilistes et tentons de déterminer leur impact sur l'analyse de performances et le dimensionnement des systèmes. Nous considérons deux aspects du problème d'imprécision. Le premier, consiste à étudier des chaînes en temps discret dont les probabilités ou taux de transition ne sont pas parfaitement connus. Nous construisons de nouveaux algorithmes de calcul de bornes par éléments sur les vecteurs de distribution stationnaires de chaînes partiellement spécifiées. Ces algorithmes permettent de déterminer des bornes par élément à chaque étape de calcul. Le second aspect étudié concerne le problème de mesures de traces de trafic réelles dans les réseaux. Souvent très volumineuses, la modélisation des traces de trafic est généralement impossible à effectuer de façon suffisamment précise et l'adéquation avec une loi de probabilité connue n'est pas assez réaliste. Utilisant une description par histogramme du trafic, nous proposons d'appliquer une nouvelle méthode d’évaluation de performance des réseaux. Fondée sur la comparaison stochastique pour construire des bornes optimales de supports réduits des histogrammes de trafics et sur la notion de monotonie stochastique des éléments de réseau, cette méthode permet de définir, de manière très pertinente, des garanties sur les mesures de performance. Nous obtenons en effet des bornes stochastiques supérieures et inférieures sur la longueur du tampon, les pertes, etc. L'intérêt et l'impact de notre méthode sont présentés sur diverses applications : éléments de réseau, AQM, réseaux de files d'attente, file avec processus d'arrivée non-stationnaire, etc / This thesis is devoted to the uncertainty in probabilistic models, how it impacts their analysis and how to apply these methods to performance analysis and network dimensioning. We consider two aspects of the uncertainty. The first consists to study a partially specified Markov chains. The missing of some transitions in the exact system because of its complexity can be solved by constructing bounding systems where worst-case transitions are defined to obtain an upper or a lower bound on the performance measures. We propose to develop new algorithms which give element-wise bounds of the steady-state distribution for the partially specified Markov chain. These algorithms are faster than the existing ones and allow us to compute element-wise bounds at each iteration.The second aspect studied concerns the problem of the measurements of real traffic trace in networks. Exact analysis of queueing networks under real traffic becomes quickly intractable due to the state explosion. Assuming the stationarity of flows, we propose to apply the stochastic comparison method to derive performance measure bounds under histogram-based traffics. We apply an algorithm based on dynamic programming to derive optimal bounding traffic histograms on reduced state spaces. Using the stochastic bound histograms and the monotonicity of the networking elements, we show how we can obtain, in a very efficient manner, guarantees on performance measures. We indeed obtain stochastic upper and lower bounds on buffer occupancy, losses, etc. The interest and the impact of our method are shown on various applications: elements of networks, AQM, queueing networks and queue with non-stationary arrival process