Submitted by Cássio da Cruz Nogueira (cassionogueirakk@gmail.com) on 2017-08-31T16:35:28Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_InversaoVelocidadesOtimizacao.pdf: 16170706 bytes, checksum: 1d10f311dfa0d1972ce89dfbef3c1907 (MD5) / Approved for entry into archive by Irvana Coutinho (irvana@ufpa.br) on 2017-09-11T15:52:36Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_InversaoVelocidadesOtimizacao.pdf: 16170706 bytes, checksum: 1d10f311dfa0d1972ce89dfbef3c1907 (MD5) / Made available in DSpace on 2017-09-11T15:52:36Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_InversaoVelocidadesOtimizacao.pdf: 16170706 bytes, checksum: 1d10f311dfa0d1972ce89dfbef3c1907 (MD5) Previous issue date: 2016-08-25 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A literatura geofísica recente tem mostrado que a construção de um modelo inicial mais realístico possível é a forma mais apropriada de se reduzir complicações do problema mal posto da inversão da forma da onda completa, e de fornecer as condições necessárias de convergência da função objetivo em direção ao mínimo global. Modelos otimizados são úteis como estimativas iniciais para métodos mais sofisticados de inversão e migração. Desenvolvo um método de inversão de velocidade da onda P usando dados sísmicos pré-empilhados para grandes afastamentos e baseado em medidas de coerência. A estratégia de inversão proposta é totalmente automática, baseada no cálculo do semblance e regida pela aproximação de tempo de trânsito paraxial, o chamado método da Superfície de Reflexão Comum com Afastamento Finito. Ela é realizada em dois passos, a princípio, usando raios imagens e o conhecimento de um modelo de velocidades conhecido a priori, determino as interfaces refletoras em profundidade a partir de seção migrada em tempo. A seguir, o modelo em profundidade gerado é usado como entrada na parametrização do modelo de velocidades, o qual é feito camada por camada. A estratégia de inversão é baseada na análise dos semblances calculados em cada ponto médio comum pelo método da Superfície de Reflexão Comum com Afastamento Finito. Para iniciar a inversão no segundo passo, a aproximação paraxial é feita pelo traçamento de raios no modelo de velocidades em profundidade obtido no primeiro passo. Usando a média aritmética dos semblances calculados em todos os pontos médios comuns como função objetivo, camada após camada, o algoritmo de otimização global Very Fast Simulated Annealing é aplicado para obter a convergência da função objetivo em direção ao máximo global. Ao aplicar a estratégia de inversão em dados sintéticos e reais, mostro a robustez do algoritmo de inversão proposto, produzindo modelos de velocidades da onda P otimizados a partir de dados pré-empilhados. / The recent geophysical literature has shown the building of an accurate initial model is the more appropriate way to reduce the ill-posedness of the Full Waveform Inversion, providing the necessary convergence of the misfit function toward the global minimum. Optimized models are useful as initial guess for more sophisticated velocity inversion and migration methods. I developed an automatic P-wave velocity inversion methodology using pre-stack two-dimensional seismic data. The proposed inversion strategy is fully automatic, based on the semblance measurements and guided by the paraxial traveltime approximation, so-called Finite-Offset Common-Reflection-Surface. It is performed in two steps, at first using image rays and an a priori known initial velocity model we determine the reflector interfaces in depth from time migrated section. The generated depth macro-model is used as input at the second step, where the parametrization of the velocity model is made layer by layer. Each layer is separated from each other by smoothed interfaces. The inversion strategy is based on the scan of semblance measurements in each common-midpoint gather guided by the Finite-Offset Common-Reflection-Surface traveltime paraxial approximations. For beginning the inversion in the second step, the finite-offset common-midpoint central rays is built by ray tracing from the velocity macro-model obtained in the first step. By using the arithmetic mean of total semblance calculated from the whole common-midpoint gathers as objective function, layer after layer, a global optimization method called Very Fast Simulated Annealing algorithm is applied in order to obtain the convergence of the objective function toward the global maximum. By applying to synthetic and real data, I showed the robustness of the inversion algorithm for yielding an optimized P-wave velocity macro-model from pre-stack seismic data.

Neste trabalho, estudamos o problema a recoloração convexa de grafos, denotado por RC. Dizemos que uma coloração dos vértices de um grafo G é convexa se, para cada cor tribuída d, os vértices de G com a cor d induzem um subgrafo conexo. No problema RC, é dado um grafo G e uma coloração de seus vértices, e o objetivo é recolorir o menor número possível de vértices de G tal que a coloração resultante seja convexa. A motivação para o estudo deste problema surgiu em contexto de árvores filogenéticas. Sabe-se que este problema é NP-difícil mesmo quando G é um caminho. Mostramos que o problema RC parametrizado pelo número de mudanças de cor é W[2]-difícil mesmo se a coloração inicial usa apenas duas cores. Além disso, provamos alguns resultados sobre a inaproximabilidade deste problema. Apresentamos uma formulação inteira para a versão com pesos do problema RC em grafos arbitrários, e então a especializamos para o caso de árvores. Estudamos a estrutura facial do politopo definido como a envoltória convexa dos pontos inteiros que satisfazem as restrições da formulação proposta, apresentamos várias classes de desigualdades que definem facetas e descrevemos os correspondentes algoritmos de separação. Implementamos um algoritmo branch-and-cut para o problema RC em árvores e mostramos os resultados computacionais obtidos com uma grande quantidade de instâncias que representam árvores filogenéticas reais. Os experimentos mostram que essa abordagem pode ser usada para resolver instâncias da ordem de 1500 vértices em 40 minutos, um desempenho muito superior ao alcançado por outros algoritmos propostos na literatura. / In this work we study the convex recoloring problem of graphs, denoted by CR. We say that a vertex coloring of a graph G is convex if, for each assigned color d, the vertices of G with color d induce a connected subgraph. In the CR problem, given a graph G and a coloring of its vertices, we want to find a recoloring that is convex and minimizes the number of recolored vertices. The motivation for investigating this problem has its roots in the study of phylogenetic trees. It is known that this problem is NP-hard even when G is a path. We show that the problem CR parameterized by the number of color changes is W[2]-hard even if the initial coloring uses only two colors. Moreover, we prove some inapproximation results for this problem. We also show an integer programming formulation for the weighted version of this problem on arbitrary graphs, and then specialize it for trees. We study the facial structure of the polytope defined as the convex hull of the integer points satisfying the restrictions of the proposed ILP formulation, present several classes of facet-defining inequalities and the corresponding separation algorithms. We also present a branch-and-cut algorithm that we have implemented for the special case of trees, and show the computational results obtained with a large number of instances. We considered instances which are real phylogenetic trees. The experiments show that this approach can be used to solve instances up to 1500 vertices in 40 minutes, comparing favorably to other approaches that have been proposed in the literature.

In this thesis, we consider an analog antenna combining architecture for a MIMO wireless transceiver, while pointing out its advantages with respect to the traditional MIMO architectures. In the first part of this work, we focus on the transceiver design, especially the calculation of the beamformers that must be applied at the RF. This analysis is performed in an OFDM system under different assumptions on the channel state information. As a result, several criteria and algorithms for the selection of the beamformers are proposed. In the second part, we address the FPGA design and implementation of a baseband processor for this architecture. This baseband processor is based on the standard IEEE 802.11a. Finally, some real-time tests of the implemented baseband processor are carried out both in stand-alone configuration and also with the whole physical layer setup. / En esta tesis consideramos una arquitectura de combinación analógica de antenas para una estación inalámbrica MIMO, señalando las ventajas de ésta con respecto a la arquitectura tradicional MIMO. En la primera parte de este trabajo analizamos el cálculo de los pesos que se deben aplicar en RF. Este análisis es realizado para un sistema OFDM bajo diferentes suposiciones sobre el conocimiento del canal en el transmisor. Como resultado, se ofrecen varios criterios y algoritmos para el cálculo de los pesos. La segunda parte se centra en el diseño y la implementación FPGA de un procesador banda base para esta arquitectura. Este procesador está basando en el estándar IEEE 802.11a. Finalmente se llevan a cabo algunos experimentos en tiempo-real del procesador banda base. Estos experimentos se han realizado tanto con el procesador aislado como integrado en el resto de la capa física del sistema.

[pt] A indústria de transporte marítimo é essencial para o comércio internacional. No entanto, no despertar da crise financeira de 2008, essa indústria foi severamente atingida. Nessas ocasiões, empresas de transporte só são capazes de obter lucro se suas frotas forem roteadas de forma eficaz. Neste trabalho, nós estudamos uma classe de problemas de roteamento de navios relacionados ao Pickup and Delivery Problem with Time Windows. Para resolver esses problemas, nós introduzimos um método heurístico e um exato. O método heurístico é uma meta-heurística híbrida com uma vizinhança larga baseada em set partitioning, enquanto o método exato é um algoritmo de branch-and-price. Nós conduzimos experimentos em um conjunto de instâncias baseadas em rotas de navios reais. Os resultados obtidos mostram que nossos algoritmos superam as metodologias estado da arte. Em seguida, nós adaptamos o conjunto de instâncias para modelar um problema de roteamento de navios no qual a velocidade em cada segmento de rota é uma variável de decisão, e o consumo de combustível por unidade de tempo é uma função convexa da velocidade e carga do navio. A fim de resolver esse novo problema de roteamento de navios com otimização de velocidade, nós estendemos nossa meta-heurística para encontrar decisões de velocidade ótimas em toda avaliação de solução vizinha de uma busca local. Nossos experimentos demonstram que essa abordagem pode ser altamente rentável, e que requer apenas um aumento moderado de recursos computacionais. / [en] The shipping industry is essential for international trade. However, in the wake of the 2008 financial crisis, this industry was severely hit. In these times, transportation companies can only obtain profit if their fleet is routed effectively. In this work, we study a class of ship routing problems related to the Pickup and Delivery Problem with Time Windows. To solve these problems, we introduce a heuristic and an exact method. The heuristic method is a hybrid metaheuristic with a set-partitioning-based large neighborhood, while the exact method is a branch-and-price algorithm. We conduct experiments on a benchmark suite based on real-life shipping segments. The results obtained show that our algorithms largely outperform the state-of-the-art methodologies. Next, we adapt the benchmark suite to model a ship routing problem where the speed on each sailing leg is a decision variable, and fuel consumption per time unit is a convex function of the ship speed and payload. To solve this new ship routing problem with speed optimization, we extend our metaheuristic to find optimal speed decisions on every local search move evaluation. Our computational experiments demonstrate that such approach can be highly profitable, with only a moderate increase in computational effort.

[pt] A geração de malhas geomecânicas de reservatórios ainda é uma tarefa tediosa que consome muito tempo. Para acelerar este processo, soluções que reconstroem analiticamente a geometria do reservatório têm sido propostas, mas essas soluções não são as mais adequadas para modelagem de objetos naturais. Este trabalho propõe uma modelagem discreta para a geometria do reservatório, onde os vértices da malha são posicionados por meio da solução de um problema de otimização quadrático e convexo. O problema de otimização é modelado de forma a garantir que as malhas geomecânicas de saída sejam suaves e que ao mesmo tempo respeitem as restrições do reservatório e dos horizontes presentes. Além disso, a metodologia proposta permite uma implementação eficiente, paralelizável e de baixo consumo de memória. Casos de teste com milhões de variáveis são apresentados para validar essa abordagem. Finalmente, a metodologia proposta neste trabalho para malhas de geomecânica pode ser naturalmente estendida para a modelagem estrutural de sub-superfícies na interpretação sísmica e de restauração geológica. / [en] Geomechanical mesh generation of complex reservoirs remains a tedious task prone to errors. Recently proposed solutions based on analytical reconstruction of the sub-surfaces are not capable to represent all the geometric details of natural objects. This work proposes a discrete model where the mesh vertices are positioned based on a convex quadratic optimization process. The optimization problem seeks to guarantee smooth meshes that conform with prescribed constraints. The resulting mesh therefore respects, as far as possible, the finite volume mesh of the reservoir pay zone and the existing horizons. Finally, the proposed methodology for Geomechanical meshes can be easily extend to model sub-surfaces present in the structural interpretation and geological restauration.

Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2017-02-13T19:22:38Z No. of bitstreams: 1 CarolineAlbuquerqueDantasSilva_DISSERT.pdf: 1138216 bytes, checksum: b1401c36a2ad5415e6adc770fee68fbc (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2017-02-14T17:45:51Z (GMT) No. of bitstreams: 1 CarolineAlbuquerqueDantasSilva_DISSERT.pdf: 1138216 bytes, checksum: b1401c36a2ad5415e6adc770fee68fbc (MD5) / Made available in DSpace on 2017-02-14T17:45:51Z (GMT). No. of bitstreams: 1 CarolineAlbuquerqueDantasSilva_DISSERT.pdf: 1138216 bytes, checksum: b1401c36a2ad5415e6adc770fee68fbc (MD5) Previous issue date: 2016-07-18 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior (CAPES) / Esse trabalho prop?e um esquema de otimiza??o convexa, baseada em programa??o linear e algoritmos gen?ticos, para equalizadores cegos aplicados a sistemas de comunica??es digitais. Ele surgiu da necessidade crescente de melhorias nos sistemas de comunica??o no intuito de transportar o m?ximo de informa??o poss?vel por um meio f?sico de forma con??vel.O esquema proposto, ELC-GA (Equalizador Linear Cego baseado em Algoritmos Gen?ticos), ? caracterizado por realizar a equaliza??o adaptativa cega do canal em blocos ?xos de dados, utilizando como algoritmo adaptativo um algoritmo gen?tico, cuja fun??o objetivo ? uma fun??o linear com restri??es, globalmente convergente. Entretanto, devido ?s caracter?sticas aleat?rias do sinal modelado com interfer?ncia intersimb?lica e ru?do aditivo branco gaussiano, a fun??o linear utilizada passa a representar uma programa??o linear estoc?stica. Nesse sentido, o uso de algoritmos gen?ticos ? particularmente adequado por ser capaz de buscar solu??es ?timas percorrendo uma por??o consider?vel do espa?o de busca, que corresponde aos v?rios cen?rios estoc?sticos. O trabalho tamb?m descreve os detalhes de implementa??o do esquema proposto e as simula??es computacionais realizadas. Na an?lise de desempenho, os resultados do ELC-GA s?o comparados aos resultados de uma das mais tradicionais t?cnicas de equaliza??o cega, o CMA, utilizado como refer?ncia dessa an?lise. Os resultados obtidos s?o exibidos e comentados segundo as m?tricas de an?lise adequadas.As conclus?es do trabalho apontam o ELC-GA como uma alternativa promissora para equaliza??o cega devido ao seu desempenho de equaliza??o, que atinge a converg?ncia global num intervalo de s?mbolos consideravelmente menor que a t?cnica usada como refer?ncia. / This paper proposes a convex optimization scheme based on linear programming and genetic algorithms for the blind equalizers applied to digital communications systems. It arose from the growing need for improvements in communication systems in order to transmit as much information as possible in a physical environment reliably. The proposed scheme, ELC-GA (Blind Linear Equalizer Linear based on Genetic Algorithms), is characterized by performing blind adaptive channel equalization in fixed units of data, using a genetic algorithm as adaptive algorithm, whose objective function is a globally convergent constrained linear function. However, due to the random characteristics of the signal modeled with intersymbol interference and additive white Gaussian noise, the used linear function now represents a stochastic linear programming. Accordingly, the use of genetic algorithms is particularly suitable for being able to get optimal solutions covering a considerable portion of the search space, which corresponds to the various stochastic scenarios. This work also describes the implementation details of the proposed scheme and the performed computational simulations. In the performance analysis, the ELC- GA results are compared to the results of one of the traditional blind equalization techniques, CMA, used as reference in this analysis. The results are shown and discussed under the appropriate metric analysis. The conclusions of the study indicate the GA - ELC as a promising alternative to blind equalization due to its equalization performance, which reaches global convergence in a considerably smaller range of symbols than the technique used as reference.

In this doctoral thesis, we propose new iterative methods for solving a class of convex optimization problems. In general, we consider problems in which the objective function is composed of a finite sum of convex functions and the set of constraints is, at least, convex and closed. The iterative methods we propose are basically designed through the combination of incremental subgradient methods and string-averaging algorithms. Furthermore, in order to obtain methods able to solve optimization problems with many constraints (and possibly in high dimensions), generally given by convex functions, our analysis includes an operator that calculates approximate projections onto the feasible set, instead of the Euclidean projection. This feature is employed in the two methods we propose; one deterministic and the other stochastic. A convergence analysis is proposed for both methods and numerical experiments are performed in order to verify their applicability, especially in large scale problems. / Nesta tese de doutorado, propomos novos métodos iterativos para a solução de uma classe de problemas de otimização convexa. Em geral, consideramos problemas nos quais a função objetivo é composta por uma soma finita de funções convexas e o conjunto de restrições é, pelo menos, convexo e fechado. Os métodos iterativos que propomos são criados, basicamente, através da junção de métodos de subgradientes incrementais e do algoritmo de média das sequências. Além disso, visando obter métodos flexíveis para soluções de problemas de otimização com muitas restrições (e possivelmente em altas dimensões), dadas em geral por funções convexas, a nossa análise inclui um operador que calcula projeções aproximadas sobre o conjunto viável, no lugar da projeção Euclideana. Essa característica é empregada nos dois métodos que propomos; um determinístico e o outro estocástico. Uma análise de convergência é proposta para ambos os métodos e experimentos numéricos são realizados a fim de verificar a sua aplicabilidade, principalmente em problemas de grande escala.

Orientadores: Carlos Eduardo Durán Fernandez, Márcio Antônio de Faria Rosa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Cientifica / Made available in DSpace on 2018-08-16T14:48:33Z (GMT). No. of bitstreams: 1 ManoOtero_Diego_M.pdf: 1221591 bytes, checksum: 33ae6e3b671523a9602f3398e14d4fb7 (MD5) Previous issue date: 2010 / Resumo: A motivação inicial deste trabalho foi tentar relacionar os conceitos de geometria de Finsler com situações físicas que temos uma certa dependência de direções no nosso espaço. Apresentamos o conceito do cálculo variacional em variedades e sua relação com as geodésicas. Estudamos também o operador laplaciano ?? para espaços de Minkowski, que generaliza o caso Euclideano, e mais especificamente o problema...Observação: O resumo, na íntegra poderá ser visualizado no texto completo da tese digital / Abstract: The initial motivation of this study was to try to relate the concepts of Finsler geometry with physical situations where we have a certain dependence on the directions of our space. We introduce the concept of variational calculus on manifolds and their relationship with the geodesics. We also studied the Laplacian operator ?? in Minkowski space, which generalizes the Euclidean case, and more specifically the problem ...Note: The complete abstract is available with the full electronic digital thesis or dissertations. / Mestrado / Geometria / Mestre em Matemática

Não informado. / No presente trabalho fazemos um estudo sobre transformações geométricas no plano, explorando características geométricas e algébricas. A relação entre a geometria e a álgebra é responsável por extraordinários progressos na matemática e suas aplicações. Nosso objetivo inicial é apresentar algumas das principais transformações geométricas, a exemplo das Homotetias, das Translações, de Cisalhamentos, das Simetrias, das Rotações, das Re exões, das Isometrias, etc., de forma intuitiva e ilustrando com exemplos simples. Em seguida exploramos características algébricas elementares que permitem tratar e generalizar o estudo de transformações. Apresentamos ainda os conceitos de Mor smos e Deformações de imagens utilizando noções, por exemplo, como Combinação Linear Convexa.

Orientador: João Bosco Ribeiro do Val / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-14T00:07:24Z (GMT). No. of bitstreams: 1 Calmon_AndreduPin_M.pdf: 862345 bytes, checksum: 122780715dca28ac7fa3199aa0586e7c (MD5) Previous issue date: 2009 / Resumo: Este trabalho apresenta a caracterização teórica e a estratégia de controle para sistemas estocásticos em tempo discreto onde a variação da ação de controle aumenta a incerteza sobre o estado (sistemas VCAI). Este tipo de sistema possui várias aplicações práticas, como em problemas de política monetária, medicina e, de forma geral, em problemas onde um modelo dinâmico completo do sistema é complexo demais para ser conhecido. Utilizando ferramentas da análise de funções não suaves, mostra-se para um sistema VCAI multidimensional que a convexidade é uma invariante da função valor da Programação Dinâmica quando o custo por estágio é convexo. Esta estratégia indica a existência de uma região no espaço de estados onde a ação ótima de controle é de não variação (denominada região de não-variação), estando de acordo com a natureza cautelosa do controle de sistemas subdeterminados. Adicionalmente, estudou-se algoritmos para a obtenção da política ótima de controle para sistemas VCAI, com ênfase no caso mono-entrada avaliado através de uma função custo quadrática. Finalmente, os resultados obtidos foram aplicados no problema da condução da política monetária pelo Banco Central. / Abstract: This dissertation presents a theoretical framework and the control strategy for discrete-time stochastic systems for which the control variations increase state uncertainty (CVIU systems). This type of system model can be useful in many practical situations, such as in monetary policy problems, medicine and biology, and, in general, in problems for which a complete dynamic model is too complex to be feasible. The optimal control strategy for a multidimensional CVIU system associated with a convex cost functional is devised using dynamic programming and tools from nonsmooth analysis. Furthermore, this strategy points to a region in the state space in which the optimal action is of no variation (the region of no variation), as expected from the cautionary nature of controlling underdetermined systems. Numerical strategies for obtaining the optimal policy in CVIU systems were developed, with focus on the single-input input case evaluated through a quadratic cost functional. These results are illustrated through a numerical example in economics. / Mestrado / Automação / Mestre em Engenharia Elétrica