Search

Orientador: Francisco de Assis Magalhães Gomes Neto Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica Resumo: Uma maneira de resolver problemas gerais de programação não linear é utilizar estratégias de passos compostos. Essas estratégias normalmente combinam um passo tangente às restrições e um passo normal, alternando entre a diminuição da função objetivo e da norma da infactibilidade. Esse tipo de método exige o controle dos passos ou dos iterandos, para que não se perca o progresso de um vii passo no outro. Apresentaremos uma extensão do método de Controle Dinâmico da Infactibilidade, que utiliza uma estratégia de controle de passos chamado de Cilindros de Confiança. Esse método foi desenvolvido para problemas com restrições apenas de igualdade, e nossa extensão lida com restrições gerais. Mostraremos testes numéricos comparando nosso método com um método do mesmo tipo Abstract: One way to solve general nonlinear programming problems is the composite-step strategies. These strategies usually combine a step tangent to the constraints and a normal step, alternating between reducing the objective function value and the norm of the infeasibility. This kind of method requires the control of the steps or the iterates, in order to prevent one step from destroying the progress of another. We will present an extension of the Dynamic Control of Infeasibility method, which utilizes a strategy to control the steps known as Trust Cylinders. This method was originally designed for problems with equality contraints only, and our extension will handle general constraints. We'll show numerical experiments comparing our method with another composite-step method Doutorado Matemática Aplicada Doutor em Matemática Aplicada

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) Petróleo Brasileiro (Petrobrás) Nas últimas décadas, as técnicas de reconstrução de imagens e sinais baseadas em modelos possibilitaram importantes melhorias em termos de contraste e resolução espacial em aplicações como ressonância magnética e tomografia computadorizada. No entanto, o uso de técnicas desse tipo em aplicações de pulso-eco como ultrassom é limitado pelo fato delas pressuporem uma grade finita de possíveis localizações para os refletores existentes num meio -- um pressuposto que vai contra a natureza contínua dos objetos do mundo real, o que cria um problema conhecido como desvio da grade. Com o objetivo de superar esse problema, este trabalho apresenta um método de expansão de dicionário e de reconstrução com restrições que aproxima a variedade (comumente referida como manifold) contínua dos dados de aquisição formada por todas as localizações possíveis de refletores ao longo de uma região de interesse (RDI). A criação do dicionário expandido baseia-se numa amostragem altamente coerente da RDI, seguida de uma redução de posto matricial nos dados correspondentes para a qual são propostos dois critérios: um baseado em decomposição em valores singulares (SVD) e um baseado em minimização do máximo (Minimax). Embora a formulação seja aqui desenvolvida para o caso de 2 dimensões, a mesma é extensível para quaisquer D dimensões. É proposto um algoritmo baseado no Orthogonal Matching Pursuit (OMP), que usa um conjunto de restrições não convexas baseadas em correlação e permite que a RDI seja dividida em células de qualquer tamanho. O método proposto é avaliado através da reconstrução de imagens de ultrassom em 2 dimensões a partir de dados simulados para uma aplicação de ensaios não destrutivos. O método proposto obteve êxito na reconstrução de imagens esparsas a partir de dados de aquisição ruidosos e possibilitou maior acurácia do que abordagens concorrentes baseadas em modelos discretos sem expansão do dicionário. Os resultados confirmaram também uma expectativa teórica de que o dicionário Minimax supera o dicionário SVD com relação à estimativa de cardinalidade da solução. Model-based image and signal reconstruction has brought important improvements in terms of contrast and spatial resolution to applications such as magnetic resonance imaging and emission computed tomography. However, their use for pulse-echo techniques like ultrasound imaging is limited by the fact that model-based algorithms assume a finite grid of possible locations of scatterers in a medium -- an assumption that does not reflect the continuous nature of real world objects and creates a problem known as off-grid deviation. To cope with this problem, we present a method of dictionary expansion and constrained reconstruction that approximates the continuous manifold of all possible scatterer locations within a region of interest (ROI). The creation of the expanded dictionary is based on a highly coherent sampling of the ROI, followed by a rank reduction of the corresponding data that encompasses two possible approximation criteria: one based on singular-value decomposition (SVD) and one minimize-maximum (Minimax). Although we develop here a formulation for two-dimensional sparse imaging problems, it can be readily extended to any D dimensions. We develop a greedy algorithm, based on the Orthogonal Matching Pursuit (OMP), that uses a correlation-based non-convex constraint set that allows for the division of the ROI into cells of any size. To evaluate the performance of the proposed method, we present results of two-dimensional ultrasound image reconstructions with simulated data in a nondestructive testing application. The proposed method succeeds at reconstructing sparse images from noisy measurements and provides higher accuracy than previous approaches based on regular discrete models. Results also confirm a theoretical expectation that the Minimax dictionary outperforms the SVD dictionary on the estimation of the cardinality of the solution.

Orientadores: Sandra Augusta Santos, Jose Mario Martinez Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica Resumo: Este trabalho encaminha a investigação de questões relacionadas ao desempenho de algoritmos de região de confiança para problemas de otimização irrestrita de grande porte. O algoritmo clássico de Moré e Sorensen, baseado em fatorações de Cholesky, é comparado com a abordagem de Rojas, Santos e Sorensen (algoritmo RSS). Do ponto de vista teórico são estudados os resultados de convergência dos dois algoritmos. Em termos práticos, são resolvidos problemas com a estrutura típica de empacotamento de cilindros. Também são pesquisados o desempenho efetivo do algoritmo RSS na solução aproximada dos subproblemas, e a repercussão da precisão com que os subproblemas são resolvidos no esforço global do algoritmo. Abstract: This work investigates issues related to the performance of trust-region algorithms for large-scale unconstrained minimization. The classic algorithm of Moré and Sorensen, based on Cholesky?s factorizations, is compared with the approach of Rojas, Santos and Sorensen (algorithm RSS). From the theoretic standpoint, the convergence results of both algorithms are compiled. In practical terms, problems with the typical structure of packying of cylinders are solved. The effective performance of the algorithm RSS in the approximate solution of the subproblems is analyzed as well, together with the influence of the inner precision of the subproblems to the global effort of the algorithm Mestrado Otimização Mestre em Matemática Aplicada