We consider unconstrained Simulation Optimization (SO) problems, that is, optimization problems where the underlying objective function is unknown but can be estimated at any chosen point by repeatedly executing a Monte Carlo (stochastic) simulation. SO, introduced more than six decades ago through the seminal work of Robbins and Monro (and later by Kiefer and Wolfowitz), has recently generated much attention. Such interest is primarily because of SOs flexibility, allowing the implicit specification of functions within the optimization problem, thereby providing the ability to embed virtually any level of complexity. The result of such versatility has been evident in SOs ready adoption in fields as varied as finance, logistics, healthcare, and telecommunication systems. While SO has become popular over the years, Robbins and Monros original stochastic approximation algorithm and its numerous modern incarnations have seen only mixed success in solving SO problems. The primary reason for this is stochastic approximations explicit reliance on a sequence of algorithmic parameters to guarantee convergence. The theory for choosing such parameters is now well-established, but most such theory focuses on asymptotic performance. Automatically choosing parameters to ensure good finite-time performance has remained vexingly elusive, as evidenced by continuing efforts six decades after the introduction of stochastic approximation! The other popular paradigm to solve SO is what has been called sample-average approximation. Sample-average approximation, more a philosophy than an algorithm to solve SO, attempts to leverage advances in modern nonlinear programming by first constructing a deterministic approximation of the SO problem using a fixed sample size, and then applying an appropriate nonlinear programming method. Sample-average approximation is reasonable as a solution paradigm but again suffers from finite-time inefficiency because of the simplistic manner in which sample sizes are prescribed. It turns out that in many SO contexts, the effort expended to execute the Monte Carlo oracle is the single most computationally expensive operation. Sample-average approximation essentially ignores this issue since, irrespective of where in the search space an incumbent solution resides, prescriptions for sample sizes within sample-average approximation remain the same. Like stochastic approximation, notwithstanding beautiful asymptotic theory, sample-average approximation suffers from the lack of automatic implementations that guarantee good finite-time performance. In this dissertation, we ask: can advances in algorithmic nonlinear programming theory be combined with intelligent sampling to create solution paradigms for SO that perform well in finite-time while exhibiting asymptotically optimal convergence rates? We propose and study a general solution paradigm called Sampling Controlled Stochastic Recursion (SCSR). Two simple ideas are central to SCSR: (i) use any recursion, particularly one that you would use (e.g., Newton and quasi- Newton, fixed-point, trust-region, and derivative-free recursions) if the functions involved in the problem were known through a deterministic oracle; and (ii) estimate objects appearing within the recursions (e.g., function derivatives) using Monte Carlo sampling to the extent required. The idea in (i) exploits advances in algorithmic nonlinear programming. The idea in (ii), with the objective of ensuring good finite-time performance and optimal asymptotic rates, minimizes Monte Carlo sampling by attempting to balance the estimated proximity of an incumbent solution with the sampling error stemming from Monte Carlo. This dissertation studies the theoretical and practical underpinnings of SCSR, leading to implementable algorithms to solve SO. We first analyze SCSR in a general context, identifying various sufficient conditions that ensure convergence of SCSRs iterates to a solution. We then analyze the nature of such convergence. For instance, we demonstrate that in SCSRs which guarantee optimal convergence rates, the speed of the underlying (deterministic) recursion and the extent of Monte Carlo sampling are intimately linked, with faster recursions permitting a wider range of Monte Carlo effort. With the objective of translating such asymptotic results into usable algorithms, we formulate a family of SCSRs called Adaptive SCSR (A-SCSR) that adaptively determines how much to sample as a recursion evolves through the search space. A-SCSRs are dynamic algorithms that identify sample sizes to balance estimated squared bias and variance of an incumbent solution. This makes the sample size (at every iteration of A-SCSR) a stopping time, thereby substantially complicating the analysis of the behavior of A-SCSRs iterates. That A-SCSR works well in practice is not surprising" the use of an appropriate recursion and the careful sample size choice ensures this. Remarkably, however, we show that A-SCSRs are convergent to a solution and exhibit asymptotically optimal convergence rates under conditions that are no less general than what has been established for stochastic approximation algorithms. We end with the application of a certain A-SCSR to a parameter estimation problem arising in the context of brain-computer interfaces (BCI). Specifically, we formulate and reduce the problem of probabilistically deciphering the electroencephalograph (EEG) signals recorded from the brain of a paralyzed patient attempting to perform one of a specified set of tasks. Monte Carlo simulation in this context takes a more general view, as the act of drawing an observation from a large dataset accumulated from the recorded EEG signals. We apply A-SCSR to nine such datasets, showing that in most cases A-SCSR achieves correct prediction rates that are between 5 and 15 percent better than competing algorithms. More importantly, due to the incorporated adaptive sampling strategies, A-SCSR tends to exhibit dramatically better efficiency rates for comparable prediction accuracies. / Ph. D.

[pt] Esta Dissertação procura, sob um enfoque freqüentista, discutir tecnologias para que se imponham restrições no processo de estimação de componentes não observáveis associadas a um modelo em Espaço de Estado (EE) arbitrário. O escopo do texto abrange desde procedimentos propostos pioneiramente por Howard Doran para restrições de igualdade, lineares e/ou não lineares, invariantes ou variantes no tempo, em modelos em EE lineares, até a adoção e o ajuste de estruturas mais delicadas, como os modelos em EE não lineares. Entende-se que estes últimos se constituem em uma alternativa relevante, caso seja requerida, por exemplo, a imposição de restrições de desigualdade. Técnicas e estratégias de implementação são apresentadas, debatidas e comparadas, incluindo-se também o processo de estimação de parâmetros desconhecidos e a questão de diagnósticos. Ao final, são apresentados exercícios empíricos com base nas tecnologias discutidas. Os modelos propostos para esta ilustração visam à realização da análise dinâmica de estilo baseado no retorno para carteiras de investimento brasileiras (a versão estática desses modelos fora introduzida por William Sharpe, para carteiras norte-americanas), os quais devem, eventualmente, abranger dois tipos de restrições nas componentes de interesse, quais sejam, um de igualdade e outro de desigualdade. / [en] This Dissertation aims, in a frequentist way, to discuss technologies for imposing restrictions in non-observable components associated with an arbitrary State Space (SS) model. The text scope ranges from procedures proposed originally by Howard Doran for equality, linear or non- linear, time invariant or time varying restrictions in a linear SS model, to adoption and estimation of more complicated structures like non-linear SS models. It is understood that these last ones are a relevant alternative, in cases of, for instance, inequality restrictions requirement. Implementation techniques and strategies are given, debated and compared, also including unknown parameters estimation and diagnostics analysis. At the end, empirical exercises are presented based on discussed methodologies. The proposed models for this illustration aim at dynamic return based style analysis for Brazilian investment portfolios (the static version of these models had been introduced by William Sharpe, for American portfolios), which shall eventually satisfy two kinds of restrictions on components of interest, namely one of equality and other of inequality.

Nous considérions des modèles à espace d'état où les observations sont multicatégorielles et longitudinales, et l'état est décrit par des modèles du type CHARN. Nous estimons l'état au moyen des récursivités de Kalman généralisées. Celles-ci reposent sur l'application d'une variété de filtres particulaires et de l’algorithme EM. Nos résultats sont appliqués à l'estimation du trait latent en qualité de vie. Ce qui fournit une alternative et une généralisation des méthodes existantes dans la littérature. Ces résultats sont illustrés par des simulations numériques et une application aux données réelles sur la qualité de vie des femmes ayant subi une opération pour cause de cancer du sein / We consider state space models where the observations are multicategorical and longitudinal, and the state is described by CHARN models. We estimate the state by generalized Kalman recursions, which rely on a variety of particle filters and EM algorithm. Our results are applied to estimating the latent trait in quality of life, and this furnishes an alternative and a generalization of existing methods. These results are illustrated by numerical simulations and an application to real data in the quality of life of patients surged for breast cancer