The work presented in this dissertation has been focused on exploiting the branch-and-price (BNP) method for the solution of various stochastic mixed integer programming problems (MIPs). In particular, we address the stochastic generalized assignment problem (SGAP), a hospital staff scheduling problem (HSSP), a stochastic hospital staff scheduling problem (SHSSP), and a stochastic short-term personnel planning problem (SSTPP). The BNP method has been developed in concert with the dual stabilization technique and other enhancements of this method for each of these problems. In view of an excessive number of scenarios that arise for these problems, we also implement the Monte Carlo method within the BNP scheme. The superiority of the BNP-based method over the branch-and-cut (BNC) method is demonstrated for all of these problems. The first problem that we address is the SGAP for which the processing time of a job on a machine is assumed to be stochastic. Even though the generalized assignment problem (GAP) has been solved using the BNP method, yet no study has been reported in the literature on the use of the BNP method for the solution of the SGAP. Our work has been motivated by the desire to fill this gap. We begin by showing that it is better to solve the SGAP as a stochastic program in contrast to solving it by using the expected values of the times required to process the jobs on the machines. Then, we show that the stochastic model of the SGAP is a complete recourse model — a useful property which permits the first stage decisions to produce feasible solutions for the recourse problems. We develop three BNP-based methods for the solution of the SGAP. The first of these is BNP-SGAP, which is a combination of branch-and-bound and column generation methods. The pricing problem of BNP-SGAP is separable with regard to each machine, and it is a multiple-constraint knapsack problem. The second method is BNP-SGAP implemented in concert with the dual stabilization technique (DST), and it is designated as BNPDST-SGAP. We have introduced a new DST by modifying the Boxstep method of Pigatti et al. [76]. We have shown that our method performs better than the method of Pigatti et al. [76] resulting in over two-fold savings in cpu times on average. The third method that we develop for the solution of the SGAP is BNPDST-SGAP implemented with an advanced start to obtain an initial feasible solution. We use a greedy heuristic to obtain this solution, and this heuristic is a modification of a similar method used for the knapsack problem. It relies on the information available at a node of the underlying branch-and-bound tree. We have shown that this procedure obtains an initial feasible solution, if it exists at that node. We designate this method as BNPDSTKP-SGAP. We have also developed a BNC method to solve the SGAP using CPLEX 9.0. We have compared the performances of the BNP and BNC methods on various problem instances obtained by varying the number of machines, the ratio of the number of machines to the number of jobs, the machine capacity, and the penalty cost per unit of extra resource required at each machine. Our results show that all BNP-based methods perform better than the BNC method, with the best performance obtained for BNPDSTKP-SGAP. An issue with the use of the scenario-based methods that we have employed for the solution of the SGAP is that the number of scenarios generally grows exponentially in problem parameters, which gives rise to a large-size problem. To overcome the complexity caused by the presence of a large number of scenarios for the solution of the SGAP, we introduce the use of the Monte Carlo method (MCM) within the BNP scheme. We designate this method as BNPDSTKP-SGAP with MCM. It affords the use of a small subset of scenarios at a time to estimate the "true" optimal objective function value. Replications of the subsets of scenarios are carried out until the objective function value satisfies a stopping criterion. We have established theoretical results for the use of the MCM. These pertain to determining unbiased estimates of: (i) lower and upper bounds of the "true" optimal objective function value, (ii) the "true" optimal solution, and (iii) the optimality gap. We have also provided the 100(1-ï ¡) confidence interval on the optimality gap. Our experimental investigation has shown the efficacy of using this method. It obtains almost optimal solutions, with the objective function value lying within 5% of the "true" optimal objective function value, while giving almost ten-fold savings in cpu time. Our experimentation has also revealed that an increment in the number of scenarios in each replication makes a greater impact on the quality of the solution obtained than an increment in the number of replications. We have also observed the impact of a change in the variance of a processing time distribution on cpu time. As expected, the optimal objective function value increases with increment in processing time variability. Also, by comparing the results with the expected value solution, it is observed that the greater the variability in the data, the better it is to use the stochastic program. The second problem that we study is the hospital staff scheduling problem. We address the following three versions of this problem: HSSP (General): Implementation of schedule incorporating the four principal elements, namely, surgeons, operations, operating rooms, and operation times; HSSP (Priority): Inclusion of priority for some surgeons over the other surgeons regarding the use of the facility in HSSP (General); HSSP (Pre-arranged): Implementation of a completely pre-fixed schedule for some surgeons. The consideration of priority among the surgeons mimics the reality. Our BNP method for the solution of these problems is similar to that for the SGAP except for the following: (i) a feasible solution at a node is obtained with no additional assignment, i.e., it consists of the assignments made in the preceding nodes of that node in the branch-and-bound tree; (ii) the columns with positive reduced cost are candidates for augmentation in the CGM; and (iii) a new branching variable selection strategy is introduced, which selects a fractional variable as a branching variable by fixing a value of which we enforce the largest number of variables to either 0 or 1. The priority problem is separable in surgeons. The results of our experimentation have shown the efficacy of using the BNP-based method for the solution of each HSSP as it takes advantage of the inherent structure of each of these problems. We have also compared their performances with that of the BNC method developed using CPLEX. For the formulations HSSP (General), HSSP (Priority), and HSSP (Pre-arranged), the BNP method gives better results for 22 out of 30, 29 out of 34, and 20 out 32 experiments over the BNC method, respectively. Furthermore, while the BNC method fails to obtain an optimal solution for 15 experiments, the BNP method obtains optimal solutions for all 96 experiments conducted. Thus, the BNP method consistently outperforms the BNC method for all of these problems. The third problem that we have investigated in this study is the stochastic version of the HSSP, designated as the Stochastic HSSP (SHSSP), in which the operation times are assumed to be stochastic. We have introduced a formulation for this formulation, designated as SHSSP2 (General), which allows for overlapping of schedules for surgeons and operating rooms, and also, allows for an assignment of a surgeon to perform an operation that takes less than a pre-arranged operation time, but all incurring appropriate penalty costs. A comparison of the solution of SHSSP2 (General) and its value with those obtained by using expected values (the corresponding problem is designated as Expected-SHSSP2 (General)) reveals that Expected-SHSSP2 (General) may end up with inferior and infeasible schedules. We show that the recourse model for SHSSP2 (General) is a relatively complete recourse model. Consequently, we use the Monte Carlo method (MCM) to reduce the complexity of solving SHSSP2 (General) by considering fewer scenarios. We employ the branch-and-cut (BNC) method in concert with the MCM for solving SHSSP2 (General). The solution obtained is evaluated using tolerance ratio, closeness to optimality, length of confidence interval, and cpu time. The MCM substantially reduces computational effort while producing almost optimal solutions and small confidence intervals. We have also considered a special case of SHSSP2 (General), which considers no overlapping schedules for surgeons and operating rooms and assigns exactly the same operation time for each assignment under each scenario, and designate it as SHSSP2 (Special). With this, we consider another formulation that relies on the longest operation time among all scenarios for each assignment of a surgeon to an operation in order to avoid scheduling conflicts, and we designate this problem as SHSSP (Longest). We show SHSSP (Longest) to be equivalent to deterministic HSSP, designated as HSSP (Equivalent), and we further prove it to be equivalent to SHSSP (General) in terms of the optimal objective function value and the optimal assignments of operations to surgeons. The schedule produced by HSSP (Equivalent) does not allow any overlap among the operations performed in an operating room. That is, a new operation cannot be performed if a previous operation scheduled in that room takes longer than expected. However, the schedule generated by HSSP (Equivalent) may turn out to be a conservative one, and may end up with voids due to unused resources in case an operation in an operating room is completed earlier than the longest time allowed. Nevertheless, the schedule is still a feasible one. In such a case, the schedule can be left-shifted, if possible, because the scenarios are now revealed. Moreover, such voids could be used to perform other procedures (e.g., emergency operations) that have not been considered within the scope of the SHSSP addressed here. Besides, such a schedule can provide useful guidelines to plan for resources ahead of time. The fourth problem that we have addressed in this dissertation is the stochastic short-term personnel planning problem, designated as Stochastic STPP (SSTPP). This problem arises due to the need for finding appropriate temporary contractors (workers) to perform requisite jobs. We incorporate uncertainty in processing time or amount of resource required by a contractor to perform a job. Contrary to the SGAP, the recourse model for this problem is not a relatively complete recourse model. As a result, we cannot employ a MCM method for the solution of this problem as it may give rise to an infeasible solution. The BNP method for the SSTPP employs the DST and the advanced start procedure developed for the SGAP, and due to extra constraints and presence of binary decision variables, we use the branching variable selection strategy developed for the HSSP models. Because of the distinctive properties of the SSTPP, we have introduced a new node selection strategy. We have compared the performances of the BNC-based and BNP-based methods based on the cpu time required. The BNP method outperforms the BNC method in 75% of the experiments conducted, and the BNP method is found to be quite stable with smaller variance in cpu times than those for the BNC method. It affords solution of difficult problems in smaller cpu times than those required for the BNC method. / Ph. D.

Integrated data analyses are becoming increasingly popular in studies of wild animal populations where two or more separate sources of data contain information about common parameters. Here we develop an integrated population model using abundance and demographic data from a study of common guillemots (Uria aalge) on the Isle of May, southeast Scotland. A state-space model for the count data is supplemented by three demographic time series (productivity and two mark-recapture-recovery (MRR)), enabling the estimation of prebreeder emigration rate - a parameter for which there is no direct observational data, and which is unidentifiable in the separate analysis of MRR data. A Bayesian approach using MCMC provides a flexible and powerful analysis framework. This model is extended to provide predictions of future population trajectories. Adopting random effects models for the survival and productivity parameters, we implement the MCMC algorithm to obtain a posterior sample of the underlying process means and variances (and population sizes) within the study period. Given this sample, we predict future demographic parameters, which in turn allows us to predict future population sizes and obtain the corresponding posterior distribution. Under the assumption that recent, unfavourable conditions persist in the future, we obtain a posterior probability of 70% that there is a population decline of >25% over a 10-year period. Lastly, using MRR data we test for spatial, temporal and age-related correlations in guillemot survival among three widely separated Scottish colonies that have varying overlap in nonbreeding distribution. We show that survival is highly correlated over time for colonies/age classes sharing wintering areas, and essentially uncorrelated for those with separate wintering areas. These results strongly suggest that one or more aspects of winter environment are responsible for spatiotemporal variation in survival of British guillemots, and provide insight into the factors driving multi-population dynamics of the species.

本論文主要在估計門檻式自動迴歸模型之參數的信賴區間。由線性自動迴歸 模型衍生出來的非線性自動迴歸模型中，門檻式自動迴歸模型是其中一種經常會被應用到的模型。雖然，門檻式自動迴歸模型之參數的漸近理論已經發展了許多；但是，相較於大樣本理論，有限樣本下參數的性質討論則較少。對於有限樣本的研究，Woodroofe (1989) 提出一種近似法：非常弱近似法。 Woodroofe 和 Coad (1997) 則利用此方法去架構一適性化線性模型之參數的修正信賴區間。Weng 和 Woodroofe (2006) 則將此近似法應用於線性自動迴歸模型。這個方法的應用始於定義一近似樞紐量，接著利用此方法找出近似樞紐量的近似期望值及近似變異數，並對此近似樞紐量標準化，則標準化後的樞紐量將近似於標準常態分配，因此得以架構參數的修正信賴區間。而在線性自動迴歸模型下，利用非常弱展開所導出的近似期望值及近似變異數僅會與一階動差及二階動差的微分有關。因此，本論文的研究目的就是在樣本數為適當的情況下，將線性自動迴歸模型的結果運用於門檻式自動迴歸模型。由於大部分門檻式自動迴歸模型的動差並無明確之形式；因此，本研究採用蒙地卡羅法及插分法去近似其動差及微分。最後，以第一階門檻式自動迴歸模型去配適美國的國內生產總值資料。 / Threshold autoregressive (TAR) models are popular nonlinear extension of the linear autoregressive (AR) models. Though many have developed the asymptotic theory for parameter estimates in the TAR models, there have been less studies about the finite sample properties. Woodroofe (1989) and Woodroofe and Coad (1997) developed a very weak approximation and used it to construct corrected confidence sets for parameters in an adaptive linear model. This approximation was further developed by Woodroofe and Coad (1999) and Weng and Woodroofe (2006), who derived the corrected confidence sets for parameters in the AR(p) models and other adaptive models. This approach starts with an approximate pivot, and employs the very weak expansions to determine the mean and variance corrections of the pivot. Then, the renormalized pivot is used to form corrected confidence sets. The correction terms have simple forms, and for AR(p) models it involves only the first two moments of the process and the derivatives of these moments. However, for TAR models the analytic forms for moments are known only in some cases when the autoregression function has special structures. The goal of this research is to extend the very weak method to the TAR models to form corrected confidence sets when sample size is moderate. We propose using the difference quotient method and Monte Carlo simulations to approximate the derivatives. Some simulation studies are provided to assess the accuracy of the method. Then, we apply the approach to a real U.S. GDP data.

Le présent travail est consacré au développement et à la validation d'un modèle hybride de propagation d'un incendie de végétation à grande échelle prenant en compte les hétérogénéités locales liées à la végétation, à la topographie du terrain et aux conditions météorologiques. Dans un premier temps, on présente différentes méthodes permettant de générer un réseau amorphe, représentatif d'une distribution réaliste de la végétation. Le modèle hybride est un modèle de réseau où les phénomènes qui se produisent à l'échelle macroscopique sont traités de façon déterministe, comme le préchauffage du site végétal provenant du rayonnement de la flamme et des braises et de la convection par les gaz chauds, mais aussi son refroidissement radiatif et son inflammation pilotée. Le rayonnement thermique provenant de la flamme est calculé en combinant le modèle de flamme solide à la méthode de Monte Carlo et en considérant son atténuation par la couche d'air atmosphérique entre la flamme et la végétation réceptive. Le modèle est ensuite appliqué à des configurations simples de propagation sur un terrain plat ou incliné, en présence ou non d'un vent constant. Les résultats obtenus sont en bon accord avec les données de la littérature. Une étude de sensibilité a été également menée permettant d'identifier les paramètres les plus influents du modèle, en termes de vitesse de propagation du feu, et de les hiérarchiser. La phase de validation a portée sur l'analyse comparative des contours de feux calculés par le modèle avec ceux mesurés lors d'un brûlage dirigé réalisé en Australie et d'un feu réel qui a lieu en Corse en 2009, montrant un très bon accord en termes de vitesse de propagation / The present work is devoted to the development of a hybrid model for predicting the rate of spread of wildland fires at a large scale, taking into account the local heterogeneities related to vegetation, topography, and meteorological conditions. Some methods for generating amorphous network, representative of real vegetation landscapes, are proposed. Mechanisms of heat transfer from the flame front to the virgin fuel are modeled: radiative preheating from the flame and embers, convective preheating from hot gases, radiative heat losses and piloted ignition of the receptive vegetation item. Flame radiation is calculated by combining the solid flame model with the Monte Carlo method and by taking into account its attenuation by the atmospheric layer between the flame and the receptive vegetation. The model is applied to simple configurations where the fire spreads on a flat or inclined terrain, with or without a constant wind. Model results are in good agreement with literature data. A sensitivity study is conducted to identify the most influential parameters of the model. Eventually, the model is validated by comparing predicted fire patterns with those obtained from a prescribed burning in Australia and from a historical fire that occurred in Corsica in 2009, showing a very good agreement in terms of fire patterns, rate of spread, and burned area.

Le contexte de cette thèse est celui des communications optiques sans fil pour des applications en environnements indoor. Pour discuter des performances d'une liaison optique sans fil, il est nécessaire d'établir une étude caractéristique du comportement du canal de propagation. Cette étude passe par l'étape de la mesure ou de l'estimation par la simulation de la réponse impulsionnelle. Après avoir décrit la composition d'une liaison et passé en revue les méthodes de simulation existantes, nous présentons nos algorithmes de simulation dans des environnements réalistes, en nous intéressant à leurs performances en termes de précision et de temps de calcul. Ces méthodes sont basées sur la résolution des équations de transport de la lumière par du lancer de rayons associées aux méthodes d'intégration stochastique de Monte Carlo. La version classique de ces méthodes est à la base de trois algorithmes de simulations proposés. En utilisant une optimisation par des chaînes de Markov, nous présentons ensuite deux autres algorithmes. Un bilan des performances de ces algorithmes est établi dans des scénarios mono et multi-antennes. Finalement, nous appliquons nos algorithmes pour caractériser l'impact de l'environnement de simulation sur les performances d'une liaison de communication par lumière visible, à savoir les modèles d'émetteurs, les matériaux des surfaces, l'obstruction du corps de l'utilisateur et sa mobilité, et la géométrie de la scène de simulation. / The context of this PhD thesis falls within the scope of optical wireless communications for applications in indoor environments. To discuss the performance of an optical wireless link, it is necessary to establish a characteristic study of the behavior of the optical wave propagation channel. This study can be realized by measurement or by the simulation of the channel impulse response. After describing the composition of an optical wireless link and reviewing existing simulation methods, we present our new simulation algorithms channel in realistic environments by focusing on their performances in terms of accuracy and their complexity in terms of computation time. These methods are based on solving the light transport equations by ray-tracing techniques associated with stochastic Monte Carlo integration methods. The classical version of these methods is the basis of three proposed simulation algorithms. By applying an optimization using Markov Chain, we present two new algorithms. A performance assessment of our simulation algorithms is established in mono and multi-antenna scenarios of our simulation algorithms. Finally, we present the application of these algorithms for characterizing the impact of the simulation environment on the performances of a visible light communication link. We particularly focus on the transmitter models, surface coating materials, obstruction of the user's body and its mobility, and the geometry of the simulation scene.

Dans le monde économique, les contrats d'options sont très utilisés car ils permettent de se couvrir contre les aléas et les risques dus aux fluctuations des prix des actifs sous-jacents. La détermination du prix de ces contrats est d'une grande importance pour les investisseurs.Dans cette thèse, on s'intéresse aux problèmes d'évaluation des options, en particulier les options Européennes et Quanto sur un actif financier dont le prix est modélisé en multi dimensions par un modèle de diffusion-saut à volatilité stochastique avec sauts (1er cas considère la volatilité sans sauts, dans le 2ème cas les sauts sont pris en compte, finalement dans le 3ème cas, l'actif sous-jacent est sans saut et la volatilité suit un CEV modèle sans saut). Ce modèle permet de mieux prendre en compte certains phénomènes observés dans les marchés. Nous développons des méthodes numériques qui déterminent les valeurs des prix de ces options. On présentera d'abord le modèle qui s'écrit sous la forme d'un système d'équations intégro-différentielles stochastiques "EIDS", et on étudiera l'existence et l'unicité de la solution de ce modèle en fonction de ses coefficients, puis on établira le lien entre le calcul du prix de l'option et la résolution de l'équation Intégro-différentielle partielle (EIDP). Ce lien, qui est basé sur la notion des générateurs infinitésimaux, nous permet d'utiliser différentes méthodes numériques pour l'évaluation des options considérées. Nous introduisons alors l'équation variationnelle associée aux EIDP et démontrons qu'elle admet une unique solution dans un espace de Sobolev avec poids en s'inspirant des travaux de Zhang [106].Nous nous concentrons ensuite sur l'approximation numérique du prix de l'option en considérant le problème dans un domaine borné, et nous utilisons pour la résolution numérique la méthode des éléments finis de type (P1), et un schéma d'Euler-Maruyama, pour se servir, d'une part de la méthode de différences finies en temps, et d'autre part de la méthode de Monté Carlo et la méthode Quasi Monte Carlo. Pour cette dernière méthode nous avons utilisé les suites de Halton afin d'améliorer la vitesse de convergence.Nous présenterons une étude comparative des différents résultats numériques obtenus dans plusieurs cas différents afin d'étudier la performance et l'efficacité des méthodes utilisées. / In the modern economic world, the options contracts are used because they allow to hedge against the vagaries and risks refers to fluctuations in the prices of the underlying assets. The determination of the price of these contracts is of great importance for investors.We are interested in problems of options pricing, actually the European and Quanto options on a financial asset. The price of that asset is modeled by a multi-dimentional jump diffusion with stochastic volatility. Otherwise, the first model considers the volatility as a continuous process and the second model considers it as a jump process. Finally in the 3rd model, the underlying asset is without jump and volatility follows a model CEV without jump. This model allow better to take into account some phenomena observed in the markets. We develop numerical methods that determine the values of prices for these options. We first write the model as an integro-differential stochastic equations system "EIDS", of which we study existence and unicity of solutions. Then we relate the resolution of PIDE to the computation of the option value. This link, which is based on the notion of infinitesimal generators, allows us to use different numerical methods. We therefore introduce the variational equation associated with the PIDE, and drawing on the work of Zhang [106], we show that it admits a unique solution in a weights Sobolev space We focus on the numerical approximation of the price of the option, by treating the problem in a bounded domain. We use the finite elements method of type (P1), and the scheme of Euler-Maruyama, for this serve, on the one hand the finite differences method in time, and on the other hand the method of Monte Carlo and the Quasi Monte Carlo method. For this last method we use of Halton sequences to improve the speed of convergence.We present a comparative study of the different numerical results in many different cases in order to investigate the performance and effectiveness of the used methods.

Les études de Sûreté de Fonctionnement (SdF) sur les barrières instrumentées de sécurité représentent un enjeu important dans de nombreux domaines industriels. Afin de pouvoir réaliser ce type d'études, TOTAL développe depuis les années 80 le logiciel GRIF. Pour prendre en compte la complexité croissante du contexte opératoire de ses équipements de sécurité, TOTAL est de plus en plus fréquemment amené à utiliser le moteur de calcul MOCA-RP du package Simulation. MOCA-RP permet d'analyser grâce à la simulation de Monte-Carlo (MC) les performances d'équipements complexes modélisés à l'aide de Réseaux de Petri (RP). Néanmoins, obtenir des estimateurs précis avec MC sur des équipements très fiables, tels que l'indisponibilité, revient à faire de la simulation d'événements rares, ce qui peut s'avérer être coûteux en temps de calcul. Les méthodes standard d'accélération de la simulation de Monte-Carlo, initialement développées pour répondre à cette problématique, ne semblent pas adaptées à notre contexte. La majorité d'entre elles ont été définies pour améliorer l'estimation de la défiabilité et/ou pour les processus de Markov. Par conséquent, le travail accompli dans cette thèse se rapporte au développement de méthodes d'accélération de MC adaptées à la problématique des études de sécurité se modélisant en RP et estimant notamment l'indisponibilité. D'une part, nous proposons l'Extension de la Méthode de Conditionnement Temporel visant à accélérer la défaillance individuelle des composants. D'autre part, la méthode de Dissociation ainsi que la méthode de ``Truncated Fixed Effort'' ont été introduites pour accroitre l'occurrence de leurs défaillances simultanées. Ensuite, nous combinons la première technique avec les deux autres, et nous les associons à la méthode de Quasi-Monte-Carlo randomisée. Au travers de diverses études de sensibilité et expériences numériques, nous évaluons leur performance, et observons une amélioration significative des résultats par rapport à MC. Par ailleurs, nous discutons d'un sujet peu familier à la SdF, à savoir le choix de la méthode à utiliser pour déterminer les intervalles de confiance dans le cas de la simulation d'événements rares. Enfin, nous illustrons la faisabilité et le potentiel de nos méthodes sur la base d'une application à un cas industriel. / The dependability analysis of safety instrumented systems is an important industrial concern. To be able to carry out such safety studies, TOTAL develops since the eighties the dependability software GRIF. To take into account the increasing complexity of the operating context of its safety equipment, TOTAL is more frequently led to use the engine MOCA-RP of the GRIF Simulation package. Indeed, MOCA-RP allows to estimate quantities associated with complex aging systems modeled in Petri nets thanks to the standard Monte Carlo (MC) simulation. Nevertheless, deriving accurate estimators, such as the system unavailability, on very reliable systems involves rare event simulation, which requires very long computing times with MC. In order to address this issue, the common fast Monte Carlo methods do not seem to be appropriate. Many of them are originally defined to improve only the estimate of the unreliability and/or well-suited for Markovian processes. Therefore, the work accomplished in this thesis pertains to the development of acceleration methods adapted to the problematic of performing safety studies modeled in Petri nets and estimating in particular the unavailability. More specifically, we propose the Extension of the "Méthode de Conditionnement Temporel" to accelerate the individual failure of the components, and we introduce the Dissociation Method as well as the Truncated Fixed Effort Method to increase the occurrence of their simultaneous failures. Then, we combine the first technique with the two other ones, and we also associate them with the Randomized Quasi-Monte Carlo method. Through different sensitivities studies and benchmark experiments, we assess the performance of the acceleration methods and observe a significant improvement of the results compared with MC. Furthermore, we discuss the choice of the confidence interval method to be used when considering rare event simulation, which is an unfamiliar topic in the field of dependability. Last, an application to an industrial case permits the illustration of the potential of our solution methodology.

許多公司在發行公司債的時候，會給此公司債一個可提前贖回的特性，此種公司債稱為可贖回公司債(Callable Bond)，用來規避利率變動風險的金融商品也與我們熟知的利率交換不同，稱為可取消利率交換(Cancelable Swap)。其實可取消利率交換可以拆解成百慕達利率交換選擇權(Bermudan Swaption)加上利率交換，由於利率交換之評價較簡單也有市場一致的評價方法，因此百慕達利率交換選擇權便成為評價的重點。 評價的部分，由於百慕達式的商品有提前履約的特性，造成其封閉解不存在，因此需要利用其他的近似解或是數值方法來求它的價格。由於本文採用BGM(1997)的市場利率模型(Libor Market Model)，其高維度的性質導致數狀方法與有限差分法使用起來較無效率，因此本文選擇使用蒙地卡羅法做為評價的方法，同時利用Longstaff and Schwartz(2001)的最小平方蒙地卡羅法(Least Squares Monte Carlo Method)來解決提前履約的問題。 最後，本文將採用2種利率波動度假設與2種不同利率間相關係數的假設，共4種組合，在歐式利率交換選擇權的市場波動度下進行校準，使用校準出來的參數進行評價來得到4種價格。再進行商品的敏感度分析(Sensitivity Analysis)和風險值(Value at Risk)的計算。

Ziel dieser Arbeit ist zunächst die Entwicklung einer Vergleichsgrundlage, auf Basis derer Algorithmen zur Berechnung der Zustandsdichte verglichen werden können. Darauf aufbauend wird ein bestehendes übergangsmatrixbasiertes Verfahren für das großkanonisch Ensemble um ein neues Auswerteverfahren erweitert. Dazu werden numerische Untersuchungen verschiedener Monte-Carlo-Algorithmen zur Berechnung der Zustandsdichte durchgeführt. Das Hauptaugenmerk liegt dabei auf Verfahren, die auf Übergangsmatrizen basieren, sowie auf dem Verfahren von Wang und Landau. Im ersten Teil der Forschungsarbeit wird ein umfassender Überblick über Monte-Carlo-Methoden und Auswerteverfahren zur Bestimmung der Zustandsdichte sowie über verwandte Verfahren gegeben. Außerdem werden verschiedene Methoden zur Berechnung der Zustandsdichte aus Übergangsmatrizen vorgestellt und diskutiert. Im zweiten Teil der Arbeit wird eine neue Vergleichsgrundlage für Algorithmen zur Bestimmung der Zustandsdichte erarbeitet. Dazu wird ein neues Modellsystem entwickelt, an dem verschiedene Parameter frei gewählt werden können und für das die exakte Zustandsdichte sowie die exakte Übergangsmatrix bekannt sind. Anschließend werden zwei weitere Systeme diskutiert für welche zumindest die exakte Zustandsdichte bekannt ist: das Ising Modell und das Lennard-Jones System. Der dritte Teil der Arbeit beschäftigt sich mit numerischen Untersuchungen an einer Auswahl der vorgestellten Verfahren. Auf Basis der entwickelten Vergleichsgrundlage wird der Einfluss verschiedener Parameter auf die Qualität der berechneten Zustandsdichte quantitativ bestimmt. Es wird gezeigt, dass Übergangsmatrizen in Simulationen mit Wang-Landau-Verfahren eine wesentlich bessere Zustandsdichte liefern als das Verfahren selbst. Anschließend werden die gewonnenen Erkenntnisse genutzt um ein neues Verfahren zu entwickeln mit welchem die Zustandsdichte mittels Minimierung der Abweichungen des detaillierten Gleichgewichts aus großen, dünnbesetzten Übergangsmatrizen gewonnen werden kann. Im Anschluss wird ein Lennard-Jones-System im großkanonischen Ensemble untersucht. Es wird gezeigt, dass durch das neue Verfahren Zustandsdichte und Dampfdruckkurve bestimmt werden können, welche qualitativ mit Referenzdaten übereinstimmen.

本文實證探討黃金期貨報酬率的特性並在標的黃金期貨價格遵循狀態轉換跳躍擴散過程時實現美式選擇權之評價。在這樣的動態過程下，跳躍事件被一個複合普瓦松過程與對數常態跳躍振幅所描述，以及狀態轉換到達強度是由一個其狀態代表經濟狀態的隱藏馬可夫鏈所捕捉。考量不同的跳躍風險假設，我們使用Merton測度與Esscher轉換推導出在一個不完全市場設定下的風險中立黃金期貨價格動態過程。為了達到所需的精確度，最小平方蒙地卡羅法被用來近似美式黃金期貨選擇權的價值。基於實際市場資料，我們提供實證與數值結果來說明這個動態模型的優點。 / This dissertation empirically investigates the characteristics of gold futures returns and achieves the valuation of American-style options when the underlying gold futures price follows a regime-switching jump-diffusion process. Under such dynamics, the jump events are described as a compound Poisson process with a log-normal jump amplitude, and the regime-switching arrival intensity is captured by a hidden Markov chain whose states represent the economic states. Considering the different jump risk assumptions, we use the Merton measure and Esscher transform to derive risk-neutral gold futures price dynamics under an incomplete market setting. To achieve a desired accuracy level, the least-squares Monte Carlo method is used to approximate the values of American gold futures options. Our empirical and numerical results based on actual market data are provided to illustrate the advantages of this dynamic model.