Optimization is a very important field with diverse applications in physical, social and biological sciences and in various areas of engineering. It appears widely in ma-chine learning, information retrieval, regression, estimation, operations research and a wide variety of computing domains. The subject is being deeply studied both theoretically and experimentally and several algorithms are available in the literature. These algorithms which can be executed (sequentially or concurrently) on a computing machine explore the space of input parameters to seek high quality solutions to the optimization problem with the search mostly guided by certain structural properties of the objective function. In certain situations, the setting might additionally demand for “absolute optimum” or solutions close to it, which makes the task even more challenging. In this thesis, we propose an optimization algorithm which is “gradient-free”, i.e., does not employ any knowledge of the gradient or higher order derivatives of the objective function, rather utilizes objective function values themselves to steer the search. The proposed algorithm is particularly effective in a black-box setting, where a closed-form expression of the objective function is unavailable and gradient or higher-order derivatives are hard to compute or estimate. Our algorithm is inspired by the well known cross entropy (CE) method. The CE method is a model based search method to solve continuous/discrete multi-extremal optimization problems, where the objective function has minimal structure. The proposed method seeks, in the statistical manifold of the parameters which identify the probability distribution/model defined over the input space to find the degenerate distribution concentrated on the global optima (assumed to be finite in quantity). In the early part of the thesis, we propose a novel stochastic approximation version of the CE method to the unconstrained optimization problem, where the objective function is real-valued and deterministic. The basis of the algorithm is a stochastic process of model parameters which is probabilistically dependent on the past history, where we reuse all the previous samples obtained in the process till the current instant based on discounted averaging. This approach can save the overall computational and storage cost. Our algorithm is incremental in nature and possesses attractive features such as stability, computational and storage efficiency and better accuracy. We further investigate, both theoretically and empirically, the asymptotic behaviour of the algorithm and find that the proposed algorithm exhibits global optimum convergence for a particular class of objective functions. Further, we extend the algorithm to solve the simulation/stochastic optimization problem. In stochastic optimization, the objective function possesses a stochastic characteristic, where the underlying probability distribution in most cases is hard to comprehend and quantify. This begets a more challenging optimization problem, where the ostentatious nature is primarily due to the hardness in computing the objective function values for various input parameters with absolute certainty. In this case, one can only hope to obtain noise corrupted objective function values for various input parameters. Settings of this kind can be found in scenarios where the objective function is evaluated using a continuously evolving dynamical system or through a simulation. We propose a multi-timescale stochastic approximation algorithm, where we integrate an additional timescale to accommodate the noisy measurements and decimate the effects of the gratuitous noise asymptotically. We found that if the objective function and the noise involved in the measurements are well behaved and the timescales are compatible, then our algorithm can generate high quality solutions. In the later part of the thesis, we propose algorithms for reinforcement learning/Markov decision processes using the optimization techniques we developed in the early stage. MDP can be considered as a generalized framework for modelling planning under uncertainty. We provide a novel algorithm for the problem of prediction in reinforcement learning, i.e., estimating the value function of a given stationary policy of a model free MDP (with large state and action spaces) using the linear function approximation architecture. Here, the value function is defined as the long-run average of the discounted transition costs. The resource requirement of the proposed method in terms of computational and storage cost scales quadratically in the size of the feature set. The algorithm is an adaptation of the multi-timescale variant of the CE method proposed in the earlier part of the thesis for simulation optimization. We also provide both theoretical and empirical evidence to corroborate the credibility and effectiveness of the approach. In the final part of the thesis, we consider a modified version of the control problem in a model free MDP with large state and action spaces. The control problem most commonly addressed in the literature is to find an optimal policy which maximizes the value function, i.e., the long-run average of the discounted transition payoffs. The contemporary methods also presume access to a generative model/simulator of the MDP with the hidden premise that observations of the system behaviour in the form of sample trajectories can be obtained with ease from the model. In this thesis, we consider a modified version, where the cost function to be optimized is a real-valued performance function (possibly non-convex) of the value function. Additionally, one has to seek the optimal policy without presuming access to the generative model. In this thesis, we propose a stochastic approximation algorithm for this peculiar control problem. The only information, we presuppose, available to the algorithm is the sample trajectory generated using a priori chosen behaviour policy. The algorithm is data (sample trajectory) efficient, stable, robust as well as computationally and storage efficient. We provide a proof of convergence of our algorithm to a high performing policy relative to the behaviour policy.

La présente thèse a pour objectif principal de développer des approches déterministes et heuristiques pour résoudre certaines classes de problèmes d'optimisation en Finance, Affectation et Recherche d’Informations. Il s’agit des problèmes d’optimisation non convexe de grande dimension. Nos approches sont basées sur la programmation DC&DCA et la méthode Cross-Entropy (CE). Grâce aux techniques de formulation/reformulation, nous avons donné la formulation DC des problèmes considérés afin d’obtenir leurs solutions en utilisant DCA. En outre, selon la structure des ensembles réalisables de problèmes considérés, nous avons conçu des familles appropriées de distributions pour que la méthode Cross-Entropy puisse être appliquée efficacement. Toutes ces méthodes proposées ont été mises en œuvre avec MATLAB, C/C++ pour confirmer les aspects pratiques et enrichir notre activité de recherche. / In this thesis we focus on developing deterministic and heuristic approaches for solving some classes of optimization problems in Finance, Assignment and Search Information. They are large-scale nonconvex optimization problems. Our approaches are based on DC programming & DCA and the Cross-Entropy method. Due to the techniques of formulation/reformulation, we have given the DC formulation of considered problems such that we can use DCA to obtain their solutions. Also, depending on the structure of feasible sets of considered problems, we have designed appropriate families of distributions such that the Cross-Entropy method could be applied efficiently. All these proposed methods have been implemented with MATLAB, C/C++ to confirm the practical aspects and enrich our research works.

[pt] A avaliação de confiabilidade da capacidade de geração é extremamente útil em diversos estudos de planejamento da expansão, na avaliação dos riscos relacionados ao dimensionamento da reserva operativa e também na programação da manutenção de unidades geradoras. O principal objetivo é avaliar se uma determinada configuração de unidades de geração atende de forma aceitável à carga do sistema, assumindo que os equipamentos de transmissão sejam totalmente confiáveis e sem limitações de capacidade. Na última década, a inserção de fontes renováveis nos sistemas elétricos de potência tem crescido de forma acentuada, na grande maioria dos países desenvolvidos como também em desenvolvimento. As flutuações de suas capacidades de geração se tornaram parte da complexidade do problema de planejamento e operação de redes elétricas, uma vez que dependem das condições ambientais em que foram instaladas. Além disso, representações detalhadas da carga têm se tornado uma preocupação a mais de muitos planejadores, tendo em vista as análises de risco ao atendimento da demanda nessas redes. Novos modelos e ferramentas computacionais devem ser desenvolvidos para tratar dessas variáveis principalmente com dependência espaço-temporal. Esta dissertação apresenta diversos estudos para avaliar a confiabilidade da capacidade de sistemas de geração via simulação Monte Carlo quasi-sequencial (SMC-QS), considerando fontes de geração e carga com forte dependência espaço-temporal. Esta ferramenta é escolhida devido à sua fácil implementação computacional e capacidade de simular eventos cronológicos. A técnica de redução de variância denominada amostragem por importância baseada no método Cross Entropy (CE) foi utilizada em conjunto com a SMC-QS. As simulações terão como base o sistema teste IEEE-RTS 96, o qual é adequada-mente modificado para incluir fontes renováveis eólicas e hídricas. Portanto, o principal objetivo desta dissertação é definir a melhor maneira de lidar com as séries temporais representativas da geração renovável e carga, nos diferentes estágios do método SMC-QS via CE, de modo a maximizar sua eficiência computacional. Vários testes de simulação são realizados com o sistema IEEE-RTS 96 modificado e os resultados obtidos são amplamente discutidos. / [en] The reliability evaluation of the generating capacity is extremely useful in several expansion planning studies, in the assessment of risks related to the requirements of the operating reserve and also in the scheduling of maintenance of generating units. The main objective is to assess whether a given generating configuration meets the system load in an acceptable manner, assuming that the transmission equipment is completely reliable and without capacity limitations. In the last decade, the insertion of renewable sources in electrical power systems has grown markedly, in the vast majority of developed and developing countries. Fluctuations in their generation capacities have become part of the complexity of the problem of planning and operating electrical networks, since they depend on the environmental conditions in which they are installed. In addition, detailed representations of the load have become a concern among many planners, given the risk analyzes to meet demand in these networks. New computational models and tools must be developed to deal with these variables mainly with space-time dependence. This dissertation presents several studies to evaluate the reliability of the capacity of generation systems via quasi-sequential Monte Carlo simulation (QS-MCS), considering generation and load sources with strong space-time dependence. This tool is chosen due to its easy computational implementation and the ability to simulate chronological events. The variance reduction technique named importance sampling based on the cross-entropy (CE) method is used in conjunction with the QS-MCS. The simulations will be carried out with the IEEE-RTS 96 test system, which is adequately modified to include renewable wind and hydro sources. Therefore, the main objective of this dissertation is to define the best way to deal with the time series representing the renewable generation and load, in the different stages of the SMC-QS method via CE, in order to maximize its computational efficiency. Several simulation tests are performed with the modified IEEE-RTS 96 system and the obtained results are widely discussed.

[pt] A reserva girante é a parcela da reserva operativa provida por geradores sincronizados, e interligados à rede de transmissão, aptos a suprir a demanda na ocorrência de falhas de unidades de geração, erros na previsão da demanda, variações de capacidade de fontes renováveis ou qualquer outro fator inesperado. Dada sua característica estocástica, essa parcela da reserva operativa é mais adequadamente avaliada por meio de métodos capazes de representar as incertezas inerentes ao seu dimensionamento e planejamento. Por meio do risco de corte de carga é possível comparar e classificar distintas configurações do sistema elétrico, garantindo a não violação dos requisitos de confiabilidade. Sistemas com elevada penetração de fontes renováveis apresentam comportamento mais complexo devido ao aumento das incertezas envolvidas, à forte dependência de fatores energético-climáticos e às variações de capacidade destas fontes. Para avaliar as correlações temporais e representar a cronologia de ocorrência dos eventos no curto-prazo, um estimador baseado na Simulação Monte Carlo Quase Sequencial é apresentado. Nos estudos de planejamento da operação de curto-prazo o horizonte em análise é de minutos a algumas horas. Nestes casos, a ocorrência de falhas em equipamentos pode apresentar baixa probabilidade e contingências que causam corte de carga podem ser raras. Considerando a raridade destes eventos, as avaliações de risco são baseadas em técnicas de amostragem por importância. Os parâmetros de simulação são obtidos por um processo numérico adaptativo de otimização estocástica, utilizando os conceitos de Entropia Cruzada. Este trabalho apresenta uma metodologia de avaliação dos montantes de reserva girante em sistemas com participação de fontes renováveis, em uma abordagem multiárea. O risco de perda de carga é estimado considerando falhas nos sistemas de geração e transmissão, observando as restrições de transporte e os limites de intercâmbio de potência entre as diversas áreas elétricas. / [en] The spinning reserve is the portion of the operational reserve provided by synchronized generators and connected to the transmission network, capable of supplying the demand considering generating unit failures, errors in load forecasting, capacity intermittency of renewable sources or any other unexpected factor. Given its stochastic characteristic, this portion of the operating reserve is more adequately evaluated through methods capable of modeling the uncertainties inherent in its design and planning. Based on the loss of load risk, it is possible to compare different configurations of the electrical system, ensuring the non-violation of reliability requirements. Systems with high penetration of renewable sources present a more complex behavior due to the number of uncertainties involved, strong dependence of energy-climatic factors and variations in the capacity of these sources. In order to evaluate the temporal correlations and to represent the chronology of occurrence of events in the short term, an estimator based on quasi-sequential Monte Carlo simulation is presented. In short-term operation planning studies, the horizon under analysis is from minutes to a few hours. In these cases, the occurrence of equipment failures may present low probability and contingencies that cause load shedding may be rare. Considering the rarity of these events, risk assessments are based on importance sampling techniques. The simulation parameters are obtained by an adaptive numerical process of stochastic optimization, using the concept of Cross Entropy. This thesis presents a methodology for evaluating the amounts of spinning reserve in systems with high penetration of renewable sources, in a multi-area approach. The risk of loss of load is estimated considering failures in the generation and transmission systems, observing the network restrictions and the power exchange limits between the different electric areas.

En raison de la gravité des accidents liés au phénomène de fatigue-propagation de fissure, les préoccupations de l’industrie aéronautique à assurer l’intégrité des structures soumises à ce mode de sollicitation revêtent un caractère tout à fait essentiel. Les travaux de thèse présentés dans ce mémoire visent à appréhender le problème de sûreté des structures aéronautiques dimensionnées en tolérance aux dommages sous l’angle probabiliste. La formulation et l’application d’une approche fiabiliste menant à des processus de conception et de maintenance fiables des structures aéronautiques en contexte industriel nécessitent cependant de lever un nombre important de verrous scientifiques. Les efforts ont été concentrés au niveau de trois domaines dans ce travail. Une méthodologie a tout d’abord été développée afin de capturer et de retranscrire fidèlement l’aléa du chargement de fatigue à partir de séquences de chargement observées sur des structures en service et monitorées, ce qui constitue une réelle avancée scientifique. Un deuxième axe de recherche a porté sur la sélection d’un modèle mécanique apte à prédire l’évolution de fissure sous chargement d’amplitude variable à coût de calcul modéré. Les travaux se sont ainsi appuyés sur le modèle PREFFAS pour lequel des évolutions ont également été proposées afin de lever l’hypothèse restrictive de périodicité de chargement. Enfin, les analyses probabilistes, produits du couplage entre le modèle mécanique et les modélisations stochastiques préalablement établies, ont entre autre permis de conclure que le chargement est un paramètre qui influe notablement sur la dispersion du phénomène de propagation de fissure. Le dernier objectif de ces travaux a ainsi porté sur la formulation et la résolution du problème de fiabilité en tolérance aux dommages à partir des modèles stochastiques retenus pour le chargement, constituant un réel enjeu scientifique. Une méthode de résolution spécifique du problème de fiabilité a été mise en place afin de répondre aux objectifs fixés et appliquée à des structures jugées représentatives de problèmes réels. / Ensuring the integrity of structural components subjected to fatigue loads remains an increasing concern in the aerospace industry due to the detrimental accidents that might result from fatigue and fracture processes. The research works presented here aim at addressing the question of aircraft safety in the framework of probabilistic fracture mechanics. It should be noticed that a large number of scientific challenges requires to be solved before performing comprehensive probabilistic analyses and assessing the mechanical reliability of components or structures in an industrial context. The contributions made during the PhD are reported here. Efforts are provided on each step of the global probabilistic methodology. The modeling of random fatigue load sequences based on real measured loads, which represents a key and original step in stochastic damage tolerance, is first addressed. The second task consists in choosing a model able to predict the crack growth under variable amplitude loads, i.e. which accounts for load interactions and retardation/acceleration effects, at a moderate computational cost. The PREFFAS crack closure model is selected for this purpose. Modifications are brought in order to circumvent the restrictive assumption of stationary load sequences. Finally, probabilistic analyses resulting from the coupling between the PREFFAS model and the stochastic modeling are carried out. The following conclusion can especially be drawn. Scatter in fatigue loads considerably affects the dispersion of the crack growth phenomenon. Then, it must be taken into account in reliability analyses. The last part of this work focuses on phrasing and solving the reliability problem in damage tolerance according to the selected stochastic loading models, which is a scientific challenge. A dedicated method is established to meet the required objectives and applied to structures representative of real problems.