Orientador: José Mario Martínez Perez / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica. / Made available in DSpace on 2018-08-19T04:47:30Z (GMT). No. of bitstreams: 1 Bueno_LuisFelipeCesardaRocha_D.pdf: 2718304 bytes, checksum: ca1c9aa7730e88989e17a5b89049c2ee (MD5) Previous issue date: 2011 / Resumo: Nesse trabalho serão propostos métodos de Lagrangiano Aumentado para tratar problemas com restrições do tipo LOVO, serão propostos novos métodos de Restauração Inexata e será introduzido o conceito de Equilíbrio Inverso de Nash. Teoremas sobre condições de otimalidade para problemas do tipo LOVO serão apresentados. Um algoritmo do tipo Lagrangiano Aumentado será proposto para abordar esse problema e teoremas de convergência global serão demonstrados. Resultados computacionais serão realizados para uma aplicação em otimização de carteiras em investimentos de grande impacto. Um método híbrido de Restauração Inexata será proposto combinando uma modificação, que usa o Lagrangiano Afiado como função de mérito, do método global de Fischer e Friedlander e o método local de Birgin e Martínez. Teoremas de convergência global e local serão apresentados. Um método de Restauração Inexata para problemas em que as derivadas da função objetivo não estejam disponíveis será introduzido. Nesse método todas as ferramentas da otimização tradicional serão usadas na fase de restauração e uma regularização será feita na fase de otimização. Teoremas de convergência global serão demonstrados e resultados numéricos apresentados. O conceito de Equilíbrio Inverso de Nash será introduzido e um método de Restauração Inexata será proposto para abordar esse problema. Esse método será uma extensão de um novo método de Restauração Inexata para problemas em dois níveis que também será proposto neste trabalho. Exemplos ilustrativos para uma aplicação para o problema de equilíbrio de Arrow-Debreu serão exibidos / Abstract: In this work an Augmented Lagrangian method will be proposed to deal with LOVO constraints, also some new Inexact Restoration methods will be presented and the Inverse Nash Equilibrium concept will be introduced. Theorems about optimality conditions for LOVO-like problems will be presented. Three Augmented Lagrangian algorithms will be proposed to approach this problem and global convergence theorems will be proved. Computational results will be performed for an application in portfolio optimization with impact. A modification of the Fischer-Friedlander global method using the Sharp Lagrangian as a merit function will be proposed. A hybrid Inexact Restoration method combining this modification and the Birgin-Martínez local method will be introduced. Global and local convergence theorems will be presented. An Inexact Restoration method for problems in which the derivatives of the objective function are not available will be introduced. In this method it will be used all the optimization traditional tools in the restoration process as well as a regularization strategy in the optimization phase. Global convergence theorems will be demonstrated and numerical results will be presented. The concept of Inverse Nash Equilibrium will be introduced and an Inexact Restoration method will be proposed to deal with this problem. This method is an extension of a new Inexact Restoration method for bilevel programming that will also be proposed in this work. Some illustrative examples for an application for the Arrow- Debreu equilibrium problem will be given / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

Orientadores: Márcia Aparecida Gomes Ruggiero, Sandra Augusta Santos / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-21T10:21:10Z (GMT). No. of bitstreams: 1 Begiato_RodolfoGotardi_D.pdf: 3815627 bytes, checksum: 59584610cfd737a94e68dc5bf3735e25 (MD5) Previous issue date: 2012 / Resumo: O objetivo desta tese é tratar da resolução de sistemas não lineares de grande porte, em que as funções são continuamente diferenciáveis, por meio de uma abordagem híbrida que utiliza um método iterativo com duas fases. A primeira fase consiste de versões sem derivadas do método do ponto fixo empregando parâmetros espectrais para determinar o tamanho do passo da direção residual. A segunda fase é constituída pelo método de Newton inexato em uma abordagem matrix-free, em que é acoplado o método GMRES para resolver o sistema linear que determina a nova direção de busca. O método híbrido combina ordenadamente as duas fases de forma que a segunda é acionada somente em caso de falha na primeira e, em ambas, uma condição de decréscimo não-monótono deve ser verificada para aceitação de novos pontos. Desenvolvemos ainda um segundo método, em que uma terceira fase de busca direta é acionada em situações em que o excesso de buscas lineares faz com que o tamanho de passo na direção do método de Newton inexato torne-se demasiadamente pequeno. São estabelecidos os resultados de convergência dos métodos propostos. O desempenho computacional é avaliado em uma série de testes numéricos com problemas tradicionalmente encontrados na literatura. Tanto a análise teórica quanto a numérica evidenciam a viabilidade das abordagens apresentadas neste trabalho / Abstract: This thesis handles large-scale nonlinear systems for which all the involved functions are continuously differentiable. They are solved by means of a hybrid approach based on an iterative method with two phases. The first phase is defined by derivative-free versions of a fixed-point method that employs spectral parameters to define the steplength along the residual direction. The second phase consists of a matrix-free inexact Newton method that employs the GMRES to solve the linear system that computes the search direction. The proposed hybrid method neatly combines the two phases in such a way that the second is called only in case the first one fails. To accept new points in both phases, a nonmonotone decrease condition upon a merit function has to be verified. A second method is developed as well, with a third phase based on direct search, that should act whenever too many line searches have excessively decreased the steplenght along the inexact- Newton direction. Convergence results for the proposed methods are established. The computational performance is assessed in a set of numerical experiments with problems from the literature. Both the theoretical and the experimental analysis corroborate the feasibility of the proposed strategies / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

Différentes techniques de chirurgie mini-invasive permettent aujourd’hui d’effectuer les procédures d'ablation de tumeurs. La cryochirurgie est une de ces techniques et fonctionne grâce à une technique de décompression très rapide de l'argon à l’extrémité d’une sonde en forme d'aiguille. La planification pré-opératoire de ce type d’intervention est très difficile pour le chirurgien, qui doit se représenter mentalement la disposition finale des aiguilles par rapport à la position des structures anatomiques complexe. Une sur-ablation ou une sous-ablation peuvent entraîner des complications donc, devant le besoin crucial d'une telle planification, dans cette thèse nous nous sommes concentrés sur la planification pré-opératoire automatisée de la cryochirurgie,avec les objectifs de assister le chirurgien grâce à une prédiction plus réaliste des zones d'ablation et proposer automatiquement un placement d'aiguille avec un risque minimal pour le patient dans un délai acceptable pour une utilisation en salle d'opération. / There exist several minimally invasive techniques to perform tumor ablation procedures.Cryosurgery is one of these techniques and works by decompressing very rapidly the argon gas through a needle-like probe. It is hard for the surgeons to imagine final results and plan the surgery in advance in a complicated anatomical environment. Over-ablation or under ablation may result in complications during the treatment. So, due to a crucial need for having such a planning tool, in this thesis we focused on an automated pre-surgical planning for cryosurgery with goals to support the physician by utilizing a more realistic prediction of ablation zones and proposing a needle placement setup with a close to minimum risk to the patient and an optimal coverage of the tumor by the iceball in an acceptable time for the use in the operation room.

The unimodality of a function seems a simple concept. But in the Euclidean space R^m, m=3,4,..., it is not easy to define. We have an easy tool to find the minimum point of a unimodal function. The goal of this project is to formalize and support distinctive strategies that typically guarantee convergence. Support is given both by analytic arguments and simulation study. Application is envisioned in low-dimensional but non-trivial problems. The convergence of the proposed iterated grid search algorithm is presented along with the results of particular application studies. It has been recognized that the derivative methods, such as the Newton-type method, are not entirely satisfactory, so a variety of other tools are being considered as alternatives. Many other tools have been rejected because of apparent manipulative difficulties. But in our current research, we focus on the simple algorithm and the guaranteed convergence for unimodal function to avoid the possible chaotic behavior of the function. Furthermore, in case the loss function to be optimized is not unimodal, we suggest a weaker condition: almost (noisy) unimodality, under which the iterated grid search finds an estimated optimum point. / Ph. D.

<p>U disertaciji su posmatrani projektivni postupci tipa konjugovanih gradijenata za re&scaron;avanje nelinearnih monotonih sistema velikih dimenzija. Ovi postupci kombinuju projektivnu metodu sa pravcima pretraživanja tipa konjugovanih gradijenata. Zbog osobine monotonosti sistema, projektivna metoda omogućava jednostavnu globalizaciju, a pravci pretraživanja tipa konjugovanih gradijenata zahtevaju malo<br />računarske memorije pa su pogodni za re&scaron;avanje sistema velikih dimenzija. Projektivni postupci tipa konjugovanih gradijenata ne koriste izvode niti funkciju cilja i zasnovani su samo na izračunavanju vrednosti funkcije sistema, pa su pogodni i za re&scaron;avanje neglatkih monotonih sistema. Po&scaron;to se globalna konvergencija dokazuje bez pretpostavki o regularnosti, ovi postupci se mogu koristiti i za re&scaron;avanje sistema sa singularnim re&scaron;enjima. U disertaciji su definisana tri nova tročlana pravca pretraživanja<br />tipa Flečer-Rivs i dva nova hibridna pravca tipa Hu-Stori. Formulisani su projektivni postupci sa novim pravcima pretraživanja i dokazana je njihova globalna konvergencija. Numeričke performanse postupaka testirane su na relevantnim primerima i poređene sa poznatim postupcima iz literature. Numerički rezultati potvrđuju da su novi postupci robusni, efikasni i uporedivi sa postojećim postupcima.</p> / <p>Projection based CG methods for solving large-scale nonlinear monotone systems are considered in this thesis. These methods combine hyperplane projection technique with conjugate gradient (CG) search directions. Hyperplane projection method is suitable for monotone systems, because it enables simply globalization, while CG directions are efficient for large-scale nonlinear systems, due to low memory. Projection based CG methods are funcion-value based, they don&rsquo;t use merit function and derivatives, and because of that they are also suitable for solving nonsmooth monotone systems. The global convergence of these methods are ensured without additional regularity assumptions, so they can be used for solving singular systems.Three new three-term search directions of Fletcher-Reeves type and two new hybrid search directions of Hu-Storey type are defined. PCG algorithm with five new CG type directions is proposed and its global convergence is established. Numerical performances of methods are tested on relevant examples from literature. These results point out that new projection based CG methods have good computational performances. They are efficient, robust and competitive with other methods.</p>

Made available in DSpace on 2016-12-23T14:33:32Z (GMT). No. of bitstreams: 1 Joao Olavo Baiao de Vasconcelos.pdf: 325868 bytes, checksum: 0459e6ca76a321095f4fc0d37ab23f21 (MD5) Previous issue date: 2011-12-21 / Petroleum Engineer activity is constantly enrolled on a series of optimization problems on many contexts, as, for instance, defining efficient and optimized projects on petroleum reserves development. However, there is an extreme difficulty on resolution of exploration and production (P&E) optimization problems, since they are often complex, with high degree of nonlinearity, presenting high uncertain number, and huge computational cost involved. Among them, there is the problem of determining the best throughput distribution among the wells of a petroleum production platform that achieves the biggest financial profitability of an E&P project, here named Petroleum Well Throughput Optimization Problem (PWTOP). In order to deal with PWTOP, some continuous optimization algorithms that deals with linearity restrictions present on the problem were studied, that are the Derivative Free Optimization (DFO), the Generating Set Search (GSS), and the Differential Evolution (DE). DFO is a sequential algorithm, whereas GSS and DE are parallel algorithms. Two case studies are also presented that represents synthetic petroleum fields. The results show how the studied algorithms behave on dealing with PWTOP for the two case studies, comparing experimental results obtained on optimized financial values, execution times and amount of objective function evaluation. Concludes, lastly, that, for the simplest case study, GSS had the best result, and for the most complex case study, more like real reservoirs, DE stood out / A atividade de Engenharia de Petróleo está rotineiramente envolvida em uma série de problemas de otimização em variados contextos, como definir projetos otimizados e eficientes na produção e no desenvolvimento de reservas de petróleo. Entretanto, há uma extrema dificuldade na resolução de problemas de otimização de exploração e produção (E&P), uma vez que são problemas frequentemente complexos, com elevado grau de não-linearidade, que apresentam alto número de incertezas e com enorme custo computacional envolvido. Dentre eles, está o problema de determinar a melhor distribuição de vazões entre os poços de uma plataforma de produção de petróleo capaz de resultar em um projeto de E&P de maior rentabilidade financeira, aqui denominado Problema de Otimização de Vazão de Poços de Petróleo (POVPP). Para tratar o POVPP, foram estudados alguns algoritmos de otimização contínua que possam lidar com as restrições lineares presentes no problema, que são o Otimização sem Derivadas (Derivative Free Optimization DFO), o Busca por Conjunto Gerador (Generating Set Search GSS) e o Evolução Diferencial (Differential Evolution DE). O DFO é um algoritmo sequencial, enquanto que o GSS e o DE são algoritmos paralelos. Também são apresentados dois estudos de caso que representam campos de petróleo sintéticos. Os resultados mostram como os algoritmos estudados se comportam ao tratar o POVPP para os dois estudos de caso, comparando-se dados obtidos de valores financeiros otimizados, tempos de execução e quantidade de avaliações da função objetivo. Conclui-se, por fim, que, para o estudo de caso simples, o GSS teve o melhor resultado, e para o estudo de caso mais complexo, mais semelhante a reservatórios reais, o DE se sobressaiu

A framework for optimization of reinsurance strategy is proposed for an insurance company with several lines of business (LoB), maximizing the Economic Value of purchasing reinsurance. The economic value is defined as the sum of the average ceded loss, the deducted risk premium, and the reduction in the cost of capital. The framework relies on simulated large claims per LoB rather than specific distributions, which gives more degrees of freedom to the insurance company.  Three models are presented, two non non-linear optimization models and a benchmark model. One non-linear optimization model is on individual LoB level and the other one is on company level with additional constraints using space bounded black box algorithms. The benchmark model is a Brute Force method using quantile discretization of potential retention levels, that helps to visualize the optimization surface.  The best results are obtained by a two-stage optimization using a mixture of global and local optimization algorithms. The economic value is maximized by 30% and reinsurance premium is halved if the optimization is made at the company level, by putting more emphasis on reduction in the cost of capital and less to average ceded loss. The results indicate an over-fitting when using VaR as the risk measure, impacting reduction in the cost of capital. As an alternative, Average VaR is recommended being numerically more robust.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O desenvolvimento de software livre de Jacobiana para a resolução de problemas formulados por equações diferenciais parciais não-lineares é de interesse crescente para simular processos práticos de engenharia. Este trabalho utiliza o chamado algoritmo espectral livre de derivada para equações não-lineares na simulação de fluxos em meios porosos. O modelo aqui considerado é aquele empregado para descrever o deslocamento do fluido compressível miscível em meios porosos com fontes e sumidouros, onde a densidade da mistura de fluidos varia exponencialmente com a pressão. O algoritmo espectral utilizado é um método moderno para a solução de sistemas não-lineares de grande porte, o que não resolve sistemas lineares, nem usa qualquer informação explícita associados com a matriz Jacobiana, sendo uma abordagem livre de Jacobiana. Problemas bidimensionais são apresentados, juntamente com os resultados numéricos comparando o algoritmo espectral com um método de Newton inexato livre de Jacobiana. Os resultados deste trabalho mostram que este algoritmo espectral moderno é um método confiável e eficiente para a simulação de escoamentos compressíveis em meios porosos. / The development of Jacobian-free software for solving problems formulated by nonlinear partial differential equations is of increasing interest to simulate practical engineering processes. This work uses the so-called derivative-free spectral algorithm for nonlinear equations in the simulation of flows in porous media. The model considered here is the one employed to describe the displacement of miscible compressible fluid in porous media with point sources and sinks, where the density of the fluid mixture varies exponentially with the pressure. The spectral algorithm used is a modern method for solving large-scale nonlinear systems, which does not solve linear systems, nor use any explicit information associated with the Jacobin matrix, being a Jacobian-free approach. Two dimensional problems are presented, along with numerical results comparing the spectral algorithm to a well-developed Jacobian-free inexact Newton method. The results of this paper show that this modern spectral algorithm is a reliable and efficient method for simulation of compressible flows in porous media.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O desenvolvimento de software livre de Jacobiana para a resolução de problemas formulados por equações diferenciais parciais não-lineares é de interesse crescente para simular processos práticos de engenharia. Este trabalho utiliza o chamado algoritmo espectral livre de derivada para equações não-lineares na simulação de fluxos em meios porosos. O modelo aqui considerado é aquele empregado para descrever o deslocamento do fluido compressível miscível em meios porosos com fontes e sumidouros, onde a densidade da mistura de fluidos varia exponencialmente com a pressão. O algoritmo espectral utilizado é um método moderno para a solução de sistemas não-lineares de grande porte, o que não resolve sistemas lineares, nem usa qualquer informação explícita associados com a matriz Jacobiana, sendo uma abordagem livre de Jacobiana. Problemas bidimensionais são apresentados, juntamente com os resultados numéricos comparando o algoritmo espectral com um método de Newton inexato livre de Jacobiana. Os resultados deste trabalho mostram que este algoritmo espectral moderno é um método confiável e eficiente para a simulação de escoamentos compressíveis em meios porosos. / The development of Jacobian-free software for solving problems formulated by nonlinear partial differential equations is of increasing interest to simulate practical engineering processes. This work uses the so-called derivative-free spectral algorithm for nonlinear equations in the simulation of flows in porous media. The model considered here is the one employed to describe the displacement of miscible compressible fluid in porous media with point sources and sinks, where the density of the fluid mixture varies exponentially with the pressure. The spectral algorithm used is a modern method for solving large-scale nonlinear systems, which does not solve linear systems, nor use any explicit information associated with the Jacobin matrix, being a Jacobian-free approach. Two dimensional problems are presented, along with numerical results comparing the spectral algorithm to a well-developed Jacobian-free inexact Newton method. The results of this paper show that this modern spectral algorithm is a reliable and efficient method for simulation of compressible flows in porous media.

Les modèles uplift (levier en français) traitent de l'inférence de cause à effet pour un facteur spécifique, comme une intervention de marketing. En pratique, ces modèles sont construits sur des données individuelles issues d'expériences randomisées. Un groupe traitement comprend des individus qui font l'objet d'une action; un groupe témoin sert de comparaison. La modélisation uplift est utilisée pour ordonner les individus par rapport à la valeur d'un effet causal, par exemple, positif, neutre ou négatif. Dans un premier temps, nous proposons une nouvelle façon d'effectuer la sélection de modèles pour la régression uplift. Notre méthodologie est basée sur la maximisation du coefficient Qini. Étant donné que la sélection du modèle correspond à la sélection des variables, la tâche est difficile si elle est effectuée de manière directe lorsque le nombre de variables à prendre en compte est grand. Pour rechercher de manière réaliste un bon modèle, nous avons conçu une méthode de recherche basée sur une exploration efficace de l'espace des coefficients de régression combinée à une pénalisation de type lasso de la log-vraisemblance. Il n'y a pas d'expression analytique explicite pour la surface Qini, donc la dévoiler n'est pas facile. Notre idée est de découvrir progressivement la surface Qini comparable à l'optimisation sans dérivée. Le but est de trouver un maximum local raisonnable du Qini en explorant la surface près des valeurs optimales des coefficients pénalisés. Nous partageons ouvertement nos codes à travers la librairie R tools4uplift. Bien qu'il existe des méthodes de calcul disponibles pour la modélisation uplift, la plupart d'entre elles excluent les modèles de régression statistique. Notre librairie entend combler cette lacune. Cette librairie comprend des outils pour: i) la discrétisation, ii) la visualisation, iii) la sélection de variables, iv) l'estimation des paramètres et v) la validation du modèle. Cette librairie permet aux praticiens d'utiliser nos méthodes avec aise et de se référer aux articles méthodologiques afin de lire les détails. L'uplift est un cas particulier d'inférence causale. L'inférence causale essaie de répondre à des questions telle que « Quel serait le résultat si nous donnions à ce patient un traitement A au lieu du traitement B? ». La réponse à cette question est ensuite utilisée comme prédiction pour un nouveau patient. Dans la deuxième partie de la thèse, c’est sur la prédiction que nous avons davantage insisté. La plupart des approches existantes sont des adaptations de forêts aléatoires pour le cas de l'uplift. Plusieurs critères de segmentation ont été proposés dans la littérature, tous reposant sur la maximisation de l'hétérogénéité. Cependant, dans la pratique, ces approches sont sujettes au sur-ajustement. Nous apportons une nouvelle vision pour améliorer la prédiction de l'uplift. Nous proposons une nouvelle fonction de perte définie en tirant parti d'un lien avec l'interprétation bayésienne du risque relatif. Notre solution est développée pour une architecture de réseau de neurones jumeaux spécifique permettant d'optimiser conjointement les probabilités marginales de succès pour les individus traités et non-traités. Nous montrons que ce modèle est une généralisation du modèle d'interaction logistique de l'uplift. Nous modifions également l'algorithme de descente de gradient stochastique pour permettre des solutions parcimonieuses structurées. Cela aide dans une large mesure à ajuster nos modèles uplift. Nous partageons ouvertement nos codes Python pour les praticiens désireux d'utiliser nos algorithmes. Nous avons eu la rare opportunité de collaborer avec l'industrie afin d'avoir accès à des données provenant de campagnes de marketing à grande échelle favorables à l'application de nos méthodes. Nous montrons empiriquement que nos méthodes sont compétitives avec l'état de l'art sur les données réelles ainsi qu'à travers plusieurs scénarios de simulations. / Uplift models deal with cause-and-effect inference for a specific factor, such as a marketing intervention. In practice, these models are built on individual data from randomized experiments. A targeted group contains individuals who are subject to an action; a control group serves for comparison. Uplift modeling is used to order the individuals with respect to the value of a causal effect, e.g., positive, neutral, or negative. First, we propose a new way to perform model selection in uplift regression models. Our methodology is based on the maximization of the Qini coefficient. Because model selection corresponds to variable selection, the task is haunting and intractable if done in a straightforward manner when the number of variables to consider is large. To realistically search for a good model, we conceived a searching method based on an efficient exploration of the regression coefficients space combined with a lasso penalization of the log-likelihood. There is no explicit analytical expression for the Qini surface, so unveiling it is not easy. Our idea is to gradually uncover the Qini surface in a manner inspired by surface response designs. The goal is to find a reasonable local maximum of the Qini by exploring the surface near optimal values of the penalized coefficients. We openly share our codes through the R Package tools4uplift. Though there are some computational methods available for uplift modeling, most of them exclude statistical regression models. Our package intends to fill this gap. This package comprises tools for: i) quantization, ii) visualization, iii) variable selection, iv) parameters estimation and v) model validation. This library allows practitioners to use our methods with ease and to refer to methodological papers in order to read the details. Uplift is a particular case of causal inference. Causal inference tries to answer questions such as ``What would be the result if we gave this patient treatment A instead of treatment B?" . The answer to this question is then used as a prediction for a new patient. In the second part of the thesis, it is on the prediction that we have placed more emphasis. Most existing approaches are adaptations of random forests for the uplift case. Several split criteria have been proposed in the literature, all relying on maximizing heterogeneity. However, in practice, these approaches are prone to overfitting. In this work, we bring a new vision to uplift modeling. We propose a new loss function defined by leveraging a connection with the Bayesian interpretation of the relative risk. Our solution is developed for a specific twin neural network architecture allowing to jointly optimize the marginal probabilities of success for treated and control individuals. We show that this model is a generalization of the uplift logistic interaction model. We modify the stochastic gradient descent algorithm to allow for structured sparse solutions. This helps fitting our uplift models to a great extent. We openly share our Python codes for practitioners wishing to use our algorithms. We had the rare opportunity to collaborate with industry to get access to data from large-scale marketing campaigns favorable to the application of our methods. We show empirically that our methods are competitive with the state of the art on real data and through several simulation setting scenarios.