Over the past decades, cost-effectiveness principle or cost-benefit analysis has been employed oftentimes as a typical assessment tool for the expansion of drinking water utility. With changing public awareness of the inherent linkages between climate change, population growth and economic development, the addition of global change impact in the assessment regime has altered the landscape of traditional evaluation matrix. Nowadays, urban drinking water infrastructure requires careful long-term expansion planning to reduce the risk from global change impact with respect to greenhouse gas (GHG) emissions, economic boom and recession, as well as water demand variation associated with population growth and migration. Meanwhile, accurate prediction of municipal water demand is critically important to water utility in a fast growing urban region for the purpose of drinking water system planning, design and water utility asset management. A system analysis under global change impact due to the population dynamics, water resources conservation, and environmental management policies should be carried out to search for sustainable solutions temporally and spatially with different scales under uncertainties. This study is aimed to develop an innovative, interdisciplinary, and insightful modeling framework to deal with global change issues as a whole based on a real-world drinking water infrastructure system expansion program in Manatee County, Florida. Four intertwined components within the drinking water infrastructure system planning were investigated and integrated, which consists of water demand analysis, GHG emission potential, system optimization for infrastructure expansion, and nested minimax-regret (NMMR) decision analysis under uncertainties. In the water demand analysis, a new system dynamics model was developed to reflect the intrinsic relationship between water demand and changing socioeconomic iv environment. This system dynamics model is based on a coupled modeling structure that takes the interactions among economic and social dimensions into account offering a satisfactory platform. In the evaluation of GHG emission potential, a life cycle assessment (LCA) is conducted to estimate the carbon footprint for all expansion alternatives for water supply. The result of this LCA study provides an extra dimension for decision makers to extract more effective adaptation strategies. Both water demand forecasting and GHG emission potential were deemed as the input information for system optimization when all alternatives are taken into account simultaneously. In the system optimization for infrastructure expansion, a multiobjective optimization model was formulated for providing the multitemporal optimal facility expansion strategies. With the aid of a multi-stage planning methodology over the partitioned time horizon, such a systems analysis has resulted in a full-scale screening and sequencing with respect to multiple competing objectives across a suite of management strategies. In the decision analysis under uncertainty, such a system optimization model was further developed as a unique NMMR programming model due to the uncertainties imposed by the real-world problem. The proposed NMMR algorithm was successfully applied for solving the real-world problem with a limited scale for the purpose of demonstration.

<p dir="ltr">This thesis presents probably approximately correct (PAC) bounds on estimates of the transition kernels of Controlled Markov chains (CMC’s). CMC’s are a natural choice for modelling various industrial and medical processes, and are also relevant to reinforcement learning (RL). Learning the transition dynamics of CMC’s in a sample efficient manner is an important question that is open. This thesis aims to close this gap in knowledge in literature.</p><p dir="ltr">In Chapter 2, we lay the groundwork for later chapters by introducing the relevant concepts and defining the requisite terms. The two subsequent chapters focus on non-parametric estimation. </p><p dir="ltr">In Chapter 3, we restrict ourselves to a finitely supported CMC with d states and k controls and produce a general theory for minimax sample complexity of estimating the transition matrices.</p><p dir="ltr">In Chapter 4 we demonstrate the applicability of this theory by using it to recover the sample complexities of various controlled Markov chains, as well as RL problems.</p><p dir="ltr">In Chapter 5 we move to a continuous state and action spaces with compact supports. We produce a robust, non-parametric test to find the best histogram based estimator of the transition density; effectively reducing the problem into one of model selection based on empricial processes.</p><p dir="ltr">Finally, in Chapter 6 we move to a parametric and Bayesian regime, and restrict ourselves to Markov chains. Under this setting we provide a PAC-Bayes bound for estimating model parameters under tempered posteriors.</p>

The goal of this thesis is two-fold. On the one hand, it pursues to provide a contribution to the conjugate duality by proposing a new duality concept, which can be understood as an umbrella for different meaningful perturbation methods. On the other hand, this thesis aims to investigate minimax location problems by means of the duality concept introduced in the first part of this work, followed by a numerical approach using epigraphical splitting methods. After summarizing some elements of the convex analysis as well as introducing important results needed later, we consider an optimization problem with geometric and cone constraints, whose objective function is a composition of n+1 functions. For this problem we propose a conjugate dual problem, where the functions involved in the objective function of the primal problem are decomposed. Furthermore, we formulate generalized interior point regularity conditions for strong duality and give necessary and sufficient optimality conditions. As applications of this approach we determine the formulae of the conjugate as well as the biconjugate of the objective function of the primal problem and analyze an optimization problem having as objective function the sum of reciprocals of concave functions. In the second part of this thesis we discuss in the sense of the introduced duality concept three classes of minimax location problems. The first one consists of nonlinear and linear single minimax location problems with geometric constraints, where the maximum of nonlinear or linear functions composed with gauges between pairs of a new and existing points will be minimized. The version of the nonlinear location problem is additionally considered with set-up costs. The second class of minimax location problems deals with multifacility location problems as suggested by Drezner (1991), where for each given point the sum of weighted distances to all facilities plus set-up costs is determined and the maximal value of these sums is to be minimized. As the last and third class the classical multifacility location problem with geometrical constraints is considered in a generalized form where the maximum of gauges between pairs of new facilities and the maximum of gauges between pairs of new and existing facilities will be minimized. To each of these location problems associated dual problems will be formulated as well as corresponding duality statements and necessary and sufficient optimality conditions. To illustrate the results of the duality approach and to give a more detailed characterization of the relations between the location problems and their corresponding duals, we consider examples in the Euclidean space. This thesis ends with a numerical approach for solving minimax location problems by epigraphical splitting methods. In this framework, we give formulae for the projections onto the epigraphs of several sums of powers of weighted norms as well as formulae for the projection onto the epigraphs of gauges. Numerical experiments document the usefulness of our approach for the discussed location problems.

Le problème d'intérêt est d'estimer la fonction de concentration et l'aire sous la courbe (AUC) à travers l'estimation des paramètres d'un modèle de régression linéaire avec un processus d'erreur autocorrélé. On construit un estimateur linéaire sans biais simple de la courbe de concentration et de l'AUC. On montre que cet estimateur construit à partir d'un plan d'échantillonnage régulier approprié est asymptotiquement optimal dans le sens où il a exactement la même performance asymptotique que le meilleur estimateur linéaire sans biais (BLUE). De plus, on montre que le plan d'échantillonnage optimal est robuste par rapport à la misspecification de la fonction d'autocovariance suivant le critère du minimax. Lorsque des observations répétées sont disponibles, cet estimateur est consistant et a une distribution asymptotique normale. Les résultats obtenus sont généralisés au processus d'erreur de Hölder d'indice compris entre 0 et 2. Enfin, pour des tailles d'échantillonnage petites, un algorithme de recuit simulé est appliqué à un modèle pharmacocinétique avec des erreurs corrélées. / The problem of interest is to estimate the concentration curve and the area under the curve (AUC) by estimating the parameters of a linear regression model with autocorrelated error process. We construct a simple linear unbiased estimator of the concentration curve and the AUC. We show that this estimator constructed from a sampling design generated by an appropriate density is asymptotically optimal in the sense that it has exactly the same asymptotic performance as the best linear unbiased estimator (BLUE). Moreover, we prove that the optimal design is robust with respect to a misspecification of the autocovariance function according to a minimax criterion. When repeated observations are available, this estimator is consistent and has an asymptotic normal distribution. All those results are extended to the error process of Hölder with index including between 0 and 2. Finally, for small sample sizes, a simulated annealing algorithm is applied to a pharmacokinetic model with correlated errors.

Cette thèse s'inscrit dans le domaine de l'apprentissage statistique. Le cadre principal est celui de la prévision de suites déterministes arbitraires (ou suites individuelles), qui recouvre des problèmes d'apprentissage séquentiel où l'on ne peut ou ne veut pas faire d'hypothèses de stochasticité sur la suite des données à prévoir. Cela conduit à des méthodes très robustes. Dans ces travaux, on étudie quelques liens étroits entre la théorie de la prévision de suites individuelles et le cadre statistique classique, notamment le modèle de régression avec design aléatoire ou fixe, où les données sont modélisées de façon stochastique. Les apports entre ces deux cadres sont mutuels : certaines méthodes statistiques peuvent être adaptées au cadre séquentiel pour bénéficier de garanties déterministes ; réciproquement, des techniques de suites individuelles permettent de calibrer automatiquement des méthodes statistiques pour obtenir des bornes adaptatives en la variance du bruit. On étudie de tels liens sur plusieurs problèmes voisins : la régression linéaire séquentielle parcimonieuse en grande dimension (avec application au cadre stochastique), la régression linéaire séquentielle sur des boules L1, et l'agrégation de modèles non linéaires dans un cadre de sélection de modèles (régression avec design fixe). Enfin, des techniques stochastiques sont utilisées et développées pour déterminer les vitesses minimax de divers critères de performance séquentielle (regrets interne et swap notamment) en environnement déterministe ou stochastique. / The topics addressed in this thesis lie in statistical machine learning. Our main framework is the prediction of arbitrary deterministic sequences (or individual sequences). It includes online learning tasks for which we cannot make any stochasticity assumption on the data to be predicted, which requires robust methods. In this work, we analyze several connections between the theory of individual sequences and the classical statistical setting, e.g., the regression model with fixed or random design, where stochastic assumptions are made. These two frameworks benefit from one another: some statistical methods can be adapted to the online learning setting to satisfy deterministic performance guarantees. Conversely, some individual-sequence techniques are useful to tune the parameters of a statistical method and to get risk bounds that are adaptive to the unknown variance. We study such connections for several connected problems: high-dimensional online linear regression under a sparsity scenario (with an application to the stochastic setting), online linear regression on L1-balls, and aggregation of nonlinear models in a model selection framework (regression on a fixed design). We also use and develop stochastic techniques to compute the minimax rates of game-theoretic online measures of performance (e.g., internal and swap regrets) in a deterministic or stochastic environment.

Dans cette thèse, nous nous intéressons au problème d'estimation de densité dans le modèle de convolution. Ce cadre correspond aux modèles avec erreurs de mesures additives, c'est-à-dire que nous observons une version bruitée de la variable d'intérêt. Pour mener notre étude, nous adoptons le point de vue de l'estimation non-paramétrique adaptative qui repose sur des procédures de sélection de modèle développées par Birgé & Massart ou sur les méthodes de Lepski. Cette thèse se divise en deux parties. La première développe des méthodes spécifiques d'estimation adaptative quand les variables d'intérêt et les erreurs sont des variables aléatoires positives. Ainsi nous proposons des estimateurs adaptatifs de la densité ou encore de la fonction de survie dans ce modèle, puis de fonctionnelles linéaires de la densité cible. Enfin nous suggérons une procédure d'agrégation linéaire. La deuxième partie traite de l'estimation adaptative de densité dans le modèle de convolution lorsque la loi des erreurs est inconnue. Dans ce cadre il est supposé qu'un échantillon préliminaire du bruit est disponible ou que les observations sont disponibles sous forme de données répétées. Les résultats obtenus pour des données répétées dans le modèle de convolution permettent d'élargir cette méthodologie au cadre des modèles linéaires mixtes. Enfin cette méthode est encore appliquée à l'estimation de la densité de somme de variables aléatoires observées avec du bruit. / In this thesis, we are interested in nonparametric adaptive estimation problems of density in the convolution model. This framework matches additive measurement error models, which means we observe a noisy version of the random variable of interest. To carry out our study, we follow the paradigm of model selection developped by Birgé & Massart or criterion based on Lepski's method. The thesis is divided into two parts. In the first one, the main goal is to build adaptive estimators in the convolution model when both random variables of interest and errors are distributed on the nonnegative real line. Thus we propose adaptive estimators of the density along with the survival function, then of linear functionals of the target density. This part ends with a linear density aggregation procedure. The second part of the thesis deals with adaptive estimation of density in the convolution model when the distribution is unknown and distributed on the real line. To make this problem identifiable, we assume we have at hand either a preliminary sample of the noise or we observe repeated data. So, we can derive adaptive estimation with mild assumptions on the noise distribution. This methodology is then applied to linear mixed models and to the problem of density estimation of the sum of random variables when the latter are observed with an additive noise.

De multiples problèmes en apprentissage automatique consistent à minimiser une fonction lisse sur un espace euclidien. Pour l’apprentissage supervisé, cela inclut les régressions par moindres carrés et logistique. Si les problèmes de petite taille sont résolus efficacement avec de nombreux algorithmes d’optimisation, les problèmes de grande échelle nécessitent en revanche des méthodes du premier ordre issues de la descente de gradient. Dans ce manuscrit, nous considérons le cas particulier de la perte quadratique. Dans une première partie, nous nous proposons de la minimiser grâce à un oracle stochastique. Dans une seconde partie, nous considérons deux de ses applications à l’apprentissage automatique : au partitionnement de données et à l’estimation sous contrainte de forme. La première contribution est un cadre unifié pour l’optimisation de fonctions quadratiques non-fortement convexes. Celui-ci comprend la descente de gradient accélérée et la descente de gradient moyennée. Ce nouveau cadre suggère un algorithme alternatif qui combine les aspects positifs du moyennage et de l’accélération. La deuxième contribution est d’obtenir le taux optimal d’erreur de prédiction pour la régression par moindres carrés en fonction de la dépendance au bruit du problème et à l’oubli des conditions initiales. Notre nouvel algorithme est issu de la descente de gradient accélérée et moyennée. La troisième contribution traite de la minimisation de fonctions composites, somme de l’espérance de fonctions quadratiques et d’une régularisation convexe. Nous étendons les résultats existants pour les moindres carrés à toute régularisation et aux différentes géométries induites par une divergence de Bregman. Dans une quatrième contribution, nous considérons le problème du partitionnement discriminatif. Nous proposons sa première analyse théorique, une extension parcimonieuse, son extension au cas multi-labels et un nouvel algorithme ayant une meilleure complexité que les méthodes existantes. La dernière contribution de cette thèse considère le problème de la sériation. Nous adoptons une approche statistique où la matrice est observée avec du bruit et nous étudions les taux d’estimation minimax. Nous proposons aussi un estimateur computationellement efficace. / Many problems in machine learning are naturally cast as the minimization of a smooth function defined on a Euclidean space. For supervised learning, this includes least-squares regression and logistic regression. While small problems are efficiently solved by classical optimization algorithms, large-scale problems are typically solved with first-order techniques based on gradient descent. In this manuscript, we consider the particular case of the quadratic loss. In the first part, we are interestedin its minimization when its gradients are only accessible through a stochastic oracle. In the second part, we consider two applications of the quadratic loss in machine learning: clustering and estimation with shape constraints. In the first main contribution, we provided a unified framework for optimizing non-strongly convex quadratic functions, which encompasses accelerated gradient descent and averaged gradient descent. This new framework suggests an alternative algorithm that exhibits the positive behavior of both averaging and acceleration. The second main contribution aims at obtaining the optimal prediction error rates for least-squares regression, both in terms of dependence on the noise of the problem and of forgetting the initial conditions. Our new algorithm rests upon averaged accelerated gradient descent. The third main contribution deals with minimization of composite objective functions composed of the expectation of quadratic functions and a convex function. Weextend earlier results on least-squares regression to any regularizer and any geometry represented by a Bregman divergence. As a fourth contribution, we consider the the discriminative clustering framework. We propose its first theoretical analysis, a novel sparse extension, a natural extension for the multi-label scenario and an efficient iterative algorithm with better running-time complexity than existing methods. The fifth main contribution deals with the seriation problem. We propose a statistical approach to this problem where the matrix is observed with noise and study the corresponding minimax rate of estimation. We also suggest a computationally efficient estimator whose performance is studied both theoretically and experimentally.

The goal of this thesis is two-fold. On the one hand, it pursues to provide a contribution to the conjugate duality by proposing a new duality concept, which can be understood as an umbrella for different meaningful perturbation methods. On the other hand, this thesis aims to investigate minimax location problems by means of the duality concept introduced in the first part of this work, followed by a numerical approach using epigraphical splitting methods. After summarizing some elements of the convex analysis as well as introducing important results needed later, we consider an optimization problem with geometric and cone constraints, whose objective function is a composition of n+1 functions. For this problem we propose a conjugate dual problem, where the functions involved in the objective function of the primal problem are decomposed. Furthermore, we formulate generalized interior point regularity conditions for strong duality and give necessary and sufficient optimality conditions. As applications of this approach we determine the formulae of the conjugate as well as the biconjugate of the objective function of the primal problem and analyze an optimization problem having as objective function the sum of reciprocals of concave functions. In the second part of this thesis we discuss in the sense of the introduced duality concept three classes of minimax location problems. The first one consists of nonlinear and linear single minimax location problems with geometric constraints, where the maximum of nonlinear or linear functions composed with gauges between pairs of a new and existing points will be minimized. The version of the nonlinear location problem is additionally considered with set-up costs. The second class of minimax location problems deals with multifacility location problems as suggested by Drezner (1991), where for each given point the sum of weighted distances to all facilities plus set-up costs is determined and the maximal value of these sums is to be minimized. As the last and third class the classical multifacility location problem with geometrical constraints is considered in a generalized form where the maximum of gauges between pairs of new facilities and the maximum of gauges between pairs of new and existing facilities will be minimized. To each of these location problems associated dual problems will be formulated as well as corresponding duality statements and necessary and sufficient optimality conditions. To illustrate the results of the duality approach and to give a more detailed characterization of the relations between the location problems and their corresponding duals, we consider examples in the Euclidean space. This thesis ends with a numerical approach for solving minimax location problems by epigraphical splitting methods. In this framework, we give formulae for the projections onto the epigraphs of several sums of powers of weighted norms as well as formulae for the projection onto the epigraphs of gauges. Numerical experiments document the usefulness of our approach for the discussed location problems.

Planners who are involved in locational decision making often use raster-based geographic information systems (GIS) to quantify the value of land in terms of suitability or cost for a certain use. From a computational point of view, this process can be seen as a transformation of one or more sets of values associated with a grid of cells into another set of such values through a function reflecting one or more criteria. While it is generally anticipated that different transformations lead to different ‘best’ locations, little has been known on how such differences arise (or do not arise). Examples of such spatial decision problems can be easily found in the literature and many of them concern the selection of a set of cells (to which the land use under consideration is allocated) from a raster surface of suitability or cost depending on context. To facilitate GIS’s algorithmic approach, it is often assumed that the quality of the set of cells can be evaluated as a whole by the sum of their cell values. The validity of this assumption must be questioned, however, if those values are measured on a scale that does not permit arithmetic operations. Ordinal scale of measurement in Stevens’s typology is one such example. A question naturally arises: is there a more mathematically sound and consistent approach to evaluating the quality of a path when the quality of each cell of the given grid is measured on an ordinal scale? The thesis attempts to answer the questions highlighted above in the context of path planning through a series of computational experiments using a number of random landscape grids with a variety of spatial and non-spatial structures. In the first set of experiments, we generated least-cost paths on a number of cost grids transformed from the landscape grids using a variety of transformation parameters and analyzed the locations and (weighted) lengths of those paths. Results show that the same pair of terminal cells may well be connected by different least-cost paths on different cost grids though derived from the same landscape grid and that the variation among those paths is affected by how given values are distributed in the landscape grid as well as by how derived values are distributed in the cost grids. Most significantly, the variation tends to be smaller when the landscape grid contains more distinct patches of cells potentially attracting or distracting cost-saving passage or when the cost grid contains a smaller number of low-cost cells. The second set of experiments aims to compare two optimization models, minisum and minimax (or maximin) path models, which aggregate the values of the cells associated with a path using the sum function and the maximum (or minimum) function, respectively. Results suggest that the minisum path model is effective if the path search can be translated into the conventional least-cost path problem, which aims to find a path with the minimum cost-weighted length between two terminuses on a ratio-scaled raster cost surface, but the minimax (or maximin) path model is mathematically sounder if the cost values are measured on an ordinal scale and practically useful if the problem is concerned not with the minimization of cost but with the maximization of some desirable condition such as suitability. / Planerare som arbetar bland annat med att fatta beslut som hänsyftar till vissa lokaler använder ofta rasterbaserade geografiska informationssystem (GIS) för att sätta ett värde på marken med avseende på lämplighet eller kostnad för en viss användning. Ur en beräkningssynpunkt kan denna process ses som en transformation av en eller flera uppsättningar värden associerade med ett rutnät av celler till en annan uppsättning sådana värden genom en funktion som återspeglar ett eller flera kriterier. Medan det generellt förväntas att olika omvandlingar leder till olika "bästa" platser, har lite varit känt om hur sådana skillnader uppstår (eller inte uppstår). Exempel på sådana rumsliga beslutsproblem kan lätt hittas i litteraturen och många av dem handlar om valet av en uppsättning celler (som markanvändningen övervägs tilldelas) från en rasteryta av lämplighet eller kostnad beroende på kontext. För att underlätta GISs algoritmiska tillvägagångssätt antas det ofta att kvaliteten på uppsättningen av celler kan utvärderas som helhet genom summan av deras cellvärden. Giltigheten av detta antagande måste emellertid ifrågasättas om dessa värden mäts på en skala som inte tillåter aritmetiska transformationer. Användning av ordinal skala enligt Stevens typologi är ett exempel av detta. En fråga uppstår naturligt: Finns det ett mer matematiskt sunt och konsekvent tillvägagångssätt för att utvärdera kvaliteten på en rutt när kvaliteten på varje cell i det givna rutnätet mäts med ordinalskala? Avhandlingen försöker svara på ovanstående frågor i samband med ruttplanering genom en serie beräkningsexperiment med hjälp av ett antal slumpmässigt genererade landskapsnät med en rad olika rumsliga och icke-rumsliga strukturer. I den första uppsättningen experiment genererade vi minsta-kostnad rutter på ett antal kostnadsnät som transformerats från landskapsnätverket med hjälp av en mängd olika transformationsparametrar, och analyserade lägen och de (viktade) längderna för dessa rutter. Resultaten visar att samma par ändpunkter mycket väl kan vara sammanbundna med olika minsta-kostnad banor på olika kostnadsraster härledda från samma landskapsraster, och att variationen mellan dessa banor påverkas av hur givna värden fördelas i landskapsrastret såväl som av hur härledda värden fördelas i kostnadsrastret. Mest signifikant är att variationen tenderar att vara mindre när landskapsrastret innehåller mer distinkta grupper av celler som potentiellt lockar eller distraherar kostnadsbesparande passage, eller när kostnadsrastret innehåller ett mindre antal låg-kostnad celler. Den andra uppsättningen experiment syftar till att jämföra två optimeringsmodeller, minisum och minimax (eller maximin) sökmodeller, vilka sammanställer värdena för cellerna som är associerade med en sökväg med summanfunktionen respektive maximum (eller minimum) funktionen. Resultaten tyder på att minisumbanemodellen är effektiv om sökningen av sökvägen kan översättas till det konventionella minsta kostnadsproblemet, vilket syftar till att hitta en väg med den minsta kostnadsvägda längden mellan två terminaler på en ratio-skalad rasterkostyta, men minimax (eller maximin) banmodellen är matematiskt sundare om kostnadsvärdena mäts i ordinär skala och praktiskt användbar om problemet inte bara avser minimering av kostnad men samtidigt maximering av någon önskvärd egenskap såsom lämplighet. / <p>QC 20181002</p>

[pt] Nesta tese de doutorado, é proposta uma combinação híbrida de métodos preditivos que agrega cinco abordagens distintas e genéricas, do ponto de vista de modelagem: método SSA; decomposição wavelet; redes neurais artificiais; programação matemática multiobjetivo MINIMAX, com abordagem de programação por metas; e método de simulação de quase Monte-Carlo. Para exemplificar e demonstrar a eficiência da combinação híbrida proposta, são mostrados, no Capítulo 7, os principais resultados de uma aplicação computacional, no qual é possível verificar que o seu desempenho, em termos de modelagem, foi consideravelmente superior, em relação a todas as estatísticas de aderência consideradas. / [en] In this thesis, we propose a hybrid combination of predictive methods that aggregates five distinct and general approaches, from the viewpoint of modeling: SSA method; wavelet decomposition, artificial neural networks, multiobjective mathematical programming MINIMAX, with goal programming approach; quasi- Monte-Carlo simulation method. To exemplify and demonstrate the efficiency of the proposed hybrid combination are shown, in Section 7, the main results of a computer application in which you can verify that their performance, in terms of modeling, was significantly higher, compared to all considered adherence statistics.